DevSecOps

TiKVとは？

モダンなデータベース管理システム向けに高いパフォーマンスを発揮する分散ストレージをお探しなら、TiKVが有力候補です。この製品の可能性は非常に高く、CNCFに2018年に受け入れられ、プロジェクトの成熟度において卒業レベルに達しています。

本記事では、TiKVの特徴や仕組みを幅広くご紹介します。

TiKVの名前の由来

このプロジェクト名は「チタン（Titanium、Ti）」に由来しています。開発者は元素の特性を意識し、「KV」は主に使われるキーと値を指します。発音は「タイ・ケイ・ヴィー」です。

製品概要

TiKVは拡張性、極めて低いレイテンシー、そしてシンプルさを重視して設計された分散型キー・バリュー・データベースです。他の類似ソリューションと異なり、既存の分散ファイルシステムへの依存が少ない点が特徴です。また、Google SpannerやHBase、F1と同様の機能を実現することを目指しています。

‍

アーキテクチャ

上のイメージはこのソリューションの主要なコンポーネントを示しています。ここでは、それぞれを簡単にご説明します。

Regions: 最も基本的な単位で、キーと値の範囲および移動に関する概念です。Regionsは複数のノードにコピーされ、それぞれを「Peer」と呼びます。複数のPeerをまとめてRaftグループと呼びます。
‍Node: クラスタ内のエンドポイントです。これは物理的な装置（例: デバイス）であり、そこに複数のStoreがあり、さらに複数のRegionを含みます。
‍Placement Driver: PDと略され、TiKVシステム全体の中核となるコンポーネントです。NodeやRegionのマッピング、Storeに関するメタデータを保持し、ロードバランシングやデータの保存場所に関する決定を行う役割を担います。
‍Store: 各Storeはローカルディスクを使ってデータを保存し、RocksDBを用います。

プロトコル

前のセクションではTiKVのコンポーネントを取り上げました。これらのコンポーネントは互いに通信しながら動作し、その中でProtocol Buffer Protocolが使われます。ただしRustはgRPCとの互換性がないため、TiKVでは独自にプロトコル形式を定義しています。

それぞれの通信は1つまたは複数のメッセージを交換することで行われ、メッセージ形式はHeader + Payloadです。

ここで、PayloadにはProtocol Bufferのデータが含まれており、ヘッダに指定された長さを持ちます。そのため最終的なメッセージやペイロードはヘッダ情報をもとに読み取り、適切にデコードされます。

kvprotoというプロジェクトにはTiKVの通信を行うためのプロトコルが実装されています。もう一つのプロジェクトtipBにはプッシュダウンのアルゴリズムが含まれています。

TiKVアーキテクチャをより深く知りたい場合は、kvprotoの下記ファイルが参考になります:

metapb.proto: TiKVのPlacement Driver(PD)で必要になる情報がすべてまとまっています。Peer、Store、Region、Raftなどに関するメタデータが含まれています。
‍pdpb.proto: TiKVとPDが相互通信する際のプロトコルです。
‍msgpb.proto: 内部のTiKV同士でやりとりするメッセージはすべて同様の流れをたどりますが、MessageTypeが識別子として使われます。
‍raftpb.proto: etcdから移植されており、Raft(この記事の後半で解説)に不可欠です。etcdと一致している必要があります。
‍coprocessor.proto: 後ほど述べるコプロセッサが、TiKVでプッシュダウンを実行する仕組みをサポートします。
‍raft_serverpb.proto: Raftノード同士がスムーズに通信するためのものです。
‍mvccpb.proto: 内部でMVCCを扱うためのファイルです。
‍raft_cmdpb.proto: Raftを実装するときに使われるコマンドを定義しています。
‍kvrpcpb.proto: TiKVトランザクションを制御するキーと値のプロトコルをまとめたファイルです。

貴社の外部プロジェクトでTiKV APIを活用したい場合、次のファイルを使用してください:

‍raft_cmdpb.proto: 基本的なKey-Value機能のみ必要な場合に利用します。

kvrpcpb.proto: トランザクション型のKV機能が必要な場合に利用します。
coprocessor.proto: プッシュダウンの機能が必要な場合に利用します。

‍

Raft

