Dropbox, Inc.

James Cowling

James Turner

Venkata Harish Mallipeddi, Iv

Nipunn Koorapati

Sujay Jayakar

Braden Walker

David Wetterau

Kevin P Modzelewski

Olga Kechina

Oleksandr Senyuk

William Ehlhardt

Gevorg Karapetyan

Stas Ilinskiy

Jonathan Lee

One variation of a system for implementing a key-value data store includes one or more processors, storage media and instructions stored in the storage media which, when executed by the system cause the system to: receive a request store a particular key-value item; request a first networked distributed data storage system to store the particular key-value item; based on a determination that a set of one or more offload criteria is satisfied: retrieve a first set of key-value items from the first networked distributed data storage system, and request a second networked distributed data storage system to store the first set of key-value items in a first set of one or more data objects. The first networked distributed data storage system can have a lower data write latency and a higher data storage cost than the second networked distributed data storage system.

System and methods for implementing a key-value data store

A system can serialize moves and mounts across namespaces based on lamport clocks. In some examples, the system obtains a request to move a content item from a source namespace to a destination namespace. The system processes an incoming move at the destination and an outgoing move at the source. The system processes for the content item a delete at the source and an add at the destination. The system assigns a first clock to the incoming move and a second clock to the outgoing move, the first clock being lower than the second clock. The system assigns a third clock to the delete and a fourth clock to the add, the third clock being higher than the second clock and lower than the fourth clock. The system serializes the incoming and outgoing moves, the delete and the add based on the first, second, third and fourth clocks.

Atomic moves with lamport clocks in a content management system

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.

Reconstructing in-memory indices in a distributed data storage system

A distributed computing system that executes a set of long-lived jobs is described. During operation, each worker process performs the following operations. First, the worker process identifies a set of jobs to be executed and a set of worker processes that can execute the set of jobs. Next, the worker process sorts the set of worker processes based on unique identifiers for the worker processes. Then, the worker process assigns jobs to each worker process in the set of worker processes, wherein approximately the same number of jobs is assigned to each worker process, and jobs are assigned to the worker processes in sorted order. While assigning jobs, the worker process uses an identifier for each worker process to seed a pseudorandom number generator, and then uses the pseudorandom number generator to select jobs for each worker process to execute.

Distributed technique for allocating long-lived jobs among worker processes

A data storage system includes multiple storage zones that store replicated copies of data items. Upon receiving a delete operation at a particular time to delete a data item, the system computes a maximum last update time based on the particular time and a minimum data item lifetime. Based on determining that a copy of the data item is stored in the data storage zone, the system then determines a last update time of the data item. In addition, based on determining that the last update time is less than the first maximum last update time, the system deletes the copy of the data item from the data storage zone.

Managing distributed deletes in a replicated storage system

An append-only data storage system is described that stores sets of data blocks in extents that are located in storage devices. During operation of the system, upon receiving a request to copy an extent from a source storage device to a destination storage device, the system creates a scratch extent on the destination storage device, and associates the scratch extent with a private identifier, whereby the scratch extent can only be accessed through the private identifier. The system uses the private identifier to perform a copying operation that copies the extent from the source storage device to the scratch extent on the destination storage device. After the copying operation is complete and the scratch extent is closed, the system associates the scratch extent with a public identifier, whereby the copy of the extent on the destination storage device becomes publically accessible to other entities in the data storage system.

Using scratch extents to facilitate copying operations in an append-only storage system

A system that stores sets of data blocks in extents located in storage devices is described. During operation, a receiving device receives, through an RPC framework, a first call asking to transfer an extent from a sending device to the receiving device. In response, the receiving device opens a port for a data connection that operates outside the RPC framework. The receiving device makes a second call, to the sending device through the RPC framework, asking to stream the extent to the port. The receiving device subsequently receives the extent from the sending device through the port and computes a checksum for the extent. The receiving device also receives a return from the second call, including a checksum for the extent computed by the sending device. If the computed checksum matches the received checksum, the receiving device returns the first call to indicate the transfer operation completed successfully.

Using an RPC framework to facilitate out-of-band data transfers

