In practical terms, under scale, it's pretty much the case. If you don't have enough memory to have your entire dataset in memory, the performance degrades to a point where it'll be too slow to do anything, so it might as well not work at all.

Similar problems with MongoDB. Anytime your indexed data starts hitting disk, kiss your site goodbye.

Sharding seems like the proper workaround though, so maybe you could take the same approach of flockdb and shard the redis social graph.