Technologies for computing rolling hashes

1. A computing device for computing rolling hashes during identification of one or more data chunks to de-duplicate in a data de-duplication operation, the computing device comprising:

one or more processors; and

a memory storing a plurality of instructions, which, when executed on the one or more processors, cause the computing device to:

retrieve, as part of the data de-duplication operation in the memory, a block of data from a data buffer;

generate, by the one or more processors, a hash based on the block of data, a previously generated hash, a first hash table initialized with a first plurality of random-valued entries, and a second hash table initialized with a second plurality of random-valued entries, wherein the second plurality of random-valued entries is the first plurality of random-valued entries rotated by a number of table indices equal to a hash window size of a hash algorithm;

determine whether the generated hash matches a predefined trigger;

record a data boundary in response to a determination that the generated hash matches the trigger, wherein the data boundary is indicative of a data chunk to de-duplicate;

de-duplicate the data chunk using the recorded data boundary as input; and

store a result of the de-duplication of the data chunk in the memory.

2. The computing device of claim 1 , wherein to retrieve the block of data from the data buffer comprises to retrieve a next byte of data from the data buffer.

3. The computing device of claim 1 , wherein to generate the hash comprises to generate a hash based on rotation and exclusive-or bitwise operations.

4. The computing device of claim 1 , wherein to generate the hash comprises to generate a hash according to hash=(hash prev «<1)^table1[buf[i]]^table2[buf[i−w]];

wherein hash prev is the previously generated hash;

wherein hash prev <<<1 denotes bitwise rotation of the previously generated hash;

wherein ^ denotes an exclusive-or bitwise operation;

wherein w is the hash window size of the hash algorithm;

wherein buf[i] is the retrieved block of data of the data buffer;

wherein buf[i−w] is a previous block of data of the data buffer offset by an index difference equal to the hash window size;

wherein table1[buf[i]] is the random-valued entry of the first hash table corresponding with the retrieved block of data; and

wherein table2[buf[i−w]] is the random-valued entry of the second hash table corresponding with the previous block of data.

5. The computing device of claim 1 , wherein to determine whether the generated hash matches the predefined trigger comprises to apply a bitmask to the generated hash.

6. The computing device of claim 1 , wherein to record the data boundary comprises to record a data de-duplication boundary that defines a boundary of a data chunk for the data de-duplication.

7. The computing device of claim 1 , wherein the plurality of instructions further causes the computing device to determine an initial hash value.

8. The computing device of claim 7 , wherein the initial hash value is indicative of a value at which to start the rolling hashes.

9. The computing device of claim 1 , wherein the plurality of instructions further causes the computing device to initialize a rolling hash algorithm to generate the hash.

10. The computing device of claim 9 , wherein to initialize the rolling hash algorithm comprises to determine a size of the data buffer.

11. The computing device of claim 9 , wherein to initialize the rolling hash algorithm comprises to determine a hash window size of the hash algorithm.

12. The computing device of claim 9 , wherein to initialize the rolling hash algorithm comprises to determine a bitmask and the trigger associated with the data boundary.

13. One or more non-transitory machine-readable storage media comprising a plurality of instructions stored thereon that, in response to execution by a computing device, cause the computing device to:

retrieve, as part of a data de-duplication operation in a memory of the computing device, a block of data from a data buffer;

generate, by one or more processors, a hash based on the block of data, a previously generated hash, a first hash table initialized with a first plurality of random-valued entries, and a second hash table initialized with a second plurality of random-valued entries, wherein the second plurality of random-valued entries is the first plurality of random-valued entries rotated by a number of table indices equal to a hash window size of a hash algorithm;

determine whether the generated hash matches a predefined trigger;

record a data boundary in response to a determination that the generated hash matches the trigger, wherein the data boundary is indicative of a data chunk to de-duplicate;

de-duplicate the data chunk using the recorded data boundary as input; and

store a result of the de-duplication of the data chunk in the memory of the computing device.

