Indexing data updates associated with an electronic catalog system

• US 9,043,311 B1
• Filed: 10/20/2011
• Issued: 05/26/2015
• Est. Priority Date: 10/20/2011
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Goo, Almann T., McInerny, Michael J.
• Primary Examiner(s): Waldron, Scott A
• Application Number:
  US13/278,041
• Time in Patent Office: 1,314 Days
• Field of Search: 707/715, 707/740
• US Class Current: 707/715
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 2201/80 Database-specific techniques

Abstract

Systems and methods are provided for efficiently indexing archived objects in an archive data store to allow for efficient and quick access to the archived objects. The systems and methods provided also allow alleviate the strain on a live data store and enable a requester wishing to retrieve updates to do so without knowledge of the location of the stored update on a live or archive data store.

Claims

1. A system for providing a response to a query regarding updates to an electronic catalog, the system comprising:

a live data store that accepts updates to items of the electronic catalog,

wherein items of the electronic catalog are associated with one or more item attributes,

wherein the updates to the items of the electronic catalog comprise updates to an item attribute, and wherein individual updates are indexed in a dynamic index according to an update key and an associated update value;

an archive data store that stores the updates accepted from the live data store in objects, wherein individual objects comprise a plurality of updates and wherein individual objects are indexed in a static index according to an object key and an associated object value;

a computing device in communication with the live data store and the archive data store, the computing device comprising a hardware processor that;

in response to receiving a query regarding updates to the electronic catalog from a requestor, wherein the query comprises a query key, determines whether the query key matches an update key in the dynamic index;

in response to determining that the query key does not match an update key in the dynamic index, determines whether the query key matches an object key in the static index; and

provides a response to the received query based on one of a matched update key or a matched object key, wherein the response includes information corresponding to the matched update key or a pointer to an object that corresponds to the matched object key.

2. The system of claim 1, wherein the computing device further retrieves the update value associated with the update key matched in the dynamic index.

3. The system of claim 2, wherein the computing device further retrieves the object value associated with the object key matched in the static index.

4. A system for collating values from two indices in response to a query regarding updates to items of an electronic catalog, wherein items of the electronic catalog are associated with one or more item attributes, wherein the updates to the items of the electronic catalog comprise updates to an item attribute, the system comprising:

a first data store that receives updates, wherein the updates are indexed in a dynamic index in accordance with a first key and a first value associated with individual received updates;

a second data store that stores the received updates in collections of records, wherein the collections of records are indexed in a static index in accordance with a second key and second value associated with individual collections;

a computing device in communication with the first and second data stores, the computing device comprising a hardware processor that;

in response to receiving a query regarding updates to the electronic catalog from a requestor, wherein the query comprises a query key, determines whether the query key matches at least one of the first key in the dynamic index, or the second key in the static index; and

provides a response comprising at least one of the first value associated with a matched first key or the second value associated with a matched second key, wherein the second value corresponds to a pointer to a collection of records stored in the second data store and wherein the collection of records is indexed in accordance with the matched second key.

5. The system of claim 4, wherein the computing device further:

correlates the query key to the first key in the dynamic index to determine if the query key matches the first key in the dynamic index;

if the query key does not match the first key in the dynamic index, correlates the query key to the second key in the static index to determine if the query key matches the second key in the static index; and

if the query key matches the first key in the dynamic index, provides a response comprising the first value associated with the matched first key.

6. The system of claim 4, wherein the computing device further:

correlates the query key to the second key in the static index to determine if the query key matches the second key in the static index;

if the query key does not match the second key in the static index, correlates the query key to the first key in the dynamic index to determine if the query key matches the first key in the dynamic index; and

if the query key matches the second key in the static index, provides a response comprising the second value associated with the matched second key.

7. The system of claim 4, wherein the computing device further:

correlates the query key to the second key in the static index to determine if the query key matches the second key in the static index;

correlates the query key to the first key in the dynamic index to determine if the query key matches the first key in the dynamic index; and

if the query key matches the second key in the static index and the first key in the dynamic index, provides a response comprising an aggregate of the first value associated with the first matched key and the second value associated with the matched second key;

if the query key matches only the second key in the static index, provides a response comprising the second value associated with the second matched key;

if the query key matches only the first key in the dynamic index, provides a response comprising the first value associated with the first matched key; and

if the query key does not match the first key in the dynamic index and does not match the second key in the static index, provides a response indicating that the query key is not found in the indices.

8. The system of claim 4, wherein the computing device further:

applies a first filter associated with the dynamic index to indicate first keys listed in the dynamic index; and

applies a second filter associated with the static index to indicate second keys listed in the static index; and