Raftは多くのシステムで採用されるアルゴリズムで、高いパフォーマンスやフォールトトレランスを得るのに役立ちます。TiKVではこの合意アルゴリズムを用いて分散システムでの一貫性を高められるようにしています。貴社のプロジェクトで必要に応じて利用できます。

Raftが選ばれた理由は、実装が比較的容易で、実運用にも向き、高い実用性と移行のしやすさを備えているからです。TiKVでのRaftは、etcdから完全に移植されています。

‍TiKVプロジェクトでRaftを使う方法を知りたいですか？次のステップをご参照ください。

ストレージの詳細情報（HardStateとConfStateなど）は、この関数で返されます。

fn initial_state(&self) -> Result<RaftState>;

このステップでは、lowからhighの範囲内にあるログエントリを返します。

fn entries(&self, low: u64, high: u64, max_size: u64) -> Result<Vec<Entry>>;

指定したログインデックスに対応するログエントリのtermを取得します。

fn term(&self, idx: u64) -> Result<u64>;

// 4. 現在位置における最初のログエントリのインデックスを取得

fn first_index(&self) -> Result<u64>;

// 5. 現在位置における最後のログエントリのインデックスを取得

fn last_index(&self) -> Result<u64>;

// 6. 現在のスナップショットを生成し、返します

fn snapshot(&self) -> Result<Snapshot>;

Step 1: ここでは、Raftのストレージ特性を定義し、デプロイします。

Step 2: 初期状態に関する設定（構成やハードウェア/ストレージ）を渡すために、RawNodeオブジェクトを作成します。

configデータでは、election_tickやheartbeat_tickなど定期的に行われるtickが重要です。リーダーはハートビートの頻度を設定し、heartbeat_tickの値がこのしきい値に達すると、フォロワーにハートビートを送信し、経過時間をリセットします。

フォロワー側では、election_tickによって選挙の経過が監視され、しきい値に達すると選挙(合意形成)が開始されます。

Step 3: RawNodeが生成された後は、たとえば100msごとなどのtick間隔で、このノードのtickインターフェイスが繰り返し呼ばれます。

Step 4: TiKVのRaftでデータを書き込みたい場合、Proposeインターフェイスを呼び出します。このとき任意のバイナリ形式データをパラメータとして渡すと、それが複製されます。データの取り扱いは外部ロジックに委ねられます。

Step 5: メンバーシップを変更する必要がある場合は、propose_conf_changeインターフェイスを使います。RawNodeからConfChangeオブジェクトを送ることで、特定ノードの追加や削除などを行えます。

Step 6: TickやProposeのような関数が呼び出されると、Raftは該当するRawNodeの状態をReadyにします。これには3つの意味のいずれか、または複数が含まれます:

RawNodeに送信すべきメッセージがある。
RawNodeにエントリやハードステート、スナップショットがあり、Raftストレージに保存する必要がある。
RawNodeにコミット済みエントリ(committed_entries)があり、他のステートマシンへ適用する必要がある。

Raftはこれらの状態を処理し終わると、Advance関数を使って次のノードまたはプロセスにReady状態を通知します。

TiKVではMioというRustライブラリを使ってRaftを利用しています。手順は以下のとおりです:

Raft用にベースとなるtickタイマー(例:100ms)を設定し、タイマーが切れるたびに再登録してRawNodeのtickを呼び出す。
Mioを利用して外部コマンドを受け取り、notifyという関数が呼ばれたらProposeやpropose_conf_changeなどのインターフェイスを呼ぶ。
Mioのtickコールバック（イベントループの終了時など）でRaftの準備状況を確認し、もしReadyなら処理を開始する。

これらのステップはすべてのRaftグループに対して行われます。それぞれのグループは独立して動作し、特定のRegionに紐づきます。

SplitとMerge

TiKVの起動直後は、(-inf, +inf)という範囲を持つ1つのRegionだけが存在します。最初のSplitはデータが64MBのしきい値に達したときに行われます。その後もSplit Keyに基づいてリピートされ、必要に応じて新たなRegionが作られます。

TiKVのロードマップにはMergeプロセスもありますが、まだ実装が進行中です。将来的には、データ量が少ない隣接するRegionをまとめてより大きいRegionとする仕組みが考えられています。

‍

Placement Driver

先に述べたように、PDはTiKVクラスタの中枢となる存在です。クラスタの高い一貫性と可用性を確保する責任を担っています。

