In large distributed systems, we all hear about clusters, such as Redis clusters, ES clusters, etc.

So what is the main function of clustering?

In my opinion, clusters do these things, or clusters are designed to solve the following problems:

(1) Scalable, good cluster design can achieve nearly linear expansion, that is, storage and performance increase linearly with the increase of hardware;

(2) High availability, can realize failover when some nodes fail.

Today let’s take a look at how Redis clusters are designed to address scalability and high availability issues and what we can learn from them.

Scalable design for Redis clusters

The Redis cluster introduces the concept of Hash Slots, which are actually data partitions. There are 16,384 Hash slots in the Redis cluster, and each node in the cluster is responsible for a portion of the hash slots.

If we have three nodes in the cluster, then:

(1) Node A contains hash slot 0 to 5500.

(2) Node B will contain hash slot 5501 to 11000;

(3) Node C contains hash slot 11001 to 16383.

The Redis cluster calculates the CRC16 value of each key value and then modulates 16384 to obtain the hash slot corresponding to the key to implement data writing/reading.

HASH_SLOT = CRC16(key) mod 16384
Copy the code

Redis introduced the concept of Hash Slot to facilitate cluster scaling, that is, to provide cluster scalability. When adding or subtracting nodes, data can be migrated with hash slot granularity.

For a stateful cluster, data migration is required to be scalable. The granularity of data migration is hash Slot for Redis and Shard partition for ElasticSearch.

Redis clustering allows us to dynamically add and remove nodes. To add a new node, we can migrate some Hash slots to the new node. If a node needs to be deleted, we can migrate the Hash slots of the node to other nodes and delete the corresponding nodes after the migration is complete.

Data repartitioning in the Redis cluster does not affect client operations.

So how does that work?

For example, if we are migrating Hash Slot 3 from node A to node B (hash Slot migration will migrate all data in that slot), the key value that the client will initiate the query in this process will be in Hash Slot 3:

(1) All nodes in the cluster will still direct requests to node A;

(2) If the corresponding key value in node A has not been migrated, the query result is returned.

(3) If the corresponding key value in node A has been migrated, user A redirects the client query to USER B. User B processes the query and returns the query result.

No new keys will be created on node A during the migration. The new keys are in Hash Slot 3 and will be created on node B.

After data migration is complete, the hash slot information corresponding to each node is updated in the cluster through internal protocols, and subsequent queries for corresponding keys are directed to B.

Redis clusters achieve scalability by dividing data into Hash slots and migrating data with hash slot granularity. By cooperating with clients, requests are not interrupted during cluster expansion.

Highly available design for Redis clusters

Because Redis itself is stateful, and for stateful applications, the highly available implementation is replication.

High availability of Redis clusters is achieved through master-slave replication.

Assume that Redis cluster has three primary nodes A, B, and C, and their secondary nodes are A1, B1, and C1 respectively. When primary node A fails, the failover process is as follows (simplified process) :

(1) If node A fails, the cluster elects A1 as the new primary node and continues to provide services;

(2) Some read/write requests will return failed before the new primary election is successful;

(3) Restart node A. It will join the cluster again as A secondary node.When it comes to master-slave replication, one unavoidable issue is data consistency.

There is a trade-off between performance and consistency.

Redis chooses performance.

Redis clustering does not guarantee strong consistency because master/slave replication in Redis is asynchronous.

The data writing process of Redis is as follows:

(1) The client writes data to Master B;

(2) master B returns OK;

(3) Master B sends write data to its slave node B1.

You can see that master B did not wait to confirm the write from the node when it returned client OK. So while master B returns a write success, if it hangs before sending data to the slave node, the newly elected master node will lose that data.

It’s really a trade-off between performance and consistency. With synchronous replication, where data is returned to the user after a successful write from the node is confirmed, we gain data consistency at the expense of performance.

As you can see, the trade-off between performance and consistency in distributed systems is currently a theoretical constraint that cannot be broken.

Redis cluster client

Clustering also requires client support. From a single node to a cluster, the client’s most basic support requires the ability to configure multiple node IP addresses so that requests can be sent to each node in the cluster.

The Redis client can further cache routing information between hash Slot and individual nodes so that requests can be sent directly to the corresponding nodes, further improving performance.

It can be seen that the complete cluster scheme design, not only the cluster server, the client is also a very important place to consider. Combination of the two, in order to play a better effect.

Write in the last

Clustering is an increasingly common concept in today’s computer systems.

Cluster design is mainly used to solve the following two problems:

(1) Extensible;

(2) High availability.

Scalability means that storage and performance grow almost linearly with hardware.

High availability is the ability to failover when some nodes fail.

Scalability is achieved through data migration, which in turn involves data migration granularity. The migration granularity in Redis cluster is Hash Slot, and other cluster implementations have similar concepts of data migration granularity.

For stateful systems, high availability can only be achieved through replication. Replication inevitably involves trade-offs between data consistency and performance. Given the limitations of theory, it’s one or the other.

Cluster design is not only a service side affair, but also requires client side support. The combination of the two, can play a better effect.

Today mainly explains the Redis cluster design, I believe that some of the design ideas can inspire us.