Selecting files for compaction

• US 9,639,548 B2
• Filed: 10/28/2014
• Issued: 05/02/2017
• Est. Priority Date: 10/28/2013
• Status: Active Grant

• Current Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Original Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Inventors: Bawaskar, Swapnil Prakash, Smith, Daniel Allen, Baker, Anthony M., Ramnarayanan, Jagannathan, Bhanawat, Hemant
• Primary Examiner(s): Lee, Wilson
• Application Number:
  US14/526,416
• Publication Number:
  US 20150120684A1
• Time in Patent Office: 917 Days
• Field of Search: None
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files

Abstract

Methods, systems, and apparatus for identifying two or more files, each of which include multiple entries, determining a respective size of each of the files, each size being an estimate of how many distinct entries exist in the respective file that are not garbage entries, determining a combined size of the files, where the combined size of the files is an arithmetic sum of the respective sizes of the files, estimating a compacted size of the files, where the estimated compacted size of the files is an estimate of how many distinct entries exist in the files that are not garbage entries, selecting the two or more files for compaction, based at least on a comparison of the combined size of the files to the estimated compacted size of the files, and compacting the two or more selected files.

Claims

1. A computer-implemented method comprising:

identifying two or more files, each file being a persistent electronic file stored as a separate file in a persistent file storage, each file including multiple entries;

determining a respective size of each of the two or more files, each size being an estimate of how many distinct entries exist in the respective file that are not garbage entries;

determining a combined size of the two or more files, where the combined size of the two or more files is an arithmetic sum of the respective sizes of the two or more files;

estimating a compacted size of the two or more files, where the estimated compacted size of the two or more files is an estimate of how many distinct entries exist in the two or more files that are not garbage entries when the two or more files are taken together;

determining that a result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies a threshold; and

in response to determining that the result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies the threshold, compacting the two or more files to generate a single compacted file including multiple entries, where each entry of the single compacted file is a distinct entry that is not a garbage entry.

2. The method of claim 1, wherein determining the respective size of each file comprises:

obtaining a hashed key value for each entry in the file, wherein the hashed key value is a string of bits that identifies the entry associated with a particular data record in the file, wherein each hashed key value consists of a predetermined number of leading bits followed by a predetermined number of remaining bits;

determining, based on the predetermined number of leading bits in the hashed key value, one or more indices;

determining, for each index, a number of leading zeros in the remaining bits of the hashed key value, wherein the number of leading zeros in the remaining bits of the hashed key value is used to estimate a number of entries associated with the index; and

estimating how many distinct entries exist in the file that are not garbage entries based on the one or more indices and the corresponding one or more numbers of leading zeros in the remaining bits of the hashed key values.

3. The method of claim 1, wherein determining the respective size of each file comprises:

applying a HyperLogLog algorithm to entries in the file; and

determining an estimate of how many distinct entries exist in the file that are not garbage entries based on applying the HyperLogLog algorithm to the file.

4. The method of claim 1, wherein the entries of the two or more files are stored in a log-structured merge-tree.

5. The method of claim 1, wherein determining that the result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies the threshold comprises

determining that the combined size of the two or more files is larger than the estimated compacted size of the two or more files by at least a threshold amount.

6. The method of claim 1, comprising:

in response to determining that the result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies the threshold, adjusting a compaction priority associated with the two or more files, wherein the compaction priority is used to determine when the two or more files are compacted relative to when other files are compacted.

7. The method of claim 1, where each entry of the two or more files represents a request by a user to perform an operation relating to data, wherein the operation relating to data is one of a request to update data, a request to insert data, a request to delete data, or a request to synchronize data with an external data repository.

25. The method of claim 1, wherein garbage entries in each particular file are entries that are redundant in the particular file or entries in the particular file that are outdated.

8. A system comprising:

a plurality of computers; and

a non-transitory storage device storing instructions operable to cause the computers to perform operations comprising;

identifying two or more files, each file being a persistent electronic file stored as a separate file in a persistent file storage, each file including multiple entries;

determining a respective size of each of the two or more files, each size being an estimate of how many distinct entries exist in the respective file that are not garbage entries;

determining a combined size of the two or more files, where the combined size of the two or more files is an arithmetic sum of the respective sizes of the two or more files;

estimating a compacted size of the two or more files, where the estimated compacted size of the two or more files is an estimate of how many distinct entries exist in the two or more files that are not garbage entries when the two or more files are taken together;

determining that a result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies a threshold; and

in response to determining that the result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies the threshold, compacting the two or more files to generate a single compacted file including multiple entries, where each entry of the single compacted file is a distinct entry that is not a garbage entry.

9. The system of claim 8, wherein determining the respective size of each file comprises:

obtaining a hashed key value for each entry in the file, wherein the hashed key value is a string of bits that identifies the entry associated with a particular data record in the file, wherein each hashed key value consists of a predetermined number of leading bits followed by a predetermined number of remaining bits;