高可用性の実現

PDは制御の中心点であるため、単一障害点になりうる可能性があります。これを避けるため、複数のPDサーバーを起動し、その中から1つをリーダーとして選出します。リーダー選出にはetcdの選挙メカニズムが使われ、公平に進行します。

選出されたリーダーは外部との通信を担当し、サービスを提供します。障害などで応答しなくなったときは、同じ選挙プロセスにより別のリーダーが選ばれます。

高い一貫性の実現

リーダーがダウンして別のリーダーに切り替わる場合、その新リーダーが最新のデータを持ち、一貫性を保てるかどうかが問題です。

この対策として、PDのデータはetcdに保存されます。etcdは分散型のKVストアなので、データの一貫性を保証できます。新しいPD（リーダー）はetcdにあるデータを取得して動作します。

以前のバージョンでは外部のetcdサービスが必要でしたが、現在のバージョンではPDがetcdに組み込まれており、高速かつシンプルでパフォーマンスも高くなっています。

現在のPlacement Driverの主な役割は以下のとおりです:

TSO (TimeStamp Oracle)サービスを用いて、TiDBの分散トランザクションで使う一意のタイムスタンプを生成する。
TiKVやPDのハートビート、または定期的なトリガーによって、tiKVの各Regionを自動的にバランシングする。
新しいTiKVストアやRegionに一意のIDを払い出す。

‍

トランザクション

TiKVのトランザクション機能は、GoogleのPercolatorやXiaomi - Themisに着想を得ています。しかし、TiKVのモデルは若干異なり、最適化を加えています。主な違いは以下のとおりです:

PercolatorではTSOタイムスタンプサービスが単調増加のタイムスタンプを割り当てます。TiKVでも同様ですが、TSOはPD上で行われ、情報はetcdに定期的に記録され、メモリ操作として扱われます。
RocksDBのカラムファミリー(CF)を使ってLock情報を管理します。TiKVではLock処理の速度や同時操作を高めるため、追加のカラムCFを利用できます。
余分なCFを利用することで、取り残されたLockを見つけやすくし、クリーニングも容易にします。
同時に動く複数のトランザクションはTSOで決まるタイムスタンプ系列を使います。競合などが発生した場合は、外部クライアントによって早期終了や中断が行われる可能性があります。

TiKVでのトランザクションが動作する大まかな流れは、以下のとおりです:

クライアントはトランザクション(t1)を開始すると同時に、TSOからstartTS（即時のタイムスタンプ）を取得します。
t1が進行する間、TiKVはリクエストを処理します。読み取り操作はstartTSより前に書かれたデータのみ取得します。書き込みは楽観的な並行制御方式で行われるため、クライアント側でキャッシュし、コミット時点まで他のトランザクションや実データに影響を与えません。
コミットはプリライト(Prewrite)と最終コミットの2段階で行われます。専用のトランザクションマネージャーはなく、プライマリキーがクォーラムによってコミット可能と判断された段階で処理が始まります。

Pre-write: クライアントは更新対象のデータを複数のTiKVサーバーに送ります。衝突があればトランザクションは中断・ロールバックされます。問題がなければTSOから新たなタイムスタンプ(commitTS)を取得し、次のフェーズへ進みます。
Commit: 受信したリクエストにはPrimaryKeyが含まれており、TiKVはcommitTSのタイムスタンプを使ってデータを書き込み、対応するLockを解放します。コスト最適化のため、トランザクションt1に関わる他のキーも非同期で書き込みます。

‍

コプロセッサ

この概念はHBaseで使われている仕組みと似ていますが、TiKVのコプロセッサは動的ロードではなく静的に処理されます。主な役割はTiDB TiKVをサポートする場面で、Splitやプッシュダウンのシナリオに効果を発揮します。以下に具体的な例を示します:

Splitリクエストでは、SplitKeyの妥当性を確認する必要があります。なぜなら、Region分割前にTiDBの行に新バージョンが発生する可能性があり、そのキーが別のRegionに移動する恐れがあるからです。SplitコプロセッサはSplitKeyを必要なRegionに移しておき、分割時にキーをスムーズに扱えるようにします。
プッシュダウンリクエストでは、TiDBのパフォーマンス向上に寄与します。たとえば単純なSELECT COUNT(*)のようなクエリを各ノード側で計算して結果をまとめ、TiDBが最終的に返すことで効率を高めます。

