Compaction policy

• US 10,346,432 B2
• Filed: 03/17/2016
• Issued: 07/09/2019
• Est. Priority Date: 03/17/2015
• Status: Active Grant

• Current Assignee: Cloudera Incorporated
• Original Assignee: Cloudera Incorporated
• Inventors: Lipcon, Todd
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US15/073,509
• Publication Number:
  US 20160275094A1
• Time in Patent Office: 1,209 Days
• Field of Search: 707803, 707692, 707609, 709219, 711161
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

A compaction policy imposing soft limits to optimize system efficiency is used to select various rowsets on which to perform compaction, each rowset storing keys within an interval called a keyspace. For example, the disclosed compaction policy results in a decrease in a height of the tablet, removes overlapping rowsets, and creates smaller sized rowsets. The compaction policy is based on the linear relationship shared between the keyspace height and the cost associated with performing an operation (e.g., an insert operation) in that keyspace. Accordingly, various factors determining which rowsets are to be compacted, how large the compacted rowsets are to be made, and when to perform the compaction, are considered within the disclosed compaction policy. Furthermore, a system and method for performing compaction on the selected datasets in a log-structured database is also provided.

Claims

1. A server-implemented method of selecting rowsets to compact in a tablet storing data associated with a distributed file system (DFS), the method comprising:

restricting, by a server, each rowset in a plurality of rowsets included in the tablet to have a size less than a predetermined size threshold, wherein the each rowset stores keys covering a range that is less than or equal to a keyspace of the tablet;

determining a height of the tablet across the keyspace, wherein the height of the tablet is based on a number of rowsets having key ranges that overlap;

determining a rowset width of the each rowset in the keyspace of the tablet, wherein the rowset width of the each rowset is proportional to a percentage of the keyspace that is covered by the rowset;

until a minimum operational cost is reached, iteratively calculating, by the server, an operational cost associated with compaction of two or more rowsets in the keyspace, wherein the cost is calculated by integrating the rowset width of the each rowset included in the tablet across the height of the tablet, wherein the operational cost depends on a size of the each rowset; and

selecting, by the server, the two or more rowsets for compaction based on the two or more rowsets resulting in the minimum operational cost over the each rowset included in a workspace.

2. The method of claim 1, further comprising:

receiving new data for the tablet in a memory element stored on a data node associated with the tablet; and

flushing the new data into a new rowset stored on the tablet.

3. The method of claim 2, further comprising:

if a new rowset reaches the size threshold, creating a new rowset in the keyspace to include any data overflow.

4. The method of claim 2, wherein the new data includes a first data and a second data, the new rowset is a first rowset, further comprising:

flushing the first data into the first rowset stored on the tablet;

flushing the second data into the second rowset stored on the tablet, wherein the first rowset and the second rowset are equally sized;

estimating an on-disk size for the first data and the second data prior to the flush, wherein the estimating is (i) based on the amount of the first data and the second data in the memory element and (ii) based on a range covered by the first rowset and a range covered by the second rowset.

5. The method of claim 4, further comprising:

sending a command to the data node to flush the first data and the second data in the memory element to the tablet, wherein the first rowset and the second rowset have key ranges that do not overlap.

6. The method of claim 1, further comprising:

translating the keyspace of the tablet into an interval tree for determining the height of the tablet based on an union of the key ranges that overlap.

7. The method of claim 6, further comprising:

determining a rowset height of the each rowset included in the tablet, wherein rowset heights and rowset widths of the two or more rowsets are greatest in the plurality of rowsets.

8. The method of claim 1, wherein the plurality of rowsets includes a first rowset and a second rowset with overlapping ranges, wherein the minimum operational cost involves merging the first rowset and the second rowset resulting in a reduction in the height of the tablet, upon compaction and for a given input/output (I/O) budget.

9. The method of claim 8, wherein the operational cost is applicable for point queries, short scans, inserts, and random reads.

