MongoDBシャーディングのサンプル実装、及びEtehreum（イーサリアム）Shardingとの比較 #MongoDB

0.目次

はじめに
Sharding（シャーディング）の概要
MongoDBのSharding（シャーディング）動作
MongoDBにおけるSharding（シャーディング）のサンプル実装
MongoDBでSharding（シャーディング）を行う際に考慮すべきこと 6.　　Ethereum（イーサリアム）をはじめとしたブロックチェーンのSharding（シャーディング）

1. はじめに（MongoDBにおけるSharding（シャーディング））

Sharding（シャーディング）は、Ethereumをはじめとしたブロックチェーンをスケーリングさせるための技術として注目されているが、もともと一般的なデータベースを複数のサーバに分散させる機能である。NoSQL構造をとるMongoDBは、開発当初からSharding（シャーディング）をサポートするように設計されているデータベースである。データとその処理の分散を、単一障害点なしに実現することが目指された。

本記事では、ブロックチェーン技術に使われているShardingについて考察するために、データ分散におけるSharding（シャーディング）についてMongoDBを利用しながら述べていく。実装例を見てサンプルを実行しながら、Sharding（シャーディング）のような複雑な仕組みを深く理解し、以下の順に従って考察していく。

Sharding（シャーディング）とは何か。なぜ重要となるのか。
MongoDBではどのように実装されているのか。
MongoDBにおけるSharding（シャーディング）のサンプル実装

2. Sharding（シャーディング）の概要

ブロックチェーンなど、様々な分散システムにおいて、レプリカが用意されるケースはしばしば存在するが、それぞれのレプリカには他のレプリカのデータが全て複製されていることが多い。BitcoinやEthereumをはじめとしたブロックチェーンネットワークにおいてもそれは例外ではなく、実際にBitcoinやEthereumネットワークにマイナーとして参加する全ノード（レプリカ）はどれもブロックチェーンネットワークの全データを保有し処理している。しかしながら、データサイズが大きくなっていき、より頻繁により多くの読み書きのスループットを要求するようになると、処理能力に限界がきてしまう。このような問題に対し、データベースやネットワークを複数のノード群に分散させることが一つの解決策となる。具体的には、Sharding（シャーディング）を行う上でのメリットは以下のようなものがある。

CPUやI/O負荷を分散させる
メモリやストレージの分散によるコストパフォーマンスの向上。必要に応じた容量の追加も可能。（メモリ64GB一枚より、4GB16枚の方が安い。）

Mongodbは、このような仕組みを導入したNOSQL型のデータベースの一つであり、開発当初からすでにSharding（シャーディング）を実現することが目指されていた。特に、既存の仕組みにおいてSharding（シャーディング）は自動で行われるものではなく手動で行うものであり、これを自動化することでより多くのエンジニアがSharding（シャーディング）を実装できるようになったことはMongoDBの大きな特徴であるといえる。

3. MongoDBのSharding（シャーディング）動作

3-1. 用語説明

Shard（シャード）
分散されたデータ群が格納されているmongodプロセスの集合体。

mongosサーバ
Sharding（シャーディング）のルーティングプロセス。mongosのプロセスは、全ての読み書きを適切なShardに振り分けることでシャードとクライアントを連携させる。mongosによって、クライアントからはデータストアが一貫性を持っているように見える。mongosサーバ自体は状態やデータは持っていない。

configサーバ
Sharding（シャーディング）のメタデータを管理するmongodプロセス。各シャード群の正しい状態を確実に保存する役割をもつ。このメタデータには、グローバルなシャード群の設定、各データベースやコレクションの場所、特定の範囲のデータのありか、シャード間のデータの移行履歴が保存される変更ログが含まれる。

また、このメタデータは、シャードを正しく動作させ続けるための中心的な役割をもっており、mongosのプロセスは起動される度に設定サーバからメタデータのコピーをフェッチする。

