Percolator
酢ろう調べている理由
TiDBのトランザクション処理がどのように実装されているのか気になり調べていたところ、Percolatorの仕組みを利用していると書いてあったため
このスクラップの目的
こちらの論文を読んで理解する。
理解できなかった用語を調べてメモする。
概要
『Percolator』の由来
コーヒーを淹れる器具。
沸騰させ、徐々にコーヒーフィルターを通す。
Percolatorとは
大規模データセットの更新を「段階的に」行うシステム。
Googleでは検索インデックスを更新するために利用。
酢ろう1 Introduction
まとめ
ペタバイト級のデータを並列性と不変性を保ちながら処理するために、MapReduceでは不十分であったためPercolatorを開発した。
Percolatorは一連のオブザーバーとして実装されており、上流タスクが終了すると次の下流タスクが実行されるような仕組みになっている。オブザーバーの最初のトリガーは、最初のテーブル書き込みとなる。
用語
MapReduce
大規模データを処理する方式
- Mapで分割
- Reduceで処理を行い、結果を統合する
ランダムアクセス
データストレージにおいて、任意の位置にあるデータに直接アクセスできることを指す
シーケンシャルアクセスと対になる概念。
Percolatorは、ペタバイト級のデータに対する従来の処理方式「MapReduce」と異なり、任意のデータへのアクセスを可能にする。
インクリメンタル処理
大きなタスクを小さなタスクに分割し、順番または並行に処理すること。
酢ろう2 Design（前おき）
まとめ
Percolatorは、「大規模データ処理が必要なこと」と「レイテンシへの厳しい要求がないこと」によって、利用できる技術である。
Percolatorワーカー、Bigtableタブレットサーバー、GFSチャンクサーバーの関係性。
用語
GFSチャンクサーバー
GFS（Google File System）
分散ファイルシステム。
ファイルを「チャンク」と呼ばれる固定サイズブロックに分割。これらのチャンクを複数のチャンクサーバーに分散して保存する。
ファイルシステムの冗長性と信頼性を向上させる。
Bigtableタブレットサーバー
Bigtable: Googleの分散ストレージシステム。
タブレットサーバーはBigtableのデータを効率的に処理する。
タブレットは、Dynamoでいうシャードのような位置付けっぽい？
スナップショット分離
データベースのトランザクションが同時に行われても、それぞれのトランザクションが他のトランザクションの途中型をを見ることなく一貫したデータの状態を見れるためのもの。
各トランザクションはタイムスタンプをKeyとしたスナップショットを対象としており、他で更新があっても影響を受けない。
酢ろう2.1 Bigtable
まとめ
PercolatorはBigtable上に構築されており、Bigtableのインターフェースを維持しつつ、Percolatorとして必要なトランザクション・オブザーバーを提供する。
用語
Bigtable
ワイドカラム型のNoSQLデータベース
Bigtable全体のアーキテクチャは以下を見た方が早い
SSTable
Sorted String Table
酢ろう2.2 Transactions（途中まで）
- ~~
We’ll now consider the transactionの前まで - なかなか本題に入れないので、飛ばす
まとめ
Bigtableでは行を跨ぐトランザクションを提供しておらず、これはPercolator側で実装する必要がある。
PercolatorのロックはBigtable上で管理されている。そのためデータマネジメント専用のノードは不要である。
用語
クロスロウ・クロステーブルトランザクション
トランザクションが複数行、複数テーブルにまたがって行われること
canonical
正規の~~という意味。
webの文脈で言うと、同じコンテンツが二つのURLにある場合、正規のものをcanonical-urlとする。
バックオフ
「バックオフ」は、ネットワーク通信やソフトウェアエンジニアリングのコンテキストでよく使われる用語で、何らかの操作が失敗した後に次の再試行までの待機時間を増やす戦略のことを指す。
バックオフ戦略は、再試行間隔を一定に保つ固定バックオフと、再試行ごとに間隔を増やす指数バックオフの2つの主要な形式がある。
Bigtableのトランザクション
「行をまたがるトランザクション」
行をまたがないトランザクションは存在する？
↓
1レコードの中で1フィールドのみ更新され他フィールドの更新が失敗する、という自体があれば、一行単位のトランザクションが失敗していることになる。
BigTable タイムスタンプディビジョン
Bigtableでは、各データ項目（セル）はタイムスタンプとともに保存される。
書き込みスキュー
書き込みスキュー（Write Skew）は、同時に実行される複数のトランザクションが、同じデータを読み取った後で異なる更新を行うときに発生する現象。
感想
どこまで行けば、「連続した更新」の話が出てくるのかな...？
酢ろう2.3 Timestamps
まとめ
- タイムスタンプオラクルは厳密な順序で増加するタイムスタンプを返すサーバーである
- 異なるシャード間でタイムスタンプの厳密性を担保することは非常に重要。
- タイムスタンプを取得することで、Transactionを制御できる。
用語
タイムスタンプオラクル
ここでは、タイムスタンプを返すサーバーのことを指している。
システムの世界で、hoge oracleというと、「絶対的に信用できる」という意味を持つことがあり、今回でいうと 信頼できるタイムスタンプを返すサーバーのことになる。
他にも、 test oracle といった用語がある。
オラクルに対して1つの保留中のRPCのみを維持する
各ワーカーがオラクルに対して一度に一つのRPCリクエストだけを送信し、その応答を待つ、という意味。複数のリクエストが送られることはない。
ロックの関係性
Timestampを基準にすることで、Writeのロック取得よりあとにReadが走った場合、ロックが解放されるまで読み取りを待つことになる。
フロー。タイムスタンプオラクルは図上では省略。