DATABASE SYSTEMS AND APPLICATIONS FOR ASSIGNING RECORDS TO CHUNKS OF A PARTITION IN A NON-RELATIONAL DATABASE SYSTEM WITH AUTO-BALANCING

• US 20200134081A1
• Filed: 10/29/2018
• Published: 04/30/2020
• Est. Priority Date: 10/29/2018
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Ho, Shan-Cheng
• Granted Patent: US 11,921,750 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/252 between a Database Management System and a front-end application
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

A method and system are provided for assigning a particular record into a chunk of a partition within a non-relational database system. When a number of records in a particular candidate chunk is greater than a particular threshold number, an application performs an auto-balancing operation to split the particular candidate chunk such that records originally assigned to the particular candidate chunk are divided among the particular candidate chunk and a new chunk. Some of the number of records that were originally part of the particular candidate chunk are assigned to a new chunk and the other remaining ones of the number of records that were originally part of the particular candidate chunk remain assigned to the particular candidate chunk.

Claims

1. A method for assigning a particular record into a chunk of a partition within hardware-based network storage of a non-relational database system, wherein the partition comprises a plurality of chunks, and wherein each chunk stores a number of records within the partition, the method comprising:

executing an application at a hardware-based processing system of an application server to generate a particular record having a corresponding record key;

accessing the non-relational database system via a query interface and application programming interface for the application when the particular record is ready to be inserted into the partition;

determining, at a mapping function of the application based on the particular record, a natural chunk key;

assigning the particular record, at a chunk assignment module of the application, to a particular candidate chunk that is a closest chunk available for insertion of the particular record at a particular time that satisfies an assignment formula, wherein the particular candidate chunk comprises a plurality of records sorted by their corresponding record keys;

inserting the particular record into the particular candidate chunk having the particular chunk key, wherein the record key of the particular record is mapped to the particular chunk key associated with the particular record;

determining whether a number of records in the particular candidate chunk exceeds a particular threshold number; and

when the number of records in the particular candidate chunk is greater than the particular threshold number;

performing an auto-balancing operation at a chunk splitting module to split the particular candidate chunk such that records originally assigned to the particular candidate chunk are divided among the particular candidate chunk and a new chunk after the auto-balancing operation is complete, wherein some of the number of records that were originally part of the particular candidate chunk are assigned to the new chunk and wherein other remaining ones of the number of records that were originally part of the particular candidate chunk remain assigned to the particular candidate chunk.

2. The method according to claim 1, wherein the particular record remains inserted into the particular candidate chunk when the number of records in the particular candidate chunk is less than or equal to the particular threshold number.

3. The method according to claim 1, wherein the natural chunk key is greater than or equal to the chunk key of a chunk at index k and less than a chunk key of the chunk at index k+1, and wherein the mapping function maps the record key to the particular chunk key, and wherein k and k+1 are indices of two consecutive chunks that are available at the time of insertion.

4. The method according to claim 1, wherein performing the auto-balancing operation comprises:

computing, at the mapping module via a mapping function based on the record key, the natural chunk key using the record key of the particular record, wherein the natural chunk key corresponds to the particular record to be inserted;

determining whether the natural chunk key equals the particular chunk key;

when it is determined that the natural chunk key equals the particular chunk key;

performing a binary search by record key within the particular candidate chunk to find anew record to serve as the split point for splitting the particular candidate chunk into the particular candidate chunk and the new chunk;

computing, at the mapping module via the mapping function using a new record key of the new record, a new chunk key that satisfies the assignment formula; and

repeating the step of determining whether the natural chunk key equals the particular chunk key;

when it is determined that the natural chunk key is greater than the particular chunk key, wherein the particular record is the split point for a new chunk to-be created having a new chunk key that is equal to the natural chunk key; and

splitting the particular candidate chunk into the particular candidate chunk and the new chunk.

5. The method according to claim 4, wherein performing a binary search by record key within the particular candidate chunk, comprises:

retrieving all records in the particular candidate chunk having the natural chunk key;

sorting all the records by record key; and

