Granted Patent B2

US 9,405,643 · App. 14/091,119 · Granted Aug 2, 2016

Abstract

Claims (74)

1. A computer-implemented method for operating a data storage system, comprising:

receiving a request to retrieve a data block from the data storage system, wherein the request includes a hash that functions as a global identifier for the data block;

using the hash to look up a bucket and an associated cell that contains the data block, wherein the bucket aggregates a large number of data blocks, wherein the bucket is located in the associated cell that comprises a set of object storage devices (OSDs), and wherein the lookup is performed in a hash database (HDB) for the data storage system;

within the cell, using the bucket to look up an OSD that contains the bucket, wherein the lookup is performed in a local bucket database (BDB) for the cell;

within the OSD, using the bucket and the hash to determine an offset and a length for the data block in a write-ahead log that stores data blocks for the bucket; and

returning the data block from the determined offset in the write-ahead log;

wherein an OSD comprises a server that comprises one or more storage devices.

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

receiving a request to write a data block to the data storage system;

using the data block to compute a hash that functions as a global identifier for the data block;

selecting a writeable bucket and an associated cell for the data block;

within the associated cell, using the selected bucket to look up an OSD for the data block, wherein the lookup is performed in a local BDB for the selected cell;

within the OSD, appending the data block to a write-ahead log that stores data blocks for the bucket; and

updating the HDB to include an entry that maps the hash to the selected bucket and associated cell.

3. The computer-implemented method of claim 1 , wherein upon detecting a failure associated with a bucket in a cell, the method further comprises:

marking the bucket as non-writable;

performing a fast block-copy of the bucket to a new OSD in the cell; and

updating the BDB for the cell to indicate that the bucket is associated with the new OSD.

4. The computer-implemented method of claim 1 , wherein the HDB comprises a sharded database that stores hash-to-bucket mappings for multiple cells.

5. The computer-implemented method of claim 1 , wherein the BDB is stored in random access memory to facilitate performing bucket-to-OSD lookups without having to access a storage device.

6. The computer-implemented method of claim 1 , wherein determining the offset for the data block in a write-ahead log comprises performing an in-memory lookup in the OSD without accessing a storage device.

7. The computer-implemented method of claim 1 ,

wherein each OSD is associated with a generation number that is incremented after a failure-recovery operation completes; and

wherein the generation number is used to prevent an OSD associated with an old generation number, and therefore possibly containing invalid data, from servicing read operations.

8. The computer-implemented method of claim 1 , wherein a storage device corresponds to a disk drive.

9. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for operating a data storage system, the method comprising:

receiving a request to retrieve a data block from the data storage system, wherein the request includes a hash that functions as a global identifier for the data block;

using the hash to look up a bucket and an associated cell that contains the data block, wherein the bucket aggregates a large number of data blocks, wherein the bucket is located in the associated cell that comprises a set of object storage devices (OSDs), and wherein the lookup is performed in a hash database (HDB) for the data storage system;

within the cell, using the bucket to look up an OSD that contains the bucket, wherein the lookup is performed in a local bucket database (BDB) for the cell;

within the OSD, using the bucket and the hash to determine an offset and a length for the data block in a write-ahead log that stores data blocks for the bucket; and

returning the data block from the determined offset in the write-ahead log;

wherein an OSD comprises a server that comprises one or more storage devices.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the method further comprises:

receiving a request to write a data block to the data storage system;

using the data block to compute a hash that functions as a global identifier for the data block;

selecting a writeable bucket and an associated cell for the data block;

within the associated cell, using the selected bucket to look up an OSD for the data block, wherein the lookup is performed in a local BDB for the selected cell;

within the OSD, appending the data block to a write-ahead log that stores data blocks for the bucket; and

updating the HDB to include an entry that maps the hash to the selected bucket and associated cell.

11. The non-transitory computer-readable storage medium of claim 9 , wherein upon detecting a failure associated with a bucket in a cell, the method further comprises:

marking the bucket as non-writable;

performing a fast block-copy of the bucket to a new OSD in the cell; and

updating the BDB for the cell to indicate that the bucket is associated with the new OSD.

12. The non-transitory computer-readable storage medium of claim 9 , wherein the HDB comprises a sharded database that stores hash-to-bucket mappings for multiple cells.

13. The non-transitory computer-readable storage medium of claim 9 , wherein the BDB is stored in random access memory to facilitate performing bucket-to-OSD lookups without having to access a storage device.

14. The non-transitory computer-readable storage medium of claim 9 , wherein determining the offset for the data block in a write-ahead log comprises performing an in-memory lookup in the OSD without accessing a storage device.

15. The non-transitory computer-readable storage medium of claim 9 ,

wherein each OSD is associated with a generation number that is incremented after a failure-recovery operation completes; and

wherein the generation number is used to prevent an OSD associated with an old generation number, and therefore possibly containing invalid data, from servicing read operations.

16. A data storage system, comprising:

one or more zones, wherein each zone is associated with a data center;

wherein each zone is divided into a plurality of cells;

wherein each cell comprises a plurality of object storage devices (OSDs) for storing blocks of data, and a master for managing the OSDs and wherein the master comprises one or more processors and memory; and

wherein during operation, the data storage system is configured to,

receive a request to retrieve a data block from the data storage system, wherein the request includes a hash that functions as a global identifier for the data block,

use the hash to look up a bucket and an associated cell that contains the data block, wherein the bucket aggregates a large number of data blocks and is located in the associated cell, and wherein the lookup is performed in a hash database (HDB) for the data storage system;

within the cell, use the bucket to look up an OSD that contains the bucket, wherein the lookup is performed in a local bucket database (BDB) for the cell;

within the OSD, use the bucket and the hash to determine an offset and a length for the data block in a write-ahead log that stores data blocks for the bucket; and

return the data block from the determined offset in the write-ahead log;

wherein an OSD comprises a server that comprises one or more storage devices.

17. The data storage system of claim 16 , wherein during operation, the data storage system is additionally configured to:

receive a request to write a data block to the data storage system;

use the data block to compute a hash that functions as a global identifier for the data block;

select a writeable bucket and an associated cell for the data block;

within the associated cell, use the selected bucket to look up an OSD for the data block, wherein the lookup is performed in a local BDB for the selected cell;

within the OSD, append the data block to a write-ahead log that stores data blocks for the bucket; and

update the HDB to include an entry that maps the hash to the selected bucket and associated cell.

18. The data storage system of claim 16 , wherein upon detecting a failure associated with a bucket in a cell, the data storage system is configured to:

mark the bucket as non-writable;

perform a fast block-copy of the bucket to a new OSD in the cell; and

update the BDB for the cell to indicate that the bucket is associated with the new OSD.

19. The data storage system of claim 16 , wherein the HDB comprises a sharded database that stores hash-to-bucket mappings for multiple cells.

20. The data storage system of claim 16 , wherein the BDB is stored in random access memory to facilitate performing bucket-to-OSD lookups without having to access a storage device.

21. The data storage system of claim 16 , wherein while determining the offset for the data block in a write-ahead log, the OSD is configured to perform an in-memory lookup without accessing a storage device.

Assignments (8)