guide:glossary@ja

ガイド

用語集

Zanzibar の論文で出会うすべての用語を平易に説明し、それを解説するガイドページと論文の節を示す。

事実確認日

用語は英語名のアルファベット順に並べる。論文の設定言語に出てくるコード名 (_this、computed_userset、tuple_to_userset) は、アンダースコアを除いて並べる。例には共通の例を使う。Anne、Beto、Chen、folder:A の中の doc:readme、group:eng である。

A–C

ACL
アクセス制御リスト。あるオブジェクトに対してある操作を許されたユーザーの集合である。Zanzibar では ACL は 1 つのリストとしてではなく、多数のリレーションタプルとして格納される。詳細: アクセス制御モデル、§1、§2.1。
aclserver
Zanzibar の主要なサーバーの種類。Check、Read、Expand、Write に応答し、作業をクラスタ内の他の aclserver にファンアウトする。詳細: アーキテクチャ、§3。
少なくとも同じだけ新しい (at-least-as-fresh)
zookie の規則。Zanzibar は zookie のタイムスタンプちょうどのスナップショットだけでなく、それより古くない任意のスナップショットで評価してよい。この自由があるので、ほとんどのリクエストをローカルのレプリカから処理できる。詳細: 一貫性、§2.2。
有界な古さ (bounded staleness)
スナップショット読み取りは「現在」より古くてもよいが、ある上限より古くてはならない。Zanzibar ではその上限はクライアントが送る zookie である。Spanner はこれを直接提供しており、クライアントが古さの上限を与え、Spanner がタイムスタンプを選ぶ (Spanner の論文、§4.1)。詳細: 一貫性、§2.2。
キャッシュスタンピード (cache stampede)
キャッシュされていない同じ結果に対する多数の同時リクエストが、キャッシュが埋まる前に一斉にストレージへ向かうこと。Zanzibar はロックテーブルでこれを防ぐ。論文はこの用語の出典として Wikipedia の記事 を挙げている (参考文献 [3])。詳細: アーキテクチャ、§3.2.5。
変更ログ (changelog)
タプル更新の履歴を保持する Spanner データベース。各タプル書き込みと同じトランザクションで書き込まれる。Watch はここから読む。詳細: アーキテクチャ、§3.1.2。
Check
ユーザーがユーザーセット ⟨object#relation⟩ に含まれるかを問う API 呼び出し。たとえば「Chen は doc:readme の閲覧者か」。与えられた zookie より古くないスナップショットで評価される。詳細: リレーションタプル、§2.4.4、§3.2.3。
computed_userset
同じオブジェクト上の別の関係のユーザーセットを取る、書き換えルールの葉。たとえば「すべての編集者は閲覧者である」。詳細: リレーションタプル、§2.3.1。
コンシステントハッシュ (consistent hashing)
サーバーを追加・削除しても、ごく一部のキーしか移動しないようにキーをサーバーに割り当てる方法。Zanzibar はこれを使ってキャッシュエントリをクラスタ内のサーバーに分散させる。Web キャッシュのために Karger ら (STOC 1997) が導入した。詳細: アーキテクチャ、§3.2.5。
コンテンツ変更チェック (content-change check)
ユーザーが新しい内容を保存しようとするときに送る Check。zookie を持たず、最新のスナップショットで評価され、クライアントが新しいコンテンツバージョンとともに格納する zookie を返す。詳細: 一貫性、§2.2、§2.4.4。

D–H

