Patent Description:
Software (for example, a file system) can send an instruction by using a processor, to read data from or write data into an internal memory. The internal memory stores an index table to help search for data stored in a storage.

When cache space in the storage is insufficient, data stored in the storage cache can be deleted, and indexes in the index table in the internal memory can also be deleted.

In the prior art, it is necessary to perform a plurality of IOs to read indexes corresponding to a plurality of pieces of data cached in the storage, and delete the same indexes in the index table in the internal memory. The storage is read for quite many times, affecting overall system performance.

Therefore, how to reduce storage reads and improve system performance in a process of deleting indexes in the index table in the internal memory has become a problem to be urgently resolved at present. <CIT> discloses a storage apparatus, including a first storage device; a second storage device having an access speed higher than an access speed of the first storage device; a monitor that monitors a write access load for the first storage device; a comparator that compares the write access load for the first storage device monitored by the monitor, with a load threshold; and a switch that causes write access target data to be written into the first and second storage devices, when it is determined by the comparator that the write access load for the first storage device does not exceed the load threshold, while causing the write access target data to be written into the first storage device, when it is determined by the comparator that the write access load for the first storage device exceeds the load threshold.

Preferable embodiments are defined by the dependent claims. This application provides a method and an apparatus for deleting indexes in an internal memory. Because all indexes in a target storage unit are consecutively rather than discretely stored, indexes corresponding to a plurality of pieces of data cached in a storage can be read through one IO, so that the same indexes in an index table in the internal memory can be deleted at a time, thereby improving deletion efficiency.

According to a first aspect, a method for deleting indexes in an internal memory is provided. The method is applied to a storage manager, and the storage manager includes the internal memory and communicates with a first storage, where the first storage records a plurality of storage units, and each storage unit includes a plurality of data blocks and an index corresponding to each of the plurality of data blocks. The internal memory stores an index table, and the index table records indexes corresponding to data blocks of the plurality of storage units. The method includes:.

With reference to the first aspect, in some implementations of the first aspect, the storage manager communicates with a second storage, and before the deleting all the read indexes from the index table in the internal memory, the method further includes:
storing a plurality of data blocks in the target storage unit into the second storage.

With reference to the first aspect, in some implementations of the first aspect, all the indexes in the target storage unit are read at a time by using a start address and a length, where the start address is a start address of all the indexes in the target storage unit, and the length is a total length of all the indexes in the target storage unit.

With reference to the first aspect, in some implementations of the first aspect, the index table in the internal memory includes a plurality of members, and the members include the index corresponding to each of the plurality of data blocks.

With reference to the first aspect, in some implementations of the first aspect, the first storage records information about the plurality of storage units, and the information includes a quantity of the storage units and/or a quantity of storage units in an empty state.

In this embodiment of this application, the information about the plurality of storage units recorded in the first storage can help the storage manager manage storage information.

According to a second aspect, an apparatus for deleting indexes in an internal memory is provided. The apparatus is applied to a storage manager, and the storage manager includes the internal memory and communicates with a first storage, where the first storage records a plurality of storage units, and each storage unit includes a plurality of data blocks and an index corresponding to each of the plurality of data blocks. The internal memory stores an index table, and the index table records indexes corresponding to data blocks of the plurality of storage units. The apparatus includes:.

With reference to the second aspect, in some implementations of the second aspect, the storage manager communicates with a second storage, and the apparatus further includes:
a storage module, configured to store the plurality of data blocks in the target storage unit into the second storage.

With reference to the second aspect, in some implementations of the second aspect, the reading module is specifically configured to read, by using a start address and a length, all the indexes in the target storage unit at a time, where the start address is a start address of all the indexes in the target storage unit, and the length is a total length of all the indexes in the target storage unit.

With reference to the second aspect, in some implementations of the second aspect, the index table in the internal memory includes a plurality of members, and the members include the index corresponding to each of the plurality of data blocks.

With reference to the second aspect, in some implementations of the second aspect, the first storage records information about the plurality of storage units, and the information includes a quantity of the storage units and/or a quantity of storage units in an empty state.

