Alibaba Group Holding Limited
EFFICIENT INDEXED DATA STRUCTURES FOR PERSISTENT MEMORY

Abstract:

Indexed data structures are provided which are optimized for read and write performance in persistent memory of computing systems. Stored data may be searched by traversing an indexed data structure while still being sequentially written to persistent memory, so that the stored data may be accessed more efficiently than on non-volatile storage, while maintaining persistence against system failures such as power cycling. Mapping correspondences between leaf nodes of an indexed data structure and sequential elements of a sequential data structure may be stored in RAM, facilitating fast random access. Data writes are recorded as appended delta encodings which may be periodically compacted, avoiding write amplification inherent in persistent memory. Delta encodings are stored in iterative flows, such as log streams, enabling access to multiple buckets of data in parallel, while also providing a chronological record to enable recovery of mapping correspondences in RAM, guarding non-persistent data against system failures.