Back to results
US 12,748,701 B2Granted
Storage device for caching data segment in hash-based data segment cache and operating method of the storage device
AssigneeSK hynix Inc.
InventorHye Mi Kang
Life of this patent
Estimating the term…
Abstract
A storage device may determine a target data segment from among a plurality of data segments, execute a hash function on the target data segment, and cache the target data segment in a data segment cache based on a result of executing the hash function on the target data segment. The data segment cache may be a hash table including N buckets each of which is able to cache one or more data segments. The hash function may be a function which outputs an index of the target bucket based on N, an index of the target data segment, and a seed value.
Claims12
A storage device comprising:
- a memory for storing a plurality of data segments, each of the plurality of data segments comprising at least one mapping data unit;
- a data segment cache comprising a plurality of buckets configured to cache all or part of the plurality of data segments;
- and
- a controller configured to:
- control the data segment cache to determine a target bucket among the plurality of buckets based on a result of executing a hash function on a target data segment among the plurality of data segments, the hash function being function outputting an index of the target bucket based on a total number of the plurality of buckets, an index of the target data segment and a seed value,
- control the data segment cache to cache the target data segment in the target bucket, and
- when a number of data segments cached in the target bucket is equal to or greater than the threshold number, relocate at least one of data segments cached in the target bucket to another bucket among the plurality of buckets based on the result of executing the hash function with the seed value increased by a first value.
4 more elements
An operating method of a storage device comprising:
- determining a target data segment from among a plurality of data segments, each of the plurality of data segments comprising at least one mapping data units;
- executing a hash function on the target data segment;
- and
- caching the target data segment in a data segment cache, which comprising a plurality of buckets each of which is able to cache one or more data segments, configured to cache all or part of the plurality of data segments based on a result of executing the hash function on the target data segment,
- wherein the caching comprises determining a target bucket, which is a bucket in which the target data segment is to be cached, among the plurality of buckets based on the result of executing the hash function on the target data segment, and caching the target data segment in the target bucket using the hash function which outputs an index of the target bucket based on a total number of the plurality of buckets, an index of the target data segment, and a seed value, and
- wherein, when the number of data segments cached in the target bucket is equal to or greater than a threshold number, the seed value is changed by increasing it by a first value and at least one of data segments cached in the target bucket is relocated to another bucket among the plurality of buckets based on the result of executing the hash function.
3 more elements
Dependencies are inferred from the claim text.