非正規化 (denormalization)
平坦化したグループ間のメンバーシップのような派生データを、元の行から計算する代わりに、事前に計算したコピーとして格納すること。Zanzibar はストレージでは非正規化を避け、Leopard でのみ用いる。詳細: Leopard、§3.2.4、§3.2.5。
除外 (exclusion)
書き換えルールの演算子。あるユーザーセットに含まれ、別のユーザーセットには含まれないユーザー。詳細: リレーションタプル、§2.3.1。
Expand
書き換えルールをたどり、⟨object#relation⟩ の実効的なユーザーセットを木として返す API 呼び出し。葉はユーザー ID またはユーザーセット、中間ノードは和集合、積集合、除外である。詳細: リレーションタプル、§2.4.5。
外部一貫性 (external consistency)
更新 x が更新 y より前に起きたなら、2 つがシステムの外で調整された場合でも、x には y より小さいタイムスタンプが付く。Zanzibar はこれを Spanner から得ている。論文はこの用語の出典として Gifford の 1981 年のスタンフォード大学の博士論文を挙げている (参考文献 [18])。Spanner はこれを「T1 が T2 の開始前にコミットするなら、T1 のコミットタイムスタンプは T2 のものより小さい」と述べている。詳細: 一貫性、§2.2。
ファンアウト (fan-out)
1 つのリクエストが多数のサブリクエストに分かれること。たとえば aclserver が Check の一部をクラスタ内の他のサーバーに送る場合である。詳細: アーキテクチャ、§3、§3.2.5。
ハートビート zookie (heartbeat zookie)
各 Watch レスポンスに含まれ、ストリームがどこまで進んだかを示す zookie。クライアントはそこから再開できる。詳細: §2.4.3。
ヘッジ (hedging)
最初のサーバーが遅いとわかった時点で同じリクエストを 2 台目のサーバーに送り、先に届いた応答を使って、もう一方をキャンセルすること。Zanzibar がヘッジするのは Spanner と Leopard への呼び出しであり、自身のサーバー間の呼び出しではない。この技法は Dean と Barroso の 「The Tail at Scale」 (CACM、2013) で説明されている。詳細: アーキテクチャ、§3.2.7。
ホットスポット (hot spot)
他よりはるかに多くのトラフィックを受け、それを格納するサーバーを過負荷にしうるキー、オブジェクト、グループ。たとえば多くの ACL で共有される人気のグループである。詳細: アーキテクチャ、§3.2.5。

I–N

積集合 (intersection)
書き換えルールの演算子。複数のユーザーセットのすべてに含まれるユーザー。詳細: リレーションタプル、§2.3.1。
Leopard
深く入れ子になったグループや非常に大きいグループのためのインデックスシステム。グループメンバーシップを整数の集合に平坦化してメンバーシップチェックを積集合の演算に変え、Watch によって最新の状態を保つ。詳細: Leopard、§3.2.4。
ロックテーブル (lock table)
処理中の読み取りとチェックを記録する、サーバーごとの表。キャッシュキーを共有するリクエストのうち実行されるのは 1 つだけで、残りはその結果を待つ。詳細: アーキテクチャ、§3.2.5。
ロックタプル (lock tuple)
クライアントがオブジェクトへの書き込みのたびに更新する通常のリレーションタプル。これにより、読み取り以降に誰も書き込んでいないことを条件に書き込みを行える。詳細: §2.4.2。
名前空間 (namespace)
クライアントが定義するオブジェクトの種類。doc や folder など。doc:readme のコロンより前の部分である。各名前空間のタプルはそれぞれ専用のデータベースに置かれる。詳細: リレーションタプル、§2.1、§2.3、§3.1.1。
名前空間設定 (namespace config)
1 つの名前空間の設定。その関係 (それぞれに省略可能なユーザーセット書き換えルールが付く) と、シャーディングなどのストレージパラメータから成る。詳細: リレーションタプル、§2.3、§3.1.3。
「new enemy」問題 (new enemy problem)
ACL から削除された人に内容を見せてしまうこと。チェックが 2 つの ACL 変更の順序を無視したり、内容より古い ACL を適用したりすると起きる。詳細: 一貫性、§2.2。

O–R

