# Research on Multicore Key-Value Storage System for Domain Name Storage
## 3 Model Description
### Cache Replacement Algorithm  
We have designed a hybrid replacement algorithm that mixes FIFO and LRU. This algorithm combines the advantages of LRU and FIFO buffers, reducing the use of locks as much as possible. Each cache sub-table is divided into three partitions: the hot partition, the temporary storage partition, and the recycle partition. FIFO rules are used internally in hot partitions, which follow the first-in-first-out principle.  
Figure 4: Schematic diagram of cache table split.  
Figure 5: LRU data structures.  
When the cache item is written to the cache table for the first time, the cache item is first written to the temporary storage partition. In addition, the flag bit of the cache item is set to 0. If the cache item in temporary partition is hit again, the flag bit of the cache item is set to 1. If the cache item cannot be found in the cache table at this time, the operation is performed the same way as the first time the cache item is written. We describe our implementation of the replacement algorithm in Algorithm 1.  
```
1:item, command;
2:item.
3:\(flag\_item=0\)
4:functionCache_replacement(item, command)
5:ifwrite then
6:if item in cache table then
7:if item in hot partition then
8:return
9:elseif item in temporary partition then
10:if\(flag\_item=0\)then
11:\(flag\_item=1\)
12:else
13: remove item from temporary partition
14:insert item to hot partition
15:endif
16:elseif item in recycle partition then
17: remove item from recycle partition
18:insert item to hot partition
19:endif
20:else
21:insert item to temporary partition
22:endif
23:elseif read then
24:if item in cache table then
25:if item in hot partition then
26: Return item
27:insert item to hot partition
28:elseif item in recycle partition then
29: remove item from recycle partition
30:insert item to hot partition
31:endif
32:endif
33:endif
34:endif
35:endfunction
```  
**Algorithm 1** Cache replacement  
The three partitions in the cache table are used to store different cache items. At the same time, a flag bit is set to indicate whether the cache item enters the current partition for the first time. In this situation, 0 means that the partition is entered for the first time, and 1 means that the cache item has been hit after entering the partition.  
When the item is cached for the first time, it will be stored in the temporary partition. When it is hit for the second time, only the flag is set to 1. The cache item is moved to the hot partition on the third hit. If it has not been hit in the temporary partition, the cache entry is deleted. No operation is performed when the cache item in the hot partition is hit again. When the hot partition is full, the last cache item is moved to the recycle partition instead of deleted directly. The recycling partition is used to store cache items eliminatedby the hot partition temporarily. When the cache item in the reclaimed partition is hit again, the cache item is returned to the hot partition. However, when the cache items in the recycling partition are eliminated, they are eliminated directly. This ensures that the cache items in the hot partition cannot be easily eliminated, and the hit rate of the cache table is guaranteed. In the temporary partition, the cache item is hit three times before being moved to the hot partition. This is a separate design for the DNS request-response parsing scenario. It is also possible to change the cache item in the temporary partition to be moved to the hot partition after being hit twice. The hit mentioned in our article can be either a read operation or a write operation.