Distributed processing framework file system fast on-demand storage listing

• US 10,599,621 B1
• Filed: 02/02/2015
• Issued: 03/24/2020
• Est. Priority Date: 02/02/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Wu, Xing, McPherson, George Steven, Leidle, Robert Frederick, Fritz, Jonathan Andrew
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US14/611,980
• Time in Patent Office: 1,877 Days
• CPC Class Codes: G06F 16/182 Distributed file systems

Abstract

A system and method for improving the speed of generating a list of previously-uncounted items stored with a computing resource service provider. The system and method involve obtaining a set of keys from a data store, wherein each key of the set of keys corresponds to an item in a group of items, wherein a quantity of items in the group is uncounted. The system and method further includes generating a first sub-listing of keys based at least in part on a first key range of the set of keys by executing a first thread, generating a second sub-listing of keys based at least in part on a second key range of the set of keys by executing a second thread, combining the first sub-listing of keys with the second sub-listing of keys to produce a list of keys, and providing the list of keys.

Claims

1. A computer-implemented method, comprising:

receiving a request from a requestor to provide a listing of keys for data objects in a directory of a distributed processing framework file system, wherein the data objects are stored with a storage service of a computing resource service provider;

obtaining a set of keys from a data store of the computing resource service provider, wherein each key of the set of keys from the data store corresponds to a data object in the data objects stored with the storage service;

determining a first starting key and a second starting key based at least in part on a scheme for partitioning the set of keys;

generating a first sub-listing of keys by executing a first thread, wherein the first sub-listing of keys includes one or more keys in an order from the first starting key to the second starting key;

generating a second sub-listing of keys by executing a second thread, wherein the second sub-listing of keys includes one or more keys in the order from the second starting key to an end of the data objects, and wherein the second thread executes in parallel with the first thread;

merging the first sub-listing of keys with the second sub-listing of keys to produce the listing of keys; and

providing the listing of keys to the requestor.

2. The computer-implemented method of claim 1, wherein the request is received through an application programming interface provided by the computing resource service provider.

3. The computer-implemented method of claim 1, wherein the distributed processing framework file system is associated with one or more virtual machine instances of a virtual computer system service of the computing resource service provider.

4. The computer-implemented method of claim 1, wherein the keys of the set of keys are ordered alphanumerically.

5. A system, comprising:

one or more processors; and

memory including instructions that, if executed by the one or more processors, cause the system to;

obtain a set of keys from a data store, wherein each key of the set of keys corresponds to a respective item in a group of items, wherein a quantity of items in the group is uncounted;

generate a first sub-listing of keys based at least in part on a first key range of the set of keys by executing a first thread;

generate a second sub-listing of keys based at least in part on a second key range of the set of keys by executing a second thread;

combine the first sub-listing of keys with the second sub-listing of keys to produce a list of keys; and

provide the list of keys.

6. The system of claim 5, wherein the group of items is a serialized list of items and the first thread and second thread are executed in parallel.

7. The system of claim 5, wherein the instructions further cause the system to:

determine a first starting key and a second starting key based at least in part on a scheme for partitioning the set of keys;

determine the first key range as a range of keys ordered from the first starting key up to the second starting key; and

determine the second key range as a range of keys ordered from the second starting key.

8. The system of claim 5, wherein the list of keys is ordered alphanumerically by key value.

9. The system of claim 5, wherein the items in the group of items are file system objects in a directory of a file system.

10. The system of claim 9, wherein the first key range starts at a beginning of a keyspace of the directory.

11. The system of claim 9, wherein the second key range ends at an end of a keyspace of the directory.

12. The system of claim 5, wherein the instructions further cause the system to:

receive a request from a requestor, through an application programming interface call, to provide the list of keys, and wherein providing the list of keys comprises causing the system to provide the list of keys to the requestor.

13. The system of claim 5, wherein each item in the group of items is a data object stored with a data storage service on behalf of a customer of a computing resource service provider.

14. The system of claim 5, wherein keys in the data store are ordered and the instructions that cause the system to obtain the set of keys from the data store cause the system to:

execute a first thread to retrieve a first subset of keys from the data store according to a first order;

execute a second thread to retrieve a second subset of keys from the data store according to a second order, wherein the second order is reversed from the first order, and

in response to a determination that the first thread and the second thread have retrieved at least one common key included in the first subset of keys and the second subset of keys, combine the first subset of keys and the second subset of keys, sorted in the first order, to create the set of keys.

15. A non-transitory computer-readable storage medium having stored thereon executable instructions that, if executed by one or more processors of a computer system, cause the computer system to at least:

obtain a set of keys from a data store;

initialize one or more threads, wherein each thread is configured to generate a respective sub-listing of keys ordered from a respective start key to a respective end key, the respective sub-listing of keys determined based at least in part on a scheme for partitioning the set of keys, and wherein a first key in the respective sub-listing of keys corresponds to a respective data object of a file system;

generate a second sub-listing of keys based at least in part on a second key range of the set of keys by executing a second thread;

receive the respective sub-listing of keys from a first thread of the one or more threads;

combine the respective sub-listing of keys with the second sub-listing of keys to produce a master list, and

provide the master list.

16. The non-transitory computer-readable storage medium of claim 15, wherein keys in the master list are sorted in an order and the keys in the master list are not duplicated.

17. The non-transitory computer-readable storage medium of claim 15, wherein the data objects of the file system are stored with a data storage service, wherein the respective sub-listing of keys is obtained from metadata stored in the data store, and wherein the metadata comprises information about the data objects stored with the data storage service.

18. The non-transitory computer-readable storage medium of claim 15, wherein each key of the respective sub-listing of keys is a uniform resource indicator.

19. The non-transitory computer-readable storage medium of claim 15, wherein the file system is configured to interconnect with one or more services of a computing resource service provider and further configured to process batch jobs affecting data objects replicated over a plurality of computing systems.

20. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further cause the computer system to, for each thread of the one or more threads, until an end of a keyspace is reached or until the respective end key is detected in a given batch of keys:

obtain the given batch of keys from a data storage service, wherein a batch size is limited to a predetermined number of keys; and

include the given batch of keys in the respective list of keys.

21. The non-transitory computer-readable storage medium of claim 20, wherein the instructions further cause the computer system to, for each thread of the one or more threads, if the respective end key is detected in the given batch of keys:

include a portion of the given batch of keys up to the respective end key in the respective sub-listing of keys;

provide the respective sub-listing of keys; and

exit the thread.