Efficient name coding

Patent metadata

Field	Value
Publication number	US-10528488-B1
Application number	US-201715499085-A
Country	US
Kind code	B1
Filing date	Apr 27, 2017
Priority date	Mar 30, 2017
Publication date	Jan 7, 2020
Grant date	Jan 7, 2020

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 for efficient name coding in a storage system, comprising:
identifying common prefixes, common suffixes, and midsections of a plurality of strings in the storage system;
writing the common prefixes, midsections and common suffixes to a string table in the storage system;
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.

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 prefix of the string relative to prefixes, the midsection of the string relative to the midsections, and the suffix of the string relative to suffixes.

4. The method of claim 1 , wherein the encoding comprises:
determining a first start position of a prefix in the string table matching the prefix of the string;
determining a second start position of a midsection in the string table matching the midsection of the string;
determining a third start position of a suffix in the string table matching the suffix of the string; and
encoding a first offset of the first start position relative to a base position of prefixes in the string table, a second offset of the second start position relative to a base position of the midsections in the string table, and a third offset of the third start position relative to a base position of suffixes 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 , further comprising:
identifying common midsections of the plurality of strings; and
writing the common midsections to the string table, wherein each common prefix, each common midsection, and each common suffix is recorded only once in the string table.

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 and at least one storage node having two or more authorities.

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:
determining common prefixes, common suffixes, and midsections of a plurality of strings of a storage system;
writing the common prefixes, the midsections and the common suffixes to a string table in the storage system;
determining, for each string of the plurality of strings, position in the string table of prefix, midsection and suffix of the string; and
writing a concatenation of the position in the string table of the prefix of the string, the position in the string table of the midsection of the string, and the position in the string table of the suffix of the string as an encoding of the string in memory of the storage system, for the plurality of strings.

9. The computer-readable media of claim 8 , wherein the writing the common prefixes and the common suffixes to the string table comprises:
recording each common prefix only once in the string table; and
recording each common suffix 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 the prefix of the string relative to prefixes in the string table;
second zero offset encoding with a second minimum number of bits to record offset from a second base position in the string table for the midsection of the string relative to the midsections in the string table; and
third zero offset encoding with a third minimum number of bits to record offset from a third base position in the string table for the suffix of the string relative to suffixes in the string table.

11. The computer-readable media of claim 8 , wherein the encoding comprises:
determining a first start position of a prefix in the string table matching the prefix of the string;
determining a second start position of a midsection in the string table matching the midsection of the string;
determining a third start position of a suffix in the string table matching the suffix of the string;
encoding a first offset of the first start position relative to a base position of prefixes in the string table;
encoding a second offset of the second start position relative to a base position of the midsections in the string table; and
encoding a third offset of the third start position relative to a base position of suffixes 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 determining, 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 of the plurality of storage nodes has one or more such authorities with each authority owning a range of user data and at least one storage node has two or more authorities.

14. A storage cluster with efficient name coding, 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 prefixes, common suffixes, and midsections of a plurality of strings of the storage cluster;
writing the common prefixes, the midsections and the common suffixes to a string table in the storage cluster;
encoding position of each of prefix, midsection and suffix of each of the plurality of strings relative to prefixes, midsections and suffixes in the string table; and
writing the encoded position of the prefix, the midsection and the suffix of each of the plurality of strings to memory in the storage cluster.

15. The storage cluster of claim 14 , wherein:
the at least one of the processors is configurable to identify common midsections of the plurality of strings; and
record the common midsections to the string table, wherein each common prefix, each common midsection, and each common suffix is recorded 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 prefix of the string relative to the prefixes, the midsection of the string relative to the midsections, and the suffix of the string relative to the suffixes.

17. The storage cluster of claim 14 , wherein the encoding comprises:
determining a first start position of a common prefix in the string table that matches the prefix of the string, a second start position of a midsection in the string table that matches the midsection of the string, and a third start position of a common suffix in the string table that matches the suffix of the string; and
encoding a first offset of the

Assignees

• Pure Storage Inc

Inventors

• Lee Robert
• Sandvig Cary A

Classifications

• G06F3/0688 Primary

  Non-volatile semiconductor memory arrays · CPC title

• G06F3/0667

  at data level, e.g. file, record or object virtualisation · CPC title

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title

• G06F3/0647

  Migration mechanisms · CPC title

• G06F3/0623

  in relation to content · CPC title