Facilitating distributed deletes in a replicated storage system

Patent metadata

Field	Value
Publication number	US-2016140201-A1
Application number	US-201414540628-A
Country	US
Kind code	A1
Filing date	Nov 13, 2014
Priority date	Nov 13, 2014
Publication date	May 19, 2016
Grant date	—

Abstract

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 d , if a copy of the first data item exists in the local zone, the system computes a maximum last update time t mlu =t d −t min , wherein t min is a minimum lifetime for a data item. Next, the system determines, from a local index, a time t lu that the first data item was last updated. If t lu <t mlu , 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 mlu , wherein the delete operation is performed in another zone if the other zone determines that the first data item was last updated before t mlu.

First claim

What is claimed is:

1 . A computer-implemented method, comprising:
operating a data storage system including multiple zones, wherein each zone comprises a separate geographic storage location, and wherein data items are replicated across multiple zones for fault tolerance purposes; and wherein operating the data storage system involves performing a delete operation to delete a first data item by:
receiving the delete operation at a time t d at a local zone in the data storage system; and
if a copy of the first data item exists in the local zone,
computing a maximum last update time for the delete operation t mlu =t d −t min , wherein t min is a minimum lifetime for a data item,
determining, from a local index in the local zone, a time t lu that the first data item was last updated,
deleting the copy of the first data item in the local zone if t lu <t min , and
asynchronously propagating the delete operation to other zones in the data storage system along with t mlu , wherein the delete operation is performed in another zone if the other zone determines that the first data item was last updated before t mlu.

2 . The computer-implemented method of claim 1 , wherein the method further comprises:
receiving an asynchronous delete operation at the local zone from a remote zone, wherein the asynchronous delete operation is directed to a second data item and includes a time t mlu ; and if a copy of the second data item exists in the local zone,
determining, from a local index maintained in the local zone, a time t lu that the second data item was last updated, and
deleting the copy of the second data item in the local zone if t lu <t mlu .

3 . The computer-implemented method of claim 1 , wherein the method further comprises:
receiving a put operation at the local zone, wherein the put operation is directed to a third data item; applying the put operation to either update or instantiate a copy of the third data item in the local zone; updating a last update time t lu for the third data item in a local index maintained at the local zone to specify a time that the put operation was applied to the third data item; and asynchronously propagating the put operation to other zones in the data storage system along with t lu .

4 . The computer-implemented method of claim 1 , wherein the method further comprises:
receiving an asynchronous put operation at the local zone from a remote zone, wherein the asynchronous put operation is directed to a fourth data item and includes a time t lu indicating when the fourth data item was last updated; applying the asynchronous put operation to update or instantiate a copy of the fourth data item in the local zone; and updating an entry for the fourth data item in a local index maintained at the local zone to indicate that the fourth data item was last updated at the later of: the time t lu , and the time the fourth data item was actually updated or instantiated in the local zone.

5 . The computer-implemented method of claim 1 , wherein the local index maintained at the local zone maps identifiers for data items to corresponding locations for the data items in the local zone.

6 . The computer-implemented method of claim 1 ,
wherein asynchronously propagating the delete operation to other zones involves enqueuing the delete operation in a first-in, first-out (FIFO) buffer maintained in the local zone; wherein the FIFO buffer contains entries for asynchronous delete operations and asynchronous put operations; and wherein the method further comprises propagating operations specified by the entries in the FIFO buffer to other zones in the data storage system.

7 . The computer-implemented method of claim 1 , wherein the data items that are replicated across multiple zones comprise extents, wherein each extent stores multiple data blocks.

8 . A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:
operating a data storage system including multiple zones, wherein each zone comprises a separate geographic storage location, and wherein data items are replicated across multiple zones for fault tolerance purposes; and wherein operating the data storage system involves performing a delete operation to delete a first data item by:
receiving the delete operation at a time t d at a local zone in the data storage system; and
if a copy of the first data item exists in the local zone,
computing a maximum last update time for the delete operation t mlu =t d −t min , wherein t min is a minimum lifetime for a data item,
determining, from a local index in the local zone, a time t lu that the first data item was last updated,
deleting the copy of the first data item in the local zone if t lu <t mlu , and
asynchronously propagating the delete operation to other zones in the data storage system along with t mlu , wherein the delete operation is performed in another zone if the other zone determines that the first data item was last updated before t mlu.

9 . The non-transitory computer-readable storage medium of claim 8 , wherein the method further comprises:
receiving an asynchronous delete operation at the local zone from a remote zone, wherein the asynchronous delete operation is directed to a second data item and includes a time t mlu ; and if a copy of the second data item exists in the local zone,
determining, from a local index maintained in the local zone, a time t lu that the second data item was last updated, and
deleting the copy of the second data item in the local zone if t lu <t mlu .

10 . The non-transitory computer-readable storage medium of claim 8 , wherein the method further comprises:
receiving a put operation at the local zone, wherein the put operation is directed to a third data item; applying the put operation to either update or instantiate a copy of the third data item in the local zone; updating a last update time t lu for the third data item in a local index maintained at the local zone to specify a time that the put operation was applied to the third data item; and asynchronously propagating the put operation to other zones in the data storage system along with t lu .

11 . The non-transitory computer-readable storage medium of claim 8 , wherein the method further comprises:
receiving an asynchronous put operation at the local zone from a remote zone, wherein the asynchronous put operation is directed to a fourth data item and includes a time t lu indicating when the fourth data item was last updated; applying the asynchronous put operation to either update or instantiate a copy of the fourth data item in the local zone; and updating an entry for the fourth data item in a local index maintained at the local zone to indicate that the fourth data item was last updated at the later of: the time t lu , and the time the fourth data item was actually updated or instantiated in the local zone.

12 . The non-transitory computer-readable storage medium of claim 8 , wherein the local index maintained at the local zone maps identifiers for data items to corresponding locations for the data items in the local zone.

13 . The non-transitory computer-readable storage medium of claim 8 ,
wherein asynchronously propagating the delete operation to other zones involves enqueuing the delete operation in a first-in, first-out (FIFO) buffer maintained in the local zone; wherein the FIFO buffer contains entries for asynchronous delete operations and asynchronous put operations; and wherein the method further comprises propagating operation

Assignees

• Dropbox Inc

Inventors

• Cowling James
• Mallipeddi Venkata Harish

Classifications

• G06F11/2094 Primary

  Redundant storage or storage space (G06F11/2056 takes precedence) · CPC title

• G06F17/30578 Primary

  Physics · mapped topic

• G06F16/273 Primary

  Asynchronous replication or reconciliation · CPC title

• G06F11/14

  Error detection or correction of the data by redundancy in operations (error detection or correction of the data by redundancy in hardware G06F11/16) · CPC title

• G06F16/162

  Delete operations (erasing in storage systems G06F3/0652) · CPC title