# EC-Kad: An Efficient Data Redundancy Scheme for Cloud Storage
## 3 Cloud Storage System Model Based on Erasure Code
### Efficient Retrieval of Data Blocks  
In cloud storage systems, after the original data file is encoded, divided into data blocks, and distributed across storage server nodes, retrieving the data file requires searching for the corresponding encoded data blocks among numerous storage service nodes. In traditional simple copy redundancy backup, the search process is relatively straightforward, as locating just one copy is sufficient to fulfill the request. However, under distributed storage redundancy backup using erasure codes, a predetermined number of data blocks must be retrieved to reconstruct the original data file. This imposes high demands on the data block retrieval process. To efficiently retrieve these data blocks, we adopt the peer-to-peer lookup method of the Kademlia protocol and design a fast resource location method based on the same Kademlia process. In a cloud storage system, through the XOR distance metric and the distributed hash table (DHT) characteristics of the Kademlia method, each cloud storage node maintains a routing table (K-Bucket) to hierarchically manage neighboring nodes according to XOR distance. Data blocks processed by erasure coding are hashed to generate a key and are stored on the node closest to the key. The Kademlia lookup process is completed by iteratively querying the nodes closest to the key, which has high query efficiency and dynamic adaptability. Here are some relevant definitions. **Definition 1**. : _Data Block Key: Each data block resulting from the erasure coding of a file generates a unique key through the SHA-1 hash function. The generation method of the key is \(Key_{i}=hash(file\_id+i)\), where \(file\_id\) is the unique identifier of the data file and is the sequence number of the data block after file segmentation and encoding._  
**Definition 2**. : _NodeID: Each storage node generates a unique NodeID through a hash function, and the method for generating NodeIDs is \(NodeID=hash(IP+port)\). Here, \"IP\" and \"port\" are the IP address and port number of the node, respectively._  
**Definition 3**. : _XOR distance: The data blockKey\({}_{i}\) is stored on the node closest to \(Key_{i}\), which is not a physical distance but a logical distance \(d(Key_{i},NodeID)=Key_{i}\otimes NodeID\) calculated through the XOR distance. The smaller the XOR result, the shorter the distance._  
In cloud storage systems, the network topology is divided into multiple buckets by nodes known as K-Buckets based on their own node IDs. Each K-Bucket contains a set of nodes that are similar to the current node. The criterion for these similar nodes is generally the Hamming distance of the node ID, which is the number of differing bits in the binary strings between the node IDs. In the Kademlia protocol, the routing table maintained by nodes is hierarchically organized to manage neighboring nodes based on the XOR distance. The structure of the routing table in the Kademlia protocol consists of the number of K-Bucket layers and the number of nodes in each layer. Regarding the number of K-Buckets, assuming that the node ID is a 160-bit hash space, the K-Buckets are divided into 160 layers, with each layer corresponding to one bit of the node ID. For the number of nodes per layer in the K-Buckets, each layer maintains up to \(k\) nodes (typically \(k=20\)) sorted by XOR distance. The Kademlia routing table structure is shown in Figure 3. The table records all K-Buckets, with a maximum limit of \(k\) nodes per K-Bucket. To locate the target node, we first identify the K-Bucket that is nearest or closest to the target node. If the target node is already within that K-Bucket, then it is directly returned. Otherwise, query requests are sent to the nodes within that K-Bucket, which continue to iteratively search for the target. The search process ultimately converges on the target node, from which the encoded data block is retrieved. Finally, the original data  
Figure 3: Kademlia routing table structure diagram.