It looks like the performance is degrading with the size of the data and its amount:
If my data size is 2K then I get awesome performance.
It starts getting worse at about 5M Keys. […] So looks like as the overall database size increases beyond to what can fit in the cache the performance starts degrading.