10. The method of claim 1, wherein the operational cost for long scans is directly proportional to a number of megabytes covered by a scan and inversely proportional to a disk bandwidth.

11. The method of claim 1, wherein the operational cost for long scans includes a direct proportionality to a cost of a key lookup and a number of rowsets accessed during the scan.

12. The method of claim 1, wherein the operational cost for short scans is directly proportional to a number of rowsets accessed during a scan and a cost of a key lookup, wherein overlapping rowsets are looked up by a respective primary key.

13. An apparatus executing a method of selecting rowsets to compact in a tablet storing data associated with a distributed file system (DFS), the method comprising:

restricting, by a server, each rowset in a plurality of rowsets included in the tablet to have a size less than a predetermined size threshold, wherein the each rowset stores keys covering a range that is less than or equal to a keyspace of the tablet;

determining a height of the tablet across the keyspace, wherein the height of the tablet is based on a number of rowsets having key ranges that overlap;

determining a rowset width of the each rowset in the keyspace of the tablet, wherein the rowset width of the each rowset is proportional to a percentage of the keyspace that is covered by the rowset;

until a minimum operational cost is reached, iteratively calculating, by the server, an operational cost associated with compaction of two or more rowsets in the keyspace, wherein the cost is calculated by integrating the rowset width of the each rowset included in the tablet across the height of the tablet, wherein the operational cost depends on the size of the each rowset; and

selecting, by the server, the two or more rowsets for compaction based on the two or more rowsets resulting in the minimum operational cost over the each rowset included in a workspace.

14. The apparatus of claim 13, wherein the plurality of rowsets includes a first rowset and a second rowset with overlapping ranges, wherein the minimum operational cost involves merging the first rowset and the second rowset resulting in a reduction in the height of the tablet, upon compaction and for a given input/output (I/O) budget.

15. The apparatus of claim 13, wherein the operational cost is applicable for point queries, short scans, inserts, and random reads.

16. A non-transitory computer-readable storage medium storing a set of instructions that, when executed by a computer system implements a method of selecting rowsets to compact in a tablet storing data associated with a distributed file system (DFS), the method comprising:

restricting, by a server, each rowset in a plurality of rowsets included in the tablet to have a size less than a predetermined size threshold, wherein the each rowset stores keys covering a range that is less than or equal to a keyspace of the tablet;

determining a height of the tablet across the keyspace, wherein the height of the tablet is based on a number of rowsets having key ranges that overlap;

determining a rowset width of the each rowset in the keyspace of the tablet, wherein the rowset width of the each rowset is proportional to a percentage of the keyspace that is covered by the rowset;

until a minimum operational cost is reached, iteratively calculating, by the server, an operational cost associated with compaction of two or more rowsets in the keyspace, wherein the cost is calculated by integrating the rowset width of the each rowset included in the tablet across the height of the tablet, wherein the operational cost depends on a size of the each rowset; and

selecting, by the server, the two or more rowsets for compaction based on the two or more rowsets resulting in the minimum operational cost over the each rowset included in a workspace.

17. The non-transitory computer-readable medium of claim 16, wherein the set of instructions, when executed by the computer system further cause the computer system to:

translate the keyspace of the tablet into an interval tree for determining the height of the tablet based on an union of the key ranges that overlap.

18. The non-transitory computer-readable medium of claim 17, wherein the set of instructions, when executed by the computer system further cause the computer system to:

determine a rowset height of the each rowset included in the tablet, wherein rowset heights and rowset widths of the two or more rowsets are greatest in the plurality of rowsets.

19. The non-transitory computer-readable medium of claim 16, wherein the plurality of rowsets includes a first rowset and a second rowset with overlapping ranges, wherein the minimum operational cost involves merging the first rowset and the second rowset resulting in a reduction in the height of the tablet, upon compaction and for a given input/output (I/O) budget.

20. The non-transitory computer-readable medium of claim 16, wherein the operational cost for long scans is directly proportional to a number of megabytes covered by a scan and inversely proportional to a disk bandwidth.