determining records in the particular candidate chunk where the particular candidate chunk is to be split into a first half and a second half.

6. The method according to claim 5, wherein determining the records in the particular candidate chunk comprises:

determining, when the size (nk) of the chunk is even, that a middle two records where the particular candidate chunk is to be split into the first half and the second half are a first record n and a second record n+1.

7. The method according to claim 5, wherein determining the records in the particular candidate chunk comprises:

determining, when the size (2n+1) of the chunk is odd, that the records where the particular candidate chunk is to be split into the first half and the second half are a middle record n+1 and a record n+1 before the middle record.

8. The method according to claim 1, wherein the particular chunk key is a unique identifier that identifies the particular candidate chunk in the partition and allows groups of records to be queried more efficiently within the database and rendered in a page,

wherein each record has a corresponding record key having a value, and a chunk key that maps the value of the record key to a corresponding chunk such that the assignment formula:

chunk_key(k)≤

f (record key)<

chunk_key(k+1), is satisfied, where k and k+1 are indices of two consecutive chunks and chunk keys are in sorted order, and

wherein the record key is an identifier that uniquely identifies the particular record and maps to the particular chunk key.

9. The method according to claim 1, wherein the non-relational database system is capable of supporting chunking of the records in the partition so that auto-balancing functionality can be implemented at a query level within the application, wherein the partition is a collection of records that have a common attribute for grouping and within that partition.

10. The method according to claim 9, wherein the application is written to follow a particular database schema supported by a database management system (DBMS), wherein information needed to store a record in accordance with the particular database schema comprises:

(1) a partition key, (2) a chunk key, (3) a record key, and (4) data associated with the record.

11. A system, comprising:

a non-relational database system comprising;

hardware-based network storage that comprises a plurality of partitions, wherein each partition comprises one or more chunks, wherein each chunk stores a number of records within a particular partition; and

a database management system (DBMS) having a query interface and application programming interface for an application, and a database storage engine used to create, read, update and delete (CRUD) records at the hardware-based network storage; and

an application server, comprising;

a hardware-based processing system configured to execute the application as a server process to generate a particular record having a corresponding record key that is to be inserted into the non-relational database system, wherein the application is configured to;

access the non-relational database system through the query interface and application programming interface for the application when the particular record is ready to be inserted into the partition; and

wherein the application is configured to;

determine, at a mapping function of a mapping module of the application based on the particular record, a natural chunk key;

assign the particular record, at a chunk assignment module of the application, to a particular candidate chunk that is a closest chunk available for insertion of the particular record at a particular time that satisfies an assignment formula, wherein the record key of the particular record is mapped to the particular chunk key associated with the particular record;

insert the particular record into the particular candidate chunk;

determine whether a number of records in the particular candidate chunk exceeds a particular threshold number; and

when the number of records in the particular candidate chunk is greater than the particular threshold number;

perform an auto-balancing operation at a chunk splitting module to split the particular candidate chunk such that records originally assigned to the particular candidate chunk are divided among the particular candidate chunk and a new chunk after the auto-balancing operation is complete, wherein some of the number of records that were originally part of the particular candidate chunk are assigned to the new chunk and wherein other remaining ones of the number of records that were originally part of the particular candidate chunk remain assigned to the particular candidate chunk.

12. The system according to claim 11, wherein the particular record remains inserted into the particular candidate chunk when the number of records in the particular candidate chunk is less than or equal to the particular threshold number.

13. The system according to claim 11, wherein the natural chunk key is greater than or equal to the chunk key of a chunk at index k and less than a chunk key of the chunk at index k+1, and wherein the mapping function maps the record key to the particular chunk key, and wherein k and k+1 are indices of two consecutive chunks that are available at the time of insertion.

14. The system according to claim 11, wherein the application performs the auto-balancing operation by executing computer-executable instructions that are capable of causing the application to:

compute, at the mapping module via a mapping function based on the record key, the natural chunk key using the record key of the particular record, wherein the natural chunk key corresponds to the particular record to be inserted;

determine whether the natural chunk key equals the particular chunk key;

