
migration occurs. Although an alternative RAID-4 scaling
scheme can reduce the number of data blocks to be moved
by migrating certain blocks to newly added disks [31], the
RAID-4 scaling scheme suffers from a very expensive cost
of parity updates during new data filling. Traditional
RAID-5 scaling schemes are based on round-robin layout. If
these RAID-5 scaling schemes are deployed in RS-coded
storage clusters, then the clusters will inevitably encounter
high I/O overhead incurred by data migrations and parity
updates. The parity layout of each RAID-6 code is unique;
RAID-6 scaling techniques designed for a specific RAID-6
code are inadequate for RS-coded storage clusters. In short,
there is a wide application gap between RAID scaling
schemes and cluster scaling.
In this study, we design an efficient cluster scaling
scheme called Scale-RS, which exploits the structural prop-
erties of erasure codes to optimize both data migrations and
parity updates. Scale-RS not only makes the total number of
moved data blocks equal to the lower bound of data migra-
tion traffic, but it also minimizes the data movement
induced by parity updates.
1.4 Roadmap
The remainder of this paper is organized as follows.
Section 2 summarizes the preliminaries of this study. The
design of Scale-RS is detailed in Section 3. Section 4
describes the experimental settings and results. Section 5
surveys the related work of storage scaling schemes. Sec-
tion 6 discusses implementation issues. Finally, we con-
clude our work in Section 7.
2PRELIMINARIES
Recognizing that RS codes are widely deployed in in-pro-
duction storage systems (see Table 1), we investigate scaling
schemes for RS-coded storage clusters in this study.
2.1 Update Penalty in RS-Coded Storage Clusters
There is an update penalty issue in erasure-coded storage
systems [37], [10], [38]—modifying any data block leads to
updates of corresponding parity blocks. There exist two
updating methods, namely, reconstruction write (a.k.a.,
RCW) [39] and read-modify-write (a.k.a., RMW) [40]. In the
‘RMW’ updating method, parity block P
row;j
in parity chunk
PC
j
is updated to P
row;j
þ DP
row;j
when data block D
row;i
in
data chunk DC
i
is changed to D
0
row;i
, where parity difference
block DP
row;j
equals to a
j;i
(D
0
row;i
D
row;i
), and coefficient a
j;i
denotes an element at the jth row and the ith row of a
redundancy matrix.
In cluster scaling
<k!kþDk>
, all r parity chunks should be
updated when Dk new data chunks join a (k þr, k) RS-
coded chunk group. If Round-Robin method [26], [34] is
adopted, almost all data blocks will be migrated, and all
parity blocks must be regenerated using the encoding pro-
cedure. Therefore, we should consider the following two
issues when designing the Scale-RS scheme: (1) how to min-
imize the number of migrated data blocks, and (2) how to
reduce the data movement induced by parity updates.
2.2 Categories of Cluster Scaling
One cluster scaling process can be logically divided into two
stages: data redistribution and data filling. Data redistribu-
tion is a composite operation—apart from migrating data
blocks, all associated parity blocks should be updated
accordingly. Therefore, there exist the following three clus-
ter-scaling patterns from a methodological point of view
(see Table 2):
(1) No Data-Migration (No-DM). No data migration is
involved in the No-DM-based scaling scheme, which only
places Dk new nodes into a storage cluster, resulting in zero
migration overhead. In the data filling stage, new data is
filled into new chunks and associated parity blocks are
updated.
TABLE 2
Scaling Categories of Erasure-Coded Chunk Groups
1706 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 6, JUNE 2015