Efficient and Scalable Hashing Scheme for Persistent Memory

Abstract

The new advances in memory have brought many potential innovations in the data structure. The byte-addressable Persistent Memory(PM) with high capacity and low latency accelerated the shift of most existing hashing-based indexes to exploit these benefits. Hence, many new hashing schemes have been proposed using emulators which are found to be sub-optimal and also not scalable on the real device. Few hash table designs addressed important properties like load factor, scalability, efficient memory utilization, and recovery. One of the challenges in redesigning data structures for an effective hashing scheme in PM is to reduce the overheads of dynamic hashing operations in the hash table. In this paper, we present an Efficient and Scalable hashing scheme called ESH that improves memory efficiency, scalability, and performance on PM. ESH enables us to efficiently use the available spaces in the hash table and delays the full table rehashing to improve performance. This makes ESH achieve maximum load factor with efficient allocated memory space utilization. We evaluate our scheme and compare it with the widely used state-of-the-art dynamic hashing schemes that apply similar hashing techniques on Intel Optane® DC Persistent Memory (DCPMM). The experiment result shows ESH improves data insertion performance by 30% and 4% compared to CCEH and Dash respectively. It also improves the lookup operation by nearly 10% compared to Dash and achieves up to 91% load factor which is higher compared to the other competitors.

메모리의 발전은 자료 구조에서의 잠재적인 혁신을 가져왔다. 대용량이고 낮은 지연시간을 보이며 바이트 단위 접근이 가능한 영구 메모리(PM)는 그 이점을 활 용하여 대부분의 기존 해시 기반 인덱스들의 변화를 가속시켰다. 이로 인해 많은 새로운 해시 기법들이 에뮬레이터를 통해 제시되어왔지만 최적의 설계를 가지지 못 했고 실제 장치에서의 확장성(Scalable)을 갖추지 못 하였다. 일부 해시 테이블 설계만이 load factor나 확장성(Scalability), 메모리 효율성, 복구 등의 중요한 속 성을 다루었다. PM에서 효과적인 해시 기법을 다시 설계하는 것에 어려운 점 중 하나는 해시 테이블에서의 동적 해싱 연산 비 을 줄이는 것이다. 본 논문에서는 PM에서 메모리 효율성, 확장성(Scalable), 성능을 개선하는 효율적이고 확장성 가능한(Scalable) 해시 기법을 제시하며 그것을 ESH라고 부른다. ESH는 해시 테 이블의 공간을 효율적으로 사용할 수 있게 해주며 성능을 향상시키기 위해 전체 테이블의 재해시(rehashing)를 늦춘다. 이는 ESH가 할당된 메모리 공간을 효율 적으로 사용하게 하여 최대 load factor를 낼 수 있게 한다. 우리는 Intel Optane DC Persistent Memory(DCPMM)을 사용하여 우리의 기법을 평가하고 최신 동적 해싱 기법들과 비교한다. 실험 결과는 ESH가 삽입 연산에 대해 CCEH보다 30%, Dash보다 4% 성능을 개선했음을 보인다. 또한 검색 연산에 대해 Dash에 비해 약 10% 성능을 개선하였고 다른 경쟁 기법들에 해 최대 91%의 load factor를 달성하였다.