手順はざっくり以下のようになります:

TiDBがテーブルの範囲(例:t1)に合わせてSQLをパースします。
データが必要なのはRegion1とRegion2だけだと判明したので、それらに対してのみプッシュダウンを行います。
各RegionはRaft経由で自分のデータのスナップショットを取得します。
両方のRegionがスナップショットを走査し、count()の値を計算します。
TiDBは両方の結果を合計してクライアントに返します。

‍

主要な手順の概要

TiKVがGETやPUTリクエストをどのように処理しているか、あるいはレプリカをどう更新するかなどを簡単に見ていきます。

キーと値の操作

TiKVには、シンプルな操作、プッシュダウン付き、トランザクション型の3種類が存在します。リクエストの性質によって使い分けますが、現在は最終的にすべて単純なKV操作として扱われています。

たとえばPUT操作(k1, v1)が行われる場合の流れは以下のとおりです:

クライアントからPutコマンド(k1 v1など)が送られる。
最初にk1が属するRegion IDを取得します。同時にPDリーダーから対応するRegionのPeer情報を入手します。
クライアントは2で得た情報を使い、該当TiKVノードにPutリクエストを送ります。
TiKVサーバーはリクエストを受け取ると、Mioチャンネルを使って内部のRaftStoreスレッドに通知します。チャンネルはコールバック関数を介してTiKVサーバーに行動を指示します。
RaftStoreスレッドはリクエストが正当かを確認し、受信したRegionのリーダーPeerを見つけます。Peerが合った場合、リクエストをバイナリエンコードし、Proposeインターフェイスを呼び出してRaft処理を開始します。
エントリが準備完了になると、Raftログには新規エントリが追加され、同時に他のフォロワーに転送されます。
大多数(Region内)のノードがエントリを受け入れて追記すると、コミットが行われます。こうしてコミットされたエントリはcommitted_entriesリストに入り、デコードされてRocksDBに書き込まれます。
リーダーがエントリログを適用し終わると、エントリのコールバックが呼ばれ、クライアントへレスポンスが返ります。

GETリクエストの場合も同様のフローをたどります。つまり、Raftノードの大多数で複製されることで、分散システムとしてデータのリニアライズ性を保ちます。

TiKVのRaftではフォロワーが読み取りサービスを提供する仕組みや、リーダーがleaseを活用してRaftログを介さずに読み取りを行う提案もあります。これらの提案はTiKVのパフォーマンスを最適化する目的があります。

‍

メンバーシップ変更

TiKVのStoreは、データのサイバーセキュリティを高めるために複数の複製（レプリカ）を用意しています。これらのレプリカはPeerとして扱われ、Region内に配置されます。もしRegionに必要な数のレプリカが不足していれば新たに追加し、多すぎる場合は削除します。

このレプリカの増減を扱うのがTiKVのRaftメンバーシップ変更機能で、タイミングや変更内容はPDによって制御されます。

イメージとしては、PDがマネージャー役で、Membership Changeが実際に働くアクターという関係です。

具体例で流れを見てみましょう:

PDは定期的にすべてのRegionからハートビートを受け取ります。Peerや各種データを含む情報が送られます。
PDは受け取った情報を見て、各Regionのレプリカ数が設定どおりかを確認します。
たとえばあるRegionがレプリカ5つ必要だが、ハートビートでは4となっていた場合。PDは適切なStoreを見つけ、そのRegionに対して「ChangePeer」コマンドを送信します。
該当のRegionは、Peerが不足していると判断すると、Raftを通じてChangePeerリクエストを提案します。ログが適用されればRegionのメタ情報に新しいPeerが追加され、Membership Changeが完了します。

注意: この時点ではRegionのメタ情報にレプリカが追加されたことが反映されただけです。もしリーダーが新しいフォロワーにデータがないと判断した場合は、そのフォロワーへスナップショットを送ります。

注意2: Raftの論文では、TiKVやetcdのMembership Changeの実装方法とは少し異なる手順が書かれています。そこではPropose時点でRegionのメタにPeerが追加されますが、TiKVやetcdではログ適用時にPeerが追加される形をとっています。