Perturb key technique

Patent metadata

Field	Value
Publication number	US-2016248583-A1
Application number	US-201615052332-A
Country	US
Kind code	A1
Filing date	Feb 24, 2016
Priority date	Feb 25, 2015
Publication date	Aug 25, 2016
Grant date	—

Abstract

A technique perturbs an extent key to compute a candidate extent key in the event of a collision with metadata (i.e., two extents having different data that yield identical hash values) stored in a memory of a node in a cluster. The perturbing technique may be used to compute a candidate extent key that is not previously stored in an extent store instance. The candidate extent key may be computed from a hash value of an extent using a perturbing algorithm, i.e., a hash collision computation, which illustratively adds a perturb value to the hash value. The perturb value is illustratively sufficient to ensure that the candidate extent key resolves to a same hash bucket and node (extent store instance) as the original extent key. In essence, the technique ensures that the original extent key is perturbed in a deterministic manner to generate the candidate extent key, so that the original extent and candidate extent key “decode” to the same hash bucket and extent store instance.

First claim

What is claimed is:

1 . A method comprising:
receiving first and second extents at a storage system having a processor and a memory, the storage system coupled to a storage device, the first extent different from the second extent; applying a hash function to generate first and second keys associated respectively with the first extent and second extents, the first key mapping to a first hash bucket selected from among a set of approximately uniformly distributed hash buckets, the second key mapping to a second hash bucket selected from among the set of approximately uniformly distributed hash buckets; determining whether the second key collides with the first key; in response to determining that the second key collides with the first key, perturbing the second key using a deterministic function to generate a candidate key such that the second hash bucket is identical to the first hash bucket and associating the candidate key with the second extent; and storing the first and second extents on the storage device.

2 . The method of claim 1 wherein perturbing the second key using the deterministic function to generate the candidate key further comprises:
determining whether the candidate key collides with the first key; and
in response to determining that the candidate key collides with the first key, perturbing the candidate key repeatedly until the first key does not collide with the candidate key.

3 . The method of claim 1 wherein the storage device is a solid state drive.

4 . The method of claim 1 wherein mapping the first key to the first hash bucket uses an arithmetic remainder function.

5 . The method of claim 2 wherein the deterministic function performs one of addition and subtraction of an integer multiple of a number of hash buckets included in the set of approximately uniformly distributed hash buckets.

6 . The method of claim 1 further comprising:
mapping the first key to a set of hash tables having the association of the first key to the first extent and having the association of the candidate key to the second extent; and
mapping the candidate key to the set of hash tables.

7 . The method of claim 6 wherein mapping the first key and candidate key to the set of hash tables uses of a same field of bits from the first key and candidate key respectively.

8 . The method of claim 1 wherein the storage system includes a plurality of nodes, and wherein each hash bucket is mapped to a respective node of the plurality of nodes.

9 . The method of claim 1 wherein the deterministic function increases a probability that identical extents are deduplicated.

10 . A method comprising:
receiving first and second extents at a storage system having a processor and a memory, the storage system coupled to a storage device, the first extent different from the second extent; applying a hash function to generate first and second keys associated respectively with the first and second extents, the first key mapping to a first hash bucket selected from among a set of approximately uniformly distributed hash buckets, the second key mapping to a second hash bucket selected from among the set of approximately uniformly distributed hash buckets; determining whether the second key collides with the first key; in response to determining that the second key collides with the first key, perturbing the second key using a deterministic function to generate a candidate key such that the second hash bucket is identical to the first hash bucket and associating the candidate key with the second extent, wherein the deterministic function increases a probability that identical extents are deduplicated; determining whether the candidate key collides with the first key; in response to determining that the candidate key collides with the first key, perturbing the candidate key repeatedly until the first key does not collide with the candidate key; and storing the first and second extents on the storage device.

11 . A system comprising:
a storage system having a node including a memory connect to a processor via a bus; a storage array coupled to the storage system; a storage I/O stack executing on the processor of the storage system, the storage I/O stack when executed operable to:
receive first and second extents, the first extent different from the second extent;
apply a hash function to generate first key and second keys associated respectively with the first extent and second extents, the first key mapping to a first hash bucket selected from among a set of approximately uniformly distributed hash buckets, the second key mapping to a second hash bucket selected from among the set of approximately uniformly distributed hash buckets;
determine whether the second key collides with the first key;
in response to determining that the second key collides with the first key, perturb the second key using a deterministic function to generate a candidate key such that the first hash bucket is identical to the second hash bucket and associating the candidate key with the second extent; and storing the first and second extents on the storage array.

12 . The system of claim 11 wherein the storage I/O stack operable to perturb the second key using the deterministic function to generate the candidate key further comprises:
determine whether the candidate key collides with the first key; and
in response to determining that the candidate key collides with the first key, perturb the candidate key until the first key does not collide with the candidate key.

13 . The system of claim 11 wherein the storage array includes one or more solid state drives.

14 . The system of claim 11 wherein mapping the first key to the first hash bucket uses an arithmetic remainder function.

15 . The system of claim 12 wherein the deterministic function performs one of addition and subtraction of an integer multiple of a number of hash buckets included in the set of approximately uniformly distributed hash buckets.

16 . The system of claim 11 wherein the storage I/O stack is further operable to:
map the first key to a set of hash tables having the association of the first key to the first extent and having the association of the candidate key to the second extent; and
map the candidate key to the set of hash tables.

17 . The system of claim 16 wherein mapping the first key and candidate key to the set of hash tables uses of a same field of bits from the first key and candidate key respectively.

18 . The system of claim 11 wherein the storage system includes a plurality of nodes, and wherein each hash bucket is mapped to a respective node of the plurality of nodes.

19 . The system of claim 11 wherein the deterministic function increases a probability that identical extents are deduplicated.

20 . The system of claim 15 wherein the number of hash buckets included in the set of approximately uniformly distributed hash buckets is a prime number.

Assignees

• Netapp Inc

Inventors

• Mcclanahan Edward D
• Kimmel Jeffrey S

Classifications

• G06F21/78 Primary

  to assure secure storage of data (address-based protection against unauthorised use of memory G06F12/14; record carriers for use with machines and with at least a part designed to carry digital markings G06K19/00) · CPC title

• H04L9/0861 Primary

  Generation of secret information including derivation or calculation of cryptographic keys or passwords · CPC title

• H04L9/16

  the keys or algorithms being changed during operation · CPC title