According to a third aspect, a storage manager is provided, where the storage manager includes a processor, an internal memory, and a first storage. The first storage records a plurality of storage units, and each storage unit includes a plurality of data blocks and an index corresponding to each of the plurality of data blocks. The internal memory stores an index table, and the index table records indexes corresponding to data blocks of the plurality of storage units. The internal memory stores a program, and the processor runs the program to perform the following method: selecting a to-be-evicted target storage unit from the plurality of storage units; reading all indexes in the target storage unit, where all the indexes in the target storage unit are consecutively stored in the target storage unit; deleting all the read indexes from the index table in the internal memory; and marking the target storage unit as empty.

According to a fourth aspect, a computer program product is provided, where the computer program product includes computer program code. When the computer program code is run on a computer, the computer is enabled to perform the method according to the foregoing aspects.

According to a fifth aspect, a computer readable medium is provided, where the computer readable medium stores program code. When the computer program code is run on a computer, the computer is enabled to perform the method according to the foregoing aspects.

<FIG> is a schematic diagram of a possible storage structure applied to embodiments of this application. The storage structure may include: a processor <NUM>, a dynamic random access memory (dynamic random access memory, DRAM) <NUM>, a solid state disk (solid state disk, SSD) <NUM>, and a hard disk drive (hard disk drive, HDD) <NUM>.

The DRAM <NUM> may serve as a level <NUM> cache. A read/write latency of the SSD <NUM> is between those of the DRAM <NUM> and the HDD140, and the SSD <NUM> may serve as a level <NUM> cache.

Software (for example, a file system) can send an instruction by using the processor <NUM> and read data from or write data into the DRAM <NUM>. The SSD <NUM> may provide the DRAM <NUM> with a get (get) interface, a put (put) interface, and a delete (delete) interface. After software sends a read request, data can be read from the cache. If no data is read from the DRAM <NUM> cache, the software can call the get interface to read data from the SSD <NUM> cache. If still no data is read, the software can read data from the HDD <NUM>. After software sends a write request, data can be written into the DRAM <NUM> cache. If the DRAM <NUM> cache is full, the software can call the put interface to write the data in the DRAM <NUM> cache into the SSD <NUM>. If the SSD <NUM> cache is full, the software can write the data from the SSD <NUM> to the HDD <NUM>.

Cache management of the SSD <NUM> may be divided into two parts. One is data layout on the SSD <NUM>, and the other is an internal memory index structure in the DRAM <NUM>. In performing a read or write operation, software may look up data in the SSD <NUM> by using internal memory indexes in the DRAM <NUM>. The following describes a specific implementation process of cache management of the SSD <NUM> in detail with reference to <FIG>.

<FIG> is a schematic diagram of possible cache management of the SSD <NUM>. <FIG> may include the SSD <NUM> and an internal memory index table in the DRAM <NUM>.

Referring to <FIG>, a cache management system may write data (value) into the SSD <NUM> and create an index table in the DRAM <NUM>. The index table may include a plurality of indexes, and each index may include a key (key) and an offset (offset). Based on a key or an offset in a created index table, data stored in the SSD <NUM> can be quickly found. The key may be understood as a position of a data value in the HDD <NUM>, and the offset may be understood as an offset of the data value in the SSD <NUM>.

In an example, when writing data (put), the cache management system may first search the index table in the DRAM <NUM>, and determine whether the data write operation is an update operation or a new data write operation. If an index with a key identical to that of the to-be-written data can be found in the index table in the DRAM <NUM>, it means that the HDD <NUM> has stored data with the key, indicating that the write operation is an update operation. If an index with a key identical to that of the to-be-written data is not found in the index table in the DRAM <NUM>, it means that there is no data stored with the key in the HDD <NUM>, and that the data can be written into the SSD <NUM>. Then, the index corresponding to the data is added to the index table in the DRAM <NUM>.

In another example, when reading data (get), the cache management system may first search the index table in the DRAM <NUM>. If an index with a key identical to that of the to-be-read data is found, the data can be read from the SSD <NUM> based on an offset. If no index with a key identical to that of the to-be-read data is found, the read fails.

