This is the 16th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Consistent Hash algorithm

Hash conflict resolution

Open addressing

Looking forward or backward for free space to store

Zipper method

Place a linked list in the array storage location

The doha round of bush method

Hash through multiple hash algorithms

Establish public overflow areas

Hash table is divided into two parts: basic table and overflow table. All elements that conflict with basic table are filled into overflow table

Application scenarios

  • Request load balancing

    Nignx’s ipHash strategy

  • Distributed storage

    Mysql, mongodb or Redis distributed storage

Existing problems

In load balancing scenarios, session storage can be problematic if the number of servers changes.

Consistent Hash principle

The number 0-2 ^ 32 -1 is marshalled clockwise into a ring, the node is hashed to the hash ring, the requester is hashed to the hash ring, and the request falls on the nearest node clockwise.

After nodes are scaled down, the requests originally routed to the nodes are routed to the next node. Only a small part of the requests are affected, avoiding a large number of requests to migrate.

After node capacity is expanded, some requests that are originally routed to the next node are routed to the new node. However, these requests are affected and a large number of requests are not migrated.

Virtual node

Consistent Hash has good fault tolerance and scalability because only a small part of data is affected on nodes. However, when the number of nodes is too small, it may cause the number skew problem because of the uneven distribution of nodes. To solve this problem, virtual nodes were introduced.

In the virtual node scheme, multiple hashes are calculated for each service node, and each result is placed with a service node, that is, a virtual node. Requests are routed to real nodes when they land on virtual nodes.

Code sample

Consistency of the Hash

public void hash(a){
    String[] servers = new String[]{"192.168.0.1"."192.168.0.2"."192.168.0.3"};
    SortedMap<Integer, String> hashServerMap = new TreeMap<>();
    
    for(String server: servers){
        int serverHash = Math.abs(server.hashCode());
        hashServerMap.put(serverHash, server);
    }
     
    String[] clients = new String[]{"192.168.0.4"."192.168.0.5"."192.168.0.6"};
    for(String client: clients){
        int clientHash = Math.abs(client.hashCode());
        SortedMap<Integer, String> map = hashServerMap.tailMap(clientHash);
        if(map.isEmpty()){
            Integer key =   hashServerMap.firstKey();
        }else{ Integer key = map.firstKey(); }}}Copy the code

Virtual Node Hash

public void hash(a){
    String[] servers = new String[]{"192.168.0.1"."192.168.0.2"."192.168.0.3"};
    SortedMap<Integer, String> hashServerMap = new TreeMap<>();
    
    int virtualCount =3;
    for(String server: servers){
        int serverHash = Math.abs(server.hashCode());
        hashServerMap.put(serverHash, server);
    	for(int i=0; i< virtualCount; i++){
             int virServerHash = Math.abs((server+"#"+i).hashCode());
        	 hashServerMap.put(virServerHash, server);
        }
    }
     
    String[] clients = new String[]{"192.168.0.4"."192.168.0.5"."192.168.0.6"};
    for(String client: clients){
        int clientHash = Math.abs(client.hashCode());
        SortedMap<Integer, String> map = hashServerMap.tailMap(clientHash);
        if(map.isEmpty()){
            Integer key =   hashServerMap.firstKey();
        }else{ Integer key = map.firstKey(); }}}Copy the code

Clock synchronization

Each server node in a distributed cluster can connect to the Internet

Synchronizes with the national time center/time server and executes through scheduled tasks

Ntpdate -u ntp.api.bz # Synchronizes time from a time serverCopy the code

Only some nodes in a distributed cluster can access the Internet

Accessible nodes access the Internet through ntpDate, and other machines access from accessible nodes

None of the distributed nodes can access the Internet

One of the nodes is selected as the time server from which the other servers access

Configure the time server
vim /etc/ntp.conf
Restrict Default ignore
172.17.0.0 is the LAN network segmentRestrict 172.17.0.0 mask 255.255.255.0 nomodify Notrap Server 127.127.1.0 service NTPD restart chkconfig ntpd onCopy the code