Validity map-based tracking of user data updates

• US 9,715,520 B1
• Filed: 12/20/2013
• Issued: 07/25/2017
• Est. Priority Date: 12/20/2013
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Johnson, Jeffrey Arthur, Seigle, Mark Christopher
• Primary Examiner(s): Arjomandi, Noosha
• Application Number:
  US14/136,538
• Time in Patent Office: 1,313 Days
• Field of Search: 707690
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity

Abstract

A method and apparatus is disclosed for utilizing a validity map to indicate whether an overwriting data portion of user data is received. In the method and apparatus, a plurality of data portions of user data are received, whereby each data portion of the plurality of data portion may overwrite another data portion. A validity map may be utilized to indicate whether a data portion is an overwriting data portion. The validity map may be utilized for retrieving the data portion instead of the data portion being replaced.

Claims

1. A computer-implemented method, comprising:

receiving a plurality of data portions of user data;

storing the plurality of data portions in an authoritative storage and in a cache, the plurality of data portions being more readily accessible from the cache than the authoritative storage;

receiving a set of overwriting data portions, each overwriting data portion of the set of overwriting data portions being associated with a data portion of a first set of data portions from the plurality of data portions and being received to replace the data portion of the first set of data portions;

updating a validity map to indicate that each data portion of the first set of data portions is replaced;

sending an instruction to store the received set of overwriting data portions in the authoritative storage;

causing an unsuccessfully written subset of the received set of overwriting data portions to be stored in a cache;

obtaining the user data, based at least in part on the updated validity map, by at least;

obtaining a successfully written subset of the received set of overwriting data portions from the authoritative storage; and

obtaining the unsuccessfully written subset from the cache;

sending the obtained user data to a data storage system.

2. The computer-implemented method of claim 1, wherein:

obtaining the user data further includes obtaining a second set of data portions of the user data from the cache; and

the second set of data portions is not replaced by an overwriting data portion of the set of overwriting data portions.

3. The computer-implemented method of claim 1, wherein the validity map includes a plurality of bits, each bit of the plurality of bits being associated with a data portion of the plurality of data portions and each bit indicating whether the data portion is overwritten.

4. The computer-implemented method of claim 1, further comprising:

updating the validity map to indicate that an associated data portion is overwritten upon receiving each overwriting data portion of the set of overwriting data portions; and

if updating the validity map is unsuccessful, reattempting updating the validity map or requesting the user to resend the overwriting data portion.

5. The computer-implemented method of claim 1, wherein storing the plurality of data portions includes storing at least one of a digest of a data portion of the plurality of data portions, a time of receipt of the data portion, an upload time of the data portion or a range value of the data portion.

6. The computer-implemented method of claim 1, further comprising:

receiving an indication from a user that sending the plurality of data portions of user data and the set of overwriting data portions is complete; and

upon the instruction being received, obtaining the user data from the authoritative storage or the cache.

7. A system, comprising a set of computing devices that collectively implement at least:

a staging entity that at least;

receives a set of overwriting data portions, each overwriting data portion of the set of overwriting data portions being associated with a data portion of user data stored in a first storage system to be overwritten by the overwriting data portion;

identifies at least one overwriting data portion of the set of overwriting data portions; and

updates a validity map to indicate that the at least one overwriting data portion is received;

sends an instruction to overwrite the data portion of user data with the set of overwriting data portions; and

causes a subset of the set of overwriting data portions associated with an unsuccessful overwriting attempt to be stored in a second storage system for retrieval based at least in part on the validity map; and

a retrieval entity that retrieves each overwriting data portion of the set of overwriting data portions from the first storage system or the second storage system based at least in part on the validity map.

8. The system of claim 7, wherein the staging entity causes the user data to be stored by at least:

determining whether the received data portion is an overwriting data portion of the set of overwriting data portions; and

if the received data portion is not an overwriting data portion, storing the data portion in a cache and in authoritative storage.

9. The system of claim 8, wherein:

the validity map includes a plurality of bits, each bit of the plurality of bits being associated with a data portion of the user data; and

causing the validity map to indicate that the at least one overwriting data portion is received further includes causing each bit of the plurality of bits to indicate whether an overwriting data portion associated with the bit is received.

10. The system of claim 8, wherein:

the validity map includes one bit associated with the user data; and

causing the validity map to indicate that the at least one overwriting data portion is received further includes causing the one bit to indicate that an overwriting data portion is received.

11. The system of claim 10, wherein each overwriting data portion of the set of overwriting data portions is retrieved from the authoritative storage on a condition that the validity map indicates that the at least one overwriting data portion is received.

12. The system of claim 7, wherein the staging entity attempts to overwrite the data portion by further storing at least one of a digest of a data portion of the user data, a time of receipt of the data portion, an upload time of the data portion or a range value of the data portion.

13. The system of claim 7, wherein the staging entity further instructs a user to resend the at least one overwriting data portion when updating the validity map fails.

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

receive a first part of user data;

cause a validity map to indicate that the first part of the user data is received;

send an instruction to store the first part of the user data in a first storage system so as to attempt to overwrite a second part of the user data;

identify whether the first part successfully overwrites the second part of the user data;

on a condition that the first part successfully overwrites the second part of the user data, cause the validity map to indicate that the second part is overwritten; and

on a condition that the first part does not successfully overwrite the second part of the user data, cause the first part to be stored in a second storage system for retrieval based at least in part on the validity map.

15. The non-transitory computer-readable storage medium of claim 14, wherein the instructions that cause the computer system to store the first part of the user data in the first storage system further include instructions that cause the computer system to store at least one of a digest of the first part of the user data, a time of receipt of the first part, an upload time of the first part or a range value of the first part.

16. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to:

receive an instruction indicating that user data upload is complete; and

upon the instruction being received, retrieve the user data from the first storage system or the second system based at least in part on the validity map.

17. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to:

for each data part of the user data, determine whether the data part has been overwritten based at least in part on a validity bit associated with the data part in the validity map;

if the data part is not determined to be overwritten, retrieve the data part from the second storage system; and

if the data part is determined to be overwritten, retrieve the overwriting data part from the first storage system.

18. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to:

on a condition that the second part is overwritten, retrieve the user data from the first storage system; and

on a condition that the second part is not overwritten, retrieve the user data from the first storage system.

19. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to, on a condition that causing the validity map to indicate that the second part is overwritten fails, requesting a user to resend the first part of the user data.

20. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to persistently store the user data in archival storage following the retrieval of the user data from the second storage system or the first storage system.