Use Memcached to implement the distributed algorithm
Distributed algorithm
Dispersion method of remainder calculation
The CRC is calculated based on the key, and the result is moduloed against the number of servers to get the Memcached server nodes. When the server fails to connect, the number of connection attempts is added to the key and recalculated.
Disadvantages:
When servers are added or removed, almost all caches are rebuilt and avalanche crashes need to be considered.
16 keys and 5 servers
| The server | The key value | The key value | The key value | The key value |
|---|---|---|---|---|
| S0 | 5 | 10 | 15 | |
| S1 | 1 | 6 | 11 | 16 |
| S2 | 2 | 7 | 12 | |
| S3 | 3 | 8 | 13 | |
| S4 | 4 | 9 | 14 |
Here’s an example: If the S3 server goes down directly, all the traffic from the S3 server will be diverted to the S4 server, which means that the S4 server will be under twice the previous pressure. If the S4 server can no longer withstand the pressure and crashes directly, all the traffic from S3 and S4 will be diverted to the S0 server
| The server | The key value | The key value | The key value | The key value | The key value |
|---|---|---|---|---|---|
| S0 | 4 | 8 | 12 | 16 | |
| S1 | 1 | 5 | 9 | 13 | |
| S2 | 2 | 6 | 10 | 14 | |
| S3 (assuming the S3 server is removed) | |||||
| S4(3) | 3 | 7 | 11 | 15 |
The above example shows that when a server is removed, basically all the caches need to be rebuilt, and the key values are all messed up except for S1 server 1 and S2 server 2
Consistent hashing algorithm
- Find the hash value of the server node and assign it to the circle from 0 to 2^32
- Find the hash value that stores the data key mapped onto the circle
- Start the search clockwise from the location to which the data is mapped, saving the data to the first server found
Advantages:
- Less redundant
- Load balancing
- Smooth transition
- Storage is balanced
Disadvantages:
Still no way to solve the avalanche problem