はじめに
OpenStack SwiftやAmazon S3などのオブジェクトストレージの業務利用は珍しくなくなってきました。これらのオブジェクトストレージでは、データの可用性を保証するために、オブジェクトの複製を複数のディスクや拠点に保存しています。OpenStack Swiftの設定ガイドでは3つの複製を異なるディスクに作成する例が紹介されています。Amazon S3では2拠点までの障害に耐えられると言われているため、3つの複製を異なる拠点に保存していると考えられます。すなわち、これらのオブジェクトストレージでは、保存するデータのサイズの3倍のストレージ容量が必要となると言えます。
IBM Cloud Object Storage (以下、COS)とは2015年10月にIBMが買収したCleversafeをベースとしたオブジェクトストレージです。IBM COSが必要とするストレージ容量は保存するデータの1.6倍、すなわちOpenStack Swiftなどのオブジェクトストレージと比較して約47% ($= 100 \times (1 - \frac {1.6}{3})$) ストレージ容量を削減できるそうなのです。どのような仕組みでストレージ容量を削減できるのか調査したところ、英文のホワイトペーパーを見つけました。この記事では、これらのホワイトペーパーから読み解いたIBM COSの仕組みについて解説します。
#IBM Cloud Object Storage概要
IBM COSの構成は以下の図のように二層になっているそうです。Slicestoreと呼ばれるノードはオブジェクトのデータを管理します。Accessorと呼ばれるノードはあるオブジェクトのデータがどのSlicestorのどのディスクに保存されているかを管理します。また、Manager Softwareと呼ばれるソフトウェアを適当なノードにインストールし、全体を監視します。
OpenStack Swiftも同様の二層の構成になっており、Object Nodeがオブジェクトのデータを管理し、Proxy NodeがObject Nodeのどのディスクデータが保存されているかを管理しています。ただし、Swiftの場合はオブジェクトの複製を3つのディスクに保存しているため、保存したいデータの3倍の容量が必要になります。ではIBM COSではどのような仕組みで1.7倍の容量としているのでしょうか？その肝となる技術はInformation Dispersal Algorithmと呼ばれています。
#Information Dispersal Algorithmとは
読者の皆様は中学校の数学の授業で連立方程式を習ったことがあるかと思います。また、連立方程式の変数の数が$K$個ある時、その方程式が解ける条件は式の数が$K$個以上あること、と習ったことを覚えている方もいるかと思います。この連立方程式が解ける条件について覚えていれば、Information Dispersal Algorithmは簡単に理解することができます。
下の図が、Information Dispersal Algorithmの概要になります。まず、事前にデータをいくつの塊に分割して保存するかを決めておきます。この分割の数を$K$（下の図の例では$K=5$）とします。また、データをいくつのディスクに分散して保存するかも決めておきます。このディスクの数をN（下の図の例では$N=8$）とします。ここで、$K$と$N$の値を決める時に$K<N$とする必要があります。では、これからデータをIBM COSに保存するときの内部の流れを追ってみましょう。
まず、IBM COSがあるデータの書き込み要求を受け取ると、Accessor nodeがデータを$K$個の塊に分割します。上の図の例では、5個の塊に分割し、それぞれ$a, b, ..., e$という値を持つとします。ついで、事前に準備しておいた$N \times K$個の連立方程式の係数と$K$個の値を掛け合わせ、$N$個の値を計算します。上の図の例では$8 \times 5 = 40$個の係数を事前に準備し、8個の値$s_1, s_2, ..., s_8$を算出しています。最後に、$N$個の値をそれぞれSlicestor nodeの異なるディスクに保存します。また、そのデータがどのSlicestor nodeのどのディスクに保存されているか、Accessor nodeが覚えておきます。以上がIBM COSにデータを保存するときの処理の流れです。では、IBM COSからデータを読むときの流れはどうなるのでしょう。
IBM COSがあるデータの読み出し要求を受け取ると、そのデータがどのSlicestore nodeのどのディスクに分散されて保存されているか、Accessor nodeに問い合わせます。ついで、$N$個のデータをそれぞれのディスクから読み出します。上の図の例では$s_1, s_2, ..., s_8$の値が読み出されます。最後に、事前に用意していある連立方程式の係数と読み出した値から、$K$個の変数を求め、元のデータを得ることができます。上の図の例では、8個の連立方程式から5個の変数$a, b, ..., e$を求めています。
ここで、最初に述べた変数が$K$個ある方程式が解ける条件を思い出してください。変数が$K$個ある方程式が解ける条件は、方程式が最低$K$個あることです。すなわち、仮に$N-K$個のディスクが壊れてしまった場合でも、$K$個の方程式を作ることができるので、元のデータを復元することができます。
さて、Information Dispersal Algorithmの何が嬉しいのでしょう。私の理解では、IBM COSの管理者がデータの冗長度合いとそのデータの保存に必要なストレージ容量のバランスを柔軟に調節できる、という点にあると思っています。$N$と$K$を使って説明すると、$N$の値が大きくなるほど$N-K$の値は大きくなり、多くのディスクが壊れてもデータを復元することができるため、耐障害性は向上します。一方で、そのデータを保存するのに必要なストレージ容量も大きくなります。逆に、$N$の値が小さくなり$K$の値に近づくほど、耐障害性は低下しますが必要なストレージ容量は小さくなります。OpenStack Swiftなどのオブジェクトストレージでは、耐障害性を上げるためにはデータ全体のコピーを異なるディスクにとっておく必要があるため、冗長度を上げると必要なストレージ容量は2倍、3倍と増えていきます。これに対して、IBM COSでは例えば先の$N=8$かつ$K=5$の例の場合、保存するデータのサイズに対して1.6倍（$=8/5$）のストレージ容量を用意すればよく、より細かい粒度で容量を決めることができます。
#まとめ
以上が、ホワイトペーパーから読み取れるIBM COSの仕組みの紹介になります。その肝となる部分は中学校レベルの数学の知識があれば理解できる内容ですが、それをストレージに適用するという発想や、その方法が非常にスマートであるように思いました。IDAというアルゴリズムは30年近く前に提案され、論文も公開されているようです。今後は公開されている論文を読み、より深く内容を理解したいと思います。