Compaction policies for append-only stores

1. A method for updating an append-only store, comprising:

dividing into streams the append-only store, each stream storing at least one data record having an estimated update distance, and each stream corresponding with a different range of estimated update distances;

receiving a data record;

estimating the update distance of the data record;

selecting in the append-only store, a stream having a range of estimated update distances that includes the estimated update distance of the data record; and

writing the received data record to the selected stream;

wherein for a data record P, the estimated update distance D(P), of the data record P, is a function of the number of updates to data records other than data record P, between successive updates to data record P.

2. The method of claim 1 , wherein estimating the update distance of a data record comprises:

computing the logarithmic update distance between at least one pair of successive updates of the data record received; and

computing the exponentially weighted moving average (EWMA) of the logarithmic update distance, using the logarithmic update distances between the at least one pair of successive updates of the data record received.

3. The method of claim 1 , wherein selecting a stream comprises, for each stream:

computing the logarithmic update distance between at least one pair of successive updates of a data record in the stream;

computing the exponentially weighted moving average (EWMA) of the logarithmic update distance, using the at least one pair of successive updates of a data record in the stream;

computing the exponentially weighted moving standard deviation of the logarithmic update distance, using the at least one pair of successive updates of the data record in the stream, and

selecting a stream based on

the exponentially weighted moving average (EWMA) of the logarithmic update distance, and

the exponentially weighted moving standard deviation of the logarithmic update distance.

4. The method of claim 1 , wherein a range of estimated update distances that is specific to a stream has fixed bounds.

5. The method of claim 4 , wherein the fixed bounds of a range of estimated update distances are equally spaced on a logarithmic scale.

6. The method of claim 1 , wherein a range of estimated update distances that is specific to a stream has variable bounds.

7. The method of claim 6 , further comprising

writing the data record to the stream, if the estimated update distance of the data record is within a factor of the standard deviation from the estimated update distance in the stream;

verifying a neighbouring stream, and assigning the data record to the neighbouring stream, if the estimated update distance of a data record is within a factor of the standard deviation from the estimated update distance in the neighbouring stream;

creating a new stream, if the estimated update distance of a data record is outside a factor of the standard deviation from the estimated update distance in any stream; and

merging a stream with another stream, if either stream contains less than a set minimum number of data records.

8. The method of claim 7 , wherein conditions for creating a new stream further include:

the number of streams remains less than a set maximum number of streams; and

the estimated average logarithmic update distance and standard deviation in a stream are calculated using at least a set minimum number of updates in the stream.

9. The method of claim 1 , further comprising

dividing each stream into at least one segment, each segment storing at least one data record, and

performing a compaction process that

is triggered under user-defined conditions; and

comprises:

copying live records from one segment of a stream to another stream, and

discarding a segment storing at least one obsolete data record;

where a live record is a data record that is not obsolete and that must not be discarded.

10. The method of claim 9 , wherein the compaction process further comprises:

using an append-only store having a set memory limit;

using a triggering condition based on whether the memory required to store the data records exceeds the append-only store's set memory limit;

finding in the streams, the segment having the fewest live versions of data records;

selecting for each live record, of the segment having the fewest live versions of data records, the stream having a range of average logarithmic update distances that includes the average logarithmic update distance of the live record, based on the live record's average logarithmic update distance as estimated using EWMA methods; and

appending the live record to the selected stream.

11. The method of claim 10 , wherein the compaction process further comprises using streams that store data records having estimated update distances, in a range of estimated update distances that is fixed.

12. The method of claim 10 , wherein the compaction process further comprises using streams that store data records having estimated update distances, in a range of estimated update distances that is variable and based on the estimated update distances of the data records received by and stored in the streams.

13. The method of claim 10 , wherein the compaction process further comprises:

creating a new stream to store a live record, if none of the existing streams has a range of estimated update distances that includes the estimated update distance of the live record; and

merging two streams, if one of the existing streams stores less than a set minimum number of data records.

14. The method of claim 9 , wherein the compaction process further comprises:

using streams, each stream having a set memory limit;

determining the stream for which the compaction process is expected to reduce write amplification the most;

using a triggering condition based on whether the stream's memory usage exceeds the stream's set memory limit;

selecting for compaction the segment in the stream, having the fewest live versions of data records;

selecting for each live record of the segment, the stream having a range of estimated update distances that includes the estimated update distance of the live record, based on the live record's estimated update distance; and

appending the live record to the selected stream.

15. The method of claim 14 , wherein the compaction process further comprises using streams that store data records having estimated update distances, in a range of estimated update distances that is fixed.

16. The method of claim 14 , wherein the compaction process further comprises using streams that store data records having estimated update distances, in a range of estimated update distances that is variable and based on the estimated update distances of the data records received by and stored in the streams.

17. The method of claim 14 , wherein the compaction process further comprises:

creating a new stream to store a live record, if none of the existing streams has a range of estimated update distances that includes the estimated update distance of the live record; and

merging two streams, if one of the existing streams stores less than a set minimum number of data records.

18. The method of claim 14 , wherein determining the stream for which compaction is expected to reduce write amplification the most, comprises

optimally distributing memory usage among the streams by

formulating the optimal distribution of memory usage among the streams as an optimization problem, and

periodically computing the optimal distribution.

19. The method of claim 18 , wherein the optimization problem is formulated by:

using for each stream:

the number of data records assigned to the stream,

the fraction of updates to the stream relative to the total number of updates to all streams, and

the Lambert W function to express the probability that the earliest version of a data record has not been updated in the stream;

summing the products between fractions of updates and probabilities; and

minimizing the summation of products between fractions of updates and probabilities,

considering the memory limits of each stream, and the memory limit of all the streams.

20. An append-only store comprising:

a plurality of streams, each stream designated to store at least one data record having an estimated update distance within a range of estimated update distances specific to the stream;

an input operative to receive at least one of: a new data record and an updated version of a data record;

a processor operative for:

estimating the update distance of a data record;

selecting in the append-only store of data records, a stream having a range of estimated update distances that includes the estimated update distance of a data record; and

writing a data record to the selected stream;

wherein the estimated update distance of a data record P is a function of the number of updates to data records other than data record P, between successive updates to data record P.

21. The append-only store of claim 20 , further comprising a separate data structure, referred to as a log directory, that keeps track of the location of a record, the version of a record, and other information about each record.