In another example, the cache management system may delete data stored in the SSD <NUM> when cache space of the SSD <NUM> is insufficient. In addition, storage space occupied by the data in the SSD <NUM> may be set to be empty, so that the cache management system can write data in the storage space when writing data.

Specifically, the cache management system may read indexes corresponding to the data stored in the SSD <NUM>, and delete the same indexes in the DRAM <NUM>. In this way, when the cache management system is writing data, if an index with a key identical to that of the to-be-written data is not found in the index table in the DRAM <NUM>, the data can be written into the SSD <NUM>, and then indexes corresponding to the data can be added to the index table in the DRAM <NUM>.

In the prior art, in the index table in the DRAM <NUM>, a hash value (hashkey for short below) and an offset of a key are stored in each index, and a data block including a key and a value (KV pair for short below) can be stored in the SSD <NUM>. In the data layout of the SSD <NUM>, an index area is obtained through division in the SSD <NUM> for storing a corresponding index table in the DRAM <NUM>, and the KV pair is stored in a data (data) area in the SSD <NUM>.

In the prior art, when cache space of the SSD <NUM> is insufficient, during eviction of a plurality of KV pairs stored in the SSD <NUM>, a plurality of input and output (input output, IO) operations are required to read indexes corresponding to the plurality of KV pairs to the DRAM <NUM> from the index area of the SSD <NUM>. In addition, all read indexes may be traversed, and the corresponding indexes in the index table in the DRAM <NUM> may be deleted.

In the prior art, when cache space of the SSD <NUM> is insufficient, the plurality of indexes corresponding to the index table in the DRAM <NUM> can be deleted only after a plurality of read IOs with the SSD <NUM>, thereby affecting the deletion performance.

An embodiment of this application provides a method for deleting indexes of an internal memory. The method is applied to a storage manager, where the storage manager includes the internal memory and communicates with a first storage. In this method, a plurality of corresponding indexes in the index table in the DRAM <NUM> can be deleted after one read IO, thereby improving performance.

The following describes the system architecture provided in this application in detail with reference to <FIG> by using an example in which the first storage is an SSD <NUM>.

<FIG> is a schematic structural diagram of a system architecture <NUM> according to an embodiment of this application. The system architecture <NUM> may include an internal memory DRAM <NUM> and the SSD <NUM>.

The DRAM <NUM> may serve as a level <NUM> cache and can communicate with the SSD <NUM>. An index table may be stored in the DRAM <NUM>. The index table may record indexes corresponding to data blocks (corresponding to the KV pairs mentioned above) of a plurality of storage units in the SSD <NUM>. A storage unit is a segment of data space that stores a plurality of pieces of data according to a specific rule.

The SSD <NUM> may be divided into a super block area <NUM> and a data area <NUM>.

The data area <NUM> may be managed based on a fixed granularity. In an example, slabs (slab) may be used as storage units to manage data stored in the SSD <NUM>. For example, a slab <NUM>, a slab <NUM>, a slab <NUM>, and a slab <NUM> may be used. Each slab may store management information (for example, in <FIG>, a head <NUM> is stored in the slab <NUM>), a plurality of centrally stored consecutive indexes (for example, in <FIG>, an index <NUM> and an index <NUM> are stored in the slab <NUM>), and a plurality of stored KV pairs (for example, in <FIG>, a KV pair <NUM> and a KV pair <NUM> are stored in the slab <NUM>).

It should be understood that the head <NUM> may record necessary management information, for example, numbers of the slabs.

The super block area <NUM> may record related information of the SSD <NUM>, and the related information may include but is not limited to: a total quantity of slabs in the data area <NUM>, a quantity of empty slabs in the data area <NUM>, and a quantity of full slabs in the data area <NUM>.

It should be noted that an empty slab may be understood as a slab with no KV pair stored in any KV space. A full slab may be understood as a slab with KV pairs stored in all its KV space.

<FIG> is a schematic flowchart of a method for deleting indexes in an internal memory according to an embodiment of this application. The method shown in <FIG> may include step <NUM> to step <NUM>, and the following describes step <NUM> to step <NUM> in detail.

