Can't reply on the comparison with other products since I myself have still to compare and build an experience about this, but as far as how Redis performs, there is a demo here: http://autocomplete.redis.io. Basically for 8 million records it takes 1GB of memory (32 bit system), however here the records are source code lines so the average length is bigger than the usual search-term length. Definitely no problems in the ~10 millions range even with just a few GBs of memory. For +100 millions you need to either split the range across servers or use a machine with some non-trivial amount of memory, like 16-32 GB or alike.
Also with that much data is sensible to set up redis in a master-slave fashion for better availability. Once you have that up and running you can split the work between the two, since autocomplete searches are intrinsically read operations.
