Optimizing multi-key operations in Clustered Redis

Redis is extremely fast but occasionally you can push your node beyond its limits. When some key/values are used across many requests; these may need to be retrieved so frequently that the Redis shard cannot keep up with the read requests.

To alleviate this issue, a commonly employed pattern is to store the same key multiple times in the Redis cluster, using different hash (this is achieved by specifying a ‘slot selector’ together with the key in {}). Redis will have more writes but the advantage will be more read throughput as each of the write location can serve the read requests. Normally, we use this syntax to store value v1 for key k1:

redis.put(“k1”, v1)

To store a value v1 with key k1; in 3 nodes, we can do something like:

redis.put(“{0:k1}”, v1);
redis.put(“{1:k1}”, v1);
redis.put(“{2:k1}”, v1);

This will have 3 times write amplification, however your reads can scale 3 times now. For retrieving, you will randomly select one of the above nodes (rand%3):

redis.get(“{rand()%3:k1}”)

While reading, you can randomly select any of these three shards; NOTE: There is no guarantee that the different hash values generated this way will actually land each of the above key on different redis nodes; however we hope that in most cases CRC will work nicely to distribute the keys across different redis nodes.

Optimizing Bulk Redis Operations

Redis clients provide mget and mset functionality to retrieve and update multiple keys in one network call. These work well for Non-Clustered Redis. However, most Redis clients don’t support them for Clustered redis; as Redis requires all keys in one request to be located on the same keyslot (Keyslot is like a virtual shard and a list of keyslots are assigned to one redis node).

One option will be to parallelize the i/o operations, but that does not scale well when we are reading 100s of keys in one user flow. A better option is to control the slot selector for the keys — like we saw for single key operations. This way we can be deterministic about sending Redis requests only to the shard which has some or all of the required keys; and gather all the relevant keys from that redis node in one network round-trip

One scenario in our service requires restaurant data for 100s of restaurants to return for one user request. In such cases, if we distribute data by restaurant-id, then we will end up querying almost all the redis nodes — multiple times , since we are not able to use mget — for each request. This can be inefficient due to tail-latency issue, as well as requiring multiple roundtrips to the Redis cache. Here are some possible solutions:
1. shard restaurants by ‘mod n’, where n is much smaller than the total number of shards. This ensures, that even in the worst case we will have to query only n shards.
2. shard restaurants by some ‘parent key’, e.g. zipcode, etc.

Both of these have pros and cons. Depending on your data, one approach may work better than the other. We have found option 1 work reliably for cache purposes; as it also distributes the data almost uniformly. It has the obvious disadvantage that when we scale redis nodes, we may not be utilizing more nodes efficiently; however this is one of our design goals — to limit the number of nodes which we query for each type of data. Newer nodes, can store data for other types of entities, this can be ensured by using different prefixes for each type of data.

So assuming n = 5 (i.e. we want to restrict our number of redis mget to 5) while retrieving restaurants data. Then the key for following 6 restaurants (13, 17, 20, 23, 28, 37) will be generated as:

13 => “{restaurant:3}13”
17 => “{restaurant:2}17”
20 => “{restaurant:0}20”
23 => “{restaurant:3}23”
28 => “{restaurant:3}28”
37 => “{restaurant:2}37”

And they can be grouped for multikey operations as follows, based on the slot selector prefix. Later the results can be combined into one list.

call 1: redis.mget(“{restaurant:0}20”)
call 2: redis.mget(“{restaurant:3}13”, “{restaurant:3}23”, “{restaurant:3}28”)
call 3: redis.mget(“{restaurant:2}17”, “{restaurant:2}37”)

Summary

In practice, we use both of above patterns at the same time. We cache our restaurants data in a limited number of slots, but multiple times in the same cluster. So, if we want to have 3 copies for each data (to scale reads); and also restrict our redis requests to 5; while retrieving restaurants data, this is how we cache a restaurant with id=1234

1234%5 => 4

redis.set(“{restaurant:4:0}1234”, “{id:1234, name:‘Curry King’, …”);
redis.set(“{restaurant:4:1}1234”, “{id:1234, name:‘Curry King’, …”);
redis.set(“{restaurant:4:2}1234”, “{id:1234, name:‘Curry King’, …”);

While retrieving data for restaurant 1234: we calculate 1234%5 => 4, and use rand%3 to select one of the copies:

redis.mget(“{restaurant:4:rand%3}1234”)

PS: Since these patterns can cause skew in data distribution, you may need to rebalance shards occasionally. Redis provides the ability to rebalance a cluster during live operation, which can be used during off-peak hours.