オープンソースの分散型NewSQLデータベースによるタイムサービス配信の仕組み

※このブログは2022年03月16日に公開された英語ブログ「Time Synchronization in Distributed Systems: TiDB’s Timestamp Oracle」の拙訳です。

著者: Haitao Gao (TiDB contributor)

トランスクリエーター: Fendy Feng; Editor: Tom Dewan

現在のところ、分散型データベースが市場をリードしていますが、分散システムにおける時刻同期は依然として難題です。クロックスキューのため、分散データベースの異なるノードの時刻を完全に同期させることはできません。これまでにもチューリング賞を受賞したレスリー・ランポートによる論理クロック、ハイブリッド論理クロック、TrueTimeなど、多くのコンピュータ科学者が解決策を提示してきました。

PingCAPのTiDBは、オープンソースの分散型NewSQLデータベースで、タイムサービスの配信にTSO（Timestamp Oracle）を採用し、単調に増加するタイムスタンプの割り当てに集中制御サービスであるPD（Placement Driver）を用いています。

本稿では、TiDBのTSOについて、タイムサービスの配信方法とその長所・短所を紹介します。

TiDBのアーキテクチャについて

TiDBのタイムサービスを深く理解する前に、TiDBのアーキテクチャをおさらいしておきましょう。

TiDBは、水平方向のスケーラビリティ、強力な一貫性、高可用性を備えたオープンソースの分散型データベースです。PDクラスタ、TiDBクラスタ、ストレージクラスタ、TiSparkなどの複数のコンポーネントで構成されています。また、これらのコンポーネントは相互に通信し、TiDBシステムを形成しています。

TiDB architecture/TiDB　アーキテクチャ

TiDBデータベースの内部にあるTiDBクラスタは、計算、SQLの解析、ストレージクラスタへのデータ読み込みリクエストの送信を行うためのものです。ストレージクラスタには、TiKVサーバーとTiFlashサーバーがあり、データを保存する役割を担っています。TiSparkは、複雑なオンライン分析処理（OLAP）のクエリに答えるために、TiDBやTiKVの上でApache Sparkを実行するために作られたレイヤーです。

PDはTiDBデータベース全体の「頭脳」であり、今回のトピックの焦点でもあるPDは、以下3つの主要なタスクを持っています：

• TiDBシステム全体のメタデータをリアルタイムに保存および管理
• TiKVとTiFlashノード上のワークロードをリアルタイムにスケジューリングし、バランスをとることが可能
• タイムサービスを配信

TiDBのPDクラスタとTSO

PDクラスタは、通常、複数のPDインスタンス（多くの場合3インスタンス）で構成され、そのうちのPDリーダーが外部サービスを提供します。また、PDクラスタにはetcdストアが組み込まれており、PDの可用性を保証するとともに、メタデータの保存能力を高めています。

PDリーダーがクラッシュした場合、タイムサービスの可用性を確保するために、新しいリーダーが自動的に選出されます。etcdリーダーは、PDリーダーと同じPDインスタンスを共有しているため、リーダー選出中はetcdリーダーがPDリーダーより優先されます。選出プロセスは以下の通りです。

PD Leader election process / PD リーダーの選出プロセス

TiDBのTSOは、集中型ハイブリッド論理クロックを使用して時間サービスを配信しています。時間間隔を表現するために64ビットを使用します。下位18ビットが論理クロックを表し、残りの46ビットが物理クロックを表しています。論理クロックは18ビット構造なので、1秒間に合計2^18 * 1,000 つまり262,144,000のタイムスタンプを生成して割り当てることができます。

続いて、 PDサーバーのTSOがどのように機能するのかを紹介します。ここでは、PDがどのように時刻の校正、配信、繰り上げを行っているかを説明します。

時刻の校正

新しいPDリーダーが選出されたとき、PDリーダーは現在のシステム時刻を知りません。そのため、時刻の校正を行うことが最優先となります。

まず、新しく選ばれたPDリーダーは、前のPDリーダーによってetcdに保存された時刻を読み出します。保存された時刻はTlastと呼ばれ、前のPDリーダーが適用した物理時刻の最大値です。 Tlastを読み出した後、新しいPDリーダーは前のリーダーによって割り当てられたタイムスタンプがTlastより小さくなっていることを知ります。