Step <NUM>: Select a to-be-evicted target storage unit from a plurality of storage units.

In this embodiment of this application, when a quantity of empty storage units in an SSD <NUM> is less than a preset threshold, an eviction process of the storage unit may be triggered.

In this embodiment of this application, no specific limitation is imposed on an implementation in which the to-be-evicted target storage unit is selected from the plurality of storage units. In an example, a least recently used (least recently used, LRU) algorithm may be used to move a data block that is stored in the SSD <NUM> but not frequently used out of the SSD <NUM>, so that an internal memory occupied by the data block can be used to load another data block.

Step <NUM>: Read all indexes in the target storage unit.

Referring to <FIG>, in this embodiment of this application, indexes corresponding to all data blocks in the storage unit are consecutively stored in the storage unit. In this embodiment of this application, all indexes in one storage unit can be read at a time. In an example, for one read request, all indexes centrally stored in one storage unit can be read at a time based on a start address and a length. The start address may be an address of the first index in the storage unit, and the length may be a total length of all the indexes centrally stored in the storage unit.

Step <NUM>: Delete all the read indexes from the index table in the internal memory.

In this embodiment of this application, after all the indexes centrally stored in the storage unit are read at a time, all the indexes may be traversed and corresponding indexes in the internal memory DRAM <NUM> may be deleted.

Step <NUM>: Mark the target storage unit as empty.

In this embodiment of this application, after the corresponding indexes in the internal memory DRAM <NUM> are deleted, the target storage unit may be marked as empty. When a write request is read, data can be written into the target storage unit, and an index corresponding to the written data can be added to the index table in the DRAM <NUM>.

In this embodiment of this application, a specific eviction manner of the data blocks stored in the target storage unit is not limited. In an example, the data may be deleted. In another example, the data may be deleted after being stored into the HDD <NUM>. In this example, the first storage serves as a level <NUM> cache. Therefore, the data evicted from the SSD <NUM> (the first storage) needs to be permanently stored in the HDD <NUM> (a second storage). It should be noted that the second storage is not mandatory. For example, the SSD (the first storage) may serve as a permanent storage instead of a cache.

In this embodiment of this application, because the indexes corresponding to the data blocks are consecutively stored in one storage unit, an index corresponding to each data block in all the data blocks can be read through one IO. Therefore, a plurality of data blocks can be evicted through one IO, thereby reducing SSD reads during operation and improving system performance.

Optionally, in some embodiments, the index table cached in the DRAM <NUM> is lost after abnormal power outage or normal start of a node. The SSD cache management system may trigger a recovery process, to recover the indexes cached in the SSD <NUM> to the index table in the DRAM <NUM>. The following describes a specific implementation process in which the cache management system performs the recovery process in detail with reference to <FIG>.

<FIG> is a schematic flowchart of cache recovery according to an embodiment of this application. The method shown in <FIG> may include step <NUM> to step <NUM>, and the following describes step <NUM> to step <NUM> in detail.

Step <NUM>: Read a super block area <NUM> to obtain an identifier of a to-be-recovered slab in the SSD <NUM>.

The SSD cache management system may trigger a cache recovery thread after abnormal power outage or normal start of a node. The recovery thread may read the super block area <NUM> in <FIG> to obtain identifiers of all to-be-recovered slabs in the SSD <NUM>.

It should be understood that to-be-recovered indexes in the DRAM <NUM> are indexes corresponding to KV pairs stored in the SSD <NUM>. Therefore, an identifier of a full slab in the SSD <NUM> can be determined based on information recorded in the super block area <NUM>.

Step <NUM>: Read indexes in the slabs in the SSD <NUM>.

The recovery thread can read the indexes in the slabs in the SSD <NUM>. For example, the index <NUM> and the index <NUM> stored in the slab <NUM> in <FIG> can be read.

Step <NUM>: Traverse all the read indexes and insert the indexes into the index table in the DRAM <NUM>.

