# ESL: A High-Performance Skiplist with Express Lane
## 4 Design of ESL
### Write Operation (Insert/Update/Delete)  
The write operation in ESL first traverses the COIL and then finds the target locations in the PDL and the data level. In the PDL and the data level, the writer performs the write operation in a lock-free manner and writes the operation log entry.  
**Insert.** Since a skiplist is a probabilistic data structure, it needs to generate a random number to determine the level for a given key-value pair. When the level is determined, the writer allocates a new data node at the data level and writes the key-value pair. After allocating the data node, the writer traverses the COIL (11 in Figure 2) and the PDL, (11), finds the target location at the data level (11 in Figure 2), and then adds it using the CAS instruction to atomically connect the newly created data node (11 in Figure 2). Finally, the writer creates a new operation log entry and adds it to the operation log (11 in Figure 2). The background threads will process the operation using the operation log in an asynchronous manner.  
**Update.** The update operation of ESL does not create a new key-value pair. Instead, it changes the pointer value in the existing data node at the data level, which has the same key. Hence, the update operation of ESL requires traversing the COIL, the PDL, and the data level. Within the data level, the writer finds the target data node. After finding the target data node, the writer changes the pointer value atomically using the CAS instruction. In the update operation, ESL does not employ an asynchronous update for this update operation since there is no update operation for the COIL.  
**Delete.** ESL's delete operation traverses the COIL and the PDL, similar to the insert and update operation. If the writer finds the index node, which has the same key as the given key, the writer logically deletes the index node by marking it as a deleted node. After marking the node, the writer moves to the lower level and logically deletes the index node at the index level. At the PDL and the data level, the writer finds the target node and deletes the data node by disconnecting the pointer from the previous node. After disconnecting the pointer, the writer deletes the data node. In order to safely reclaim the memory space, ESL uses epoch-based memory reclamation [37; 38; 41; 42]. Note that since the index node in the lowest level of the COIL and the PDL has the target node's virtual address instead of the index, deleting the data node from the PDL does not hurt the correctness.  
Figure 3: Layout of index levels in the COIL. Each entry of an index level consists of an 8-byte key, 8-byte next_elem, an index of the key at the next level, and an 8-byte shortcut. next_elem is an index number at the next level. The shortcut is a pointer to the data node.  
Figure 2: An illustration of the ESL structure and an example of the insert operation. 1 The foreground thread traverses the COIL to find the target node in the PDL. 2 The foreground thread finds the target data node by traversing the PDL. 3 The foreground thread moves to the target data node at the data level. 4 The foreground thread adds the new data node using a CAS operation. 5 The foreground thread writes the operation log entry. 1 The background thread reads the operation log entry from the operation log and adds the new data to the index level according to the operation log entry.