The disclosed embodiments relate to the design of an append-only data storage system that stores sets of data blocks in extents that are located in storage devices in the system. During operation of the system, when an extent becomes full, the system changing the extent from an open state, wherein data can be appended to the extent, to a closed state, wherein data cannot be appended to the extent. Changing the extent from the open state to the closed state includes performing the following operations at one or more storage devices that contain copies of the extent: constructing an index to facilitate accessing data blocks in a copy of the extent contained in the storage device; and appending the index to the copy of the extent in non-volatile storage in the storage device.

Constructing an index to facilitate accessing a closed extent in an append-only storage system

The disclosed embodiments relate to the design of an append-only data storage system that stores sets of data blocks in extents that are located in storage devices in the system. During operation of the system, when an extent is in an open state, the system allows data blocks to be appended to the extent, and disallows operations to be performed on the extent that are incompatible with data being concurrently appended to the extent. When the extent becomes full, the system changes the extent from the open state to a closed state. Then, while the extent is in the closed state, the system disallows data blocks to be appended to the extent, and allows operations to be performed on the extent that are incompatible with data being concurrently appended to the extent.

Append-only storage system supporting open and closed extents

A append-only data storage system that stores sets of data blocks in extents that are located in storage devices. When an extent becomes full, the system changes the extent from an open state, wherein data can be appended to the extent, to a closed state, wherein data cannot be appended to the extent. This change involves performing a synchronization operation by: obtaining a list of data blocks in the extent from each storage device that has a copy of the extent; forming a union of the lists; looking up data blocks from the union in a database that maps data blocks to storage devices and extents to determine which data blocks belong in the extent; and if a copy of the extent is missing data blocks that belong in the extent, performing a remedial action before changing the extent from the open state to the closed state.

Synchronizing copies of an extent in an append-only storage system

A data storage system stores sets of data blocks in extents located on storage devices. During operation, the system performs an erasure-coding operation by obtaining a set of source extents, wherein each source extent is stored on a different machine in the data storage system. The system also selects a set of destination machines for storing destination extents, wherein each destination extent is stored on a different destination machine. Next, the system performs the erasure-coding operation by retrieving data from the set of source extents, performing the erasure-coding operation on the retrieved data to produce erasure-coded data, and then writing the erasure-coded data to the set of destination extents on the set of destination machines. Finally, after the erasure-coding operation is complete, the system commits results of the erasure-coding operation to enable the set of destination extents to be accessed in place of the set of source extents.

Erasure-coding extents in an append-only storage system

A data storage system includes multiple zones that comprise separate geographic storage locations and store replicated copies of data items. Upon receiving a delete operation at a local zone at a time t, if a copy of the first data item exists in the local zone, the system computes a maximum last update time t=t&#x2212;t, wherein tis a minimum lifetime for a data item. Next, the system determines, from a local index, a time tthat the first data item was last updated. If t&#x3c;t, the system deletes the copy of the first data item in the local zone. The system also asynchronously propagates the delete operation to other zones in the data storage system along with t, wherein the delete operation is performed in another zone if the other zone determines that the first data item was last updated before t.

Facilitating distributed deletes in a replicated storage system

The disclosed embodiments relate to a system that uses colocation hints to facilitate storing data blocks in a distributed data storage system, which includes a plurality of data centers. During operation, the system receives a write request from a client to write a data block to the distributed data storage system, wherein the write request includes a colocation hint that identifies a colocation group associated with the data block. In response to the write request, the system uses the colocation hint to identify one or more data centers associated with the colocation group. Next, the system writes copies of the data block to the one or more identified data centers. In this way, the system situates copies of data blocks associated with the colocation group in the same data centers when possible.

Using colocation hints to facilitate accessing a distributed data storage system

The disclosed embodiments relate to a data storage system that facilitates efficiently recovering from storage device failures. Upon receiving a request to retrieve a data block from the data storage system, the system uses a hash that identifies the data block to look up a bucket and an associated cell containing the data block. Note that the bucket aggregates a large number of data blocks and is located in the associated cell that comprises a set of object storage devices (OSDs). Within the cell, the system uses the bucket to look up an OSD that contains the bucket in a local bucket database (BDB) for the cell. Within the OSD, the system uses the bucket and the hash to look up an offset and a length for the data block in a write-ahead log that stores data blocks for the bucket. Finally, the system returns the data block from the determined offset.

Growing community of inventors

San Francisco, CA, United States of America

James Cowling