guide:leopard@ja

ガイド

Leopard:グループのインデックス

Zanzibar が深く入れ子になったグループのメンバーシップを 1 回の積集合演算で答える仕組みと、それが書き込みのたびに払うコスト。

事実確認日 論文の該当節 §3.2.4, §4.4

Zanzibar は通常、オブジェクトからユーザーへと、1 回に 1 つずつ検索しながらタプルをたどることで Check に答える。ほとんどのデータではこれで速い。しかし何段にも入れ子になったグループでは速くない。Zanzibar はそうしたチェックを、入れ子を事前計算したインデックスである Leopard に任せる。

入れ子が遅い理由

共通の例を拡張する。group:eng は group:product の中にあり、group:product は group:all の中にあり、readme は group:all 全体に共有されているとする。Beto が readme を閲覧できることを知るには、何回の検索が必要か。

入れ子になったグループの連鎖user:beto は group:eng のメンバーであり、group:eng のメンバーは group:product のメンバーであり、group:product のメンバーは group:all のメンバーであり、group:all のメンバーは doc:readme の閲覧者である。Beto のアクセスのチェックは doc:readme から始まり、1 ステップごとに 1 つのオブジェクトを読む。doc:readme、group:all、group:product、group:eng の 4 回の読み取りが順に行われる。doc:readmegroup:allgroup:productgroup:enguser:beto1. doc:readme を読む: 閲覧者は group:all2. group:all を読む: group:product を含む3. group:product を読む: group:eng を含む4. group:eng を読む: Beto はメンバーviewermembermembermember
各ステップが次のステップのオブジェクトを決めるので、4 回の読み取りを同時に始めることはできない。各オブジェクトは別々のサーバーにあることもある (アーキテクチャのページを参照)。

図の背後にあるタプルは次のとおりである。

doc:readme#viewer@group:all#member
group:all#member@group:product#member
group:product#member@group:eng#member
group:eng#member@user:beto

ステップ n はステップ n − 1 が返るまで始められないことに注意されたい。論文はこれをポインタ追跡と呼び、“can be expensive when indirect ACLs or groups are deep or wide” (間接 ACL やグループが深い場合や広い場合にはコストが高くなりうる) と述べている (§3.2.3)。広さも問題になる。group:all が 100 個の子グループを持っていれば、ステップ 2 は 100 通りに分岐する。そこで次のようになる。“Recursive pointer chasing during check evaluation has difficulty maintaining low latency with groups that are deeply nested or have a large number of child groups. For selected namespaces that exhibit such structure, Zanzibar handles checks using Leopard, a specialized index that supports efficient set computation.” (チェック評価中の再帰的なポインタ追跡では、深く入れ子になったグループや多数の子グループを持つグループに対して低レイテンシを維持するのが難しい。そのような構造を示す選ばれた名前空間について、Zanzibar は効率的な集合演算をサポートする専用のインデックスである Leopard を用いてチェックを処理する。) (§3.2.4)

2 種類の集合

Leopard は “a collection of named sets using (T, s, e) tuples, where T is an enum representing the set type and s and e are 64-bit integers representing the set ID and the element ID” ((T, s, e) タプルを用いた名前付き集合の集まり。ここで T は集合の種類を表す列挙型、s と e は集合 ID と要素 ID を表す 64 ビット整数である) を格納する (§3.2.4)。グループのメンバーシップには 2 種類の集合を使う。

  • GROUP2GROUP(s):祖先グループ s の「直接または間接の」(“directly or indirectly”) サブグループであるグループ。
  • MEMBER2GROUP(s):ユーザー s が「直接の」(“direct”) メンバーであるグループ。

例では、これらの集合は何を保持しているか。

