# US 2022/0027349 A1 · Efficient indexed data structures for persistent memory

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0027349 A1
- Document ID: US20220027349A1
- Status: Published application
- Kind: A1
- Application number: 16/938,399
- Filed: 2020-07-24
- Published: 2022-01-27
- Earliest claimed: 2020-07-24
- Assignees: Alibaba Group Holding Limited
- Applicants: Alibaba Group Holding Limited
- Inventors: Chen Shuo; Qingda Lu; Jiesheng Wu; Zhu Pang; Yuanjiang Ni
- Web page: https://patentgrep.com/patent/US20220027349A1

## CPC

- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

A method comprising:
receiving, by a database, a call having a key parameter, the database comprising a data structure stored at least in part on random-access memory and at least in part on persistent memory;
looking up a first element corresponding to the key by traversing an indexed data structure stored on persistent memory; and
retrieving a second element mapped to the first element by a mapping correspondence stored on random-access memory.

### Claim 2 (depends on 1)

The method of claim 1, further comprising traversing an iterative flow implemented on a sequential database structure starting from the second element.

### Claim 3 (depends on 2)

The method of claim 2, wherein multiple iterative flows are traversed in parallel by multiple threads of the database.

### Claim 4 (depends on 1)

The method of claim 1, wherein the call further has a value parameter, and further comprising writing a delta encoding from the key and the value in persistent memory.

### Claim 5 (depends on 4)

The method of claim 4, further comprising prepending the delta encoding to the second element.

### Claim 6 (depends on 5)

The method of claim 5, further comprising compacting the delta encoding with a plurality of delta encodings of an iterative flow implemented on a sequential database structure starting from the second element.

### Claim 7 (depends on 6)

The method of claim 6, further comprising splitting the iterative flow into two iterative flows.

### Claim 8

A system comprising:
one or more processors; and
memory communicatively coupled to the one or more processors, the memory storing computer-executable modules executable by the one or more processors that, when executed by the one or more processors, perform associated operations, the computer-executable modules comprising:
a searching module, the searching module further comprising:
a retrieval calling submodule configured to respond to a retrieval call having a key parameter made to a database;
an index traversing submodule configured to look up a first element corresponding to the key by traversing an indexed data structure stored on persistent memory; and
a mapping retrieving submodule configured to retrieve a second element mapped to the first element by a mapping correspondence stored on random-access memory.

### Claim 9 (depends on 8)

The system of claim 8, wherein the searching module further comprises a flow traversing submodule configured to traverse an iterative flow implemented on a sequential database structure starting from the second element.

### Claim 10 (depends on 9)

The system of claim 9, wherein multiple iterative flows are traversed in parallel by multiple threads of the database.

### Claim 11 (depends on 8)

The system of claim 8, further comprising an updating module, the updating module further comprising:
a write calling submodule configured to respond to a write call having a key parameter and a value parameter made to a database;
an index traversing submodule configured to look up a first element corresponding to the key by traversing an indexed data structure stored on persistent memory; and a mapping retrieving submodule configured to retrieve a second element mapped to the first element by a mapping correspondence stored in random-access memory; and
a delta writing submodule configured to write a delta encoding from the key and the value in persistent memory.

### Claim 12 (depends on 11)

The system of claim 11, wherein the updating module further comprises a delta prepending submodule configured to prepend the delta encoding to the second element.

### Claim 13 (depends on 12)

The system of claim 12, wherein the delta writing submodule is further configured to compact the delta encoding with a plurality of delta encodings of an iterative flow implemented on a sequential database structure starting from the second element.

### Claim 14 (depends on 13)

The system of claim 13, further comprising a flow splitting submodule configured to split the iterative flow into two iterative flows.

### Claim 15

A computer-readable storage medium storing computer-readable instructions executable by one or more processors, that when executed by the one or more processors, cause the one or more processors to perform operations comprising:
receiving, by a database, a call having a key parameter, the database comprising a data structure stored at least in part on random-access memory and at least in part on persistent memory;
looking up a first element corresponding to the key by traversing an indexed data structure stored on persistent memory;
and retrieving a second element mapped to the first element by a mapping correspondence stored on random-access memory.

### Claim 16 (depends on 15)

The computer-readable storage medium of claim 15, wherein the operations further comprise traversing an iterative flow implemented on a sequential database structure starting from the second element.

### Claim 17 (depends on 16)

The computer-readable storage medium of claim 16, wherein multiple iterative flows are traversed in parallel by multiple threads of the database.

### Claim 18 (depends on 15)

The computer-readable storage medium of claim 15, wherein the call further has a value parameter, and the operations further comprise writing a delta encoding from the key and the value in persistent memory.

### Claim 19 (depends on 18)

The computer-readable storage medium of claim 18, wherein the operations further comprise prepending the delta encoding to the second element.

### Claim 20 (depends on 19)

The computer-readable storage medium of claim 19, wherein the operations further comprise compacting the delta encoding with a plurality of delta encodings of an iterative flow implemented on a sequential database structure starting from the second element.
