C/C++で実装するバークレーアルゴリズム――分散システムの時刻同期を徹底解説

バークレーアルゴリズムとは

バークレーアルゴリズム（Berkeley's Algorithm）は、分散システムにおいて各ノードの時計を同期させるために用いられるアルゴリズムです。特に、以下のような状況にあるシステムで有効とされています。

• マシンに正確な時刻源が存在しない場合
• ネットワークやマシンにUTCサーバーが用意されていない場合

分散システムとは、物理的に離れた場所に配置された複数のノードが、ネットワークを介して相互に接続されたシステムのことを指します。各ノードの時計は独立して動作しているため、誤差が生じやすく、何らかの同期機構が必要になります。

バークレーアルゴリズムの仕組み

このアルゴリズムでは、まずシステム内のノードの中から1つをマスターノード（リーダーノード）として選出します。選出は、サーバーのプールノードの中から行われます。

アルゴリズムの基本的な流れは以下の通りです。

• 選挙（Election）プロセスによって、サーバー内のマスターノードが決定されます。
• リーダーノードは、クリスチャンのアルゴリズム（Cristian's Algorithm）と同様の方法でフォロワーノードに時刻を問い合わせます。この処理は定期的に実行されます。
• リーダーノードは、各ノードから受け取った時刻の平均値をグローバル時計時刻とし、各ノードがそれに同期するために必要な相対的な補正値を計算します。

時計同期の手順（具体例）

バークレーアルゴリズムによる時計同期の手順を、具体的な数値例で確認してみましょう。

分散システム内の各ノードと、それぞれの時計が示す時刻は以下の通りです。

N1 → 14:20（マスターノード）
N2 → 13:46
N3 → 14:15

ステップ1： リーダーノードが選出されます。ここではノードN1がシステムのマスターノードとなります。

ステップ2： リーダーノードが全ノードに対して現在の時刻を要求します。

N1 → 時刻：14:20
N2 → 時刻：13:46
N3 → 時刻：14:15

ステップ3： リーダーノードが各時刻の平均値（14:02）を算出し、その平均に一致させるための補正後の時刻を各ノードへ送り返します。

N1 → 補正後の時刻 14:02（-18分）
N2 → 補正後の時刻 14:02（+16分）
N3 → 補正後の時刻 14:02（-13分）

このように、バークレーアルゴリズムを利用することで、分散システム内のすべてのノードの時計を、互いの平均時刻に基づいて同期させることができます。

バークレーアルゴリズムの特徴

• クリスチャンのアルゴリズムがUTCサーバーへのアクセスを前提とする「外部同期」であるのに対し、バークレーアルゴリズムはネットワーク内部のノード同士だけで時計を揃える「内部同期」アルゴリズムです。
• マスターノードは、大きく外れた時刻データ（外れ値）を破棄することで、故障したノードや誤動作するノードの影響を軽減できます。
• 平均値を基準とするため、個々のノードが持つ時計の誤差が平準化され、システム全体として一貫性のある時刻が維持されます。