correlates the query key to the keys in the first and second filters to determine if the query key exists in at least one of the static index and the dynamic index.

9. The system of claim 4, wherein the query key comprises a category associated with at least one of the updates.

10. The system of claim 4, wherein an update value comprises the update.

11. The system of claim 4, wherein an object value comprises a pointer to a location of the collection in the second data store.

12. The system of claim 4, wherein the static index associating a key to a value associated with a collection of records is created asynchronously with receiving the query regarding the updates to the electronic catalog.

13. The system of claim 12, wherein the static index is created by querying the second data store for stored updates in accordance with an indexing key, receiving, in response to the query by indexing key, a plurality of updates in the second data store, aggregating the received updates according to the indexing key, and storing the aggregated updates into a collection of records with a key comprising the indexing key.

14. The system of claim 12, wherein the static index is recreated if a threshold for index recreation has been exceeded.

15. The system of claim 14, wherein the threshold for index recreation is a time period.

16. The system of claim 12, wherein the static index is recreated periodically, aperiodically, or on an interrupt-driven basis.

17. The system of claim 4, wherein the computing device further verifies if the dynamic index comprises updates indexed by the static index, and, if so, to purge such updates from the dynamic index.

18. A computer-implemented method to generate a static index of objects, wherein individual objects comprise a plurality of updates, and the objects are stored in an archive data store, the computer-implemented method comprising:

under control of one or more computing devices,

for individual query keys, querying the archive data store for updates associated with the query key, wherein the updates comprise a change associated with an item of an electronic catalog;

in response to querying the archive data store, receiving updates stored in the archive data store that are associated with the query key;

aggregating the received updates into an object;

associating the object with the query key in the static index, wherein associating the object with the query key comprises associating a pointer to the object with the query key and wherein the pointer is included in a response to a second query matching the query key; and

in response to a request for data associated with an electronic catalog, collating the static index with a dynamic index of objects stored in a live data store to retrieve the requested data.

19. The computer-implemented method of claim 18, wherein the query key comprises a category associated with the received updates.

20. The computer-implemented method of claim 19, wherein the category comprises a time period.

21. The computer-implemented method of claim 19, wherein the category comprises a type of item in an electronic catalog.

22. The computer-implemented method of claim 18 further comprising associating, in the static index, an object value with the object, wherein the object value comprises a pointer to a location of the object in the archive data store.

23. The computer-implemented method of claim 18 further comprising updating the index if a threshold for index updating has been exceeded.

24. The computer-implemented method of claim 23, wherein the threshold for index updating is a time period.

25. The computer-implemented method of claim 18, further comprising updating the index periodically, aperiodically, or on an interrupt-driven basis.

26. The computer-implemented method of claim 18, further comprising storing the static index in the archive data store.

27. A computer-readable, non-transitory medium having computer-executable modules for providing a response to a requestor query regarding updates to an electronic catalog, the computer-executable modules comprising:

an index collating module in communication with a live data store that accepts updates to items of the electronic catalog, wherein the items of the electronic catalog are associated with one or more item attributes, wherein the updates to the items of the electronic catalog comprise updates to an item attribute, wherein individual updates are indexed in a dynamic index according to an update key and an associated update value, the index collating module further in communication with an archive data store that stores the updates accepted from the live data store in objects, wherein individual objects comprise a plurality of updates, and wherein individual objects are indexed in a static index according to an object key and an associated object value, wherein the index collating module;

in response to receiving a query regarding updates to the electronic catalog from a requestor, wherein the query comprises a query key, determines whether the query key matches an object key in the static index;

in response to determining that the query key does not match an object key in the static index, determines whether the query key matches an update key in the dynamic index; and

provides a response to the received query based on one of a matched object key or a matched update key, wherein the response includes a pointer to an object that corresponds to the matched object key or information corresponding to the matched update key.

28. The computer-readable, non-transitory medium of claim 27, further comprising a static indexing module that:

queries the archive data store in accordance with an indexing key;

receives, in response to the query by indexing key, a plurality of updates in the archive data store;

aggregates the received updates into an object and associate an object key in accordance with the indexing key;

stores the object in the archive data store; and

creates the static index associating the object with the object key and the associated object value comprising a storage location associated with the object in the archive data store.

29. The computer-readable, non-transitory medium of claim 27, further comprising a dynamic index purging module that:

retrieves the dynamic index;

determines if at least a portion of the updates indexed by the dynamic index are also indexed by the static index;

if it is determined that at least a portion of the updates indexed by the dynamic index are also indexed by the static index, then purges the at least a portion of the updates from the dynamic index;

else, provides the dynamic index to the index collating module.