In this work, we present the Replicate and Bundle (RnB) scheme for relieving back-end processor and network bottlenecks in read-mostly key-value storage systems wherein each user request spawns a large number of back-end small-item requests. This is common in Web 2.0 and online social network systems. Adding processors is of little help because this increases the number of back-end requests per user request, thereby also increasing the overall processor and network load. Instead, RnB adds memory and replicates the stored data, thereby permitting each user request to be serviced through fewer back-end requests, reducing the total amount of work required from the network-processing and storage components of the system. The scheme is very easy to deploy, completely distributed, and while oblivious to the workload, beneficially exploits its spatial locality.

We have studied RnB through simulation, and augmented this with a micro-benchmark in order to estimate the expected actual system performance.

Our results show that by using RnB, two major scaling bottlenecks are considerably relieved:
1. the TCP Incast issue and
2. the memcached multi-get hole. When utilizing the requests’ locality, we achieve a considerable improvement in these bottlenecks with relatively little additional memory. In fact, RnB can use existing replicas (included for fault tolerance), in which case the extra cost is minimal if any.

Finally, we note that this is yet another example of judicious exploitation of redundancy for performance enhancement.