オブジェクト (object)
保護される対象。⟨namespace⟩:⟨object_id⟩ と書き、たとえば doc:readme である。詳細: リレーションタプル、§2.1。
Paxos
一部のレプリカが故障しても、レプリカのグループが各書き込みに合意できるようにする合意プロトコル。論文では、Paxos トランザクションが速くコミットするよう、Zanzibar のストレージの 5 つの投票レプリカを互いに 25 ms 以内の距離に置いている。Lamport の 「Paxos Made Simple」 (2001) を参照。詳細: アーキテクチャ、§3.1.4。
ポインタ追跡 (pointer chasing)
ユーザーセットを 1 ホップずつたどって Check に答えること。readme の閲覧者から group:eng#member へ、次にそのグループのメンバーへ、という具合である。グループが深いか大きいと遅くなる。詳細: リレーションタプル、Leopard、§3.2.3、§3.2.4。
Read
1 つ以上のタプルセットにマッチする格納済みのタプルを返す API 呼び出し。書き換えルールは適用しない。詳細: リレーションタプル、§2.4.1。
Recent リクエスト (Recent request)
Safe / Recent リクエスト を参照。詳細: 一貫性、§4.1。
関係 (relation)
オブジェクトとユーザーの間、または 2 つのオブジェクトの間 (parent がドキュメントをそのフォルダに結ぶように) の名前付きの関係。owner、viewer、member、parent など。名前空間設定で定義する。詳細: リレーションタプル、§2.1、§2.3。
リレーションタプル (relation tuple)
格納された 1 つの事実。⟨object⟩#⟨relation⟩@⟨user⟩ と書き、たとえば doc:readme#owner@user:anne である。Zanzibar が格納する権限データはこれだけである。詳細: リレーションタプル、§2.1。
レプリカ (replica)
ある場所に置かれたデータのコピー。Zanzibar のデータは数十の場所に複製されており、ほとんどの読み取りを近くで処理できる。詳細: アーキテクチャ、§3.1.4。

S

Safe / Recent リクエスト (Safe / Recent requests)
論文による、zookie の古さに基づくリクエストの分類。Safe リクエストは 10 秒より古い zookie を持ち、通常はリージョン内で処理できる。Recent リクエストはそれより新しい zookie を持ち、しばしばリージョンをまたぐラウンドトリップを必要とする。詳細: 一貫性、§4.1。
シャード (shard)
別々に格納・提供される、データベースやインデックスの一部分。タプルのシャード ID は通常オブジェクト ID から決まり、非常に大きいグループではオブジェクト ID とユーザーから決まる。詳細: アーキテクチャ、§3.1.1、§3.2.4。
スナップショット読み取り (snapshot read)
ある 1 つのタイムスタンプ時点のデータベースをそのまま見る読み取り。そのタイムスタンプ以前のすべての書き込みが見え、それより後の書き込みは見えない。Zanzibar は各 Check を単一のスナップショットで評価する。Spanner はこれを “a read in the past that executes without locking” (ロックをとらずに実行される過去の時点の読み取り) と定義している (Spanner の論文、§4.1)。詳細: 一貫性、§2.2。
Spanner
Google のグローバル分散データベース。Zanzibar はタプル、名前空間設定、変更ログをこれに格納し、一貫性をそのタイムスタンプに依存している。Corbett ら、OSDI 2012 で説明されている。詳細: 一貫性、アーキテクチャ、§2.2、§3。

T