After reading the indexes in the slabs in the SSD <NUM> to the DRAM <NUM>, the recovery thread may insert the read indexes into the index table in the DRAM <NUM>. For example, the read index <NUM> and the read index <NUM> stored in the slab <NUM> may be inserted into the index table in the DRAM <NUM>. The following describes a specific implementation of inserting an index into the DRAM <NUM> in detail with reference to <FIG> and <FIG>, and details are not described herein.

Step <NUM>: Determine whether indexes in the last slab have been read.

The recovery thread may repeat step <NUM> and step <NUM> until indexes are recovered in all slabs in the SSD <NUM>.

If the indexes in the last to-be-recovered slab have not been read, step <NUM> may be performed to read the indexes in the slabs in the SSD <NUM>.

If the indexes in the last to-be-recovered slab have been read, step <NUM> may be performed.

In this embodiment of this application, during cache recovery, a plurality of indexes consecutively stored in a slab can be read through only one IO, and the plurality of indexes can be recovered to the internal memory DRAM <NUM>. Because there is no need to read all the slabs in the SSD <NUM>, fast recovery may be implemented.

Optionally, in some embodiments, during cache data writing, data may be first aggregated in the internal memory DRAM <NUM> and then the aggregated data may be written into the SSD <NUM>, thereby reducing internal garbage collection overheads of the SSD <NUM>.

Specifically, referring to <FIG>, in an embodiment of this application, a cache segment may be reserved in the DRAM <NUM>, and managed based on a fixed granularity. In an example, a slab, for example, a slab <NUM>, a slab <NUM>, a slab <NUM>, or a slab <NUM>, may be used as one storage unit to manage data stored in the DRAM <NUM>. After the written data fills up one storage unit in the DRAM <NUM>, the data of the storage unit can be written into one storage unit in the SSD <NUM> at a time. For example, after the slab <NUM> in the DRAM <NUM> is fully written, data stored in the slab <NUM> can be written into the slab <NUM> in the SSD <NUM> at a time.

It should be understood that a slab in the SSD <NUM> may be categorized as follows in terms of state: an empty slab (no KV pair is stored in any KV space in the slab in the SSD <NUM>), a full slab (KV pairs are stored in all KV space in the slab in the SSD <NUM>), and a partially filled slab (a new KV pair in the SSD <NUM> can still be written into the slab).

It should be noted that a data structure of a slab in the DRAM <NUM> is the same as a data structure of a slab in the SSD <NUM>. Each slab may store management information (for example, in <FIG>, the head <NUM> stored in the slab <NUM>), a plurality of centrally stored consecutive indexes (for example, in <FIG>, the index <NUM> and the index <NUM> stored in the slab <NUM>), and a plurality of stored KV pairs (for example, in <FIG>, the KV pair <NUM> and the KV pair <NUM> stored in the slab <NUM>). In an embodiment of this application, after a slab cache in the DRAM <NUM> is full, all data stored in the slab in the DRAM <NUM> can be written into a slab in the SSD <NUM>.

The following describes a specific implementation process of cache data writing in the embodiments of this application in more detail with reference to <FIG>. It should be noted that the example of <FIG> is provided merely for helping a person skilled in the art understand the embodiments of this application rather than limiting the embodiments of this application to a specific value or a specific scenario shown in <FIG>. A person skilled in the art can definitely make various equivalent modifications or changes based on the example shown in <FIG>, and such modifications or changes shall also fall within the scope of the embodiments of this application.

<FIG> is a schematic flowchart of cache data writing according to an embodiment of this application. The method shown in <FIG> may include step <NUM> to step <NUM>, and the following describes step <NUM> to step <NUM> in detail.

Step <NUM>: A cache management system allocates empty KV space.

The cache management system may allocate storage space for to-be-written data when writing data. The cache management system may first attempt to allocate storage space for data from a partially filled slab in the DRAM <NUM>. If there is no partially filled slab in the DRAM <NUM>, the storage space may be allocated for data from an empty slab in the DRAM <NUM>, and the empty slab may be set to a partially filled state.

Step <NUM>: The cache management system determines whether a quantity of empty slabs in the DRAM <NUM> is lower than a water level.