例における GROUP2GROUP と MEMBER2GROUPGROUP2GROUP(group:all) は group:all、group:product、group:eng。GROUP2GROUP(group:product) は group:product と group:eng。GROUP2GROUP(group:eng) は group:eng。MEMBER2GROUP(user:beto) は group:eng。MEMBER2GROUP(user:anne) は空。GROUP2GROUP(group:all)GROUP2GROUP(group:product)GROUP2GROUP(group:eng)MEMBER2GROUP(user:beto)MEMBER2GROUP(user:anne){ group:all, group:product, group:eng }{ group:product, group:eng }{ group:eng }{ group:eng }{ }
GROUP2GROUP は平坦化されている。eng は 2 段下にあるが、group:all には group:eng が載っている。MEMBER2GROUP は平坦化されておらず、直接のメンバーシップだけを載せる。各グループは自身の GROUP2GROUP 集合にも描いてある。これは論文に書かれていない。下の注を参照。

非対称性に注意されたい。入れ子はすべて GROUP2GROUP に畳み込まれているので、ユーザー側はユーザーが直接追加された場所だけを記録すればよい。論文の言葉では、“Flattening group-to-group paths allows reachability to be efficently evaluated by Leopard” (グループからグループへの経路を平坦化することで、Leopard は到達可能性を効率的に評価できる) (§3.2.4)。

メンバーシップは空でない積集合である

“To evaluate whether user U is a member of group G, we check whether” (ユーザー U がグループ G のメンバーであるかを評価するには、次が成り立つかをチェックする) (§3.2.4)

(MEMBER2GROUP(U) ∩ GROUP2GROUP(G)) ≠ ∅

つまり、ユーザーが直接追加されたグループのいずれかが G の下のどこかにもあるか、ということである。group:all について、Beto と Anne ではどうなるか。

積集合としてのメンバーシップMEMBER2GROUP(user:beto)、すなわち group:eng と、GROUP2GROUP(group:all)、すなわち group:all、group:product、group:eng の積集合は group:eng であり、空でないので Beto は group:all のメンバーである。MEMBER2GROUP(user:anne)、すなわち空集合と、同じ集合の積集合は空集合なので、Anne はメンバーではない。MEMBER2GROUP(user:beto){ group:eng }GROUP2GROUP(group:all){ group:all, group:product, group:eng }∩ = { group:eng }空でない: メンバーMEMBER2GROUP(user:anne){ }GROUP2GROUP(group:all){ group:all, group:product, group:eng }∩ = { }空: メンバーでない
入れ子の深さにかかわらず、2 回の検索と 1 回の積集合で済む。Beto は含まれ、Anne は含まれない。

最初の図の 4 回の逐次読み取りは、2 回の集合の検索と 1 回の積集合になった。元の問いに答え切るには、Zanzibar は依然として group:all#member を指す readme のタプルを読む。Leopard が取り除くのはそこから下の深さである。論文は Check が通常の評価と Leopard への問い合わせにどう分けられるかを詳しく書いていないので、この分け方は §3.2.4 からの解釈であり、引用ではない。

ソート済みリスト上の積集合

積集合はどれほど安いのか。“Index tuples are stored as ordered lists of integers in a structure such as a skip list, thus allowing for efficient union and intersections among sets. For example, evaluating the intersection between two sets, A and B, requires only O(min(|A|, |B|)) skip-list seeks.” (インデックスタプルはスキップリストのような構造の中に整数の順序付きリストとして格納され、それにより集合間の和集合と積集合を効率的に計算できる。たとえば、2 つの集合 A と B の積集合を評価するのに必要なのは O(min(|A|, |B|)) 回のスキップリストのシークだけである。) (§3.2.4)

短いソート済みリストと長いリストの積集合リスト A は 17、42、90 を持つ。リスト B は 3、8、17、21、30、42、55、61、77、84、93、99 を持つ。A の各要素について、B で 1 回シークして、それより小さくない最初の要素を見つける。17 は 17 を、42 は 42 を見つけ、90 は 93 に着地し、これは一致しない。積集合は 17 と 42 であり、3 回のシークで見つかる。AB1742903817213042556177849399シーク 1: 一致シーク 2: 一致シーク 3: 不一致
A に 3 要素、B で 3 回のシーク。B の 12 要素を 1 つずつ走査することはない。各シークを速くしているスキップリストの上位レベルは描いていない。