テールレイテンシ (tail latency)
99 パーセンタイルや 99.9 パーセンタイルのような、最も遅いリクエストのレイテンシ。検索結果の 1 ページに数十から数百のチェックが必要になりうるため重要である。Dean と Barroso の 「The Tail at Scale」 (CACM、2013) を参照。詳細: アーキテクチャ、§1、§3.2.7、§4.2、§4.5。
_this
このオブジェクトと関係について、格納されたタプル中のユーザーを返す書き換えルールの葉。それらのタプルが指すユーザーセットも含む。関係にルールがない場合のデフォルトである。詳細: リレーションタプル、§2.3.1。
タイムスタンプの量子化 (timestamp quantization)
評価タイムスタンプを 1 秒や 10 秒といった粗い単位に切り上げ、多数のリクエストがタイムスタンプ、ひいてはキャッシュエントリを共有できるようにすること。一貫性は弱まらない。zookie は下限を決めるだけであり、将来のタイムスタンプでの Spanner のスナップショット読み取りは TrueTime がそれを過ぎるまで待つからである (§3.2.5)。詳細: アーキテクチャ、一貫性、§2.2、§3.2.5。
TrueTime
Spanner の時刻機構。各書き込みに、因果的順序を反映したマイクロ秒分解能のタイムスタンプを与える。これによって Zanzibar のタイムスタンプが意味を持つ。TT.now() は真の時刻を含むことが保証された区間を返す。Spanner の論文 (OSDI 2012) の §3 を参照。詳細: 一貫性、§2.2、§3.2.5。
タプルセット (tupleset)
格納されたタプルを選ぶ指定。単一のタプルキー、またはあるオブジェクト ID やユーザーセットに対するすべてのタプルであり、1 つの関係に絞り込むこともできる。Read と tuple_to_userset で使われる。詳細: リレーションタプル、§2.4.1。
tuple_to_userset
オブジェクトのタプルをいくつか読み、それぞれからユーザーセットを計算する書き換えルールの葉。たとえば「readme の親フォルダを調べ、その閲覧者を取る」。詳細: リレーションタプル、§2.3.1。

U–W

和集合 (union)
書き換えルールの演算子。複数のユーザーセットのいずれかに含まれるユーザー。論文の図 1 の viewer の 3 つの分岐はすべて和集合で結ばれている。詳細: リレーションタプル、§2.3.1。
ユーザー (user)
タプルの 3 番目の部分。単一のユーザー ID かユーザーセットのどちらかである。詳細: リレーションタプル、§2.1。
ユーザーセット (userset)
そのオブジェクトに対してその関係を持つすべてのユーザーを表す ⟨object⟩#⟨relation⟩ のペア。たとえば group:eng#member。これにより、タプルがグループにアクセスを付与でき、グループがグループを含むことができる。詳細: リレーションタプル、§2.1。
ユーザーセット書き換えルール (userset rewrite rule)
リレーション設定の一部。オブジェクト ID からユーザーセット式の木への関数であり、_this、computed_userset、tuple_to_userset を和集合、積集合、除外で組み合わせて作る。詳細: リレーションタプル、§2.3.1。
ユーザーセット木 (userset tree)
Expand の結果。葉はユーザー ID またはユーザーセット、中間ノードは集合演算子である。詳細: リレーションタプル、§2.4.5。
Watch
1 つ以上の名前空間のタプル変更を、zookie を起点にタイムスタンプ順でストリームする API 呼び出し。Leopard のような二次インデックスを最新に保つために使われる。詳細: アーキテクチャ、§2.4.3。
watchserver
変更ログを追いかけて Watch に応答するサーバーの種類。詳細: アーキテクチャ、§3。
Write
タプルを追加・削除する API 呼び出し。オブジェクトのすべてのタプルを書き換えるクライアントは、読み取りの後、ロックタプルが変わっていないことを条件とする書き込みを行う。詳細: アーキテクチャ (1 回の書き込みが触れるもの)、§2.4.2。

Z

zookie
タイムスタンプをエンコードした不透明なトークン。クライアントはコンテンツ変更チェックから zookie を受け取り (Read と Write のレスポンスも zookie を含む)、それを内容とともに格納し、後続のチェックで送る。これにより、それらのチェックは少なくともそれと同じだけ新しいスナップショットで評価される。詳細: 一貫性、§2.2、§2.4。

出典

  • J. C. Corbett et al., “Spanner: Google’s Globally-Distributed Database”, OSDI ’12, PDF
  • D. Karger et al., “Consistent Hashing and Random Trees”, STOC ’97, PDF
  • J. Dean and L. A. Barroso, “The Tail at Scale”, CACM 56(2), 2013, research.google
  • L. Lamport, “Paxos Made Simple”, ACM SIGACT News 32(4), 2001, PDF
  • D. K. Gifford, “Information Storage in a Decentralized Computer System”, PhD thesis, Stanford University, 1981 (論文の参考文献 [18]。オンライン版は確認していない)
  • “Cache stampede”, Wikipedia, en.wikipedia.org (論文が引用している出典)
  • Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang