HASH BASED READ AND WRITE OPERATIONS IN A STORAGE SYSTEM

摘要

A method for hash-based writing, the method comprises: receiving a received data entity to be stored in a storage system, wherein the received data entity is associated with received data entity metadata; selecting a selected data structure out of a set of data structures that comprises K data structures; wherein K is a positive integer; wherein for each value of a variable k that ranges between 2 and K, stored data entity metadata that is stored in a k'th data structure out of the set collided with stored data entity metadata that is stored in each one of a first till (k−1)'th data structures of the set; calculating an index by applying, on the received data entity metadata, a hash function that is associated with the selected data structure; determining whether an entry that is associated with the index and belongs to the selected data structure is empty; writing to the entry, if the entry is empty, the received data entity metadata, and storing the received data entity in the storage system in response to a location of the entry in the set; and selecting, if the entry is not empty, a new data structure of the set and repeating at least the stages of calculating and determining.

主权项

1. A method for hash-based writing, the method comprises:
receiving a received data entity to be stored in a storage system, wherein the received data entity is associated with received data entity metadata; selecting a selected data structure out of a set of data structures that comprises K data structures; wherein K is a positive integer; wherein for each value of a variable k that ranges between 2 and K, stored data entity metadata that is stored in a k'th data structure out of the set collided with stored data entity metadata that is stored in each one of a first till (k−1)'th data structures of the set; calculating an index by applying, on the received data entity metadata, a hash function that is associated with the selected data structure; determining whether an entry that is associated with the index and belongs to the selected data structure is empty; writing to the entry, if the entry is empty, the received data entity metadata, and storing the received data entity in the storage system in response to a location of the entry in the set; and selecting, if the entry is not empty, a new data structure of the set and repeating at least the stages of calculating and determining.