Refer to this blog for the principle of consistent Hash algorithm, and the introduction is more detailed: https://www.cnblogs.com/lpfuture/p/5796398.html

Preset scene: all requests Then, according to the consistent hash algorithm, a server is selected for forwarding, and the consistent hash algorithm obtains the server’s ip.

Assume that the node storage structure is as follows:

class Node{

 String addr; //storage server ip

}

Implementation scheme one (bitmap+HashMap)

With the help of data structure

1. 2^32 length bitmap, The following table used to mark nodes

2. HashMap, used to store the mapping from subscripts to objects

The pseudo-code for data search is implemented as follows:

bitmap = [0,0,0,1,0,0,1,...0]; //2^32 bitmap, each value of 1 indicates that this position contains node

indexToAddr map; //store the position index obtained in the bitmap Mapping to Node

n=hash(x); //x is assumed to be the user obtained in the request id, an integer between 0-2^32-1 can be obtained through the hash algorithm



//Start calculation

while(bitmap[n] != 1){

 n = (n+1)%2^32;

}



//n is the position of node in the ring, from Take this value out of hash

Node node = map.get(n);



return node.addr;

The implementation of node insertion pseudo code is as follows:

Node toBeInsert = new Node(x); / /Insert a node with value x

int n = hash(x);

bitmap[n] = 1; //Set to 1< /span>

map.put(n, toBeInsert);

This method is completely implemented in accordance with the principles introduced, and a 2 ^32 bitmap, if it is not compressed, it needs to occupy 512M of space. It takes up a lot of space, but can directly locate the value.

Realization plan two (linked list)

With the help of data structure: linked list

class LinkNode{ //define linked list data structure

 LinkNode next;

 int index; //Subscript

 Node value;

}



LinkNode head = []->[]->...->[]->head; //Linked list sorted by index



int n=hash(x);

LinkNode front = null;

LinkNode cur=head;

while(cur.index<n){

 front = cur;

 cur = cur.next;

}



if(front == null) front =< span style="color: #000000;"> head;



return front.val.node;

The linked list method will start from the list every time Start traversing once to find the specified position.

Insert in linked list mode: Just create a node and insert it directly to ensure that the linked list is in order.

class Node{

 String addr; //storage server ip

}

bitmap = [0,0,0,1,0,0,1,...0]; //2^32 bitmap, each value of 1 indicates that this position contains node

indexToAddr map; //store the position index obtained in the bitmap Mapping to Node

n=hash(x); //x is assumed to be the user obtained in the request id, an integer between 0-2^32-1 can be obtained through the hash algorithm



//Start calculation

while(bitmap[n] != 1){

 n = (n+1)%2^32;

}



//n is the position of node in the ring, from Take this value out of hash

Node node = map.get(n);



return node.addr;

Node toBeInsert = new Node(x); //insert value Node for x

int n = hash(x);

bitmap[n] = 1; //Set to 1< /span>

map.put(n, toBeInsert);

class LinkNode{ //Define the data structure of the linked list

 LinkNode next;

 int index; //Subscript

 Node value;

}



LinkNode head = []->[]->...->[]->head; //Linked list sorted by index



int n=hash(x);

LinkNode front = null;

LinkNode cur=head;

while(cur.index<n){

 front = cur;

 cur = cur.next;

}



if(front == null) front =< span style="color: #000000;"> head;



return front.val.node;