# Balancing Distributed Key-Value Stores with Efficient In-Network Redirecting
## 4 KVSwitch Design
### Functions in ASIC pipeline
#### 4.2.5 Time-Segmented Top-K Key Tracker  
KVSwitch uses the HashPipe data structure [21] to efficiently track the Top-K most popular cold keys in each time interval. HashPipe takes advantage of the high throughput of the ASIC pipeline to count the packets without sampling. Here, hot keys are not considered, since the HotkeyTable has a counter for each entry and thus every hot key query is counted accurately.  
HashPipe consists of a list of \(d\) hash tables such that each table \(j\) has a unique hash function \(h_{j}\). Moreover, each table has \(w=K/d\) slots; thus, a Hashpipe can track a total of the \(K\) hottest keys. The tables in HashPipe are implemented using registers, meaning that it is possible to inspect every query for a cold key since the control plane is not involved when the tables are changed. A hash table has two register arrays, each of which has \(w\) elements, used to store the key and associated count respectively.  
The basic idea behind HashPipe is to insert the newly arrived key into tables and to remove the key with the smallest counter. In this way, HashPipe is able to retain the \(K\) cold keys with bigger counters. To accomplish this, each query for cold items contains the lowest counter ever seen and the corresponding key in metadata, which flows through the tables in HashPipe.  
For a KVS query of a cold item, HashPipe first treats it as a new key that has never been seen before. The key of this packet, along with a counter-value of 1, is written into metadata. At each hash table \(j\), the key carried with the current packet is hashed by \(h_{j}\) to the slot \(l_{j}\). If the key matches in slot \(l_{j}\) (i.e., the \(l_{j}\) element in register array), then the count in \(l_{j}\) is updated by adding the count being carried in the metadata. Alternatively, if the slot is empty, the carried key and count are stored in this slot. Both situations above end the processing of HashPipe. Otherwise, the key and count corresponding to the larger of the counters that is carried and the one in the slot are written back into the table, and the smaller one is carried on the packet to the next hash table. Through this process, keys with larger counters are saved, while those with smaller counters are weeded out.  
Consider a newly arrived packet with a counter of one. It is possible that, in each hash table, this packet will find a larger count in the slot. As a consequence, this key will not be retained in HashPipe. The next packet of this key will then undergo the same process, which means this key will be neglected. To prevent this, HashPipe chooses to always insert the key in the first table and to evict the existing key and counter to metadata, thus ensuring that this key has been taken into consideration.  
An example that illustrates how HashPipe works is presented in Figure 6[21]. A packet with a key \(K\) and counter of 1 enters the HashPipe and is hashed to slot 2 in the first table. Since this is the first table, \(K\) is inserted and \(B\) is carried in metadata. In the second hash table, key \(B\) is hashed to theslot containing key \(E\); however, since the count of \(B\) is larger than that of \(E\), \(B\) is written into the slot and \(E\) is carried out in metadata. Finally, since the count of \(L\) (which \(E\) hashes to) is larger than that of \(E\), \(L\) stays in the table and \(E\) is dropped (as this is the last table). The net effect is that the new key \(K\) is inserted in HashPipe and the minimum of the three keys \(B\), \(E\), and \(L\) is evicted.