単一障害点とならないように複数のconfigサーバで構成することが推奨される。configサーバを複数用意する際には、非常に強固な一貫性の保証が要求されるため、2相コミットによって同期が行われる。（詳細は"ブロックチェーンを形作る分散システムにおけるフォールトトレラント性”の記事を参照。）

コレクション
データベースよりも粒度の細かいデータ群。ブロックチェーンではブロックに当たる。

シャードキー
データを分散する範囲のキー。シャードキーをMongoDBが自動調整することで、データの偏りが調整される。

チャンク（chunk）
分散するデータの単位。トランザクション群。

3-2. シャードキーのレンジ（範囲）によるデータ分散

よりイメージを明確にするために、例を踏まえながらSharding（シャーディング）に置いて実際にどのような処理によってデータが分散されるのかを見ていこう。

MongoDBでは、シャードキーを指定することで各サーバに格納されるデータの範囲が定められる。サーバ間で重複データは持たず、１つのデータが格納されるサーバはシャードキーの範囲によって一つに定まる。例えば、以下のようなコレクション（データ群）を持つスプレッドシート管理アプリケーションについて考える。

{
    _id: ObjectID ("34x78rfcnNne3792c")
    filename:"spreadsheet-1",
    updated_at: ISODate("・・・"),
    username: "adam",
    data: "raw document data"
}

ユーザー数が多くなり、MongoDBにおいてSharding（シャーディング）が必要となった場合、上記のコレクションの中からいずれかのフィールドを選んでシャードキーとして宣言する。今回の場合は、usernameとidの複合シャードキーを選択することが適切だろう。シャードキーの範囲で連続しているデータが以下のようなチャンクに分けられる。チャンクの範囲は、開始値及び終了値が付けられており、それぞれのチャンクが各シャードに振り分けられている。

開始値	終了値	シャード
_∞	adam	B
adam	dayton	A
dayton	harris	B
harrsi	norris	A
norris	∞	C

個々のチャンクが値の連続した範囲を表しているにも関わらず、それぞれのチャンクどのシャードに振り分けられても構わないという特徴を持つ。また、チャンクは物理的なものではなく論理的なものである。つまり、上の例でいえば、harrisで始まりnorrisで終わるチャンクがシャードAにあるということは、単にこのシャードキーの範囲にあるドキュメントが全てShardAに保存されているということだけを表し、その順序や連続性は問わない。

3-3.Sharding（シャーディング）におけるチャンクの分割と移行

チャンクの分割と移行は、Sharding（シャーディング）の中心となるメカニズムである。　

MongoDBのSharding（シャーディング）において、チャンクはそのサイズがある閾値を超えたタイミングで自動で分割される。チャンクのデフォルトの最大サイズは64MBもしくは100,000ドキュメントで、どちらかを超えた場合に分割される。

Sharding（シャーディング）のシステムを設計する上で、最も難しいのでは、分割後にデータが常に均等にバランスされるようにすることである。MongoDBの各シャードは、チャンクをシャード間で随時移動させることによってバランスを取る。これは移行と呼ばれ、バランサーと呼ばれるソフトウェアのプロセスによって管理される。バランサーは、各シャード上のチャンク数を追跡し、その差が一定以上になると、最も多い数のチャンクを持つシャードから最も少ない数のチャンクを持つシャードへデータの移行を行う。

3-4. MongoDB上のSharding（シャーディング）実行過程まとめ

ここまで、Sharding（シャーディング）がMongoDB上でどのように行われているのかを説明してきた。簡潔にまとめると以下のようになる。

コレクションというデータ群の生成
フィールどの中からシャードキーを定義してさらに小さなまとまりであるチャンクに分割する
データ量が増える程チャンクが細かく分割されていき、自動で各シャードに振り分けられる
シャード間のチャンク数に偏りが生じた場合、バランサーによってチャンクの移行が行われ均等になる

以上がSharding（シャーディング）の大まかな流れである。

