## 4 Design and Implementation
### High-Level Design  
The proposed scheme is specifically designed to take advantage of the performance characteristics offered by Optane persistent memory. By employing advanced hashing techniques, it aims to enhance performance and scalability while addressing challenges commonly encountered in hashing index structures. As such, this work focuses on several key design principles, including:  
1. **Avoid both unnecessary reads and writes**: In a hashing scheme, write operations typically involve frequent access to the underlying storage media, which significantly impacts the overall performance of the scheme. These frequent read and write operations have a cumulative effect on all operations, including reads, writes, and other related tasks. Furthermore, devices with slower speeds compared to DRAM experience even more severe performance overhead due to the frequency of these read-and-write operations. To achieve high end-to-end performance, ESH addresses this issue by reducing unnecessary reads and writes to persistent memory. 2. **Bucket level locking to allow multi-threading:** A well-designed locking strategy aims to minimize the frequency of lock and unlock requests for sequential data access and manipulation, resulting in reduced CPU costs. In order to achieve better concurrency, ESH adopts a fine-grained locking approach that reduces the need for locks and unlocks, thus minimizing lock contention. Specifically, during write operations, only the bucket being operated on is locked, allowing other threads to access different buckets concurrently. Other operations are lock-free, enabling higher levels of concurrency. While readers can access buckets freely, certain operations such as segment splitting and directory doubling are not lock-free to ensure data consistency. To prevent data inconsistencies, the active writer thread takes responsibility for creating and locking segments or directories during splitting or doubling. This approach in ESH focuses on using locks at the minimal data block level, specifically, the bucket level. 3. **Optimistic scaling on multicore machines**: To fully leverage the parallel resources of CPUs, ESH incorporates an optimistic scaling approach in its design. Traditional research efforts have primarily concentrated on minimizing cache-line flushes and utilizing PM writes to achieve scalable performance. However, these approaches encounter scalability challenges when deployed on actual PM devices. Due to the limited bandwidth of PM, ESH focuses on reducing unnecessary PM reads and implementing lightweight concurrency control mechanisms to further minimize PM writes, ensuring persistence with reduced overheads. As a result, ESH treats a bucket as a single block of PM, effectively reducing the PM access overhead. In Figure 3, we can observe the comprehensive architecture of the EHS. To explain the architecture, we can take the insertion of data to the hashing table. A bucket is divided into two sections. The first section, called metadata, stores information about the bucket, facilitating efficient access and ensuring data consistency. The second section is dedicated to storing the actual records, including key-value pairs. Consequently, each directory entry points to a segment that comprises a predetermined number of regular buckets, along with the necessary metadata for locking, state information, and overflow records from adjacent buckets that cannot accommodate additional insertions. To ensure data consistency, the scheme verifies the state of a bucket before performing any operations on it, utilizing the _state_ flag present in the metadata. If a bucket is found to be in an inconsistent state due to a previous operation that has not yet been persisted (e.g., due to a crash or power failure), no further operations are carried out on the affected bucket, and the data within it is considered invalid. To avoid the costly logging of all operations, a successful insertion is only acknowledged after the metadata has been persisted.