Index entry eviction
View Patent ↗Systems, methods embodied on computer-readable media, and other embodiments associated with index entry eviction are described. One example method includes selecting an index entry for eviction from a bucket of index entries based on a time value, a utility value, and a precedence value. A precedence value may be a value associated with an index entry that is static over time. Additionally, results of a function that compares two precedence values may be static over time. The example method may also include providing an index entry identifier that identifies the index entry.
1. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer cause the computer to perform a method, the method comprising:
selecting a selected index entry for eviction from a bucket of index entries as a function of a time value, a utility value, and a precedence value, where an index entry in the bucket of index entries comprises a portion of a hash value, a memory location, and a utility value describing a usefulness of the index entry; and
providing an index entry identifier that identifies the selected index entry,
where the bucket of index entries is a bucket associated with a hash-bucket data structure that stores a portion of a data deduplication index,
where the hash-bucket data structure is stored as an array in random access memory (RAM),
where the array is divided into N buckets of size M, where N and M are integers,
where a ranking value is generated for the index entry as a function of the time value and the precedence value when the index entry has not been accessed by an index lookup, where a ranking value is generated for the index entry as a function of the time value, the utility value, and the precedence value when the index entry has been accessed by an index lookup, and where index entries in the bucket of index entries are ranked according to ranking values.
2. The computer-readable medium of claim 1 , where the utility value indicates a number of times the index entry has been used as a primary source of information for confirming the existence of data in a block of memory associated with the memory location.
3. The computer-readable medium of claim 1 , where the time value indicates a time at which the index entry was recently accessed.
4. The computer-readable medium of claim 1 , where the precedence value is a value generated as a function of the portion of the hash value.
5. The computer-readable medium of claim 4 , where the precedence value is the numerical value of the portion of the hash value.
6. The computer-readable medium of claim 1 , where an index entry having the lowest rank is designated the selected index entry.
7. The computer-readable medium of claim 1 , where the index entry identifier controls a data deduplication logic to replace the selected index entry with a new index entry.
8. An apparatus, comprising:
a processor;
a first memory storing a hash bucket table that stores a portion of a data deduplication index; and
an interface to connect the processor, the first memory, and a set of logics, the set of logics comprising:
an eviction logic to provide a location of an entry in a bucket of the hash bucket table, where the location indicates that the entry is to be overwritten, where the location is provided as a function of a utility value associated with the entry, a time value associated with the entry, and a precedence value associated with the entry,
where an entry in the hash bucket table comprises a portion of a hash value, a memory location, and a utility value describing a usefulness of the entry,
where the hash bucket table is stored as an array in random access memory (RAM),
where the array is divided into N buckets of size M, where N and M are integers, and
where the eviction logic generates a ranking value for the entry in the hash bucket table as a function of the time value and the precedence value when the entry has not been accessed by an index lookup,
where the eviction logic generates a ranking value for the entry in the hash bucket table as a function of the time value, the utility value, and the precedence value when the entry has been accessed by an index lookup, and
where entries in the hash bucket table are ranked according to ranking values.
9. The apparatus of claim 8 , where the data deduplication index is stored on data store that takes a longer time to access than the time it takes to access the first memory.
10. The apparatus of claim 9 , comprising the data store.
11. The apparatus of claim 8 , the set of logics comprising a deduplication logic to search the hash bucket table for a an entry identified by a hash value, and to control the eviction logic to provide a location of an entry in the hash bucket table to be overwritten upon determining that the hash is not associated with an entry in the hash bucket table.
12. The apparatus of claim 11 , where the deduplication logic is to replace the entry with an entry associated with the hash value based on the location received from the eviction logic.
13. The apparatus of claim 11 , the set of logics comprising a hashing logic to generate the hash value as a function of a block of data to be stored to a data store.
14. The apparatus of claim 11 , where the hash value is generated as a function of a block of data on an external device, and where the apparatus selectively requests the block of data from the external device upon determining whether a matching hash is found in the deduplication index.
15. The apparatus of claim 12 , where the deduplication logic is to selectively store the entry in the hash bucket table in a second memory before replacing the entry in the hash bucket table with the entry associated with the hash value.