4. MongoDBにおけるSharding（シャーディング）のサンプル実装

本章では、実際にMongoDB上のサンプルを動かしながら、Sharding（シャーディング）を実装していくことでより詳細にSharding（シャーディング）について説明してく。大きな流れとしては、以下の手順でMongoDB上でSharding（シャーディング）が行われていく。

1. 必要なmongodを全て用意し起動する
2. 必要なconfigサーバーを全て用意し起動する
3. mongosを用意し起動する
4. シャードクラスタに各シャードを追加する
5. データベースのシャーディングを有効化する
6. シャードキーを定義してコレクションをシャード化する
7. シャード化されたクラスタにデータを書き込む
8. データ量が大きくなれば、自動で細かいチャンクに分割され、各シャードに振り分けられる
9. シャード間のチャンクの数に偏りが生じればバランサーがチャンクを移行させる

それでは、Sharding（シャーディング）のサンプルを用いながら実際の実装方法を見ていく。今回のサンプルにおけるシャードクラスタは以下のように、二つのシャードA,Bを用意するような構成に定める。

MongoDB IN ACTION (Chapter9 Sharding)

4-1. MongoDB上でのSharding（シャーディング）に必要なmongodを全て用意し起動する。

まず、Sharding（シャーディング）をするにあたって、シャードA,Bとして働く二つのレプリカセット用のデータディレクトリ群を作成する。

$ mkdir /data/rs-a-1
$ mkdir /data/rs-a-2
$ mkdir /data/rs-a-3
$ mkdir /data/rs-b-1
$ mkdir /data/rs-b-2
$ mkdir /data/rs-b-3

ディレクトリを作ることができたら、次にSharding（シャーディング）に必要となるmongodbを起動する。各プロセスに対しそれぞれターミナルウィンドウを用意し、--shardsvrオプションをつけ、どのシャードに配置されるかを設定する。--forkオプションをつければ、バックグラウンドで動かすこともできる。

<レプリカセット1（shard-a)のmongodの起動>

$ mongod --shardsvr --replSet shard-a --dbpath /data/rs-a-1 \
  --port 30000 --logpath /data/rs-a-1.log 
$ mongod --shardsvr --replSet shard-a --dbpath /data/rs-a-2 \
  --port 30001 --logpath /data/rs-a-2.log
$ mongod --shardsvr --replSet shard-a --dbpath /data/rs-a-3 \
  --port 30002 --logpath /data/rs-a-3.log

<レプリカセット2（shard-b）のmongodの起動>

$ mongod --shardsvr --replSet shard-b --dbpath /data/rs-b-1 \
  --port 30100 --logpath /data/rs-b-1.log
$ mongod --shardsvr --replSet shard-b --dbpath /data/rs-b-2 \
  --port 30101 --logpath /data/rs-b-2.log
$ mongod --shardsvr --replSet shard-b --dbpath /data/rs-b-3 \
  --port 30102 --logpath /data/rs-b-3.log

起動ができたら、それぞれのレプリカセットに接続し、rs.initiate()で初期化を行ってから、ノード群を追加していく。

$ mongo localhost:30000
> rs.initiate()

ここで、初期ノードがプライマリになるまで1分ほど待ち、PRIMARYが表示されたら残りのノードを追加していく。

> rs.add("localhost:30001")
> rs.add("localhost:30002", {arbiterOnly: true})

今回の場合、三つ目のノードはアービターでも良い。のちに詳細は説明するが、アービターとは、レプリカセットの設定データのみを保存するので、専用のサーバを用意する必要はない。

二番目のレプリカセットも、上と同じように実行すれば良い。それぞれのレプリカセットのシェルからrs.status()コマンドを実行することで、Sharding（シャーディング）のためのレプリカセットがオンラインであるかどうかや、そのシャード内のメンバーであるmongodの状態を以下のように確認することができる。