when it is determined that the natural chunk key equals the particular chunk key;

perform a binary search by record key within the particular candidate chunk to find a new record to serve as the split point for splitting the particular candidate chunk into the particular candidate chunk and the new chunk; and

compute, at the mapping module via the mapping function using a new record key of the new record, a new chunk key that satisfies the assignment formula; and

determine whether the natural chunk key equals the particular chunk key,

wherein the particular record is the split point for a new chunk to-be created having a new chunk key that is equal to the natural chunk key when it is determined that the natural chunk key is greater than the particular chunk key; and

split the particular candidate chunk into the particular candidate chunk and the new chunk.

15. The system according to claim 14, wherein the application performs the binary search by record key within the particular candidate chunk by executing computer-executable instructions that are capable of causing the application to:

retrieve all records in the particular candidate chunk having the natural chunk key;

sort all the records by record key; and

determine records in the particular candidate chunk where the particular candidate chunk is to be split into a first half and a second half.

16. The system according to claim 15, wherein the application determines the records in the particular candidate chunk by executing computer-executable instructions that are capable of causing the application to:

determine, when the size (nk) of the chunk is even, that a middle two records where the particular candidate chunk is to be split into the first half and the second half are a first record n and a second record n+1.

17. The system according to claim 15, wherein the application determines the records in the particular candidate chunk by executing computer-executable instructions that are capable of causing the application to:

determine, when the size (2n+1) of the chunk is odd, that the records where the particular candidate chunk is to be split into the first half and the second half are a middle record n+1 and a record n+1 before the middle record.

18. The system according to claim 11, wherein the particular chunk key is a unique identifier that identifies the particular candidate chunk in the partition and allows groups of records to be queried more efficiently within the database and rendered in a page,

wherein each record has a corresponding record key having a value, and a chunk key that maps the value of the record key to a corresponding chunk the assignment formula:

chunk_key(k)≤

f (record key)<

chunk_key(k+1), is satisfied, where k and k+1 are indices of two consecutive chunks and chunk keys are in sorted order, and

wherein the record key is an identifier that uniquely identifies the particular record and maps to the particular chunk key.

19. The system according to claim 11, further comprising:

a development environment that provides the application having auto-balancing functionality, wherein the application is written to follow a particular database schema supported by the DBMS, wherein information needed to store a record in accordance with the particular database schema comprises;

(1) a partition key, (2) a chunk key, (3) a record key, and (4) data associated with the particular record;

wherein the non-relational database system is capable of supporting chunking of the records in the partition so that the auto-balancing functionality can be implemented at a query level within the application,

wherein the partition is a collection of records that have a common attribute for grouping and within that partition.

20. A non-transitory, computer-readable medium containing instructions for an application thereon, which, when executed by a processor of an application server, are configurable to perform a method comprising:

executing an application to generate a particular record having a corresponding record key;

accessing a non-relational database system via a query interface and application programming interface for the application when the particular record is ready to be inserted into a partition of the non-relational database system that comprises a plurality of partitions, wherein the partition comprises a plurality of chunks, and wherein each chunk stores a number of records within the partition;

determining, at a mapping function of a mapping module of the application based on a particular record, a natural chunk key;

assigning the particular record, at a chunk assignment module of the application, to a particular candidate chunk that is a closest chunk available for insertion of the particular record at a particular time that satisfies an assignment formula, wherein the record key of the particular record is mapped to a particular chunk key associated with the particular record;

inserting the particular record into the particular candidate chunk;

determining whether a number of records in the particular candidate chunk exceeds a particular threshold number; and

when the number of records in the particular candidate chunk is greater than the particular threshold number;

performing, at an auto-balancing module, an auto-balancing operation to split the particular candidate chunk such that records originally assigned to the particular candidate chunk are divided among the particular candidate chunk and a new chunk after the auto-balancing operation is complete, wherein some of the number of records that were originally part of the particular candidate chunk are assigned to the new chunk and wherein other remaining ones of the number of records that were originally part of the particular candidate chunk remain assigned to the particular candidate chunk.