14. The one or more non-transitory machine-readable storage media of claim 13 , wherein to retrieve the block of data from the data buffer comprises to retrieve a next byte of data from the data buffer.

15. The one or more non-transitory machine-readable storage media of claim 13 , wherein the second hash table includes the random-valued entries of the first hash table rotated by a number of table indices equal to a hash window size of a hash algorithm for generating the hash;

wherein to generate the hash comprises to generate a hash according to hash=(hash prev <<<1) A table1[buf[i]]^table2[buf[i−w]];

wherein hash prev is the previously generated hash;

wherein hash prev <<<1 denotes bitwise rotation of the previously generated hash;

wherein ^ denotes an exclusive-or bitwise operation;

wherein w is the hash window size of the hash algorithm;

wherein buf[i] is the retrieved block of data of the data buffer;

wherein buf[i−w] is a previous block of data of the data buffer offset by an index difference equal to the hash window size;

wherein table1[buf[i]] is the random-valued entry of the first hash table corresponding with the retrieved block of data; and

wherein table2[buf[i−w]] is the random-valued entry of the second hash table corresponding with the previous block of data.

16. The one or more non-transitory machine-readable storage media of claim 13 , wherein to determine whether the generated hash matches the predefined trigger comprises to apply a bitmask to the generated hash.

17. The one or more non-transitory machine-readable storage media of claim 13 , wherein the plurality of instructions further cause the computing device to initialize a rolling hash algorithm to generate the hash.

18. The one or more non-transitory machine-readable storage media of claim 17 , wherein to initialize the rolling hash algorithm comprises to determine a size of the data buffer.

19. The one or more non-transitory machine-readable storage media of claim 17 , wherein to initialize the rolling hash algorithm comprises to determine a hash window size of the hash algorithm.

20. The one or more non-transitory machine-readable storage media of claim 17 , wherein to initialize the rolling hash algorithm comprises to determine a bitmask and the trigger associated with the data boundary.

21. A method for computing rolling hashes by a computing device during identification of one or more data chunks in memory to de-duplicate in a data de-duplication operation, the method comprising:

retrieving, by the computing device as part of the data de-duplication operation in the memory, a block of data from a data buffer;

generating, by one or more processors of the computing device, a hash based on the block of data, a previously generated hash, a first hash table initialized with a first plurality of random-valued entries, and a second hash table initialized with a second plurality of random-valued entries, wherein the second plurality of random-valued entries is the first plurality of random-valued entries rotated by a number of table indices equal to a hash window size of a hash algorithm;

determining, by the computing device, whether the generated hash matches a predefined trigger;

recording, by the computing device, a data boundary in response to determining that the generated hash matches the trigger, wherein the data boundary is indicative of a data chunk to de-duplicate;

de-duplicating the data chunk using the recorded data boundary as input; and

storing a result of the de-duplication of the data chunk in a memory of the computing device.

22. The method of claim 21 , wherein retrieving the block of data from the data buffer comprises retrieving a next byte of data from the data buffer.

23. The method of claim 21 , wherein the second hash table includes the random-valued entries of the first hash table rotated by a number of table indices equal to a hash window size of a hash algorithm for generating the hash;

wherein generating the hash comprises generating a hash according to hash=(hash prev <<<1) A table1[buf[i]]^table2[buf[i−w]];

wherein hash prev is the previously generated hash;

wherein hash prev <<<1 denotes bitwise rotation of the previously generated hash;

wherein ^ denotes an exclusive-or bitwise operation;

wherein w is the hash window size of the hash algorithm;

wherein buf[i] is the retrieved block of data of the data buffer;

wherein buf[i−w] is a previous block of data of the data buffer offset by an index difference equal to the hash window size;

wherein table1[buf[i]] is the random-valued entry of the first hash table corresponding with the retrieved block of data; and

wherein table2[buf[i−w]] is the random-valued entry of the second hash table corresponding with the previous block of data.