作業量は短いほうのリストに従うことに注意されたい。ユーザーが少数のグループの直接のメンバーにすぎないなら、MEMBER2GROUP(U) は短く、GROUP2GROUP(G) が巨大でもテストは安いままである。論文は集合のサイズを示しておらず、この場合は仮定である。インデックスは “is sharded by element IDs” (要素 ID でシャーディングされ)、シャードは “are usually served entirely from memory” (通常すべてメモリから提供される) (§3.2.4)。

3 つの部分

“The Leopard system consists of three discrete parts: a serving system capable of consistent and low-latency operations across sets; an offline, periodic index building system; and an online real-time layer capable of continuously updating the serving system as tuple changes occur.” (Leopard システムは 3 つの独立した部分から成る。集合をまたいで一貫性のある低レイテンシな操作が可能な提供システム、オフラインで定期的に動くインデックス構築システム、そしてタプルの変更に応じて提供システムを継続的に更新できるオンラインのリアルタイム層である。) (§3.2.4) これらはどうつながっているのか。

Leopard の 3 つの部分オフラインのインデックスビルダーは Zanzibar のタプルと設定のスナップショットを読み、インデックスのシャードを生成する。シャードは複製され、Leopard の提供システムに入れ替えられる。並行して、差分インデクサーは Zanzibar の Watch ストリームを読み、タイムスタンプ付きの更新を提供システムの差分層に書き込む。aclserver は提供システムに問い合わせ、提供システムはクエリのタイムスタンプにおいて差分層をオフラインのインデックスに重ねる。タプル + 設定のスナップショットオフラインのインデックスビルダー(定期実行)Leopard の提供オフラインのインデックス+ 差分層Watch API差分インデクサーaclservers新しいシャードタプルの変更(T, s, e, t, d)問い合わせ
オフラインの経路は完全だが古い。差分の経路は新しいが、最後のスナップショット以降の変更しか含まない。提供システムが両者を統合する。
  • オフラインのインデックスビルダー。 これは “generates index shards from a snapshot of Zanzibar relation tuples and configs, and replicates the shards globally. It respects userset rewrite rules and recursively expands edges in an ACL graph to form Leopard index tuples.” (Zanzibar のリレーションタプルと設定のスナップショットからインデックスのシャードを生成し、シャードをグローバルに複製する。ユーザーセット書き換えルールを尊重し、ACL グラフの辺を再帰的に展開して Leopard のインデックスタプルを形成する。) サーバーは “swap old shards with new ones when they become available” (新しいシャードが利用可能になると古いシャードと入れ替える)。
  • 差分層。 オフラインのインデックスだけでは “cannot do so at a fresh and consistent snapshot” (新しく一貫したスナップショットでそれを行うことはできない) ので、サーバーは “an incremental layer that indexes all updates since the offline snapshot” (オフラインのスナップショット以降のすべての更新をインデックス化する差分層) を保持する。各更新は (T, s, e, t, d) タプルであり、“where t is the timestamp of the update and d is a deletion marker” (t は更新のタイムスタンプ、d は削除マーカーである)。“Updates with timestamps less than or equal to the query timestamp are merged on top of the offline index during query processing.” (クエリのタイムスタンプ以下のタイムスタンプを持つ更新は、クエリ処理中にオフラインのインデックスの上に統合される。)
  • 供給。 “the Leopard incremental indexer calls Zanzibar’s Watch API to receive a temporally ordered stream of Zanzibar tuple modifications and transforms the updates into a temporally ordered stream of Leopard tuple additions, updates, and deletions.” (Leopard の差分インデクサーは Zanzibar の Watch API を呼び出して、時間順に並んだ Zanzibar のタプル変更のストリームを受け取り、その更新を、時間順に並んだ Leopard タプルの追加、更新、削除のストリームに変換する。)

