This book covers the use of Redis, an in-memory database/data structure server.

open all | close all

11.4.1 Structuring a sharded LIST

In order to store a sharded LIST in a way that allows for pushing and popping from both
ends, we need the IDs for the first and last shard, as well as the LIST shards themselves.

To store information about the first and last shards, we’ll keep two numbers stored
as standard Redis strings. These keys will be named <listname>:first and <listname>:
last. Any time the sharded LIST is empty, both of these numbers will be the
same. Figure 11.1 shows the first and last shard IDs.

Additionally, each shard will be named <listname>:<shardid>, and shards will be
assigned sequentially. More specifically, if items are popped from the left, then as
items are pushed onto the right, the last shard index will increase, and more shards
with higher shard IDs will be used. Similarly, if items are popped from the right, then
as items are pushed onto the left, the first shard index will decrease, and more shards
with lower shard IDs will be used. Figure 11.2 shows some example shards as part of
the same sharded LIST.

The structures that we’ll use for sharded LISTs shouldn’t seem strange. The only
interesting thing that we’re doing is splitting a single LIST into multiple pieces and
keeping track of the IDs of the first and last shards. But actually implementing our
operations? That’s where things get interesting.

Figure 11.1First and last shard IDs for sharded LISTs
Figure 11.2LIST shards with data