Log-structured file system

Patent metadata

Field	Value
Publication number	US-10452608-B2
Application number	US-201615295092-A
Country	US
Kind code	B2
Filing date	Oct 17, 2016
Priority date	Oct 17, 2016
Publication date	Oct 22, 2019
Grant date	Oct 22, 2019

Abstract

Systems, computer-readable mediums, and methods are configured to receive a first request to write a first data block to a solid state storage device. A second request is received to associate the first data block with a first snapshot identifier (ID). The first data block is stored on the solid state storage device in response to the first request. The first data block is stored on a first segment of a plurality of physical segments of memory on the solid state storage device. A first data pointer that corresponds to the first snapshot ID is generated in response to the second request. The first data pointer points to the first data block stored on the solid state storage device.

First claim

What is claimed is:

1. A system comprising:
a processor coupled to a memory; and
a solid state storage device (SSD) coupled to the processor, the memory having instructions stored thereon to cause the system to,
generate a first data pointer as metadata having a first physical location index, a first checksum, and a first bitset, based on a first request to write a first data block to the SSD, wherein the first checksum corresponds to the first data block;
set a bit in the first bitset that maps to a first snapshot identifier included within a vector of snapshot identifiers, wherein the first snapshot identifier is associated with the first data block;
store the first data pointer sequentially with the first data block in a first segment of a plurality of physical segments of the SSD, wherein the first physical location index is unique to the first segment; and
store the vector of snapshot identifiers in a checkpoint marker on the SSD during a checkpoint of the segment.

2. The system of claim 1 , wherein the memory includes further instructions stored thereon to cause the system to:
build a first hash tree corresponding to a first dataset from the first checksum and additional checksums included in additional data pointers in the plurality of physical segments; and
compare the first hash tree to a second hash tree to determine differences between the first dataset and a second dataset.

3. The system of claim 1 , wherein the memory includes further instructions stored thereon to cause the system to:
generate a second data pointer having a second physical location index, a second checksum, and a second bitset, based on a subsequent request to write a second data block to the SSD, wherein the second checksum corresponds to the second data block;
set a bit in the second bitset that maps a second snapshot identifier included within a vector of snapshot identifiers, wherein the first snapshot identifier is associated with the second data block; and
store the second data pointer sequentially with the second data block in a second segment of the plurality of physical segments of the SSD, wherein the second physical location index is unique to the second segment.

4. The system of claim 3 , wherein the SSD does not include a hierarchy of pointers to data blocks on the SSD.

5. The system of claim 1 , wherein the memory includes further instructions stored thereon to cause the system to generate the first checksum from the first data block.

6. The system of claim 1 , wherein the memory includes further instructions stored thereon to cause the system to set another bit in the first bitset to map the first data block with a second snapshot identifier in included in the vector of snapshots.

7. The system of claim 1 , wherein the memory includes further instructions stored thereon to cause the system to update the first bitset to associate the first data block with a second snapshot identifier included in the vector of snapshot identifiers instead of the first snapshot identifier.

8. The system of claim 1 , wherein the memory includes further instructions stored thereon to cause the system to maintain counters of snapshot identifiers across data block pointers.

9. The system of claim 2 , wherein the first dataset corresponds to a first snapshot and the second dataset corresponds to a second snapshot deduplicated from the first snapshot.

10. A system comprising:
a processor coupled to a solid state storage device (SSD); and
a non-transitory computer-readable medium having instructions for a sequential filesystem stored thereon, the instructions executable by the processor to cause the system to:
generate data block pointers as metadata for data blocks of a file, wherein each data block pointer includes a physical location index, a checksum for the corresponding data block, and a bitset to indicate associations with snapshots;
for each of the data blocks associated with a snapshot, set a bit at a position in the bitset mapping to a snapshot identifier associated with the snapshot, wherein the snapshot identifier is included in a vector of snapshot identifiers;
successively store the data blocks and data block pointers sequentially into segments of the SSD, wherein the physical location index of each data block pointer corresponds uniquely to a segment; and
store the vector of snapshot identifiers in a checkpoint marker on the SSD during a checkpoint of the segment.

11. The system of claim 10 , wherein the non-transitory computer-readable medium further comprises instructions to maintain the vector of snapshot identifiers.

12. The system of claim 10 , wherein the non-transitory computer-readable medium further comprises instructions to maintain counters of the data block pointers.

13. The system of claim 11 , wherein the non-transitory computer-readable medium further comprises instructions to maintain counters of snapshot identifiers across the data block pointers.

14. The system of claim 10 , wherein a same file type is associated a most recent snapshot identifier.

15. The system of claim 14 , wherein the SSD does not include a hierarchy of pointers to the data blocks on the SSD.

16. A non-transitory computer-readable medium having instructions for a linear filesystem stored thereon, the instructions to:
generate a first data pointer as metadata that includes a first physical location index, a first checksum, and a first bitset, based on a first request to write a first data block to a solid state storage device (SSD), wherein the first checksum corresponds to the first data block;
set a bit in the first bitset that maps to a first snapshot identifier included within a vector of snapshot identifiers, wherein the first snapshot identifier is associated with the first data block of a first snapshot;
store the first data pointer sequentially with the first data block in a first segment of a plurality of physical segments of the SSD, wherein the first physical location index is unique to the first segment; and
store the vector of snapshot identifiers in a checkpoint marker on the SSD during a checkpoint of the segment.

17. The non-transitory computer-readable medium of claim 16 further comprising instructions to:
build a first hash tree from checksums retrieved from data blocks associated with the first snapshot identifier; and
compare the first hash tree to a second hash tree associated with a second snapshot to deduplicate data blocks between the first snapshot and the second snapshot.

18. The non-transitory computer-readable medium of claim 16 , wherein positions in the bitset map to a plurality of snapshot identifiers.

19. The non-transitory computer-readable medium of claim 16 , further comprising instructions to maintain a counter for the first data block.

Assignees

• Netapp Inc

Inventors

• Cantwell Jared
• Parker Saxon

Classifications

• G06F16/1847

  specifically adapted to static storage, e.g. adapted to flash memory or SSD · CPC title

• G06F16/128 Primary

  Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16) · CPC title

• G06F3/0688

  Non-volatile semiconductor memory arrays · CPC title

• G06F3/064

  Management of blocks · CPC title

• G06F3/0616

  in relation to life time, e.g. increasing Mean Time Between Failures [MTBF] · CPC title