Storage system indexed using persistent metadata structures

• US 10,656,857 B2
• Filed: 06/07/2018
• Issued: 05/19/2020
• Est. Priority Date: 06/07/2018
• Status: Active Grant

• Current Assignee: VAST Data Ltd.
• Original Assignee: VAST Data Ltd.
• Inventors: Hallak, Renen, Levy, Asaf, Goren, Avi, Vaknin, Yogev, Zdornov, Vladimir
• Primary Examiner(s): Peugh, Brian R
• Application Number:
  US16/002,804
• Publication Number:
  US 20190377491A1
• Time in Patent Office: 712 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 2201/835 Timestamp
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06N 7/08 using chaos models or non-linear system models

Abstract

A storage system. The storage system includes: a data store including a plurality of data blocks; and an element store, the element store including a plurality of element trees, wherein each element tree includes a plurality of metadata blocks containing pointers, wherein each pointer points to one of the plurality of metadata blocks or to one of the data blocks, wherein data of the plurality of data blocks is read by navigating at least one of the plurality of element trees.

Claims

1. A storage system, comprising:

a data store including a plurality of data blocks; and

an element store, the element store including a plurality of element trees, wherein each element tree includes a plurality of metadata blocks containing pointers, wherein each pointer points to one of the plurality of metadata blocks or to one of the data blocks, wherein data of the plurality of data blocks is read by navigating at least one of the plurality of element trees, wherein the element store has a bottom level including a plurality of content blocks, wherein each content block is one of the metadata blocks including a pointer to one of the data blocks.

2. The storage system of claim 1, wherein the bottom level of the element store is shared among the plurality of element trees.

3. The storage system of claim 1, wherein the plurality of metadata blocks is allocated from a shared pool of metadata blocks.

4. The storage system of claim 1, wherein each element tree represents an element that is assigned a handle, wherein the plurality of metadata blocks include, for each element, a metadata block including the handle for the element.

5. The storage system of claim 1, further comprising:

a plurality of storage nodes, wherein the data blocks and the metadata blocks are stored in the plurality of storage nodes, wherein the element store has a top level including a global hash table, wherein the global hash table is distributed among the plurality of storage nodes.

6. The storage system of claim 1, wherein the plurality of metadata blocks further includes a plurality of hash table blocks, a plurality of range blocks, and a plurality of bitmap blocks, each hash table block pointing to at least one of the plurality of range blocks, each range block pointing to at least one set of bitmap blocks of the plurality of bitmap blocks, each bitmap block pointing to one of the plurality of content blocks, each content block pointing to one of the plurality of data blocks.

7. The storage system of claim 6, wherein the element store has a top level including a global hash table, wherein the global hash table includes a plurality of buckets, wherein each bucket is a composite block including contents of at least two of the plurality of metadata blocks, wherein data in each composite block is read using a single input/output operation.

8. The storage system of claim 7, wherein each composite block includes at least one of the plurality of hash table blocks, at least one of the plurality of range blocks, and at least one of the at least one set of bitmap blocks.

9. The storage system of claim 8, wherein reading each composite block results in identifying one of the plurality of content blocks.

10. The storage system of claim 6, further comprising:

at least one first storage including the plurality of hash table blocks, the plurality of range blocks, and the plurality of bitmap blocks; and

at least one second storage including the plurality of content blocks.

11. The storage system of claim 10, wherein each first storage is XPoint storage, wherein each second storage is Flash storage.

12. The storage system of claim 6, wherein each bitmap block further includes a timestamp generated based on a global counter for the storage system, wherein incrementing the global counter includes creating a snapline for the element store, wherein the snaplines are used to create snapshots of the storage system at different points in time.