# US 11,113,155 B1 · Archiving and restoration of distributed database log records

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

- Number: US 11,113,155 B1
- Document ID: US11113155B1
- Status: Granted
- Kind: B1
- Application number: 15/789,598
- Filed: 2017-10-20
- Granted: 2021-09-07
- Earliest claimed: 2015-06-19
- Assignees: Amazon Technologies, Inc.
- Applicants: Amazon Technologies, Inc.
- Inventors: Benjamin Aldouby Schwartz; Serj Kazar; Dumanshu Goyal
- Web page: https://patentgrep.com/patent/US11113155B1

## CPC

- G06F 16/2255: {Hash tables}
- G06F 11/1451: {by selection of backup contents}
- G06F 11/1464: {for networked environments}
- G06F 11/1469: {Backup restoration techniques}
- G06F 16/113: {Details of archiving (lifecycle management in storage systems G06F3/0649; point-in-time backing up or restoration of persistent data G06F11/1446)}
- G06F 16/128: {Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16)}
- G06F 16/183: {Provision of network file services by network file servers, e.g. by using NFS, CIFS (network file access protocols H04L67/1097)}
- G06F 16/185: Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof (details of archiving G06F16/11)
- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- G06F 2201/80: Database-specific techniques
- G06F 2201/84: Using snapshots, i.e. a logical point-in-time copy of the data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Transactional log data for a distributed database may be archived by a number of computing nodes scalable to a specified concurrency parameter. A log record may be mapped to a computing node for performance of an archiving operation. The log record may be stored with information indicative of a position, in a hierarchy of shards, of the shard from which the log record originated. The log record may be replayed in an order, relative to other records, that is based on the shard's position in the shard hierarchy. The log record may be replayed on a shard identified based on a time-invariant and idempotent hash function.

## Claims

### Claim 1

A method, comprising:
obtaining a request to store data associated with a distributed database;
in response to the request, storing the data based at least in part on one or more operations performed using a concurrency parameter and a hash function applied to at least a portion of the data, wherein the data is stored with information indicative of a position of the data in a storage hierarchy of the distributed database;
obtaining a request to retrieve the stored data;
in response to the request to retrieve the stored data, applying the hash function to the portion of the data to generate a hash value;
identifying a computing node to obtain the stored data based on the hash value;
retrieving the stored data; and
storing the retrieved stored data on the computing node.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the concurrency parameter defines a degree of parallelism for storing the data.

### Claim 3 (depends on 1)

The method according to claim 1, further comprising receiving the concurrency parameter in conjunction with the request to store the data associated with the distributed database, wherein the request to store the data is a request to archive the data stored in the distributed database.

### Claim 4 (depends on 1)

The method according to claim 1, wherein the data comprises at least one log record of the distributed database.

### Claim 5 (depends on 1)

The method according to claim 1, wherein the information indicative of the position of the data is based on an application of the hash function to the portion of the data.

### Claim 6 (depends on 1)

The method according to claim 1, further comprising, in response to the request to store the data, applying the information indicative of the position of the data in the storage hierarchy to the data, wherein the information indicative of the position of the data in the storage hierarchy comprises information indicating a position of a shard in the storage hierarchy, and wherein the shard is a source of the data being stored.

### Claim 7 (depends on 6)

The method according to claim 6, wherein
applying the information indicative of the position of the data in the storage hierarchy to the data comprises applying the hash function to a key associated with the data.

### Claim 8

A record archiving method, comprising:
receiving a request to generate an archive of a record stored by a distributed database;
in response to the request to generate an archive of the record, archiving the record based at least in part on one or more operations performed using a degree of parallelism in accordance with a concurrency parameter and a hash function applied to at least a portion of the record, wherein the record is archived with information indicative of a stored position of the record in a hierarchy of storage entities of the distributed database;
obtaining a request to retrieve the archived record;
in response to the request to retrieve the archived record, applying the hash function to the portion of the archived record to generate a hash value;
identifying a storage entity to obtain the archived record based on the hash value;
retrieving the archived record; and
storing the retrieved archived record on the storage entity.

### Claim 9 (depends on 8)

The method according to claim 8, wherein the record is an entry in a transaction log maintained by the distributed database, the transaction log comprising a history of changes made to data maintained by the hierarchy of storage entities of the distributed database.

### Claim 10 (depends on 8)

The method according to claim 8, further comprising receiving the concurrency parameter in conjunction with the request to generate the archive of the record stored by the distributed database.

### Claim 11 (depends on 8)

The method according to claim 8, wherein the information indicative of the stored position of the record is based on an application of the hash function to the portion of the record.

### Claim 12 (depends on 8)

The method according to claim 8, further comprising, in response to the request to generate an archive of the record, applying the information indicative of the stored position of the record to the record, wherein the information indicative of the stored position of the record in the hierarchy of storage entities comprises information indicating a position of a storage entity in the hierarchy of storage entities, and wherein the storage entity is a source of the record being archived.

### Claim 13 (depends on 12)

The method according to claim 12, wherein applying the information indicative of the stored position of the record to the record comprises applying the hash function to a primary key of the record.

### Claim 14 (depends on 8)

The method according to claim 8, wherein archiving the record comprises selecting a computing node of a plurality of computing nodes for performing an operation to store the record, the computing node selected based at least in part on the information indicative of the stored position of the record in the hierarchy of storage entities of the distributed database.

### Claim 15 (depends on 14)

The method according to claim 14, further comprising causing the computing node to store the record with the information indicative of the stored position of the record in the hierarchy of storage entities of the distributed database, wherein the information indicative of the stored position of the record in the hierarchy of storage entities is based on an application of the hash function to the portion of the record.

### Claim 16

A record replay method for a distributed database, the method comprising:
obtaining a request to replay a plurality of records stored in an archive associated with computer storage;
in response to the request, mapping a record of the plurality of records to a shard of a distributed database at least based on a mapping mechanism associated with the record and a hash function applied to at least a portion of the record, the shard of the distributed database selected based at least in part on applying the hash function to at least the portion of the record to generate a hash value used to identify the shard of the distributed database, and wherein the mapping mechanism is defined at least based on a level of concurrency; and
storing the record in the shard.

### Claim 17 (depends on 16)

The method according to claim 16, wherein the mapping mechanism associated with the record is based on an application of the hash function already associated with the record when the request to replay is obtained.

### Claim 18 (depends on 16)

The method according to claim 16, further comprising, in response to the request, applying the mapping mechanism to the record, the mapping mechanism based on an application of the hash function applied to a key of the record, the hash function to provide an output comprising a hash space including a plurality of hash space regions based on the level of concurrency, wherein the shard is associated with one of the plurality of hash space regions.

### Claim 19 (depends on 16)

The method according to claim 16, wherein in the level of concurrency is a multiplying factor useable to define a plurality of threads to process the request to replay the plurality of records stored in the archive.

### Claim 20 (depends on 19)

The method according to claim 19, wherein the multiplying factor corresponds to a number of shards of the distributed database.