Distributed database systems and structures

Patent metadata

Field	Value
Publication number	US-11030187-B1
Application number	US-201715598282-A
Country	US
Kind code	B1
Filing date	May 17, 2017
Priority date	May 18, 2016
Publication date	Jun 8, 2021
Grant date	Jun 8, 2021

Abstract

Systems and techniques are described for efficient, general-purpose, and potentially decentralized databases, distributed storage systems, version control systems, and/or other types of data repositories. Data is represented in a database system in such a way that any value is represented by a unique identifier which is derived from the value itself. Any database peer in the system will derive an identical identifier from the same logical value. The identifier for a value may be derived using a variety of mechanisms, including, without limitation, a hash function known to all peers in the system. The values may be organized hierarchically as a tree of nodes. Any two peers storing the same logical value will deterministically represent that value with a graph, such as the described “Prolly” tree, having the same topology and hash value, irrespective of possibly differing sequences of mutations which caused each to arrive at the same final value.

First claim

What is claimed is:

1. A method comprising:
generating a tree structure of chunks in a data repository to store a set of values, the generating comprising:
dividing the set of values amongst first chunks;
determining first chunk identifiers for the first chunks by, for each chunk of the first chunks, inputting one or more values of the chunk into a function to calculate a chunk identifier for the chunk;
dividing the first chunk identifiers amongst second chunks;
determining second chunk identifiers for the second chunks by, for each chunk of the second chunks, inputting one or more of the first chunk identifiers in the chunk into the function to calculate a chunk identifier for the chunk;
storing each chunk of the first chunks and the second chunks, respectively, at a storage address determined from the chunk identifier determined for the chunk; and
storing a root chunk that comprises the second chunk identifiers at a storage address determined based on inputting the second chunk identifiers into the function; and

reading, by one or more computer processors, the set of values by retrieving each chunk of the root chunk, first chunks, and second chunks from the storage address determined for the chunk.

2. A distributed database system comprising, at each of a plurality of database peers:
storage media storing a set of values in a data repository using a tree of chunks;
logic configured to generate the tree, the generating comprising:
dividing the set of values amongst first chunks;
determining first chunk identifiers for the first chunks by, for each chunk of the first chunks, inputting one or more values of the chunk into a function to calculate a chunk identifier for the chunk;
dividing the first chunk identifiers amongst second chunks;
determining second chunk identifiers for the second chunks by, for each chunk of the second chunks, inputting one or more of the first chunk identifiers in the chunk into the function to calculate a chunk identifier for the chunk;
storing each chunk of the first chunks and the second chunks, respectively, at a storage address determined from the chunk identifier determined for chunk; and
storing a root chunk that comprises the second chunk identifiers at a storage address determined based on inputting the second chunk identifiers into the function;

logic configured to read the set of values by retrieving each chunk of the root chunk, first chunks, and second chunks from the storage address determined for the chunk.

3. One or more non-transitory computer-readable media storing instructions that, when executed by one or more computing devices, cause performance of:
generating a tree structure of chunks in a data repository to store a set of values, the generating comprising:
dividing the set of values amongst first chunks;
determining first chunk identifiers for the first chunks by, for each chunk of the first chunks, inputting one or more values of the chunk into a function to calculate a chunk identifier for the chunk;
dividing the first chunk identifiers amongst second chunks;
determining second chunk identifiers for the second chunks by, for each chunk of the second chunks, inputting one or more of the first chunk identifiers in the chunk into the function to calculate a chunk identifier for the chunk;
storing each chunk of the first chunks and the second chunks, respectively, at a storage address determined from the chunk identifier determined for the chunk; and
storing a root chunk that comprises the second chunk identifiers at a storage address determined based on inputting the second chunk identifiers into the function; and

reading the set of values by retrieving each chunk of the root chunk, first chunks, and second chunks from the storage address determined for the chunk.

4. The method of claim 1 , wherein dividing the set of values comprises:
iteratively processing each value of the set of values in a sequence, and as each value in the sequence is processed:
executing a rolling hash function of the value and any previously processed values in the sequence that have not been assigned to one of the first chunks;
determining, based on output of the rolling hash function, whether a chunk boundary has been reached;
when a chunk boundary has been reached, creating a new chunk of the first chunks, the new chunk comprising all processed values in the sequence that have not yet been assigned to any of the first chunks.

5. The method of claim 1 , further comprising, for a given chunk having given values, determining the chunk identifier of the given chunk to be a hash value computed by serializing the given values of the chunk to generate a serialized chunk value and performing a hash function on the serialized chunk value.

6. The method of claim 1 , further comprising:
generating metadata describing each chunk of the first chunks and the second chunks, the metadata including an indication of characteristics of values within the chunk;
storing the metadata describing each chunk of the first chunks and the second chunks in association with the chunk identifier of the chunk in a parent chunk at a higher layer of the tree structure;
conducting a binary search of the tree structure based on the metadata.

7. The method of claim 1 , further comprising, subsequent to generating the tree structure:
determining to insert a new value into the set of values;
identifying one or more affected chunks of the first chunks that are impacted by the insertion of the new value, the one or more affected chunks being one or more consecutive chunks that collectively store a sub-sequence of the values, the first chunks further including at least one other chunk that will not be affected by the insertion of the new value;
inserting the new value into the sub-sequence;
redividing the sub-sequence of values into one or more new chunks to replace the one or more affected chunks, the one or more new chunks including a particular chunk that at least stores the new value;
storing the one or more new chunks;
updating the first chunk identifiers by replacing any chunk identifiers for the one or more affected chunks with one or more new chunk identifiers for the one or more new chunks, and generating at least one new second chunk of the second chunks along with a new root chunk based on the updated first chunk identifiers.

8. The method of claim 1 , wherein each determined storage address is a logical address within a memory space allocated to the tree structure, each determined storage address being allocated for storing only a single chunk.

9. The method of claim 1 , further comprising:
forming a first sequence from the set of values;
wherein dividing the set of values comprises splitting the first sequence into the first chunks at boundaries in the first sequence indicated by outputs of a rolling hash function over the first sequence, at least one of the first chunks including multiple values from the set of values;
wherein the first chunk identifiers form a second sequence;
wherein dividing the first chunk identifiers comprises splitting the second sequence into the second chunks at boundaries in the second sequence indicated by outputs of a rolling hash function over the second sequence, at least one of the second chunks including multiple of the first chunk identifiers.

10. The method of claim 1 , further comprising:
determining to store a file comprising multiple copies of the set of values;
generating a second tree structure representing the file, the second tree structure including multiple references to the root chunk of the first tree structure in place of the multiple copies of the set of values.

11. The method of claim 1

Assignees

• Salesforce Com Inc

Inventors

• Boodman Aaron
• Weinstein Rafael
• Arvidsson Erik
• Masone Chris
• Willhite Dan
• Kalman Benjamin

Classifications

• H04L67/1097

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• G06F16/9027

  Trees · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F16/285

  Clustering or classification · CPC title

• G06F16/235

  Update request formulation · CPC title