CAPTURING SNAPSHOTS OF VARIABLE-LENGTH DATA SEQUENTIALLY STORED AND INDEXED TO FACILITATE REVERSE READING

• US 20170371551A1
• Filed: 06/23/2016
• Published: 12/28/2017
• Est. Priority Date: 06/23/2016
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: LinkedIn Corporation (Microsoft Corporation)
• Inventors: Sachdev, Sanjay
• Application Number:
  US15/191,091
• Publication Number:
  US 20170371551A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 3/061 Improving I/O performance
• 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 capturing a snapshot of variable-length data records that are indexed and sequentially stored in a manner that facilitates reverse reading. Each data record has a fixed number of keys, a key offset for each key that leads to another record with the same key value, and size metadata identifying a size of the data record (and possibly the key offsets). An index identifies, for each known value of each key, an index offset to a first entry (e.g., the most recently stored entry) that has the key value. Capturing a snapshot includes identifying a final record within the snapshot (e.g., based on time), copying the index, and pruning it as necessary to omit records not consistent with the snapshot (e.g., to omit data records stored after a final time corresponding to the snapshot).

Claims

1. A method of capturing a snapshot of a repository of variable-length data records;

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 first data record in the repository having the key value;

the method comprising;

identifying a final data record to be included in the snapshot;

determining a snapshot offset of the final data record in the repository;

creating a copy of the index; and

within the index copy, for each of the multiple keys;

for each value of the key;

determining whether the corresponding index offset is greater than the snapshot offset; and

if the corresponding index offset is greater than the snapshot offset, pruning the index offset until the corresponding index is less than or equal to the snapshot offset.

2. The method of claim 1, wherein said pruning comprises:

using the index offset to access the first data record having the key value;

within the first data record, reading a key offset corresponding to the key value, wherein the key offset comprises an offset to a next data record having the key value;

if the key offset is greater than the snapshot offset, repeating said accessing, in the next data record, until the key offset of a subsequent next data record is less than or equal to the snapshot offset; and

in the index copy, replacing the index offset with the key offset of the subsequent next data record;

wherein one or more of the snapshot offset, the index offset, and the key offsets are absolute offsets within the repository.

3. The method of claim 1, wherein identifying a final data record to be included in the snapshot comprises:

determining an ending time of the snapshot; and

determining a last data record stored in the repository as of the ending time.

4. The method of claim 1, wherein identifying a final data record to be included in the snapshot comprises:

determining a data event associated with an end of the snapshot; and

determining a data record corresponding to the data event.

5. The method of claim 1, further comprising, rolling back the repository of data records by:

determining whether any additional snapshots of the repository are being captured that having corresponding snapshot offsets greater than the snapshot offset; and

when it is determined that no additional snapshots are being captured;

replacing the index with the index copy; and

truncating the repository after the final data record.

6. The method of claim 1, wherein:

the index offsets are absolute offsets; and

the key offsets are relative offsets.

7. The method of claim 1, wherein:

the index offsets are absolute offsets;

the key offsets are relative offsets; and

storing a given key offset derived from a given retrieved index offset comprises converting the absolute offset of the given retrieved index offset to a relative offset from the given key offset.

8. The method of claim 1, further comprising:

determining a combined length of the data record and the key offsets;

storing the combined length;

determining the size of the combined length; and

when the size of the combined length is greater than a threshold, storing one additional byte following the combined length, wherein;

the most significant bit of the one additional byte is set to 1; and

remaining bits of the one additional byte identify the size of the combined length.

9. An apparatus for capturing a snapshot of a repository of variable-length data records,

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 first data record in the repository 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;

identify a final data record to be included in the snapshot;

determine a snapshot offset of the final data record in the repository;

create a copy of the index; and

within the index copy, for each of the multiple keys;

for each value of the key;

determine whether the corresponding index offset is greater than the snapshot offset; and

if the corresponding index offset is greater than the snapshot offset, prune the index offset until the corresponding index is less than or equal to the snapshot offset.

10. The apparatus of claim 9, wherein said pruning comprises:

using the index offset to access the first data record having the key value;

within the first data record, reading a key offset corresponding to the key value, wherein the key offset comprises an offset to a next data record having the key value;

if the key offset is greater than the snapshot offset, repeating said accessing, in the next data record, until the key offset of a subsequent next data record is less than or equal to the snapshot offset; and

in the index copy, replacing the index offset with the key offset of the subsequent next data record;

wherein one or more of the snapshot offset, the index offset, and the key offsets are absolute offsets within the repository.

11. The apparatus of claim 9, wherein identifying a final data record to be included in the snapshot comprises:

determining an ending time of the snapshot; and

determining a last data record stored in the repository as of the ending time.

12. The apparatus of claim 9, wherein identifying a final data record to be included in the snapshot comprises:

determining a data event associated with an end of the snapshot; and

determining a data record corresponding to the data event.

13. The apparatus of claim 9, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to roll back the repository of data records by:

determining whether any additional snapshots of the repository are being captured that having corresponding snapshot offsets greater than the snapshot offset; and

when it is determined that no additional snapshots are being captured;

replacing the index with the index copy; and

truncating the repository after the final data record.

14. The apparatus of claim 9, wherein:

the index offsets are absolute offsets; and

the key offsets are relative offsets.

15. The apparatus of claim 9, wherein:

the index offsets are absolute offsets;

the key offsets are relative offsets; and

storing a given key offset derived from a given retrieved index offset comprises converting the absolute offset of the given retrieved index offset to a relative offset from the given key offset.

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

determine a combined length of the data record and the key offsets;

store the combined length;

determine the size of the combined length; and

when the size of the combined length is greater than a threshold, store one additional byte following the combined length, wherein;

the most significant bit of the one additional byte is set to 1; and

remaining bits of the one additional byte identify the size of the combined length.

17. A system for capturing a snapshot of a repository of variable-length data records, 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 first data record in the repository having the key value; and

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

identify a final data record to be included in the snapshot;

determine a snapshot offset of the final data record in the repository;

create a copy of the index; and

within the index copy, for each of the multiple keys;

for each value of the key;

determine whether the corresponding index offset is greater than the snapshot offset; and

if the corresponding index offset is greater than the snapshot offset, prune the index offset until the corresponding index is less than or equal to the snapshot offset.

18. The system of claim 17, wherein said pruning comprises:

using the index offset to access the first data record having the key value;

within the first data record, reading a key offset corresponding to the key value, wherein the key offset comprises an offset to a next data record having the key value;

if the key offset is greater than the snapshot offset, repeating said accessing, in the next data record, until the key offset of a subsequent next data record is less than or equal to the snapshot offset; and

in the index copy, replacing the index offset with the key offset of the subsequent next data record;

wherein one or more of the snapshot offset, the index offset, and the key offsets are absolute offsets within the repository.

19. The system of claim 17, wherein the non-transitory computer-readable medium of the snapshot module further stores instructions that, when executed, cause the system to roll back the repository of data records by:

determining whether any additional snapshots of the repository are being captured that having corresponding snapshot offsets greater than the snapshot offset; and

when it is determined that no additional snapshots are being captured;

replacing the index with the index copy; and

truncating the repository after the final data record.