The cache management system may check the quantity of empty slabs in the DRAM <NUM> after the to-be-written data is stored into the internal memory DRAM <NUM>.

If the cache management system determines that the quantity of empty slabs in the DRAM <NUM> is less than the water level (the water level may be a preset quantity of empty slabs), it indicates that cache space in the DRAM <NUM> is insufficient, and data stored in a full slab in the DRAM <NUM> needs to be written into a slab in the SSD <NUM>. In this case, step <NUM> may be performed.

If the cache management system determines that the quantity of empty slabs in the DRAM <NUM> is not lower than the water level, step <NUM> may be performed.

Step <NUM>: Trigger write-back of a full slab in the DRAM <NUM>.

If the cache management system determines that the cache space in the DRAM <NUM> is insufficient, data stored in a full slab in the DRAM <NUM> can be written into a slab in the SSD <NUM>. The full slab in the DRAM <NUM> may be set as an empty slab, and newly written data can continue to be cached in the empty slab.

If the cache management system determines that the quantity of empty slabs in the DRAM <NUM> is not lower than the water level, written KV data can be cached in the allocated KV space in the DRAM <NUM>.

Step <NUM>: Determine whether any index with an identical hashkey is found.

The cache management system may search the index table in the DRAM <NUM> after caching the written data in the DRAM <NUM>.

If an index with a key identical to that of the to-be-written data can be found in the index table in the DRAM <NUM>, it means that the HDD <NUM> has stored data with the key, indicating that the write operation is an update operation. In this case, step <NUM> may be performed.

If an index with a key identical to that of the to-be-written data is not found in the index table in the DRAM <NUM>, it means that the HDD <NUM> has not stored data with the key, indicating that the write operation is a new data write operation. In this case, step <NUM> may be performed.

After determining that the write operation is an update operation, the cache management system may use the new index corresponding to the newly written data to update the original index in the DRAM <NUM>.

After determining that the write operation is a new data write operation, the cache management system may allocate empty index space to the newly written data from the index table in the DRAM <NUM>. For a specific implementation in which a new index is inserted into the index table in the DRAM <NUM>, refer to the description of <FIG> and <FIG>.

After the empty index space is allocated to the newly written data, the index corresponding to the newly written data may be stored into the empty index space.

In this embodiment of this application, an aggregate write request may be used to store the to-be-written data into the internal memory DRAM <NUM> at a granularity of one storage unit. Then, aggregated data may be written into the SSD <NUM>, thereby reducing internal garbage collection overheads of the SSD <NUM>.

Optionally, in some embodiments, in a process of inserting a new index into the index table in the DRAM <NUM>, an empty index needs to be allocated, and a new index can be written into the empty index. A hash index table is used as an example of the index table. In an embodiment of this application, an empty index may first be allocated to the new index from a cuckoo hash table. If there is no empty index that can be allocated in the cuckoo hash table, an empty index may be allocated to the new index from a chained hash table.

<FIG> is a schematic structural diagram of hash tables in an internal memory DRAM <NUM> according to an embodiment of this application. The hash tables shown in <FIG> may include a cuckoo hash table <NUM> and a chained hash table <NUM>.

The cuckoo hash table <NUM> may include a plurality of hash buckets, and each hash bucket may include an array of a plurality of indexes. The index may record hashkeys (for example, a hashkey <NUM> and a hashkey <NUM>) respectively calculated by two hash functions for a key, and an offset of a KV pair in the SSD <NUM>.

The chained hash table <NUM> may include a plurality of hash buckets, and each hash bucket includes a plurality of members (member). Each member has at least one pointer pointing to a next member (the pointer may even be a bidirectional pointer). Each member includes an array of one or more hash indexes, and each hash index records a hashkey and an offset.

In a traditional chained hash table, one member includes one hash index, and each hash index has at least one pointer pointing to a next hash index, leading to relatively high internal memory overheads. In the chained hash table in this embodiment of this application, each member of a hash bucket stores a plurality of indexes, thereby reducing pointer overheads, and in turn reducing internal memory space overheads of the hash table.

