# ESL: A High-Performance Skiplist with Express Lane
## 1 Introduction  
Database systems are essential software systems that efficiently manage large amounts of data. They provide various functionalities for the user's convenience. Also, database systems provide strong data consistency guarantees by providing durability and crash consistency. However, these functionalities and crash consistency protocols can burden the performances of database systems [1; 2; 3; 4; 5; 6]. The data amounts have been continuously increasing [7]. In-memory databases are widely used solutions because they provide high throughput with low latency. However, due to their high costs and physical capacity limitations, in-memory databases are focusing more on scalability and cost-efficiency. Recently, the cost of DRAM has decreased [8]. Moreover, emerging memory technologies, such as persistent memory [9] and CXL-based memory [10], are expected to increase the memory capacity. The increasing number of cores and computational power in servers [11; 12; 13; 14] presents an opportunity to improve the performance of in-memory databases. As most servers have multiple cores, in-memory databases can process the queries in a concurrent manner. Hence, hardware advancements offer the potential to synergistically improve the performance of in-memory databases by leveraging modern hardware. In-memory databases mainly operate within DRAM-based memory spaces, making index structures play a key role in these databases. Index structures can be categorized as ordered indices and hash-based indices. Ordered indices offer moderate search performance but good range query performance. Hash indices provide high performance for pointer queries, yet they lag in terms of range query performance. Tree-based index structures, such as B+-tree [15; 16; 17; 18], are widely used as representative ordered indices. Tree-based index structures show good performance in both point queries and range queries. However, tree-based data structures require structure modification operation (SMO), and these operations can reduce the query performance due to their complexity. For instance, the split operation of the B+-tree creates a new node and moves half of the entries to the new node. The parent entry of the new node is added to the parent node. This split operation is repeated until the node has enough space. By virtue of simplicity, the beauty of a skiplist [19] lies in its ability to offer a more straightforward and cost-effective SMO compared to a tree-based structure. There is no split and merge operation in a skiplist. Instead, it adds a new node to the existing ones by connecting the new node's next pointer to the previous nodes. As a result, most LSM-tree-based databases, such as LevelDB [20], RocksDB [21], Hbase [22], and MongoDB [23], adopt a skiplist as the data structure for their MemTable. A skiplist is composed of multiple levels of linked lists, simplifying the SMOs. A skiplist generates multiple levels of each entry probabilistically and maintains them to reduce the cache misses when traversing the data structure. A skiplist can be divided into multiple levels, denoted as index levels and data levels. The index levels provide the shortest path to the target data node in the data level. While the multiple levels of each entry reduce cache misses, a skiplist can still suffer from performance degradation due to cache misses. Additionally, these multiple levels can extend the tail latencies of write queries, which include insert and delete operations; the insert and delete operations involve updates to the index level. Several efforts were made to improve the performance of a skiplist. Cache-Sensitive Skiplist [24] merges upper-level entries into a single array. Parallel in-memory Skiplist [25] merges multiple entries of neighbors of the same level into the skiplist. No Hot Spot Skiplist [26] adopts asynchronous updates for the index levels of a skiplist to reduce the latency of the write operation. NUMASK [27] considers NUMA awareness by replicating index levels to each NUMA socket.