Title: Sequential Checking: Reallocation-Free Data-Distribution Algorithm for Scale-out Storage,
Abstract: Using tape or optical devices for scale-out storage is one option for storing
a vast amount of data. However, it is impossible or almost impossible to
rewrite data with such devices. Thus, scale-out storage using such devices
cannot use standard data-distribution algorithms because they rewrite data for
moving between servers constituting the scale-out storage when the server
configuration is changed. Although using rewritable devices for scale-out
storage, when server capacity is huge, rewriting data is very hard when server
constitution is changed. In this paper, a data-distribution algorithm called
Sequential Checking is proposed, which can be used for scale-out storage
composed of devices that are hardly able to rewrite data. Sequential Checking
1) does not need to move data between servers when the server configuration is
changed, 2) distribute data, the amount of which depends on the server's
volume, 3) select a unique server when datum is written, and 4) select servers
when datum is read (there are few such server(s) in most cases) and find out a
unique server that stores the newest datum from them. These basic
characteristics were confirmed through proofs and simulations. Data can be read
by accessing 1.98 servers on average from a storage comprising 256 servers
under a realistic condition. And it is confirmed by evaluations in real
environment that access time is acceptable. Sequential Checking makes selecting
scale-out storage using tape or optical devices or using huge capacity servers
realistic.