shard-a:PRIMARY> rs.status()
{
"set" : "shard-a",
"date" : ISODate("・・・"),
"myState" : 1,
・・・
"members" : [
    {
        "_id" : 0,
        "name" : "localhost:30000",
        "health" : 1,
        "state" : 1,
        "stateStr" : "PRIMARY",
        ・・・
    },
    {
        "_id" : 1,
        "name" : "localhost:30001",
        "health" : 1,
        "state" : 2,
        "stateStr" : "SECONDARY",
         ・・・
・・・
・・・

4-2. MongoDB上でのSharding（シャーディング）に必要なconfigサーバを全て用意し起動する。

mongodが起動されていることを確認できたら、Sharding（シャーディング）の設定に必要なconfigサーバを全て起動する。各configサーバのデータディレクトリを作成し、--configsvrオプションをつけることで起動することができる。

$ mkdir /data/config-1
$ mongod --configsvr --replSet config --dbpath /data/config-1 --port 27019 \
  --logpath /data/config-1.log

$ mkdir /data/config-2
$ mongod --configsvrr --replSet config --dbpath /data/config-2 --port 27020 \
  --logpath /data/config-2.log

$ mkdir /data/config-3
$ mongod --configsvrr --replSet config --dbpath /data/config-3 --port 27021 \
  --logpath /data/config-3.log

それぞれのシェルから接続することで、configサーバが起動しているかどうかを確認することができる。そして、この３台でクラスタを組む。どこか一台に入ってrs.initiate()コマンドで初期化を行い、PrimaryのConfigサーバを作る。

4-3. MongoDB上でのSharding（シャーディング）に必要なmongosを用意し起動する。

mongosは、--configdbオプションをつけて起動しなければならない。設定サーバのアドレス指定にはスペースを入れないようにすること。

$ mongos --configdb config/localhost:27019,localhost:27020,localhost:27021 \
--logpath ./data/mongos.log --port 40000

4-4.MongoDB上でのSharding（シャーディング）に必要なクラスタの設定

Sharding（シャーディング）を行うための構成要素を全て用意し起動することができたため、次にクラスタをSharding（シャーディング）実行の為の設定にしていく。Sharding（シャーディング）のヘルパーメソッドを用い、shオブジェクトによって実行を行う。

sh.addShard()メソッドを用いて、先に作成した二つのレプリカセットをシャードに加える。各セットにおいて、アービターではない二つのメンバーのアドレスを指定している。

$ mongo localhost:40000
> sh.addShard("shard-a/localhost:30000,localhost:30001")
  { "shardAdded" : "shard-a", "ok" : 1 }
> sh.addShard("shard-b/localhost:30100,localhost:30101")
  { "shardAdded" : "shard-b", "ok" : 1 }

以下のコマンドを実行すれば、設定データベース上に登録されているshardの情報を確認することができる。

> db.getSiblingDB("config").shards.find()
{ "_id" : "shard-a", "host" : "shard-a/localhost:30000,localhost:30001" }
{ "_id" : "shard-b", "host" : "shard-b/localhost:30100,localhost:30101" }

4-5.MongoDB上でデータベースのSharding（シャーディング）を有効化する

sh.enableSharding()コマンドによって、MongoDB上のデータベースのSharding（シャーディング）を有効化できる。今回のデータベースはcloud-docsという名前なので、以下のようにSharding（シャーディング）を有効化することができる。

> sh.enableSharding("cloud-docs")

以下のようにコマンドを実行することで、そのデータベースのSharding（シャーディングが
有効になっているかどうか確認することができる。

> db.getSiblingDB("config").databases.find()
{ "_id" : "admin", "partitioned" : false, "primary" : "config" }
{ "_id" : "cloud-docs", "partitioned" : true, "primary" : "shard-a" }

4-6.MongoDB上でSharding（シャーディング）するため、コレクションのシャード化を行う

次にコレクションをシャード化する。今回、コレクションの名前はspreadsheetsとなっている。コレクションをシャード化する際には、シャードキーを定義する。今回のMongoDBにおけるSharding（シャーディング）では、チャンクの範囲がわかりやすく、かつデータをうまく分散できることから、複合シャードキーとして{user- name: 1, _id: 1}を用いる。

> sh.shardCollection("cloud-docs.spreadsheets", {username: 1, _id: 1})

同様に、コレクションのシャード化が設定できているかどうかを確認することができる。

> db.getSiblingDB("config").collections.findOne()
{
  "_id" : "cloud-docs.spreadsheets",
  "lastmod" : ISODate("・・・"),
  "dropped" : false,
  "key" : {
    "username" : 1,
    "_id" : 1
  },
  "unique" : false
}

4-7.MongoDB上でシャード化されたクラスタにデータを書き込んでSharding（シャーディング）を試す

今回のサンプルのデータベースには、以下のように一つのスプレッドシートを表すデータを入れる。各データのフィールドは、_id / filename / updated_at / username / data の５つである。

{
  _id: ObjectId("4d6f29c0e4ef0123afdacaeb"),
  filename: "sheet-1",
  updated_at: new Date(),
  username: "Aaron",
  data: "RAW DATA"
}

今回は、dataフィールドに5KBを挿入したデータを200個用意する為にRubyのスクリプトを用意した。外部ファイルを二つインストールしてから実行すれば、データがMongoDB内のデータベース内に保存される。

load.rb

require 'rubygems'
require 'mongo'
require 'faker'

#<start id="write_docs">
@con  = Mongo::Client.new(['127.0.0.1:40000'], options = {database: "cloud-docs"})
@col  = @con[:spreadsheets]
@data = "abcde" * 1000

def write_user_docs(iterations=0, name_count=200)
  iterations.times do |n|
    name_count.times do |n|
      doc = { :filename => "sheet-#{n}",
              :updated_at => Time.now.utc,
              :username => Faker::Name.first_name,
              :data => @data
            }
      @col.insert_one(doc)
    end
  end
end
#<start id="write_docs">

if ARGV.empty? || !(ARGV[0] =~ /^\d+$/)
  puts "Usage: load.rb [iterations] [name_count]"
else
  iterations = ARGV[0].to_i

  if ARGV[1] && ARGV[1] =~ /^\d+$/
    name_count = ARGV[1].to_i
  else
    name_count = 200
  end

  write_user_docs(iterations, name_count)
end

https://github.com/yodash/mongodb-sharding

$ gem install mongo
$ gem install faker
$ ruby load.rb 1 200

実際にmongosに接続してデータベースを確認すれば、200人分のデータが入っていることを確認することができる。

$ mongo localhost:40000
> use cloud-docs
> db.spreadsheets.count()
200
> db.spreadsheets.stats().size
1019496
> db.spreadsheets.findOne({}, {data: 0})
{
  "_id" : ObjectId("4d6d6b191d41c8547d0024c2"),
  "username" : "Aaron",
  "updated_at" : ISODate("・・・"),
  "filename" : "sheet-0"
}

4-8.MongoDBのSharding（シャーディング）チャンクの分割と移行

次に、データの書き込みを800回行いSharding（シャーディング）が行われチャンクがより細かく分割され、それぞれのシャードに振り分けられていくことを確認する。

$ ruby load.rb 800 200

時間がかかるので、ここでPockyを食べて休みましょう。
次のようにして、データの書き込みが成功したかどうかを確認することができる。

> use config
> db.chunks.count()
21
> db.chunks.count({"shard": "shard-a"})
11
> db.chunks.count({"shard": "shard-b"})
10

今回の場合は、それぞれのシャードに10,11個のチャンクが割り振られていることがわかる。sh.status()コマンドを実行することで、それぞれのシャードとチャンクの情報をより詳細に確認することもできる。
また、以下のようにして、チャンクの分割や移行の様子を確認することもできる。今回のケースでは、チャンクの分割が20回行われており、バランサーによるチャンクの移行が6回行われていることがわかる。

> db.changelog.count({what: "split"})
20
> db.changelog.find({what: "moveChunk.commit"}).count()
6

5. MongoDBでSharding（シャーディング）を行う際に考慮すべきこと

ここまで、Sharding（シャーディング）の実装を実際のサンプルを見ながら説明してきた。本章では、Sharding（シャーディング）の設計を行う際、特に留意すべき点について述べる。これらは、EthereumなどのブロックチェーンにおけるSharding（シャーディング）を行う際にも汎用性のある議論である。

5-1. Sharding（シャーディング）におけるクエリとその種類

Sharding（シャーディング）において、クエリは二種類のものに分けられる。クエリにシャードキーが含まれている対象限定クエリと、含まれていないグローバルクエリである。

シャードキーによってどのシャードに各チャンクが振り分けられるかが定まっていることを思い出して欲しい。つまり、前者のクエリの場合、mongosは高速にどのシャードがクエリの結果セットに含まれるデータを持つのかを探し当てることができるが、後者のクエリの場合、全てのシャードにアクセスしてチャンクを探さなければならない。

また、グローバルクエリを行う際、クエリを行う前にインデックスを生成した方が良い場合もある。例えば、最新のドキュメントをクエリするときに"updated_at: 1"インデックスを生成することで大幅な効率化を測れる。

5-2. Sharding（シャーディング）におけるシャードキーの選択

一度決定したシャードキーは変更できない上に、シャードキーを適切に設定できるかによって、挿入とクエリ（書き込みと読み込み）のパフォーマンスが大幅に左右される。ここでは、Sharding（シャーディング）を行う際に理想的とされるシャードキーの設定方法について議論していく。

まず、不適切なシャードキーとはどのようなものだろうか。

○Sharding（シャーディング）でデータ分散が十分に行われない

例えば、タイムスタンプのような単調に増加するフィールドをシャードキーとした場合を考えてみてほしい。シャードキーが連続した範囲がチャンクとして分けられるため、新しい挿入は全て連続した狭い範囲内で行われることになる。

このような挿入は全て１つのチャンクに回されるということに他ならず、言い換えれば、一つのシャードに負荷が集中してしまうことになる。これは、本来のSharding（シャーディング）の目的を満たさない。
　

○Sharding（シャーディング）上のローカリティの欠如

先に述べたように、増加していくシャードキーは明らかな方向性をもつ。一方、完全にランダムなシャードキーは全く方向性をもたない。前者は分散が不十分となるが、後者は分散させすぎることになり、この場合もSharding（シャーディング）における効率を低下させる。これは直感的にはわからないが、ローカリティを考慮すれば理解できる。

ここでのローカリティの概念は、「ある期間内にアクセスされたデータが多くの場合関連性がある」ということを指す。この近接性はつまり、最適化の余地があるということを意味する。完全にランダムにデータのSharding（シャーディング）を行えば、何度も全てのシャードにアクセスする必要が生まれる。しかし、例えばユーザーIDのような一段階粒度の荒いシャードキーを用いた場合、少数もしくは一つのシャードと通信を行うだけで済み、パフォーマンスを大きく向上させることができる。

○Sharding（シャーディング）内のチャンクが十分に分割できない

シャードキーが粗過ぎると、チャンクの分割が十分にできない場合がある。例えば、ユーザーIDのみをシャードキーに選ぶと、何百万回ものアクセスを行う一人のユーザーがいるかもしれない。この場合、チャンクが分割できず、シャード間のデータや負荷がアンバランスになってしまう恐れがある。

○Sharding（シャーディング）における理想のシャードキー

以上のことを踏まえると、理想のシャードキーがどのようなものかが理解できる。最適なシャードキーとは、以下のような特徴を満たすものである。

挿入がシャード間で均等に分散させられるか
CRUD操作においてローカリティの利点を活かせるか
チャンクが分割可能な粒度であるか

これらの条件を満たすシャードキーは、概して二つのフィールドから構成されるもので、一つ目は粗い粒度、二つ目は細かい粒度のフィールドが選択される。今回の例では{username: 1, _id: 1} という複合シャードキーを使ったが、これは、一人のユーザーがどれだけ大量のドキュメントを作成してもチャンクの分割可能性を保証できるような最適なシャードキーであるといえる。

5-3. Sharding（シャーディング）上でのデプロイメント

プロセスをどのように配置するかも重要な問題である。設定サーバやmongosも含め、全てに独立したマシンを用意しようとすると、非常に多くのコストがかかってしまう。しかしながら、一般的にその必要はなく、以下のような最低限の条件を満たせば一定のフォールトトレラント性を保つことができる。（フォールトトレラント性についての詳細は "ブロックチェーンを形作る分散システムにおけるフォールトトレラント性" の記事を参照。）

一つのシャード及びレプリカセットの各メンバーは、それが完全なレプリカなのか、アービターなのかに寄らず、別々のマシンに置かなければならない。
レプリケーションを行う全てのレプリカセットのメンバーには、専用のマシンを割り当てる必要がある。
レプリカセットのアービターは軽量なので、他のプロセスと共存させても良い。
設定サーバは、マシンを他と共用しても構わない。設定クラスタ中のすべての設定サーバ群は、別々のマシン上になければならない。

例えば、今回のサンプルにおける実装例では、必要なプロセスは9つだったが、以下のように4つのマシンを用意すれば十分である。もし、高い可用性や保守性が求められるようなサービスにおいては、アービターを通常のノードとし、各シャード内に三つのノードを用意することでリカバリが効くようになる。

MongoDB IN ACTION (Chapter9 Sharding)

5-4. Sharding（シャーディング）時の新規シャードの追加

新しいシャードを追加する際は、バランサーによって古いシャードからチャンクを移行して新しいシャードにも割り当てることになる。この時、例えばMondoDBにおいてはバランサーによるチャンクの移行は現状一つずつしか行えないため、多大な時間を要する事になる。Sharding（シャーディング）システム全体が異常をきたさないよう、必要な際は早い段階でシャードを追加することが必要となる。

6. Ethereum（イーサリアム）をはじめとしたブロックチェーンのSharding（シャーディング）

MongoDB上のSharding（シャーディング）との比較しながら、EthereumのようなブロックチェーンでSharding（シャーディング）を行った場合、どのようになるかを考えていく。

6-1. 分散システム × 分散システム

ブロックチェーンとは、様々なノードによってトランザクションを処理する分散システムである。また、Sharding（シャーディング）もこれまで述べてきた通り、データベースをシャードという塊に分割し全体を分散システム化する技術である。つまり、EthereumのようなブロックチェーンでSharding（シャーディング）を行うということは、分散システムを分散システム化するようなものである。

これまでの記事において、分散システム上で一貫性を実現できるような複製や同期、さらにはフォールトトレランス性を保つことの重要性を述べてきたが、そこには複雑性と困難性が伴うことを説明してきた。分散システム × 分散システムを実現するには、より緻密なシステムの設計が必要となる。

特に、暗号通貨のような重要な価値を伴うブロックチェーンを扱う際、二重支払いのようなネットワークの破壊が少しでも生じることは致命傷であり、非常にシビアなフォールトトレラント性が求められることになる。

6-2. ブロックチェーンのSharding（シャーディング）におけるシャード間の通信・同期

MongoDBのSharding（シャーディング）では、ただデータを各シャードに振り分けてデータを保存すれば良かった。しかしながら、ブロックチェーンはアカウントやトランザクション、そしてスマートコントラクトを扱う。これらは、独立したデータとして存在するものではなく、データ同士が有機的に影響を及ぼす事になる。例えば、スマートコントラクトが複数のアカウントにコインの支払いを行う際、しばしばシャードを越えたやり取りが必要となる。

元々、BitcoinやEthereumのようなブロックチェーンでは、分散システム上で同期を行うために、不完全な形ではあるが分散アルゴリズム型に近い排他制御・リーダー選出アルゴリズムに従ってコンセンサスを取っている。ブロックチェーンでSharding（シャーディング）をする場合、通常通りシャード内でコンセンサスアルゴリズムに従った同期通信を行いながら、シャード間でも同期通信を行う必要がある。これがいわゆるシャード間通信問題である。Ethereumでは、ステートの送信によってではなく、ログ情報であるreceiptをやり取りすることによってシャード間通信を行う方針で議論が進んでいる。

6-3. ブロックチェーンのSharding（シャーディング）における単一シャード内の非中央集権化の必要性

また、MongoDBのSharding（シャーディング）では、データの振り分けだけに注意を払えばよかったが、EthereumのようなブロックチェーンのSharding（シャーディング）では、それと同時に各ノードをどのように振り分けるかも重要となる。

通常、ブロックチェーンで二重支払いなどによって改ざんを行うには、PoWの場合はネットワーク全体の計算量の51%が結託する必要がある。大規模なネットワークにおいて、このことは容易ではないがSharding（シャーディング）の場合はそうではない。１００のシャードに分かれているネットワークにおいて、シャード内のデータを改竄するのに必要な計算量は全体のわずか1%でも十分である。

https://medium.com/@icebearhww/ethereum-sharding-and-finality-65248951f649

そのため、Ethereumでは常にコレーターと呼ばれるトランザクションを検証するノードがシャッフルされるような設計が考えられている。Zilliqaにおいても、epochごとにマイナーがシャッフルされ続けるだけでなく、マルチシグを導入したPBFT型のコンセンサスアルゴリズムを取り入れる事でフォークを防ぐような仕組みとなっている。

6-4. ブロックチェーンのSharding（シャーディング）における適切なシャードキーとチャンクの振り分け

ブロックチェーンでのSharding（シャーディング）において適切なシャードキーの設定とはどのようなものだろうか。MongoDBでの適切なシャードキーとは、以下のような特徴を持つものであった。

挿入がシャード間で均等に分散させられるか
CRUD操作においてローカリティの利点を活かせるか
チャンクが分割可能な粒度であるか

ブロックチェーンのSharding（シャーディング）でもこれらの条件は同様である。ただし、ブロックチェーンでは高度なフォールトトレラント性が要求されるため、二重支払いのようなネットワークの破壊を防ぐようなさらなる条件が求められる。

Zilliqaでは、シャードキーの選択について一つの解を出している。送信者のアドレスに基づいてトランザクションを各シャードに振り分けるとしているのである。この時、単一の送信者によるトランザクションは、常に同じシャード内に振り分けられることになる。これによって、シャード内のコンセンサスが明確に取れていれば、シャード間通信が遅れていても二重支払い問題を防止することができる。

ただし、このようなシャードキーの設定では、一人のユーザーのみが一度に大量の書き込み・読み込み操作を行った際に一つのシャードに極端なトランザクションが送られてしまう事になる。このため、MongoDBにおいては、トランザクションのIDとユーザー名の複合シャードキーを設定する事でチャンクを分割可能にしていた。しかしながら、一人の送信者のトランザクションを複数のシャードに分けてしまうと、先ほど触れたように二重支払いの危険性が高まる。ブロックチェーンにおいては、多少効率性を犠牲にしても高いフォールトトレラント性を保つべきであるとする意見が強いと考えられる。

<参考＞

MongoDB IN ACTION

https://livebook.manning.com/#!/book/mongodb-in-action/chapter-9/1

Ethereum wiki Sharding

https://github.com/ethereum/wiki/wiki/Sharding-introduction-R&D-compendium

Zilliqa Whitepaper

https://docs.zilliqa.com/whitepaper.pdf