The following describes a specific implementation in which a new index is inserted into the index table in the DRAM <NUM> in the embodiments of this application in more detail with reference to <FIG>. It should be noted that the example of <FIG> is provided merely for helping a person skilled in the art understand the embodiments of this application rather than limiting the embodiments of this application to a specific value or a specific scenario shown in <FIG>. A person skilled in the art can definitely make various equivalent modifications or changes based on the example shown in <FIG>, and such modifications or changes shall also fall within the scope of the embodiments of this application.

Step <NUM>: Calculate a hashkey <NUM>, and find a corresponding cuckoo hash bucket <NUM> based on the hashkey <NUM>.

A cache management system may calculate the hashkey <NUM> based on the first hash function. In addition, the corresponding cuckoo hash bucket <NUM> can be found based on the hashkey <NUM>. For example, a modulo operation may be performed on a value of the hashkey <NUM>, and the corresponding cuckoo hash bucket <NUM> can be found based on a result of the processing.

Step <NUM>: Traverse the cuckoo hash bucket <NUM> to determine whether an empty index can be found.

The cache management system may find the corresponding cuckoo hash bucket <NUM> based on the hashkey <NUM>, and may traverse the cuckoo hash bucket <NUM> to determine whether there is an empty index in the hash bucket <NUM>.

If an empty index can be found in the hash bucket <NUM>, step <NUM> is performed.

If no empty index is found in the hash bucket <NUM>, step <NUM> may be performed.

The cache management system may calculate the hashkey <NUM> by using a second hash function. In addition, the corresponding cuckoo hash bucket <NUM> can be found based on the hashkey <NUM>. For example, a modulo operation may be performed on a value of the hashkey <NUM>, and the corresponding cuckoo hash bucket <NUM> can be found based on a result of the processing.

The cache management system may find the corresponding cuckoo hash bucket <NUM> based on the hashkey <NUM>. The cuckoo hash bucket <NUM> may be traversed to determine whether there is an empty index in the hash bucket <NUM>.

Step <NUM>: Find a corresponding chained hash bucket <NUM> based on the calculated hashkey <NUM> or hashkey <NUM>.

After failing to find any empty index in the cuckoo hash bucket, the cache management system may find the corresponding chained hash bucket <NUM> in the chained hash table based on the calculated hashkey <NUM> or hashkey <NUM>, and allocate an empty index in the chained hash bucket <NUM>.

Step <NUM>: Traverse every member of the chained hash bucket <NUM> to determine whether an empty index can be found.

The cache management system may find a corresponding chained hash bucket <NUM> in the chained hash table based on the hashkey <NUM> or the hashkey <NUM>. In addition, every member of the chained hash bucket <NUM> may be traversed to determine whether an empty index can be found.

If an empty index can be found in the chained hash bucket <NUM>, step <NUM> is performed.

If no empty index is found in the chained hash bucket <NUM>, step <NUM> may be performed.

Step <NUM>: Allocate a new chained member.

If the cache management system fails to find any empty index in the chained hash bucket <NUM>, a new member can be allocated in the chained hash bucket <NUM>.

Step <NUM>: Determine whether space allocation is successful.

After allocating a new member in the chained hash bucket <NUM>, the cache management system may determine whether the member is successfully allocated.

If the allocation is successful, step <NUM> may be performed.

If the allocation is unsuccessful, step <NUM> may be performed.

Step <NUM>: Allocate the first index of the member.

If the cache management system successfully allocates a member in the chained hash bucket <NUM>, the cache management system may store a new index into first empty index space of the member.

Step <NUM>: Select the first index of an existing bucket.

If the cache management system fails to allocate a member in the chained hash bucket <NUM>, the cache management system may store a new index into the first index of the existing bucket. The new index may also be stored into other index space based on the index stored in the first index of the existing bucket.

The method for deleting indexes in an internal memory provided in the embodiments of this application is described in detail above with reference to <FIG>. The following describes an embodiment of an apparatus of this application in detail. It should be understood that the description of the method embodiments corresponds to the description of the apparatus embodiment, and therefore, for a part that is not described in detail, reference may be made to the foregoing method embodiments.

