Efficient coding in a storage system

Patent metadata

Field	Value
Publication number	US-10942869-B2
Application number	US-201916725639-A
Country	US
Kind code	B2
Filing date	Dec 23, 2019
Priority date	Mar 30, 2017
Publication date	Mar 9, 2021
Grant date	Mar 9, 2021

Abstract

A method for efficient name coding in a storage system is provided. The method includes identifying common prefixes, common suffixes, and midsections of a plurality of strings in the storage system, and writing the common prefixes, midsections and common suffixes to a string table in the storage system. The method includes encoding each string of the plurality of strings as to position in the string table of prefix, midsection and suffix of the string, and writing the encoding of each string to memory in the storage system for the plurality of strings, in the storage system.

First claim

What is claimed is:

1. A method, comprising:
identifying common sections of a plurality of strings in the storage system;
writing the common sections to a string table in the storage system, wherein each common section is recorded once and sections having no commonality are recorded once;
encoding each string of the plurality of strings as to position of respective section of each string in the string table; and
writing the encoding of each string to memory in the storage system for the plurality of strings.

2. The method of claim 1 , wherein the plurality of strings comprises object names for objects stored in the storage system.

3. The method of claim 1 , wherein the encoding comprises offset encoding to record offset from a base position in the string table for each of the sections for a string.

4. The method of claim 1 , wherein the encoding comprises:
encoding a first offset of a first start position of a first section in the string table matching the first section of the string relative to a base position of the first section in the string table, and a second offset of a second start position of a second section in the string table matching the second section relative to a base position of the second section in the string table.

5. The method of claim 1 , wherein the plurality of strings comprises a stream of strings in a schema relating to storage of user data in the storage system.

6. The method of claim 1 , wherein the plurality of strings includes object names.

7. The method of claim 1 , wherein the identifying, the writing to the string table, the encoding, and the writing to the memory are performed by each of one or more authorities per storage node of a storage cluster, with each authority owning a range of user data.

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:
identifying common sections of the plurality of strings in the storage system;
writing the common sections to a string table in the storage system, wherein each common section is recorded once and sections having no commonality are recorded once;
encoding each string of the plurality of strings as to position of respective section of each string in the string table; and
writing the encoding of each string to memory in the storage system for the plurality of strings.

9. The computer-readable media of claim 8 , wherein the writing the common sections to the string table comprises:
recording each common section only once in the string table.

10. The computer-readable media of claim 8 , wherein the encoding comprises:
first zero offset encoding with a first minimum number of bits to record offset from a first base position in the string table for a first section of the string relative to first sections in the string table and second zero offset encoding with a second minimum number of bits to record offset from a second base position in the string table for a second section of the string relative to the second sections in the string table.

11. The computer-readable media of claim 8 , wherein the encoding comprises:
encoding a first offset of a first start position of a first section in the string table matching the first section relative to a base position of first sections in the string table, and a second offset of a second start position of a second section in the string table matching the second section relative to a base position of the second sections in the string table.

12. The computer-readable media of claim 8 , wherein the plurality of strings comprises a stream of strings in a schema relating to storage of user data in the storage system or object names for objects stored in the storage system.

13. The computer-readable media of claim 8 , wherein the identifying, the writing to the string table, the encoding, and the writing to the memory are performed by an authority in one of a plurality of storage nodes of a storage cluster, wherein each authority owning a range of user data.

14. A storage cluster, comprising:
a plurality of blades supporting a plurality of storage nodes, each blade having one or more processors and storage memory; and
at least one of the processors configurable to perform a method comprising:
identifying common sections of the plurality of strings in the storage system;
writing the common sections to a string table in the storage system, wherein each common section is recorded once and sections having no commonality are recorded once;
encoding each string of the plurality of strings as to position of respective section of each string in the string table; and
writing the encoding of each string to memory in the storage system for the plurality of strings.

15. The storage cluster of claim 14 , wherein:
the at least one of the processors is configurable to record each common section from the plurality of strings only once in the string table.

16. The storage cluster of claim 14 , wherein the encoding comprises zero offset encoding with a minimum number of bits to record offset from a base position in the string table for each of the common section of the string.

17. The storage cluster of claim 14 , wherein the encoding comprises:
encoding a first offset of a first start position of a first section in the string table matching the first section relative to a first base position for first sections in the string table, and a second offset of a second start position of a second section in the string table matching the second section relative to a second base position for second sections in the string table.

18. The storage cluster of claim 14 , further comprising:
an array encoder that produces a vector relating to storage of user data in the storage cluster, wherein an array for the plurality of strings is in a stream in a schema in the vector.

19. The storage cluster of claim 14 , wherein the plurality of strings comprises object identifiers (OIDs) for objects stored in the storage cluster, with each object identifier having a service, a bucket and an object name for the object, or a taxonomy for the object.

20. The storage cluster of claim 14 , further comprising:
each of the plurality of storage nodes having one or more authorities, with each authority owning a range of user data, the authorities being transferable among storage nodes.

Assignees

• Pure Storage Inc

Inventors

• Lee Robert
• Sandvig Cary A

Classifications

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title

• G06F16/2358

  Change logging, detection, and notification (replication G06F16/27) · CPC title

• G06F16/2308

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F16/2272

  Management thereof · CPC title

• G06F16/2219

  Large Object storage; Management thereof · CPC title