はじめに

前回までにおいては，データ処理の並列化方法および宣言型のデータ処理系における問い合わせ最適化について説明してきました。今回と次回の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のことを指すこととします。

※1）

教科書や論文においては，必ずしもこの用語を用いていない場合があるためご注意ください。

さまざまな一貫性

一貫性にはさまざまなものがあり，たとえば次に示すようなものがあります。

• Strict Consistency
• Strong Consistency（Linearlizability）
• Sequential Consistency
• Causal Consistency
• Eventual Consistency

上のほうが一貫性の度合いがより強く，下にいくに従い一貫性の度合いが弱くなります（※2）⁠。ここでは，Strong ConsistencyとEventual Consistencyについてかんたんに述べておきます。

Strong Consistencyとは，あるデータに対する書き込みがあるときに，当該書き込みよりも“⁠後⁠”に当該データを読み出す場合は，（⁠いずれのレプリカを読み出す場合でもあっても）書き込まれた値が必ず得られる，ということを保証する一貫性です。一方，Eventual Consistencyとは，あるデータに対する書き込みがあるときに，書き込まれた値はいつかは得られる，ということを保証する一貫性です。いつかは得られるということを保証することは難しいですが，とりあえずそのような定義であると考えておいてください。

一貫性の整理ができたので，具体的にレプリケーションの方法を見ていきましょう。

※2）

それぞれの一貫性の厳密な定義は本連載では省略します。くわしく知りたい方は，分散システムの教科書（参考文献［1］［⁠2］）などをご参照ください。また，授業の公開資料においてもある程度の情報が得られます。これらの一貫性は日本語として正しく翻訳されていないものが多いため，本連載では英語のまま用いることとします。