# Balancing Distributed Key-Value Stores with Efficient In-Network Redirecting
## 4 KVSwitch Design
### Functions in ASIC pipeline
#### 4.2.3 Valid Check and Replica Consistency  
The _Replica Manager_ module is in charge of checking the validation and of maintaining the consistency of replicas across storage servers. For _Get_ hot key queries, it will check whether the replica on the new server assigned in the _Round-Robin_ register array is valid. For _Set_ queries, _Replica Manager_ should update the valid replica flags for this item.  
The _Replica Manager_ module consists of three tables and a _Valid_ register array, as shown in Figure 5b. The _Valid_ register array stores the valid flag for all replicas, such that it has \(M\times K\) cells in total. The _Valid_ register array is segmented into \(K\) parts; from the cell with an index of zero, every \(M\) cell is assigned to represent the replicas of a key on the \(M\) servers. ServermapTable is used for _Get_ queries to obtain the real IP address of the newly assigned server. Both KeyindexTable and ServeroffsetTable help to find the location of the valid flag of a hot item on a specified server in the _Valid_ register. KeyindexTable gives the index of the first register cell belonging to a certain key's replica. The ServeroffsetTable table specifies the offset of the cell belonging to a certain server in the _Valid_ register array.  
Three examples to illustrate the working process of _Replica Manager_ are presented in Figure 5b.  
(1) A _Get_ query for key A sent to the 20 th server containing the corresponding item: ServerMapTable matches the key and index of the server, after which the action parameters (34 and 10.0.0.3) are stored in metadata. The register index 34 denotes the location of the valid bit of the replica on the new destination server in the _Valid_ register array. Since the valid bit in the 34 th cell in the Valid register is 1, the replica of A on server 10.0.0.3 is deemed to be valid. Finally, the new IP address 10.0.0.3 is written into the packet header; thus, this query is redirected. Otherwise, if the valid bit is 0, this packet would be sent to its original destination server without being redirected.  
(2) An update response for key A from server 10.0.0.1: When a server receives an update request for an item (unless it is the original server of the item), it will inform KVSwitch with a reply packet after the update process is finished (Section 4.2.4). This packet from 10.0.0.1 first matches the KeyindexTable and obtains the beginning index in the _Valid_ register of this item (here, 32). ServeroffsetTable then matches the exact server address and returns the stride for this special server (in this case, 0). The final position of the valid bit for this particular item and server is calculated by adding the two results together (in this case, the result is 32). Accordingly, the valid bit in the 32 nd cell is set to 1, which indicates that the replica of A on server 10.0.0.1 is now valid.  
(3) A _Set_ query for key F, sent to its original server 10.0.0.3: In this situation, KeyindexTable is used to obtain the beginning index in the _Valid_ register of this key. Here, the valid register cells for key F start at 0. We then need to locate the register cell for the original server, which is given by ServeroffsetTable (here, this is 2 for 10.0.0.3). Since the _Set_ query is sent via TCP packet, it is reliable in most cases. Thus, KVSwitch sets all replicas to invalid except that on the original server. For this packet, KVSwitch sets all cells with indices from 0 to \(M-1\) to 0 except for the 2 nd cell.  
The processing in ingress pipeline ends here.