All Articles

Zanzibar

このページについて

Zanzibar: Google’s Consistent, Global Authorization Systemを読んだ内容をまとめたメモ1

そもそも、spiceDB の記事を見て知った。認可に特化した独自の schema 言語を扱う DB。一貫性レベルがAPIコール時に指定することができる。DB といいつつも、これがファイルにデータを書き込むわけではなく、既存のDB と連携させる必要がある。

- CockroachDB - Recommended for multi-region deployments
- PostgreSQL - Recommended for single-region deployments and those familiar with traditional RDBMS operations
- memdb - Recommended for local development and integration testing with applications written to be SpiceDB-native

引用

どんなもの?

Google の認可を一元で管理しているシステム。スケーラビリティ・低遅延・高可用性を備えつつ、外部一貫性モデルを持つ。ユーザアクションの順序を尊重しながら、グローバルな同期を行わずに分散した場所で認可チェックができるようになっている。毎秒数兆のアクセス制御リクエストと数百万の認証要求に対応。しかも、3年間プロダクション環境で95%タイルのレイテンシが 10ms 以下、可用性 99.999% 以上を維持している。

先行研究と比べてどこがすごい?

facebook の TAO と比べると、ACLの書き込みの因果順序を尊重できるので、new Enemy 問題を回避できる。これは外部一貫性の恩恵。(TAOは、非同期レプリケーションによる最終的なグローバルな一貫性と、同期キャッシュ更新による書き込み後の読み取りの一貫性を提供している)

ZooKeeperは高性能なコーディネーションサービスを提供しているが、Zanzibarが必要とする機能を備えていない。Chubbyと比較して、ZooKeeperは、より緩和されたキャッシュ一貫性で、より高い読み取り率と書き込み率を扱うことができる。しかし、Chubbyの線形性はノード単位であるため、異なるノード間の更新に対する外部整合性は提供されない。また、スナップショット・リードも実現できません。

技術や手法のキモはどこ?

地理的に分割できない ACL データを数十の地理的に分散したデータセンタに複製し、数千のサーバに負荷を分散している。これは、論文の参考を見るに Spanner のおかげ。
アクセス制御のグローバルな一貫性をサポート。

  • ACL の変更がデータストアにコミットされる順序を尊重する

  • クライアントが指定した変更よりも古いACLデータでチェックされることがない

    • 要は、A という変更をしている or した後には古い ACL でユーザがチェックされることがない
    • Spanner の強整合性により読み取りの際にcommit されたすべてのトランザクションが必ず反映される

外部一貫性が担保されているので、ローカルに複製されたデータで処理することができる。故に早い。
ここまではバックエンドに Spanner を利用しているからそうだよねという話。それ以外の設計でいうと、Zookie というトークンがリクエストでやりとりされる。これは Google のグローバルタイムスタンプがエンコードされている。このトークンを使って、以前のすべてのACL書き込みがより低いタイムスタンプであることを保証する。

どうやって有効だと検証した?

リクエストの一部をキャプチャして、モニタリングを行った。

議論はある?

次に読むべき論文は?

  • そもそも Spanner について。True Time 抽象化についても。

    • D. Spanner: Google’s globally-distributed database. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (2012)

  • TAO

    • TAO: Facebook’s distributed data store for the social graph. In Proceedings of the 2013 USENIX Annual Technical Conference

  • RBAC の提案

    • Role-based access control. In In 15th NIST-NCSC National Computer Security Conference (1992)

  • リクエストヘッジ

    • The tail at scale. Communications of the ACM

雑多な感想

データの書き込みを changelog server に置いておくのはいいなと思った。主キー(changelog shard ID, timestamp, unique update ID)でリクエストの依存追いやすくなりそう。

リクエストヘッジの仕組み面白いなぁ（同じリクエストを複数のサーバに送信し、最初に返ってきたレスポンスを使用し、他のリクエストはキャンセルします）。とにかく動かしつづけるためにはこういう仕組みとるのか。ただし、最初のリクエストが遅いことがわかるまで、ヘッジ付きリクエストの送信を延期するとのこと。

Spanner を利用できるスロットルがあり、一部のクライアントの利用がサービス全体に負荷をかけないようになっている。また、クライアントごとにロックテーブルキーが存在し、これを元にスロットルの個別管理を行っている。

理解のために参考にしたもの、調べたこと

  1. 記事のtemplateは落合陽一さんのスライドから拝借

    ↩

Published 4 Nov 2021

Software engineer at Tokyo. smith-30 on Twitter