determining, based on the predetermined number of leading bits in the hashed key value, one or more indices;

determining, for each index, a number of leading zeros in the remaining bits of the hashed key value, wherein the number of leading zeros in the remaining bits of the hashed key value is used to estimate a number of entries associated with the index; and

estimating how many distinct entries exist in the file that are not garbage entries based on the one or more indices and the corresponding one or more numbers of leading zeros in the remaining bits of the hashed key values.

10. The system of claim 8, wherein determining the respective size of each file comprises:

applying a HyperLogLog algorithm to entries in the file; and

determining an estimate of how many distinct entries exist in the file that are not garbage entries based on applying the HyperLogLog algorithm to the file.

11. The system of claim 8, wherein the entries of the two or more files are stored in a log-structured merge-tree.

12. The system of claim 8, wherein determining that the result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies the threshold comprises

determining that the combined size of the two or more files is larger than the estimated compacted size of the two or more files by at least a threshold amount.

13. The system of claim 8, wherein the operations comprise:

in response to determining that the result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies the threshold, adjusting a compaction priority associated with the two or more files, wherein the compaction priority is used to determine when the two or more files are compacted relative to when other files are compacted.

14. The system of claim 8, where each entry of the two or more files represents a request by a user to perform an operation relating to data, wherein the operation relating to data is one of a request to update data, a request to insert data, a request to delete data, or a request to synchronize data with an external data repository.

21. The system of claim 11, wherein the log-structured merge-tree comprises two or more hierarchical structures storing entries of the two or more files, each hierarchical structure being distributed on a corresponding node of the persistent file storage.

22. The system of claim 12, wherein the determining that the combined size of the two or more files is larger than the estimated compacted size of the two or more files by at least the threshold amount comprises determining that a number of entries that are outdated entries or redundant entries in the two or more files when the two or more files are taken together exceeds a threshold amount.

23. The system of claim 8, wherein the two or more files are log files sequentially generated by a database system, and wherein the single compacted log file replaces the two or more files.

24. The system of claim 8, wherein the operations comprise:

receiving, at a database system, a request to perform an operation relating to data stored by the system;

adding the request to perform the operation as an entry in a queue of the database system; and

transmitting the request to perform the operation from the queue of the database system for storage as an entry in one of the two or more files.

26. The system of claim 8, wherein garbage entries in each particular file are entries that are redundant in the particular file or entries in the particular file that are outdated.

15. A non-transitory storage device storing instructions operable to cause one or more computers to perform operations comprising:

identifying two or more files, each file being a persistent electronic file stored as a separate file in a persistent file storage, each file including multiple entries;

determining a respective size of each of the two or more files, each size being an estimate of how many distinct entries exist in the respective file that are not garbage entries;

determining a combined size of the two or more files, where the combined size of the two or more files is an arithmetic sum of the respective sizes of the two or more files;

estimating a compacted size of the two or more files, where the estimated compacted size of the two or more files is an estimate of how many distinct entries exist in the two or more files that are not garbage entries when the two or more files are taken together;

determining that a result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies a threshold; and

in response to determining that the result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies the threshold, compacting the two or more files to generate a single compacted file including multiple entries, where each entry of the single compacted file is a distinct entry that is not a garbage entry.

16. The non-transitory storage device of claim 15, wherein determining the respective size of each file comprises:

obtaining a hashed key value for each entry in the file, wherein the hashed key value is a string of bits that identifies the entry associated with a particular data record in the file, wherein each hashed key value consists of a predetermined number of leading bits followed by a predetermined number of remaining bits;

determining, based on the predetermined number of leading bits in the hashed key value, one or more indices;

determining, for each index, a number of leading zeros in the remaining bits of the hashed key value, wherein the number of leading zeros in the remaining bits of the hashed key value is used to estimate a number of entries associated with the index; and

estimating how many distinct entries exist in the file that are not garbage entries based on the one or more indices and the corresponding one or more numbers of leading zeros in the remaining bits of the hashed key values.

17. The non-transitory storage device of claim 15, wherein determining the respective size of each file comprises:

applying a HyperLogLog algorithm to entries in the file; and

determining an estimate of how many distinct entries exist in the file that are not garbage entries based on applying the HyperLogLog algorithm to the file.

18. The non-transitory storage device of claim 15, wherein the entries of the two or more files are stored in a log-structured merge-tree.

19. The non-transitory storage device of claim 15, wherein determining that the result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies the threshold comprises

determining that the combined size of the two or more files is larger than the estimated compacted size of the two or more files by at least a threshold amount.

20. The non-transitory storage device of claim 15, comprising:

in response to determining that the result of comparing the combined size of the two or more files to the estimated compacted size of the two or more files satisfies the threshold, adjusting a compaction priority associated with the two or more files, wherein the compaction priority is used to determine when the two or more files are compacted relative to when other files are compacted.

27. The non-transitory storage device of claim 15, wherein garbage entries in each particular file are entries that are redundant in the particular file or entries in the particular file that are outdated.