Efficient name coding

• US 10,528,488 B1
• Filed: 04/27/2017
• Issued: 01/07/2020
• Est. Priority Date: 03/30/2017
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Lee, Robert, Sandvig, Cary A.
• Primary Examiner(s): Jeanglaude, Jean B
• Application Number:
  US15/499,085
• Time in Patent Office: 985 Days
• Field of Search: 341 55, 341 50, 341 51
• CPC Class Codes: G06F 12/1425 the protection being physical, e.g. cell, word, block
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2219 Large Object storage; Management thereof
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

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.

Claims

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 first start position relative to a first base position for the prefixes in the string table, a second offset of the second start position relative to a second base position for the midsections in the string table, and a third offset of the third start position relative to a third base position for the suffixes 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 and at least one storage node having two or more authorities, the authorities being transferable among storage nodes, wherein each of the authorities is configurable to perform the method.