Reconstructing in-memory indices in a distributed data storage system

Patent metadata

Field	Value
Publication number	US-10452271-B2
Application number	US-201715601598-A
Country	US
Kind code	B2
Filing date	May 22, 2017
Priority date	Sep 25, 2014
Publication date	Oct 22, 2019
Grant date	Oct 22, 2019

Abstract

Reconstructing in-memory data block indices in a distributed data storage system where data blocks are stored in extents and the extents are replicated across storage devices. In one aspect, based on a reboot of a storage device and a copy of an extent stored in the storage device being in an open state, appends for data blocks in the copy of the extent stored in the storage device are replayed to reconstruct an in-memory data block index for the copy of the extent. In another aspect, based on a reboot of a storage device and a copy of an extent being in a closed state, a data block index for the copy of the extent is retrieved from non-volatile storage of the storage device and the retrieved data block index stored in memory at the storage device.

First claim

What is claimed is:

1. A method performed by a computing system comprising one or more processors and memory, the method comprising:
storing data blocks in extents, the extents replicated across a plurality of storage devices;
wherein a particular extent is in either an open state or a closed state;
writing a header to a copy of the particular extent, the header written indicating that the particular extent is in the open state, the copy of the particular extent stored at a particular storage device of the plurality of storage devices;
wherein, when the particular extent is in the open state, data blocks are appended to the copy of the particular extent;
based on a reboot of the particular storage device, determining that the particular extent is in the open state, and based on the determining that the particular extent is in the open state, replaying appends for the data blocks appended to the copy of the particular extent to reconstruct, at the particular storage device, an in-memory data block index for the copy of the particular extent; and
wherein the determining the particular extent is in the open state is based on reading the header of the copy of the particular extent.

2. The method of claim 1 , wherein replaying appends for the data blocks in the copy of the particular extent comprises, for each data block in the copy of the particular extent, repeating all operations involved in appending the data block to the particular extent.

3. A method performed by a computing system comprising one or more processors and memory, the method comprising:
storing data blocks in extents, the extents replicated across a plurality of storage devices;
wherein a particular extent is in either an open state or a closed state;
writing a first header to a copy of the particular extent, the copy of the particular extent stored at a particular storage device of the plurality of storage devices, the first header written indicating that the particular extent is in the open state;
wherein, when the particular extent is in the open state, data blocks are appended to the copy of the particular extent;
writing a data block index to the copy of the particular extent;
after the writing the data block index to the copy of the particular extent, writing a second header to the copy of the particular extent, the second header written indicating that the particular extent is in the closed state;
wherein, when the particular extent is in the closed state, data blocks are no longer appended to the copy of the particular extent; and
based on a reboot of the particular storage device, determining that the particular extent is in the closed state, and based on the determining that the particular extent is in the closed state, retrieving the data block index from the copy of the particular extent from non-volatile storage in the particular storage device, and storing the retrieved data block index in memory at the particular storage device; and
wherein the determining the particular extent is in the closed state is based on reading the second header of the copy of the particular extent.

4. The method of claim 3 , further comprising reading a key list associated with the retrieved data block index to obtain statistics about the data blocks stored in the particular extent.

5. The method of claim 3 , further comprising:
loading a deleted list associated with the retrieved data block index into a bit map; and
determining an end-of-file for the particular extent.

6. A non-transitory computer-readable storage medium storing instructions configured for:
storing data blocks in extents, the extents replicated across a plurality of storage devices;
wherein a particular extent is in either an open state or a closed state;
writing a header to a copy of the particular extent, the header written indicating that the particular extent is in the open state, the copy of the particular extent stored at a particular storage device of the plurality of storage devices;
wherein, when the particular extent is in the open state, data blocks are appended to the copy of the particular extent;
based on a reboot of the particular storage device, determining that the particular extent is in the open state, and based on the determining that the particular extent is in the open state, replaying appends for the data blocks appended to the copy of the particular extent to reconstruct, at the particular storage device, an in-memory data block index for the copy of the particular extent; and
wherein the determining the particular extent is in the open state is based on reading the header of the copy of the particular extent.

7. The non-transitory computer-readable storage medium of claim 6 , wherein replaying appends for the data blocks in the copy of the particular extent comprises, for each data block in the copy of the particular extent, repeating all operations involved in appending the data block to the particular extent.

8. A non-transitory computer-readable storage medium storing instructions configured for:
storing data blocks in extents, the extents replicated across a plurality of storage devices;
wherein a particular extent is in either an open state or a closed state;
writing a first header to a copy of the particular extent, the copy of the particular extent stored at a particular storage device of the plurality of storage devices, the first header written indicating that the particular extent is in the open state;
wherein, when the particular extent is in the open state, data blocks are appended to the copy of the particular extent;
writing a data block index to the copy of the particular extent;
after the writing the data block index to the copy of the particular extent, writing a second header to the copy of the particular extent, the second header written indicating that the particular extent is in the closed state;
wherein, when the particular extent is in the closed state, data blocks are no longer appended to the copy of the particular extent; and
based on a reboot of the particular storage device, determining that the particular extent is in the closed state, and based on the determining that the particular extent is in the closed state, retrieving the data block index from the copy of the particular extent from non-volatile storage in the particular storage device, and storing the retrieved data block index in memory at the particular storage device; and
wherein the determining the particular extent is in the closed state is based on reading the second header of the copy of the particular extent.

9. The non-transitory computer-readable storage medium of claim 8 , the instructions further configured for reading a key list associated with the retrieved data block index to obtain statistics about the data blocks stored in the particular extent.

10. The non-transitory computer-readable storage medium of claim 8 , the instructions further configured for:
loading a deleted list associated with the retrieved data block index into a bit map; and determining an end-of-file for the particular extent.

11. A computing system, comprising:
one or more processors;
one or more programs configured for execution by the one or more processors, the one or more programs comprising instructions configured for:
storing data blocks in extents, the extents replicated across a plurality of storage devices;
wherein a particular extent is in either an open state or a closed state;
writing a header to a copy of the particular extent, the header written indicating that the particular extent is in the open state, the copy of the particular extent stored at a particular storage device of the plurality of storage devices;
wherein,

Assignees

• Dropbox Inc

Inventors

• Cowling James
• Turner James

Classifications

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F16/2365

  Ensuring data consistency and integrity · CPC title

• G06F3/0607 Primary

  by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device · CPC title

• G06F9/4401

  Bootstrapping (security arrangements therefor G06F21/57) · CPC title

• G06F3/0688

  Non-volatile semiconductor memory arrays · CPC title