# Erasure Codes for Cold Data in Distributed Storage Systems
## 4 Implementation
### Node Schedule  
Data addressing is one of the core technologies of file systems. Local file systems usually use metadata as an index to look up data. Metadata are usually stored on a logical disk or partition. A complete < block number, data > mapping table can usually be created with a simple data structure such as a tree or bitmap. Distributed file systems also require some mechanism for data addressing. If metadata are used for data addressing, the amount  
Figure 7: The architecture of the system.  
of metadata in a distributed file system is so large that it cannot be fully stored on the local disk, requiring a separate node or cluster to store the large quantity of metadata.  
A single node or cluster hosting metadata, while capable of achieving data addressing, has a serious drawback: the node where the metadata resides can become a bottleneck node. This is because all metadata requests are concentrated in a few nodes, which can lead to overloading of these nodes. If some of the metadata nodes lose data, it can seriously affect the performance of the cluster. To avoid this bottleneck, the underlying block storage system in this paper adopts a fully symmetric decentralized ring architecture with a consistent hashing algorithm to locate files in the storage nodes. It no longer has a super node or metadata server, and all nodes have equal status.  
A ring topology is used for storage, and the nodes in the ring are divided into physical nodes and virtual nodes. The relationship between the physical nodes and virtual nodes is many-to-one, i.e., a physical node contains multiple virtual nodes, but a virtual node belongs to only one physical node. The node management module abstracts the physical nodes into multiple virtual nodes according to their storage and computing capabilities and obtains different IDs through consistent hashing algorithms based on the different IP address bits and port numbers of the physical nodes. These IDs are the unique numbers of different virtual nodes. The virtual nodes are evenly distributed to the storage ring according to the ID size. The virtualization of the physical nodes into multiple virtual nodes can play a role in load balancing.  
So, how do we determine the relationship between the data blocks, nodes, and hash spaces? The following is an example, shown in Figure 8. Assuming that the range of the hash space is [0, 100), the ID values obtained by consistent hashing of the virtual nodes \(A\), \(B\), and \(C\) are 0, 30, and 70, respectively, and the IDs along the clockwise direction until the next node is encountered belong to the hash space of this node; then, the hash spaces divided by the three nodes are \(A[0,\,30)\), \(B[30,\,70)\), and \(C[70,\,100)\), respectively. By calculating the consistent hash value of a data block, we can determined in which virtual node the data block should be stored. When a node, say node \(B\), hangs, the hash space is redistributed at that point, and the hash spaces of nodes \(A\) and \(C\) are then \(A[0,\,70)\) and \(C[70,\,100)\). The hash space of node \(B\) is redistributed to \(A\), and at the same time the data on \(B\) are transferred to node \(A\). However, if virtual node \(B\) and virtual node \(A\) are located on the same physical node, then the hash space of \(B\) is not allocated to \(A\) but to \(C\) (assuming that \(B\) and \(C\) are located on different physical nodes).