PERFORMING UPDATES ON VARIABLE-LENGTH DATA SEQUENTIALLY STORED AND INDEXED TO FACILITATE REVERSE READING

• US 20180107419A1
• Filed: 10/14/2016
• Published: 04/19/2018
• Est. Priority Date: 10/14/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: LinkedIn Corporation (Microsoft Corporation)
• Inventors: Sachdev, Sanjay
• Granted Patent: US 10,191,693 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

A system, method, and apparatus are provided for performing update operations on variable-length data records stored and indexed to facilitate reverse reading. Each record contains a key offset for each key field, and the key offset stores a reference (e.g., an offset) to the next most recently stored record that has the same value for the key. Key offsets of a new set of records are configured based on the data index and an assumed write location (e.g., an end offset of the data). The data repository is locked and, if no other intervening records were stored, the new ones are written, the index is updated, and the lock is released. If intervening records were stored, the new set of records is adjusted further based on the current index and the current write location, the records are stored, the index is updated, and the lock is released.

Claims

1. A method of performing an update operation on a collection of data records stored in a manner that facilitates reverse reading,

wherein an index of the data records comprises:

for each of multiple keys, one or more values of the key; and

for each value, a corresponding index offset to a most recent data record in the collection having the key value;

the method comprising;

obtaining a set of new records associated with the update operation;

based on an assumed write location for the set of new records, configuring the set of new records such that each new record includes, for each of the multiple keys, a corresponding key offset to a previous record having the same value as the new record for the key;

determining whether a current write location matches the assumed write location;

when the current write location does not match the assumed write location, updating the set of new records based on the current write location;

writing the set of new records at the current write location; and

updating the index.

2. The method of claim 1, wherein:

each new record includes values for one or more of the keys; and

said configuring the set of new records comprises, for each new record in the set of new records;

retrieving, from a copy of the index, the index offsets corresponding to the key values included in the new record;

writing the retrieved index offsets as the key offsets within the new record; and

updating the copy of the index to replace the retrieved index offsets with offsets to the new record.

3. The method of claim 2, wherein said configuring further comprises, for each new record in the set of new records:

updating the assumed write location.

4. The method of claim 2, wherein said updating the index comprises:

replacing the index with the copy of the index.

5. The method of claim 2, wherein said updating the set of new records comprises, for each new record:

obtaining, from the index or another copy of the index, the index offsets corresponding to the key values included in the new record;

writing the obtained index offsets as the key offsets within the new record;

updating the index or the other copy of the index to replace the obtained index offsets with offsets to the new record; and

updating the current write location of the collection of data records after the new record is written to the current write location.

6. The method of claim 1, further comprising:

creating a copy of the index.

7. The method of claim 1, further comprising:

prior to said determining, locking the collection of data records; and

after the index is updated, unlocking the collection of data records.

8. The method of claim 7, wherein locking the collection comprises locking an end offset that identifies the current write location.

9. An apparatus for performing an update operation on a collection of data records stored in a manner that facilitates reverse reading,

wherein an index of the data records comprises:

for each of multiple keys, one or more values of the key; and

for each value, a corresponding index offset to a most recent data record in the collection having the key value;

the apparatus comprising;

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to;

obtain a set of new records associated with the update operation;

based on an assumed write location for the set of new records, configure the set of new records such that each new record includes, for each of the multiple keys, a corresponding key offset to a previous record having the same value as the new record for the key;

determine whether a current write location matches the assumed write location;

when the current write location does not match the assumed write location, update the set of new records based on the current write location;

write the set of new records at the current write location; and

update the index.

10. The apparatus of claim 9, wherein:

each new record includes values for one or more of the keys; and

said configuring the set of new records comprises, for each new record in the set of new records;

retrieving, from a copy of the index, the index offsets corresponding to the key values included in the new record;

writing the retrieved index offsets as the key offsets within the new record; and

updating the copy of the index to replace the retrieved index offsets with offsets to the new record.

11. The apparatus of claim 10, wherein said configuring further comprises, for each new record in the set of new records:

updating the assumed write location.

12. The apparatus of claim 10, wherein said updating the index comprises:

replacing the index with the copy of the index.

13. The apparatus of claim 10, wherein said updating the set of new records comprises, for each new record:

obtaining, from the index or another copy of the index, the index offsets corresponding to the key values included in the new record;

writing the obtained index offsets as the key offsets within the new record;

updating the index or the other copy of the index to replace the obtained index offsets with offsets to the new record; and

updating the current write location of the collection of data records after the new record is written to the current write location.

14. The apparatus of claim 9, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

prior to said determining, lock the collection of data records; and

after the index is updated, unlock the collection of data records.

15. The apparatus of claim 14, wherein locking the collection comprises locking an end offset that identifies the current write location.

16. A system for performing an update operation on a collection of data records stored in a manner that facilitates reverse reading, the system comprising:

at least one processor;

an index, comprising;

for each of multiple keys, one or more values of the key; and

for each value, a corresponding index offset to a most recent data record in the collection having the key value; and

an update module comprising a non-transitory computer-readable medium storing instructions that, when executed, cause the system to;

obtain a set of new records associated with the update operation;

based on an assumed write location for the set of new records, configure the set of new records such that each new record includes, for each of the multiple keys, a corresponding key offset to a previous record having the same value as the new record for the key;

determine whether a current write location matches the assumed write location;

when the current write location does not match the assumed write location, update the set of new records based on the current write location;

write the set of new records at the current write location; and

update the index.

17. The system of claim 16, wherein:

each new record includes values for one or more of the keys; and

said configuring the set of new records comprises, for each new record in the set of new records;

retrieving, from a copy of the index, the index offsets corresponding to the key values included in the new record;

writing the retrieved index offsets as the key offsets within the new record; and

updating the copy of the index to replace the retrieved index offsets with offsets to the new record.

18. The system of claim 17, wherein said updating the index comprises:

replacing the index with the copy of the index.

19. The system of claim 17, wherein said updating the set of new records comprises, for each new record:

obtaining, from the index or another copy of the index, the index offsets corresponding to the key values included in the new record;

writing the obtained index offsets as the key offsets within the new record;

updating the index or the other copy of the index to replace the obtained index offsets with offsets to the new record; and

updating the current write location of the collection of data records after the new record is written to the current write location.

20. The system of claim 16, wherein the non-transitory computer-readable medium of the update module further stores instructions that, when executed, cause the system to:

prior to said determining, lock the collection of data records; and

after the index is updated, unlock the collection of data records;

wherein locking the collection comprises locking an end offset that identifies the current write location.