Wiki says that KEYS command can scan a 1 million keys database in 40
milliseconds which seems to be a good result,
but anyway, it would nice to hear if someone solved (or decided to not
to) similar task before with redis.
KEYS is not the way to go, the best thing you can do is to use instead
a sorted set.
What you want is to turn the first 4 or 5 characters of the strings
into an integer (you can
imagine every char as a digit of a radix 256 number for instance, but
there are better
representation) and add all your usernames into a sorted set.
Then using ZRANGEBYSCORE you can get all the elements between a given range.
This method is much more scalable as it's an O(log(N)) thing.
I'm covering this stuff in my very slowly evolving Redis book...
Salvatore 'antirez' Sanfilippo
"Once you have something that grows faster than education grows,
you’re always going to get a pop culture.", Alan Kay