<FIG> shows an apparatus <NUM> for deleting indexes in an internal memory according to an embodiment of this application. The apparatus <NUM> may include: a selection module <NUM>, a reading module <NUM>, a deletion module <NUM>, and a processing module <NUM>.

The selection module <NUM> is configured to select a to-be-evicted target storage unit from a plurality of storage units.

The reading module <NUM> is configured to read all indexes in the target storage unit, where all the indexes in the target storage unit are consecutively stored in the target storage unit.

The deletion module <NUM> is configured to delete all the read indexes from an index table in the internal memory.

The processing module <NUM> is configured to mark the target storage unit as empty.

Optionally, in some embodiments, the apparatus further includes: a storage module, configured to store a plurality of data blocks in the target storage unit into the HDD.

Optionally, in some embodiments, the reading module is specifically configured to read, by using a start address and a length, all the indexes in the target storage unit at a time, where the start address is a start address of all the indexes in the target storage unit, and the length is a total length of all the indexes in the target storage unit.

Optionally, in some embodiments, the index table in the internal memory includes a plurality of members, and the members include an index corresponding to each of the plurality of data blocks.

Optionally, in some embodiments, the first storage records information about the plurality of storage units, and the information includes a quantity of the storage units and/or a quantity of storage units in an empty state.

An embodiment of this application further provides a computer program product, where the computer program product includes computer program code. When the computer program code is run on a computer, the computer is enabled to perform the method according to the foregoing aspects.

An embodiment of this application further provides a computer readable medium, where the computer readable medium stores program code. When the computer program code is run on a computer, the computer is enabled to perform the method according to the foregoing aspects.

The aspects or features of this application may be implemented as a method, an apparatus, or a product that uses standard programming and/or engineering technologies. The term "product" used in this application covers computer programs that can be accessed from any computer readable device, carrier, or medium. For example, the computer-readable medium may include but is not limited to: a magnetic storage component (for example, a hard disk, a floppy disk, or a magnetic tape), an optical disc (for example, a compact disc (compact disc, CD), a digital versatile disc (digital versatile disc, DVD)), a smart card, and a flash memory device (for example, an erasable programmable read-only memory (erasable programmable read-only memory, EPROM), a card, a stick, or a key drive). In addition, the various storage media described in this specification may represent one or more devices and/or other machine-readable media for storing information. The term "machine-readable media" may include but is not limited to a radio channel, and various other media that can store, contain, and/or carry an instruction and/or data.

A person of ordinary skill in the art may be aware that the units and algorithm steps in the examples described with reference to the embodiments disclosed in this specification may be implemented by electronic hardware or a combination of computer software and electronic hardware. A person skilled in the art may use a different method to implement the described functions for each particular application, but it should not be considered that the implementation goes beyond the scope of this application.

In addition, the displayed or discussed mutual couplings or direct couplings or communication connections may be indirect couplings or communication connections through some interfaces, apparatuses, or units, and may be implemented in electrical, mechanical, or other forms.

The units described as separate parts may or may not be physically separate. Parts displayed as units may or may not be physical units, and may be located in one position or distributed on a plurality of network units.

In addition, functional units in these embodiments of this application may be integrated into one processing unit, or each of the units may exist alone physically, or two or more units are integrated into one unit.

Claim 1:
A method for deleting indexes in an internal memory, applied to a storage manager, wherein the storage manager comprises the internal memory and communicates with a first storage, wherein the first storage records a plurality of storage units, each storage unit comprises a plurality of data blocks and an index corresponding to each of the plurality of data blocks, the internal memory stores an index table, and the index table records indexes corresponding to data blocks of the plurality of storage units; and the method comprises:
selecting (<NUM>) a to-be-evicted target storage unit from the plurality of storage units;
reading (<NUM>) all indexes in the target storage unit through one I/O request;
deleting (<NUM>) all the read indexes from the index table in the internal memory; and
marking (<NUM>) the target storage unit as empty;
wherein all the indexes in the target storage unit are consecutively stored in the target storage unit.