SELECTING FILES FOR COMPACTION

• US 20150120684A1
• Filed: 10/28/2014
• Published: 04/30/2015
• 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, Agrawal, Ashvin, Baker, Anthony M., Ramnarayanan, Jagannathan, Bhanawat, Hemant, Smith, Daniel Allen
• Granted Patent: US 9,639,548 B2
• Time in Patent Office: Days
• US Class Current: 707/693
• 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 of which include 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;

selecting the two or more files for compaction, based at least on a comparison of the combined size of the two or more files to the estimated compacted size of the two or more files; and

compacting the two or more selected files.

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 selecting the two or more files for compaction comprises:

upon 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, selecting the two or more files for compaction.

6. The method of claim 1, wherein selecting the two or more files for compaction comprises:

upon 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, adjusting a compaction priority associated with the two or more files, wherein the compaction priority is used to determine when the two or more selected 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.

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 of which include 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;

selecting the two or more files for compaction, based at least on a comparison of the combined size of the two or more files to the estimated compacted size of the two or more files; and

compacting the two or more selected files.

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 selecting the two or more files for compaction comprises:

upon 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, selecting the two or more files for compaction.

13. The system of claim 8, wherein selecting the two or more files for compaction comprises:

upon 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, adjusting a compaction priority associated with the two or more files, wherein the compaction priority is used to determine when the two or more selected 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.

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 of which include 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;

selecting the two or more files for compaction, based at least on a comparison of the combined size of the two or more files to the estimated compacted size of the two or more files; and

compacting the two or more selected files.

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 selecting the two or more files for compaction comprises:

upon 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, selecting the two or more files for compaction.

20. The non-transitory storage device of claim 15, wherein selecting the two or more files for compaction comprises:

upon 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, adjusting a compaction priority associated with the two or more files, wherein the compaction priority is used to determine when the two or more selected files are compacted relative to when other files are compacted.