Recently in the Redis design and implementation, in Redis underlying data structure used skip table, taking advantage of this demand, looked at Java based on skip table implementation set.
Jump table
A SkipList is an ordered data structure in which each node maintains multiple Pointers to other nodes for fast access. For the most part, skip lists are as efficient and easier to implement as balanced trees because they are so widely used that only ConcurrentSkipListMap is implemented.
public ConcurrentSkipListMap(a) {
// comparator is a unified comparator
this.comparator = null;
initialize();
}
private void initialize(a) {
keySet = null;
entrySet = null;
values = null;
descendingMap = null;
head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
null.null.1);
}
/** header index */
static final class HeadIndex<K.V> extends Index<K.V> {
final int level;
HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
super(node, down, right);
this.level = level; }}Index / * * * /
static class Index<K.V> {
final Node<K,V> node;
final Index<K,V> down;
volatile Index<K,V> right;
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
this.node = node;
this.down = down;
this.right = right;
}
Copy the codeHere you can see new ConcurrentSkipListMap(), which just creates a raw header index, no hierarchy, no linked list. Now let’s look at his put method. Let’s say we want to put key 5.
public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
return doPut(key, value, false);
}
Copy the codeThe doPut() method is too long, so we split the method into three parts
1. Create the node to be inserted
First, find the appropriate Node location. Note that the Node obtained here does not necessarily need to be inserted in front of the Node. The obtained Node satisfies two conditions:
1. At the bottom; 2. The key of the node is smaller than that of the newly inserted nodeCopy the codeThen, we set the current traversal node as B, the next node of the current traversal node as N, and the new node to be inserted as Z. Recursively find the insertion point, and the insertion point needs to meet two conditions:
1. b < z <= n 2. b is closest to NCopy the codeprivate V doPut(K key, V value, boolean onlyIfAbsent) {
// z is the Node to be created
Node<K,V> z; // added node
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
/* * b: the node traversed currently, which is initially the front node of the newly inserted node * n: is the next node traversed currently, which is initially the rear node of b before the new node is inserted * */
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
if(n ! =null) {
Object v; int c;
// f: subsequent nodes of n
Node<K,V> f = n.next;
// If n is not a subsequent node of b, do the next for (;;). , possibly because other threads have inserted other nodes into subsequent nodes of B
if(n ! = b.next)// inconsistent read
break;
// If the value of subsequent node n is null, it indicates that the node has been deleted, then delete the node, replace n with the subsequent node f of n, the next for (;;).
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
// If the value of b is null, it is deleted by another thread. For (;;)
if (b.value == null || v == n) // b is deleted
break;
// If the key to be inserted is larger than that of the subsequent node, proceed to the subsequent node
if ((c = cpr(cmp, key, n.key)) > 0) {
b = n;
n = f;
continue;
}
// If the key to be inserted is the same as the key of the subsequent node
if (c == 0) {
// If onlyIfAbsent is true, replace the value of n to end the loop
// If the cas replacement fails, do the next for (;;)
if (onlyIfAbsent || n.casValue(v, value)) {
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
break; // restart if lost race to replace value
}
// else c < 0; fall through
}
// Create node z to be inserted, next pointing to n
z = new Node<K,V>(key, value, n);
// Change the next point of b to new node Z, cas replacement failed, next for (;;)
if(! b.casNext(n, z))break; // restart if lost race to append to b
// At this point, the bottom Node list is formed, but for skip lists, the top index and its join relationships need to be constructed
breakouter; }}Copy the codeThere are several major methods, starting with the findPredecessor(Key, CMP) method, which is used to find suitable Node locations
/** * return a node that is placed at the bottom of the skip table, and only a node that meets the following two conditions: 2. The key of the node is smaller than that of the newly inserted node * It does not mean that the returned node is followed by the newly inserted node, This does not mean that the last nodes of the newly inserted node will be the same as the original q.ext *. The relationship between the last nodes is as follows: q --> XXX --> newly inserted node --> XXX --> original q.ext * XXX indicates that there may be multiple interval * variables. The current index, and the index * r that needs to contain the final result node: the subsequent index of the current index, or whether the key of the subsequent index is greater than the key */ that needs to be inserted
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
if (key == null)
throw new NullPointerException(); // don't postpone errors
for (;;) {
// Get the original header index q and the subsequent index r of the current index
for (Index<K,V> q = head, r = q.right, d;;) {
// if r is null, it means that the index level is not larger than the key to insert
// If it is not the lowest level, q is updated as the child node of the current node, r is the child node of the latest node, and if it is the lowest level, node of the current variable q is returned
if(r ! =null) {
// Get the following index of the linked list: n
Node<K,V> n = r.node;
K k = n.key;
// If the value of this object is null, it indicates that the object has been deleted. The value of put cannot be null
// Unlink all upper-level indexes whose value is null
if (n.value == null) {
// drop the null index, that is, replace r with the subsequent index of r, and enter the inner for loop again
if(! q.unlink(r))break; // restart
// r is set again to the right of the current index for the next inner loop
r = q.right; // reread r
continue;
}
// If the key to be inserted is larger than the key of subsequent node N, skip to the next node
// q --> r r ---> r.right
// Until n's key is larger than the key to insert, breaking the loop
if (cpr(cmp, key, k) > 0) {
q = r;
r = r.right;
continue; }}// the index q is the lowest level index
if ((d = q.down) == null)
return q.node;
// If it is not the lowest index, assign q to the lower index of q,
q = d;
// r is assigned to the subsequent index qr = d.right; }}}Copy the code
Then there is the helpDelete method, which is executed only if (v = n.value) == NULL, twice to remove the node and replace n with a subsequent node of N, f.
1. Meet the f = = null | | f.v alue! = f execute and return, call this method to b --> n --> newNode<K,V>(f) --> f case 2. At this point in the next for loop, the else judgment will be satisfied, pointing NEXT of B to f, and n and next will not be in the listCopy the code void helpDelete(Node<K,V> b, Node<K,V> f) {
/* * Rechecking links and then doing only one of the * help-out stages per call tends to minimize CAS * interference among helping threads. */
// If f is the subsequent points of the Node and the Node is the subsequent Node of b, the general situation must be satisfied, unless deleted in the middle
if (f == next && this == b.next) {
// If f is null, or the value of f is not f itself, create a new node and append the tag
// execute casNext(f, new Node
(f)); And then the structure is zero
,v>
/* * b ---> n --- > new Node
(f) --- > f * */
,v>
if (f == null|| f.value ! = f)// not already marked
casNext(f, new Node<K,V>(f));
else
After executing the following statement, the structure is
/* * b --> f n and new Node
(f) * */
,v>
b.casNext(this, f.next); }}Copy the code
2. Create the node to be inserted
First, obtain the number of random layers and build a new Index from the bottom up. If the number of random layers is greater than the original maximum level, reconstruct headIndex.
// Get a random number
int rnd = ThreadLocalRandom.nextSecondarySeed();
/ / the random binary and binary 0 x80000001: with 10000000000000000000000000000001 operations
// that is, the highest and lowest bits of the binary random number are both 0, and other bits are irrelevant. If not, the layer number of the node is not increased, and the third step is not continued
if ((rnd & 0x80000001) = =0) { // test highest and lowest bits
// The initial level is 1
int level = 1, max;
// Determine the number of consecutive 1s to the left of the binary from the last to the last of the random values
while (((rnd >>>= 1) & 1) != 0)
++level;
Index<K,V> idx = null;
// header index h
HeadIndex<K,V> h = head;
// Max is assigned to the level of the header index, i.e., the highest level of the current skip table;
// If level is smaller than Max
if (level <= (max = h.level)) {
// create the upper index of z. The upper index of z points to the new node, and then points to the lower index
// There is no left or right association with skip lists
for (int i = 1; i <= level; ++i)
idx = new Index<K,V>(z, idx, null);
} else { // try to grow by one level
// If level is greater than Max, set level = Max + 1
level = max + 1; // hold in array and later pick the one to use
// Create an array of length level + 1, since we want the index to start at 1, so + 1
@SuppressWarnings("unchecked")Index<K,V>[] idxs =
(Index<K,V>[])newIndex<? ,? >[level+1];
// create the upper index of z. The upper index of z points to the new node, and then points to the lower index
// There is no left or right association with skip lists
for (int i = 1; i <= level; ++i)
idxs[i] = idx = new Index<K,V>(z, idx, null);
// Rebuild the header index
for (;;) {
// h is reassigned to the header index, which is also the final header index
h = head;
// oldLevel is assigned to the original level
int oldLevel = h.level;
// If level is equal to oldLevel, another thread has changed the level of the header loop. for
if (level <= oldLevel) // lost race to add level
break;
// Reset a header index
HeadIndex<K,V> newh = h;
// Get the node of the header index
Node<K,V> oldbase = h.node;
// Create a header index through a loop, usually only once
for (int j = oldLevel+1; j <= level; ++j)
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
// cas replaces h with newh for head, not h = newh
// There is no need to build the pointing relationship again because there is only a header index and a new node index on the new chain surface
/* Successful head Head node status: head ↓ Original head */
if (casHead(h, newh)) {
// assign h to newh
h = newh;
// set level to the level of the original header index, and then set idx to the index at level of idxs
idx = idxs[level = oldLevel];
break; }}}Copy the code
After the execution of the second step, suppose that, level is 4, the skip list structure is as shown in the figure above. The changes are as follows:
2. Create a new headIndex 3. The newly created headIndex right points to the top-level index of the newly created node, and the top-level index right points to null 4. The newly created indexes all point down in orderCopy the code3. Construct the pointing relationship of Index added in each layer
The main logic is to compare right from the highest level to the original level, find the appropriate position, build the correct pointing relationship, and then start to build the next level.
// insertionLevel: the current number of levels to build the pointing relationship, starting with the level of the original header
splice: for (int insertionLevel = level;;) {
// j: the initial level is the current level of the header index
int j = h.level;
Q -> q.ight -> q.ight. Right...
R -> r.ight -> r.ight. Right...
// t: new index at the level where q resides
// Build the pointer relationship of each new node in a loop, starting with the initial index, until the key that needs to be inserted is smaller than that of an index
for (Index<K,V> q = h, r = q.right, t = idx;;) {
// If q or t is null, the other thread deleted q or t and re-entered for (;;).
if (q == null || t == null)
break splice;
// if r is empty, it is the maximum value of this layer
if(r ! =null) {
// n Node assigned to r
Node<K,V> n = r.node;
// compare before deletion check avoids needing recheck
// Compare the key to be inserted with n's key
int c = cpr(cmp, key, n.key);
// Put does not allow the value to be null. If value is null, the index has been deleted
if (n.value == null) {
if(! q.unlink(r))break;
r = q.right;
continue;
}
// If we insert a key greater than n, proceed further
if (c > 0) {
q = r;
r = r.right;
continue; }}// If the number of levels in the current header index is the same as the number of levels in the original header index, the number of levels has not changed
if (j == insertionLevel) {
For (int insertionLevel = level;;)
if(! q.link(r, t))break; // restart
For (int insertionLevel = level;;) if the value of the new node is null, the node has been deleted by another thread.
if (t.node.value == null) {
findNode(key);
break splice;
}
// Exit the loop at the bottom layer to complete the PUT operation
if (--insertionLevel == 0)
break splice;
}
// Q, r, t move down as the number of node layers move down to prepare for the lower layer construction operation
if(--j >= insertionLevel && j < level) t = t.down; q = q.down; r = q.right; }}}return null;
}
Copy the codeThere is a findNode(key) method, annotated here
private Node<K,V> findNode(Object key) {
if (key == null)
throw new NullPointerException(); // don't postpone errors
Comparator<? super K> cmp = comparator;
outer: for (;;) {
// Find the front node b of the target node, where n is the rear node of b
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
// If the back-end node is null, no further action is required
if (n == null)
break outer;
// Get subsequent nodes of subsequent nodes
Node<K,V> f = n.next;
// If the node in position n is a subsequent node, it has been deleted, go to the next for (;;).
if(n ! = b.next)// inconsistent read
break;
// If the value of node N is null, it indicates that node N has been deleted. Set next of node B to f, and enter next for (;;).
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
// If the value of front-end node B is null, it has been deleted. Go to for (;) next time.
if (b.value == null || v == n) // b is deleted
break;
// If the target key is equal to n.key, return the subsequent node n
if ((c = cpr(cmp, key, n.key)) == 0)
return n;
// If it is larger than the key of the subsequent node, advance backward
if (c < 0)
breakouter; b = n; n = f; }}return null;
}
Copy the codeAt this point, the skip list put is complete.
1. Call the findPredecessor method and start searching from the right of the de novo Index. If the node key of the subsequent Index is larger than the key we want to search, the head Index is moved downward and searched in the lower Index until no lower Index is found. 3. Start from the nodes found by the findBody predecessor method and go right. Returns the result until the key of a node is equal to the key of the target, or null if the key is less than the target keyCopy the code public V get(Object key) {
return doGet(key);
}
Copy the code private V doGet(Object key) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
/* * b: the node traversed currently, which is initially the front node of the newly inserted node * n: is the next node traversed currently, which is initially the rear node of b before the new node is inserted * */
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null)
break outer;
// f: n after node
Node<K,V> f = n.next;
// If n is not a subsequent node of b, do the next for (;;). , possibly because other threads have inserted other nodes into subsequent nodes of B
if(n ! = b.next)// inconsistent read
break;
// If the value of subsequent node n is null, it indicates that the node has been deleted, then delete the node, replace n with the subsequent node f of n, the next for (;;).
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
// If the value of b is null, it is deleted by another thread. For (;;)
if (b.value == null || v == n) // b is deleted
break;
// The key you want to find is the same as the key of n
if ((c = cpr(cmp, key, n.key)) == 0) {
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
// If less than, exit the for loop and return null
if (c < 0)
break outer;
// If the key to be inserted is larger than that of the subsequent node, proceed to the subsequent nodeb = n; n = f; }}return null;
}
Copy the codeThe last one is the remove method, which needs to be explained here. Because ConcurrentSkipListMap supports concurrency, when a node is deleted, it may be inserted by another thread. Therefore, a special node will be added after the node to mark the node to be deleted before it is deleted. Resolve a problem where new data is added after being deleted, and then the data is deleted. The remove method is mainly divided into three steps:
1. FindPredecessor method to obtain suitable front node B 2. Then, a series of concurrent CAS operations are performed. Then, the key of N is compared with the key to be deleted. If the key to be deleted is larger than that of N, the process continues. If the keys are equal, set the value of n to null first, and then point B to N.next, indicating that N has been deleted in the linked list of nodes. Then findPredecessor is called to delete the indexes of deleted node N on each index layer.Copy the code public V remove(Object key) {
return doRemove(key, null);
}
Copy the codefinal V doRemove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
/* * Or findPredecessor method * b: the node currently traversed, initially the front node of the newly inserted node * n: is the next node currently traversed, initially the rear node of b before the new node is inserted * */
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
// If n is null, it indicates that it has been deleted and exits the loop
if (n == null)
break outer;
// f: subsequent nodes of n
Node<K,V> f = n.next;
// n is not a subsequent node of b, read inconsistent, proceed next for (;;)
if(n ! = b.next)// inconsistent read
break;
// If the value of n is null, the node is marked or deleted
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
// indicates that another thread deleted b, or has been marked for deletion, go to the next for (;;).
// The helpDelete method marks to be deleted. If the correlation is as follows, it marks to be deleted
/ / left
// Node to be removed --> new Node
(subsequent Node of Node) --> Original successor Node of Node to be removed
,v>
if (b.value == null || v == n) // b is deleted
break;
// Compare the target key with n's key
// If the key is smaller than N, there is no corresponding node. No further operation is required
if ((c = cpr(cmp, key, n.key)) < 0)
break outer;
// The value greater than 0 is traversed through subsequent nodes
if (c > 0) {
b = n;
n = f;
continue;
}
// The following is the equivalent operation
// value ! = null Indicates whether the values are the same
if(value ! =null && !value.equals(v))
break outer;
// Set the value of n to null, not yet removed from the list, continue next time for (;;)
if(! n.casValue(v,null))
break;
// appendMarker is an additional marker that marks n to be deleted and the correlation pointer is b --> n --> new Node
(f) --> f
,v>
// Then the next node of b points to f. There are no nodes in the skip list that point to N, but the Index of N is still in the skip list
if(! n.appendMarker(f) || ! b.casNext(n, f)) findNode(key);// retry via findNode
else {
// This method is used not only to find the appropriate front node, but also to unlink the null index
// the index n is removed from the skip list
findPredecessor(key, cmp); // clean index
if (head.right == null)
tryReduceLevel();
}
@SuppressWarnings("unchecked") V vv = (V)v;
returnvv; }}return null;
}
Copy the codeconclusion
Because ConcurrentSkipListMap stores key-value pairs, Node is used to store data and form a complete linked list, not a skip list structure. Skip lists are mainly realized through Index, each Index has a Node to point to, that is, Index as an Index, is used to speed up the query efficiency, Node is the real storage of data. ConcurrentSkipListMap is very efficient. If the application needs to be ordered, then hop tables are a good choice. If the application needs to be ordered, hop tables are a good choice.