# US 10,176,117 B2 · Efficient metadata in a storage system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,176,117 B2 - Document ID: US10176117B2 - Status: Granted - Kind: B2 - Application number: 15/516,265 - Filed: 2015-09-30 - Published: 2017-10-19 - Granted: 2019-01-08 - Earliest claimed: 2014-10-01 - Assignees: Cacheio LLC - Applicants: Cacheio LLC - Inventors: Arthur James Beaverson; Bang Chang - Web page: https://patentgrep.com/patent/US10176117B2 ## CPC - G06F 12/109: for multiple virtual address spaces, e.g. segmentation (G06F12/1036 takes precedence) - G06F 3/0604: {Improving or facilitating administration, e.g. storage management} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/064: {Management of blocks} - G06F 3/0641: {De-duplication techniques} - G06F 3/0647: {Migration mechanisms} - G06F 3/0664: {at device level, e.g. emulation of a storage device or system} - G06F 3/0685: {Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays} - G06F 3/0689: {Disk arrays, e.g. RAID, JBOD} - G06F 12/0246: {in block erasable memory, e.g. flash memory} - G06F 16/14: Details of searching files based on file metadata - G06F 16/1752: {based on file chunks} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for managing metadata in a storage system is disclosed. The system includes a processor, a storage medium, a first metadata table that maps every data block's LBN to its unique content ID, and a second metadata table that maps every content ID to its PBN on the storage medium. During a data movement process, the processor is configured to determine the content ID of the data block and update its entry in the second metadata table without accessing the first metadata table. A method is also disclosed to reduce the size of the first metadata table. Only content ID is stored in the first metadata table and its LBN is determined by the metadata entry's relative position in the table. Metadata entries are stored in metadata blocks and deduplicated. ## Claims ### Claim 1 A storage system configured to support storage virtualization, data services, and data mobility, comprising: a persistent storage medium; a memory; a first metadata table comprising a plurality of entries, each of which maps a data block's LBN to its unique content ID; a second metadata table comprising a plurality of entries, each of which maps a unique content ID to its PBN on the storage medium; and a storage processor configured to perform a data movement process, wherein as part of the data movement process, the storage controller is configured to: read the data block from its current physical location PBN A; determine the unique content ID of the data block; look up the content ID in the second metadata table; write the data block to its new physical location PBN B; map the content ID to PBN B in the second metadata table; and mark PBN A free on free block list; wherein the first metadata table entry only includes the data block's content ID but not its LBN; wherein the LBN can be a determined based on the metadata entry's relative position in the first metadata table. ### Claim 2 (depends on 1) The storage system of claim 1, wherein the storage processor determines the unique content ID by computing a strong hash of the block's contents. ### Claim 3 (depends on 1) The storage system of claim 1, wherein the storage processor determines the unique content ID by reading the content ID stored with the data block. ### Claim 4 (depends on 1) The storage system of claim 1, wherein the content ID is unique to the block's contents and data blocks are de-duplicated. ### Claim 5 (depends on 1) The storage system of claim 1, wherein the first metadata table is stored on the storage medium and cached in the memory based on locality of reference. ### Claim 6 (depends on 1) The storage system of claim 1, wherein the second metadata table is stored entirely in the memory. ### Claim 7 (depends on 1) The storage system of claim 1, wherein a plurality of entries in the first metadata table are stored in a metadata block, wherein a unique content ID is generated for each metadata block and metadata blocks are deduplicated. ### Claim 8 A method implemented in a storage system to support a data movement process, said storage system comprising a persistent storage medium, a memory, a first metadata table comprising a plurality of entries, each of which maps a data block's LBN to its unique content ID, a second metadata table comprising a plurality of entries, each of which maps a unique content ID to its PBN on the storage medium, said method is characterized by: reading the data block from its current physical location PBN A; determining the unique content ID of the data block; looking up the content ID in the second metadata table; writing the data block to its new physical location PBN B; mapping the content ID to PBN B in the second metadata table; and marking PBN A free on free block list; wherein the first metadata table entry only includes the data block's content ID but not its LBN; wherein the LBN can be a determined based on the metadata entry's relative position in the first metadata table. ### Claim 9 (depends on 8) The method of claim 8, wherein the determining of the unique content ID comprises computing a strong hash of the block's contents. ### Claim 10 (depends on 8) The method of claim 8, wherein the determining of the unique content ID comprises reading the content ID stored with the data block. ### Claim 11 (depends on 8) The method of claim 8, wherein the content ID is unique to the block's contents and data blocks are de-duplicated. ### Claim 12 (depends on 8) The method of claim 8, wherein the servicing of a read request comprises computing the content ID of the physical block and comparing it to the stored content ID in the metadata entry to make sure that the storage medium has returned the original data. ### Claim 13 (depends on 8) The method of claim 8, wherein the first metadata table is stored on the storage medium and cached in the memory based on locality of reference. ### Claim 14 (depends on 8) The method of claim 8, wherein the second metadata table is stored entirely in the memory. ### Claim 15 (depends on 8) The method of claim 8, wherein the first metadata table entry only includes the data block's content ID but not its LBN; wherein the LBN can be a determined based on the metadata entry's relative position in the first metadata table. ### Claim 16 (depends on 8) The method of claim 8, wherein a plurality of entries in the first metadata table are stored in a metadata block, wherein a unique content ID is generated for each metadata block and metadata blocks are deduplicated. ### Claim 17 A storage system configured to support storage virtualization, data services, and data mobility, comprising: a persistent storage medium; a memory; a first metadata table comprising a plurality of entries, each of which maps a data block's LBN to its unique content ID; a second metadata table comprising a plurality of entries, each of which maps a unique content ID to its PBN on the storage medium; and a storage processor configured to perform a data movement process, wherein as part of the data movement process, the storage controller is configured to: read the data block from its current physical location PBN A; determine the unique content ID of the data block; look up the content ID in the second metadata table; write the data block to its new physical location PBN B; map the content ID to PBN B in the second metadata table; and mark PBN A free on free block list; wherein the storage processor is further configured to reduce the size of the first metadata table by: storing only the content ID of a data block in the data block's entry in the first metadata table, wherein the data block's LBN is determined from the entry's relative position in the first metadata table; and deduplicating metadata blocks, wherein a plurality of entries in the first metadata table that include only data blocks' content IDs are stored in a metadata block and wherein a unique content ID is generated for each metadata block and metadata blocks are deduplicated based on their unique content IDs.