次に、PDリーダーはTlastとローカル物理時刻であるTnowを比較します。

 Tnow – Tlast < 1 msであれば、現在の物理時刻Tnext = Tlast + 1とします。

それ以外の場合は、Tnext = Tnow。

新PDリーダーがこれらのステップを終えると、時刻の校正が完了します。

時刻の配信

時刻の校正を終了した後、新しいPDリーダーはTSOサービスの配信を開始します。現PDリーダーがダウンした後、次に選出されたPDリーダーが時刻の校正が正常に行えるように、現PDリーダーは時間サービスを配信した後、毎回Tlastをetcdに格納する必要があります。しかし、PDリーダーが毎回そうしていたら、PDのパフォーマンスが大きく損なわれてしまいます。そこで、そのような問題を避けるために、PDリーダーは割り当て可能な時間枠Txをあらかじめ設定しておきます。その初期値は3秒です。

まず、Tnext + Txに等しいTlastをetcdに格納し、次に時間帯 [Tnext , Tnext + Tx] のすべてのタイムスタンプをメモリに割り当てます。

事前割り当ては、etcdストアでの頻繁な操作によるPDの性能低下問題を解決できるものの、PDリーダーがクラッシュした場合、事前に割り当てた多くのタイムスタンプが無駄になるという欠点があります。

クライアント側がTSOサービスをリクエストすると、64ビットのハイブリッド論理タイムスタンプが返されます。この物理的な時間値は校正されたTlastであり、その論理的なクロック値はリクエストと共にアトミックに増分されます。論理クロックが最大値（1 << 18）を超えた場合、50msスリープし、物理時刻の繰り上げを待ちます。 物理時刻が繰り上がった後、まだ割り当てるべきタイムスタンプがあれば、PDリーダーはその割り当てを継続します。

​​TSOサービスのリクエストはネットワーク間で行われるため、ネットワーク帯域の消費を抑えるために、TiDBのPDサーバーはTSOサービスのバッチリクエストに対応します。 

時刻の繰り上げ

タイムサービス中は、PDは論理時刻の増分を通してのみタイムスタンプを割り当てることができます。論理時刻の増分値が上限に達すると、タイムスタンプを割り当てられなくなり、物理時刻を繰り上げる必要があります。

PDは50msごとに現在の物理時間をチェックし、時間を繰り上げます。式によりますと、JetLag = Tnow – Tlast。JetLag > 1 msの場合、ハイブリッド論理クロックの物理時刻は現在の物理時刻より遅れており、Tnext = Tnowになるように繰り上げる必要があります。

また、タイムサービス中に論理クロックが閾値に達した場合、論理クロックが停止して待機してしまいます。そこで、このような事態を防ぐために、現在の論理クロックが閾値の半分を超えると、ハイブリッド論理クロック内の物理クロックも繰り上げるようにしています。そうすると、論理クロックの値は0にリセットされます。

Tlast – Tnext <= 1msの場合、以前に適用されたタイムウィンドウが使い切られたことを意味し、次のタイムウィンドウを適用する必要があります。そこで、PDリーダーはTlast（Tnext＋Txに等しい）をetcdに格納し、新しい時間枠の間もタイムスタンプの割り当てを継続します。 

TSOの長所と短所

TiDBは、集中型クロックソリューションであるTSOを採用しており、これも本質的にはハイブリッド論理クロックです。集中型クロックはシングルポイントタイムサービスを提供するため、すべてのイベントが順序付けされます。また、実装もかなり簡単です。一方、以下のようなデメリットもあります。幸いなことに、そのほとんどに対応するソリューションが用意されています。

• リージョンをまたぐタイムサービス配信時のパフォーマンス低下。この問題を解決するために、PDクラスタは同じリージョンに配置することができます。
• シングルポイント障害。この問題を解決するために、PDクラスタにetcdを組み込み、Raftコンセンサスアルゴリズムを用いてタイムサービスの可用性と一貫性を高めています。
• パフォーマンスのボトルネックの懸念。TSOサービスはPDリーダーによってのみ提供されるため、技術的には将来的にパフォーマンスのボトルネックが発生する恐れがあります。幸い、PD Leaderは1秒間に2億6000万件のタイムスタンプを生成でき、数多くの最適化が施されています。今のところ、パフォーマンスのボトルネックは見当たりません。

TiDBとTSOについて詳細をご要望の方は、PingCAPのエンジニアにお気軽にお問い合わせください。