LFA-SkipList: Optimizing SkipList by Reducing Access in a NUMA-Aware System

Sunghwan Ahn, Yujin Jang, Seungjun Ha, Beomseok Nam

http://doi.org/10.5626/JOK.2021.48.1.1

Intel"s Optane DC Persistent Memory is a non-volatile memory that works faster than storage devices and stores data persistently. However, in the NUMA system, it takes a longer latency to access the remote memory of another CPU socket than for local NUMA access. Therefore, performance is degraded when configuring the SkipList in multiple non-volatile memories. In this paper, an LFA-SkipList was proposed to solve this problem. The LFA-SkipList has a newly added local pointer and uses it to access the local node first and then the remote node, thereby reducing unnecessary remote node access and improving performance. The study found the LFA-SkipList demonstrated a much shorter search time than that of the legacy SkipList.