はじめに
前回 までにおいては、データ処理の並列化方法および宣言型のデータ処理系における問い合わせ最適化について説明してきました。今回と次回の2回では、並列データ処理系において用いられる分散システム技術について述べていきます。まず今回は、分散システムにおける耐障害性のための仕組みであるレプリケーションとロギングについて説明します。
レプリケーションとは
並列データ処理系におけるレプリケーションは、第3回 でも軽く説明したように、データを複数の計算機に保持しておくことにより、システムの耐障害性を保つための技術です。すなわち、データの複製（レプリカ）を複数の計算機で管理することにより、並列データ処理系を構成する計算機の一部が故障した場合や当該システムを構成するネットワークに分断が発生した場合においても、当該システムが管理するデータが失われる（ように見える）可能性を低減することができます。当該技術は、たとえばHadoopなどの並列データ処理系で用いられている分散ストレージであるHDFSなどにおいて用いられています。
レプリケーションでは、レプリカ間において、どのようなタイミングや順序で一貫した値を得ることができるかが重要なポイントの1つであると考えられています。たとえば、複数の計算機の（最新の）状態を見たときに、ある計算機が管理するデータの値はAで、別の計算機が管理する同一データの値はBであり、それが後にAに更新されるという状況を考えてみます。このとき、常に最新情報を必要とするアプリケーションにおいては、どちらが最新の情報であるかを判別することができないため、正しくアプリケーションを記述できない恐れがありますが、読み出すデータは必ずしも最新の情報でなくてよいというアプリケーションにおいては、どちらかから値を取得すればよく、つまり、アプリケーションを正しく記述することができます。一方、ある計算機が管理するデータの値がAであり、別の計算機が管理する同一データの値は必ずAであるような状況が保証される場合においては、双方のアプリケーションを正しく記述することができるでしょう。
このように、レプリケーションの理解においては、複数のレプリカがどのようなタイミングで一貫した値になるかという特性を押さえておく必要があります。当該特性を一貫性（Mutual Consistency）と呼びます。
データベースや分散システムにおいては一貫性という用語が幅広い意味で用いられ、やや誤った用いられ方も見られますので、まず次項において、用語の整理をしておきましょう。
並列分散システムにおける一貫性
並列分散システムにおいて用いられる一貫性（Consistency）はおもに3つがあり、本連載ではそれぞれを次のように命名し定義することとします[1] 。
Mutual Consistency
Transaction Consistency
Database Consistency
Mutual Consistencyは、分散システムのCAP定理におけるCに相当するものであり、上述したようなレプリカ間の値の一貫性を指します。レプリカにおいて「Mutual Consistencyがある」と言うときは、多くの場合、レプリカ間に強い（Strong）一貫性があることを意味します（次項を参照） 。
Transaction Consistencyは、データベースにおけるACIDのIに相当するものであり、複数のトランザクションが並行で実行している場合における一貫性です。トランザクションにおいて「Transaction Consistencyがある」と言うときは、（ 並列分散環境における）複数のトランザクションのグローバルな実行履歴がSerializableであることを意味します。
Database Consistencyは、データベースにおけるACIDのCに相当するものであり、トランザクションにおけるデータベースの一貫性です。トランザクションにおいて「Database Consistencyがある」と言うときは、トランザクションが、データベースをある一貫性（整合性）のある状態から別の一貫性（整合性）のある状態へと変更できることを意味します。
本連載では、レプリカ間の一貫性について議論しますので、一貫性と言う場合は、Mutual Consistencyのことを指すこととします。
さまざまな一貫性
一貫性にはさまざまなものがあり、たとえば次に示すようなものがあります。
Strict Consistency
Strong Consistency（Linearlizability）
Sequential Consistency
Causal Consistency
Eventual Consistency
上のほうが一貫性の度合いがより強く、下にいくに従い一貫性の度合いが弱くなります[2] 。ここでは、Strong ConsistencyとEventual Consistencyについてかんたんに述べておきます。
Strong Consistencyとは、あるデータに対する書き込みがあるときに、当該書き込みよりも“ 後” に当該データを読み出す場合は、（ いずれのレプリカを読み出す場合でもあっても）書き込まれた値が必ず得られる、ということを保証する一貫性です。一方、Eventual Consistencyとは、あるデータに対する書き込みがあるときに、書き込まれた値はいつかは得られる、ということを保証する一貫性です。いつかは得られるということを保証することは難しいですが、とりあえずそのような定義であると考えておいてください。
一貫性の整理ができたので、具体的にレプリケーションの方法を見ていきましょう。
[2] それぞれの一貫性の厳密な定義は本連載では省略します。くわしく知りたい方は、分散システムの教科書（参考文献［1］［ 2］ ）などをご参照ください。また、授業の公開資料 においてもある程度の情報が得られます。これらの一貫性は日本語として正しく翻訳されていないものが多いため、本連載では英語のまま用いることとします。
レプリケーションの方法
レプリケーション方法は、1つの分類として、次の2軸で整理することができます。
データの追加や更新がいつレプリカに伝播するか（Eager or Lazy）
データの追加や更新がどこを起点に発生するか（Centralized or Distributed）
1．は、データの追加や更新が当該処理の確定の段階で伝播するか（Eager） 、その後に伝播するか（Lazy）を表す軸です。すなわち、Eagerの場合は、あるデータの追加や更新を確定する段階において、2相コミット（2 Phase Commitまたは2PC）をはじめとする方法[3] により、当該データのレプリカすべてに同じ値を同期的に適用することにより、当該段階の終了時点（コミット処理が完了した時点）においてはレプリカすべてが同じ値を有することとなります。一方、Lazyの場合は、あるデータの追加や更新を確定する段階において、少なくとも1つのレプリカに最新の値を適用し、その他のレプリカに対しては非同期にその値を適用するため、当該段階の終了時点においては1つのレプリカのみが最新の値を有することとなります。
言い換えると、EagerはStrong Consistencyを保証するレプリケーション方法であり、LazyはEventual Consistencyを保証するレプリケーション方法です。
2．は、データの追加や更新が、まず初めに、中央のサーバ（マスタ）で行われるか（Centralized） 、または、いずれのサーバかで行われるか（Distributed）を表す軸です。
このように整理すると、レプリケーションの方法は（2×2の）4つの方法に分類することができます。それぞれの方法のメリット・デメリットを見てみましょう。
Eager×Centralized
Eagerであるため、Strong Consistencyという多くのアプリケーションにとって都合の良い一貫性が得られる反面、追加や更新にかかる時間（レイテンシ）が長くなる可能性があります。また、Centralizedであるため、データの格納ノードをはじめとするメタデータの管理が簡潔になり、すべての最新データはマスタにあることが保証されますが、マスタへのアクセスが集中し、システム全体のスループットや耐障害性が低くなる可能性があります。
Lazy×Centralized
Lazyであるため、レプリカ間の一貫性はEventual Consistencyになってしまいますが、アプリケーションから見た追加や更新にかかる時間（レイテンシ）が短くなる可能性があります。Centralizedが抱えるメリット・デメリットは上記のとおりです。
Eager×Distributed
Distributedであるため、メタデータの管理が複雑になりますが、アクセスが分散され、スループットと耐障害性が向上する可能性があります。加えて、Eagerであるためレイテンシは長くなる可能性があるものの、レプリカ間の一貫性を保つことができます。
Lazy×Distributed
Distributedであるため、スループットと耐障害性が向上し、また、Lazyであるためレイテンシが短くなる可能性があります。しかし、Eventual Consistentな更新が分散して起きるため、同じデータに対する更新が複数の箇所で同時に起こる可能性があり、すなわち、レプリカ間にコンフリクトが発生する可能性があります。
これらは一長一短であり、当然、アプリケーションによって適切な方法は変わります。
HDFSにおけるレプリケーション
Hadoop処理系で用いられる分散ファイルシステムであるHDFSは、メタデータの管理とデータの管理を分離し、メタデータの管理を中央のサーバ（マスタ）であるNamenodeで、データの管理をスレーブのサーバであるDatanodeで行います。データの追加においては、まずNamenodeに対してファイルエントリの追加を行い、その後、dfs.namenode.replication.min（旧dfs.replication.min）で指定されるノード数までEagerにデータの追加で行い、dfs.replication - dfs.namenode.replication.minのノード数に対してはLazyでデータの追加を行います。すなわち、HDFSは基本的にはCentralizedのアプローチを採用しており、Eager／Lazyにおいては両方を使い分けていると見ることができます。
なお、HDFSにおいては、データの値を更新することはできないため、Eventual Consistencyではあるが古い値を読むことはありません。
HDFSに関する詳細は、書籍『Hadoop Definitive Guide』やHDFS Architecture Guide 、またはHDFS Replication などを参照してください。
データのロギング
レプリケーションのように同じ形式でコピーするわけではなく、異なる形式でデータのコピー保持しておくことにより耐障害性を高める技術として、ロギングと称されるものも存在します。
ロギングには、大きく分けて物理ロギング（Physical Logging）と論理ロギング（Logical Logging）が存在します（［4］ ） 。物理ロギングにおいては、処理中のデータイメージを（別の形式で）二時記憶に保持しておき、当該処理の以降で障害があった場合は、当該イメージを用いて再度処理を行います。一方、論理ロギングにおいては、データを生成するオペレーション（命令）のみを保持しておき、障害があった場合は、障害前のデータに対して当該オペレーションを再度適用し、データを復旧し、処理を再開します。
物理ロギングはデータイメージそのものを保持しておくため、ログのサイズが大きくなる可能性がありますが、その分、障害発生時は当該ログをそのまま用いて次の処理を再開すれば良いため、復旧が速いという利点があります。一方、論理ロギングは、命令列のみを保持するため、ログのサイズは小さくて済みますが、障害発生時は当該命令列を用いて再度データを生成する必要があるため、復旧に時間がかかる可能性があります。
Hadoop MapReduceは、Map処理とReduce処理の間の整列フェーズにおける結果データ（処理全体における中間データ）を二次記憶に書き、Reduceフェーズが何らかの理由で失敗した場合は、当該中間データを用いて再度Reduce処理をやり直します。すなわち、外部ソートの結果を用いて物理ロギングを実現していると見ることができます。一方、Sparkは、RDDと称されるデータの塊を生成するオペレーションをログとして書くことで、すなわち、論理ロギングの行うことにより、中間データが失われた場合においても、当該データの前のデータに対して当該オペレーションを適用することにより、中間データを復旧します（［5］ ） 。
おわりに
少し駆け足でしたが、今回は、分散システム技術を活用した耐障害性のための仕組みとして、レプリケーションとロギングについて説明しました。次回は、複数の計算機における協調動作のための仕組みであるコーディネーション（Coordination）について説明する予定です。