この一覧の引用はすべて §3.2.4 からである。更新はタイムスタンプを持ち、クエリのタイムスタンプまで統合されるので、Leopard の答えは Check の他の部分と同じスナップショットを反映できる。論文が述べる差分層の目的は “To support consistent ACL evaluation” (一貫した ACL 評価をサポートするため) である。

コスト:1 回の書き込みで多数のインデックス更新

平坦化の代償は書き込み時に払われる。eng が product に追加される前に戻り、group:eng が自身のサブグループ group:infra と group:web を持つとする。ここで誰かが eng を product に追加する。インデックスタプルはいくつ変わるか。

1 回のタプル書き込みが多数のインデックス更新にファンアウトするタプル group:product#member@group:eng#member を追加すると、group:eng、group:infra、group:web が group:product と group:all の両方の新しい子孫になる。差分インデクサーはこの 1 つのタプルを 6 つの GROUP2GROUP の追加に変換する。product に eng、infra、web が加わり、all に eng、infra、web が加わる。group:product#member@group:eng#member差分インデクサー+ G2G(product, eng)+ G2G(product, infra)+ G2G(product, web)+ G2G(all, eng)+ G2G(all, infra)+ G2G(all, web)1 回の書き込み
Zanzibar のタプル 1 つに対して Leopard のタプル 6 つ (group: の接頭辞は省略)。product のすべての祖先 (product、all) と eng のすべての子孫 (eng、infra、web) の組み合わせである。MEMBER2GROUP は変わらない。

個数は一方の側の祖先の数と他方の側の子孫の数の積なので、深さと広さの両方に応じて増える。これを計算するために、“Generating updates for the GROUP2GROUP tuples requires the incremental indexer to maintain group-to-group membership for denormalizing the effects of a relation tuple update to potentially multiple index updates.” (GROUP2GROUP タプルの更新を生成するには、差分インデクサーがグループ間のメンバーシップを保持し、1 つのリレーションタプルの更新の影響を、潜在的に複数のインデックス更新へと非正規化する必要がある。) Google の規模では “In practice, a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events.” (実際には、Zanzibar のタプルの追加や削除 1 つが、潜在的に数万の個別の Leopard タプルイベントを生むことがある。) (§3.2.4)

削除は図より微妙である。インデックスタプルを削除できるのは、2 つのグループをつなぐ他の経路が残っていない場合に限られる。インデクサーがそれをどう判断するかは、論文に書かれていない。

これは Leopard が例外である理由でもある。他の部分では “Zanzibar avoids storage denormalization and relies only on normalized data (except for the cases described in §3.2.4)” (Zanzibar はストレージの非正規化を避け、正規化されたデータのみに依存する (§3.2.4 で述べた場合を除く)) (§3.2.5)、Leopard は “that exhibit such structure” (そのような構造を示す) 選ばれた名前空間にのみ使われる (§3.2.4)。

本番環境での実績

§4.4 より、7 日間について。“The Leopard index is performing 1.56M QPS at the median, or 2.22M QPS at the 99th percentile” (Leopard インデックスは中央値で 1.56M QPS、99 パーセンタイルで 2.22M QPS を処理している)、そして “Leopard servers respond in fewer than 150 μsec at the median, or under 1 msec at the 99th percentile.” (Leopard サーバーは中央値で 150 μs 未満、99 パーセンタイルで 1 ms 未満で応答する。) 差分層は “writes roughly 500 index updates per second at the median, and approximately 1.5K updates per second at the 99th percentile.” (中央値で毎秒約 500 件、99 パーセンタイルで毎秒約 1.5K 件のインデックス更新を書き込む。) Leopard への呼び出しは、Spanner への呼び出しと同様にヘッジされる (§3.2.7)。

出典