Probabilistic eviction of partial aggregation results from constrained results storage

• US 10,067,678 B1
• Filed: 12/22/2016
• Issued: 09/04/2018
• Est. Priority Date: 12/22/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Pandis, Ippokratis, Papakonstantinou, Yannis
• Primary Examiner(s): Tran, Denise
• Application Number:
  US15/389,316
• Time in Patent Office: 621 Days
• Field of Search: None
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Probabilistic eviction of partial aggregation results may be implemented for aggregation operations performed using constrained result storage. An aggregation operation request may be received from a client and executed by scanning and applying the aggregation operation to data retrieved by scanning a data store. Partial aggregation results that are generated while executing the aggregation operation may be stored in a result store. If a partial aggregation result is generated when no further storage space in the result store is available, then one or more currently stored partial aggregation results may be evicted according to a reoccurrence probability so that the new partial aggregation result may be stored in the result store. The evicted partial aggregation results may be sent to the client.

Claims

1. A system, comprising:

at least one processor;

a memory, storing program instructions, that when executed by the at least one processor cause the at least one processor to perform a method comprising;

receiving a request from a client to perform an aggregation operation with respect to a plurality of entries in a table stored in a data store;

accessing the data store table to scan the plurality of entries;

applying the aggregation operation to one or more entries of the table to generate a partial aggregation result for the aggregation operation with respect to the one or more entries;

determining that insufficient storage exists in a result store in the memory for the aggregation operation to store the partial aggregation result, wherein the result store stores a plurality of other partial aggregation results for the aggregation operation;

identifying one or more of the other partial aggregation results in the result store according to a respective reoccurrence probability for the one or more other aggregation results to evict;

sending the identified one or more other partial aggregation results to the client to make storage available for the partial aggregation result;

reclaiming storage space of the identified one or more other partial aggregation results in the result store; and

updating the result store to include the partial aggregation result based on the reclaimed storage space.

2. The system of claim 1, wherein the other partial aggregation results are mapped to respective buckets of aggregation results in the result store, and wherein identifying the one or more of the other partial aggregation results in the result store according to the respective reoccurrence probability for the one or more other aggregation results, comprises:

identifying one of the buckets mapped to the partial aggregation result; and

determining one or more of the other partial aggregation results mapped to the identified bucket that were least recently updated, wherein the determined one or more other partial aggregation results that were least recently updated are the identified one or more other partial aggregation results.

3. The system of claim 1, wherein the method further comprises:

applying the aggregation operation to a different one or more entries of the table to generate another partial aggregation result for the aggregation operation with respect to the different one or more entries;

determining that sufficient storage exists in the result store to store the other partial aggregation result; and

updating the result store to include the other partial aggregation result.

4. The system of claim 1, wherein the at least one processor and the memory are implemented as part of a persistent block-based storage device that stores the table.

5. A method, comprising:

performing, by one or more computing devices;

receiving a request from a client to perform an aggregation operation with respect to a plurality of entries in a table stored in a data store;

obtaining one or more entries from the table;

applying the aggregation operation to the one or more entries to generate a partial aggregation result for the aggregation operation with respect to the one or more entries;

determining that insufficient storage exists in a result store for the aggregation operation to store the partial aggregation result, wherein the result store stores a plurality of other partial aggregation results for the aggregation operation;

selecting one or more of the other partial aggregation results in the result store according to a respective reoccurrence probability for the one or more other aggregation results;

sending the selected one or more other partial aggregation results to the client to make storage available for the partial aggregation result; and

storing the partial aggregation result in the result store.

6. The method of claim 5, wherein reading the one or more entries from the table is performed as part of a single-pass scan of the entries in the table.

7. The method of claim 5, wherein the other partition aggregation results are mapped to respective buckets of aggregation results in the result store, and wherein selecting the one or more of the other partial aggregation results in the result store according to the respective reoccurrence probability for the one or more other aggregation results comprises:

identifying one of the buckets mapped to the partial aggregation results; and

determining one or more of the other partial aggregation results mapped to the identified bucket that were least recently updated, wherein the determined one or more other partial aggregation results that were least recently updated are the selected one or more other partial aggregation results.

8. The method of claim 7, wherein identifying the one bucket comprises determining a hash value for the partial aggregation result and wherein the hash value is mapped to the identified bucket.

9. The method of claim 5, wherein selecting the one or more of the other partial aggregation results in the result store according to the respective reoccurrence probability for the one or more other aggregation results comprises:

determining a respective time since last update for the plurality of other aggregation results in the results store, wherein the respective time since last update for the selected one or more other partial aggregation results is longer than the respective time since last update for remaining other partial aggregation results.

10. The method of claim 5,

upon determining that application of the aggregation operation to the plurality of entries in the table is complete, sending remaining partial aggregation results in the result store to the client.

11. The method of claim 10, further comprising:

receiving another request to perform a different aggregation operation with respect to the table from the client;

performing the reading, the applying, the determining, the selecting, the sending, and the storing as part of executing the other request.

12. The method of claim 5, further comprising:

applying the aggregation operation to a different one or more entries read from the table to generate another partial aggregation result for the aggregation operation with respect to the different one or more entries;

determining that the other partial aggregation result updates one of the other partial aggregation results in the result store; and

updating the one other partial aggregation result in the result store according to the other partial aggregation result in the result store.

13. The method of claim 5, wherein the request to perform the aggregation operation is received and the selected one or more other partial aggregation results are sent via network connection between the client and the one or more computing devices.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

receiving a request from a client to perform an aggregation operation with respect to a plurality of entries in a table stored in a data store;

scanning the table to obtain the plurality of entries;

applying the aggregation operation to one or more entries obtained from the table to generate a partial aggregation result for the aggregation operation with respect to the one or more entries;

determining that insufficient storage exists in a result store for the aggregation operation to store the partial aggregation result, wherein the result store stores a plurality of other partial aggregation results for the aggregation operation;

evicting one or more of the other partial aggregation results in the result store according to a respective reoccurrence probability for the one or more other aggregation results;

sending the selected one or more other partial aggregation results to the client to make storage available for the partial aggregation result; and

storing the partial aggregation result in the result store.

15. The non-transitory, computer-readable storage medium of claim 14, scanning the table to obtain the plurality of entries is performed in a single pass over the table.

16. The non-transitory, computer-readable storage medium of claim 14, wherein the other partition aggregation results are mapped to respective buckets of aggregation results in the result store, and wherein, in evicting the one or more of the other partial aggregation results in the result store according to the respective reoccurrence probability for the one or more other aggregation results, the program instructions cause the one or more computing devices to implement:

identifying one of the buckets mapped to the partial aggregation results; and

determining one or more of the other partial aggregation results mapped to the identified bucket that were least recently updated, wherein the determined one or more partial aggregation results that were least recently updated are the evicted one or more partial aggregation results.

17. The non-transitory, computer-readable storage medium of claim 14, wherein the table is scanned from a memory device.

18. The non-transitory, computer-readable storage medium of claim 14, wherein the aggregation operation is one of a plurality of different types of aggregation operations, wherein the request specifies the type of the aggregation operation.

19. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:

applying the aggregation operation to a different one or more entries obtained from the table to generate another partial aggregation result for the aggregation operation with respect to the different one or more entries;

determining that sufficient storage exists in the result store to store the other partial aggregation result; and

storing the other partial aggregation result in the result store.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the one or more computing devices are implemented as part of a persistent block-based storage device that stores the table.