Replication across partitioning schemes in a distributed storage system

Patent metadata

Field	Value
Publication number	US-11281394-B2
Application number	US-201916450632-A
Country	US
Kind code	B2
Filing date	Jun 24, 2019
Priority date	Jun 24, 2019
Publication date	Mar 22, 2022
Grant date	Mar 22, 2022

Abstract

A method of replication in a distributed storage system, performed by the distributed storage system is provided. The method includes managing a first index for data or metadata in a first storage system, the first storage system having a first partitioning scheme. The method includes managing a second index for data or metadata in a second storage system, the second storage system having a second partitioning scheme. The method includes replicating the data or metadata from the first storage system to the second storage system, translating an identifier of the data or metadata from the first storage system, and mapping the replicated data or metadata into the second partitioning scheme, via the translating of the identifier of the data or metadata from the first storage system.

First claim

What is claimed is:

1. A method comprising:
managing a first index for data in a first storage system, the first storage system having a first partitioning scheme;
managing a second index for data in a second storage system, the second storage system having a second partitioning scheme differing from the first partitioning scheme;
replicating the data or metadata from the first storage system to the second storage system;
translating an identifier of the data or metadata from the first storage system wherein the translating comprises performing a hash function on one or more portions of the identifier, to form a pointer into one of a plurality of partitions in the second partitioning scheme; and
mapping the replicated data into the second partitioning scheme, via the translating of the identifier of the data or metadata from the first storage system.

2. The method of claim 1 , wherein the first partitioning scheme comprises chunking of objects, to a first data chunk size and the second partitioning scheme comprises chunking of objects, to a second, differing data chunk size.

3. The method of claim 1 , wherein managing the first index in the first storage system comprises assigning ownership of portions of the data or metadata in the first storage system to a first plurality of authorities in the first storage system, to partition the data or metadata of the first storage system according to the first partitioning scheme and record the ownership by the first plurality of authorities in the first index, wherein the managing the second index in the first storage system comprises assigning ownership of portions of the data or metadata in the second storage system to a second plurality of authorities in the second storage system, differing in number from the first plurality of authorities, to partition the data or metadata of the first storage system according to the second partitioning scheme and record the ownership by the second plurality of authorities in the second index, and wherein the mapping via the translation distributes portions of the replicated data or metadata from the first storage system across the second plurality of authorities in the second storage system.

4. The method of claim 2 , wherein:
the identifier is an object identifier and the mapping via the translation maps objects in the first storage system, which are chunked to the first data chunk size, to chunks of the second data chunk size.

5. The method of claim 1 , wherein the translating comprises:
performing an XOR of bits from an authority field of an identifier of the data or metadata from the first storage system with further bits of the identifier to form a pointer to one of a plurality of authorities in the second storage system, based on results of the XOR.

6. The method of claim 1 , wherein:
the first partitioning scheme comprises partitioning the data and metadata of the first storage system into a first plurality of partitions with locality for the data and associated metadata.

7. The method of claim 1 , further comprising:
streaming, in parallel, data and metadata of each of a plurality of partitions in the first storage system according to the first partitioning scheme, wherein the translating and the mapping are performed in parallel across such streams.

8. A tangible, non-transitory, computer-readable media having instructions thereupon which, when executed by a processor, cause the processor to perform a method comprising:
replicating data or metadata from a first storage system having a first partitioning scheme to a second storage system having a second, differing partitioning scheme;
performing a transformation on an identifier of the data or metadata from the first storage system wherein performing the transformation comprises performing a hash function on one or more portions of the identifier, to form a pointer into one of a plurality of partitions in the second partitioning scheme; and
using a result of the transformation on the identifier of the data or metadata from the first storage system to map the data or metadata from the first storage system into the second partitioning scheme, in the replicating to the second storage system.

9. The computer-readable media of claim 8 , wherein using the result of the transformation to map into the second partitioning scheme comprises using the pointer to map the data or metadata from the first storage system into the one of the plurality of partitions in the second storage system in accordance with the second partitioning scheme.

10. The computer-readable media of claim 8 , wherein:
the first storage system has a first plurality of authorities each owning a portion of the data or metadata of the first storage system in accordance with the first partitioning scheme and wherein the second storage system has a second plurality of authorities, differing in number from the first plurality of authorities and each owning a portion of the data or metadata of the second storage system in accordance with the second partitioning scheme.

11. The computer-readable media of claim 8 , wherein:
the first partitioning scheme comprises chunking of objects, to a first data chunk size and wherein the second partitioning scheme comprises chunking of objects, to a second, differing data chunk size.

12. The computer-readable media of claim 8 , wherein the performing the transformation comprises:
performing an XOR of bits from an authority field of an identifier of the data or metadata from the first storage system with further bits of the identifier, the authority field identifying one of a first plurality of authorities in the first storage system and forming a pointer to one of a second plurality of authorities in the second storage system, based on results of the XOR, the second plurality of authorities differing in number from the first plurality of authorities.

13. The computer-readable media of claim 8 , wherein the transformation preserves locality for data and associated metadata, from a first plurality of partitions in the first storage system according to the first partitioning scheme, mapping into a second plurality of partitions in the second storage system according to the second partitioning scheme.

14. The computer-readable media of claim 8 , wherein the method further comprises:
forming a plurality of streams in parallel, one stream per each of a plurality of partitions in the first storage system according to the first partitioning scheme, wherein the performing the transformation and the using the result of the transformation to map are performed in parallel across the plurality of streams.

15. A storage system, comprising:
storage memory; and
one or more processors, configurable to:
replicate data or metadata having a first partitioning scheme implemented to store the data or metadata according to a first plurality of partitions in the storage memory, to a second storage system having a second, differing partitioning scheme comprising a second plurality of partitions differing in number from the first plurality of partitions;
perform a transformation on an identifier of the data or metadata from the storage system, wherein performing the transformation comprises performing a hash function on one or more portions of the identifier, to form a pointer into one of a plurality of partitions in the second partitioning scheme; and
map the data or metadata from the storage system into the second partitioning scheme, using a result of the transformation, to replicate the data or metadata to the second storage system.

16. The storage system of claim 15 ,

Assignees

• Pure Storage Inc

Inventors

• Hankins Richard A
• Ostrovsky Igor
• Colgrove John
• Sandvig Cary A
• Karr Ronald
• Yip Victor
• Miao Zong
• Jain Abhishek

Classifications

• G06F2212/1016

  Performance improvement · CPC title

• G06F2212/7205

  Cleaning, compaction, garbage collection, erase control · CPC title

• G06F3/065 Primary

  Replication mechanisms · CPC title

• G06F12/10

  Address translation · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title