According to this: http://redis.io/topics/faq
When you have a lot of small keys, it will use 5-6 times as much memory as the size of the data stored in redis.
You will probably need somewhere around 8-10 GB of memory to store your data set. Which will limit you to cache.m1.xlarge.