Key VisualizerをFirestoreの仕組みとともに理解する

## はじめに
### サマリ

- 出る出ると言われ続けてきた[**FirestoreのKey Visualizer**](https://cloud.google.com/firestore/docs/key-visualizer)がリリースされました😌
    - [リリースノート](https://cloud.google.com/firestore/docs/release-notes)に記述はないですが、**2021年12月の中旬頃**にリリースされたっぽいです[^1]
- Key Visualizerは**Firestoreのパフォーマンスをヒートマップ形式で可視化するツール**です（詳細は後述）
- FirestoreのデータがTablet（タブレット）[^2]に分散して保存されていること等、**裏側の仕組み（アーキテクチャ）をふんわり知る**と、より有意義にKey Visualizerを利用できると思います🙆‍♂️
- 以降では、Key Visualizerの概要を軽く流したのち、Firestoreの裏側についてざっくり説明します（ただしFirestoreは公開情報が少なく多分に推量も含みます）

### 想定読者

- Firestoreのアーキテクチャを知る足掛かりが欲しいひと
- Firestoreを使う上で性能もこだわりたくなってきたひと
- Firestoreをちゃんと運用していきたいひと

## Key Visualizer
### 概要

前述の通り、**Firestoreのパフォーマンスをヒートマップ形式で可視化するツール**です。
こちらのリンク先からAPIを有効化できます。

https://cloud.google.com/firestore/docs/keyvis-getting-started

余談ですが、Key VisualizerはFirestore以外にもGoogleの各種NoSQL/NewSQLデータベース（[BigTable](https://cloud.google.com/bigtable/docs/keyvis-overview)、[Spanner](https://cloud.google.com/spanner/docs/key-visualizer)、[Datastore](https://cloud.google.com/datastore/docs/key-visualizer)）にあります。

Key Visualizerは**横軸が時間で縦軸がデータ（ドキュメント）を表すヒートマップ**です。

[<img src = "https://cloud.google.com/firestore/docs/images/key-visualizer-heatmap.png">](https://cloud.google.com/firestore/docs/key-visualizer)

[Overview of Key Visualizer](https://cloud.google.com/firestore/docs/key-visualizer)

ある時間に、**各ドキュメント範囲（キーバケット）に対して何回読み取りや書き込み等のオペレーションがあったか？をヒートマップ形式で表示**します。
ヒートマップ中で明るく（赤く）表示されているドキュメントほど、その時間に多くのオペレーションがあったということです[^3]。

読み取りや書き込みの回数以外にも、各ドキュメントで発生する平均レイテンシ[^4]時間といった指標も表示することができます。

Firestoreでは「IDが辞書的に近いドキュメントに対して高頻度で読み取りや書き込みを行うと性能劣化が生じる（**ホットスポット**が生じる）」と公式でアナウンスされています。

>辞書順で近い一連のドキュメントに対して、高頻度で読み取りや書き込みを行わないでください。この問題はホットスポットといいます。

[Cloud Firestore のベスト プラクティス](https://firebase.google.com/docs/firestore/best-practices?hl=ja#high_read_write_and_delete_rates_to_a_narrow_document_range)

ヒートマップ上では、辞書的に近いドキュメントが並んで表示されています。
そのため下記のような、辞書的に近いドキュメントに対し順番に（シーケンシャルに）オペレーションが発生したことを示すヒートマップがある場合、性能劣化が生じている可能性があります。

[<img src = "https://cloud.google.com/firestore/docs/images/monotonically-increasing-keys.png">](https://cloud.google.com/firestore/docs/keyvis-patterns#sequential_keys)

[ヒートマップ パターン](https://cloud.google.com/firestore/docs/keyvis-patterns#sequential_keys)

**Key Visualizerのメイン用途は、ヒートマップをフムフムと眺めて、性能劣化に繋がる事象が発生していないか発見すること**です。

その他詳しい利用方法は公式にかなりまとまっていますのでご参照ください。

https://cloud.google.com/firestore/docs/key-visualizer

## なぜ辞書的に近いデータを順番にREAD/WRITEするとダメなの？

それではなぜ、辞書的に近いドキュメントに対してシーケンシャルなオペレーションが発生すると性能劣化が生じる場合があるのでしょうか。
理解のためには、**Firestoreがどのようにデータを保存しているかの裏側を理解することが重要**です。

[技術的にFirestoreの祖先に当たる](https://docs.google.com/presentation/d/11Jp1gt-n8LxVgrHBRy1ym6iJMsKww-mit1A00IS-oHk/edit#slide=id.g3cf869ca70_0_7)BigtableというDBがあります。
[Bigtableは内部実装が公開](https://research.google/pubs/pub27898/)されている上に、**Firestoreと同じ理由でホットスポットが生じる性質がありますので、まずはBigtableのアーキテクチャを見てみましょう**。

### Bigtableのアーキテクチャ

Bigtableの各データはレコード毎にユニークな行キー（row key）を持っています。
この行キーによってのみ各データを検索することができます[^5]。

[<img src = "https://storage.googleapis.com/static.ianlewis.org/prod/img/746/rows.png">](https://www.ianlewis.org/jp/cloud-bigtable)
[Googleのほとんどのサービスを支えるBigtableの誰でも使える版 Cloud Bigtable](https://www.ianlewis.org/jp/cloud-bigtable)

データはTablet（タブレット）というストレージ[^6]に分散して保存されます。

[<img src = "https://storage.googleapis.com/apps-gcp-tokyo-02.appspot.com/gcp-storage-service_02.png">](https://cloud-ace.jp/column/detail95/)

[GCPのストレージサービスについてまとめてみた](https://cloud-ace.jp/column/detail95/)

この際、**行キーの辞書順に各Tabletに保存**されます。
メチャクチャ簡易的に丸め込むと、行キーがaから始まるデータを保存するTablet、行キーがbから始まるデータを保存するTablet...みたいな感じでデータが分散して保存されるわけです。
そのため、例えば行キーがaから始まるデータへ高頻度でアクセスすると**「行キーがaから始まるデータを保存するTablet」を管理するサーバへのアクセスが集中**してしまいます。
これにより引き起こされる性能劣化（特定のサーバにアクセスが集中する状況）こそが**ホットスポット**です。

辞書的に近いデータは同じサーバが管理するTabletである可能性が高いため、Bigtableのアーキテクチャ（データの持ち方）上、シーケンシャルなアクセスはよろしくないわけです。

Bigtableの性能を引き出すためには、**ホットスポットが生じないようにすることがメインタスク**です。
発生を回避するためには、シーケンシャルにアクセスする可能性のあるデータについて、分散してTabletに配置するように心掛ける必要があります。

- 行キーの命名規則に気を使い、連続して取り扱うデータが分散して保存されるようにする（例えば[**ハッシュ値を行キーの頭に付与する**](https://qiita.com/tarr1124/items/168d375dc644e9e2c4d4)等）
- データが投入されるに従いTabletは増えていき、それぞれが担当範囲のPrefixから始まる行キーのデータを保存する。ジワジワとデータを投入していけばうまく分散してTabletが増えてくれるため**[500/50/5ルール](https://docs.google.com/presentation/d/11Jp1gt-n8LxVgrHBRy1ym6iJMsKww-mit1A00IS-oHk/edit#slide=id.g3cf869ca70_0_239)等に従いデータを徐々に入れていく**[^7]

等でホットスポットの対策を行っていきます。

[2022.05.27 追記]
BigTableのホットスポットをどのように回避するか、公式ブログで記事が出ていました。
内容的にもかなりタメになる感じで良かったです。

https://cloud.google.com/blog/products/databases/hotspots-and-performance-debugging-in-cloud-bigtable

### Firestoreの場合

Firestoreの場合もBigtableと同様に、各ドキュメントがTabletに分散して保存されます。
Firestoreはご存知の通り「パス」で各ドキュメントがユニークに識別されます[^8]。

```
通常の場合
collection/document_id　　　　　　　　（例） User/Taro

サブコレクションがある場合
collection/document_id/sub_collection/document_id　　　　　　　　（例）User/Taro/Book/Emile
```

このパスがBigtableにおける行キー相当として扱われていると考えられます。

**パスの辞書順にドキュメントがTabletに分散保存されていく**ため、**「ドキュメントIDが近い = パスが近い = 辞書的に近い」ドキュメントにシーケンシャルなアクセスを行うと、ホットスポットが生じてしまう**わけです。

### 余談：Firestoreのインデックスの場合

Bigtableは行キーでしかデータを引けないですが、Firestoreはフィールドにインデックスを張ってドキュメントを検索することができます。
このインデックスの作成でもホットスポットが生じる場合があると公式に書かれています。

>読み取りレートや書き込みレートが高いアプリケーションの場合、タイムスタンプのように単調に増加する値を持つフィールドにインデックスを作成すると、レイテンシに影響を与えるホットスポットが生じる可能性があります。

[Cloud Firestore のベスト プラクティス](https://firebase.google.com/docs/firestore/best-practices?hl=ja#indexes)

これは一体なぜでしょうか。
下記はDatastoreでインデックスを張った場合の図ですが、**「元々の行キー」と「インデックスを張ったフィールドの値」をくっつけた行キーを持つインデックステーブルを作成**し、実際のデータ（Entity）を引けるようにしています（インデックステーブルのデータもまたTabletに分散して保存される）。

[<img src = "https://www.school.ctc-g.co.jp/columns/nakai2/img/column08_fig03.png">](https://www.school.ctc-g.co.jp/columns/nakai2/nakai208.html)
[第8回　スケーラビリティと一貫性を両立した分散データストアMegastore（パート２） (中井悦司)](https://www.school.ctc-g.co.jp/columns/nakai2/nakai208.html)

恐らくFirestoreも同様（或いは近しい）構造になっているため、単調に増加する値を持つフィールドをインデックスに設定した場合、シーケンシャルな行キーが生成されることになり、インデックステーブルのデータが似通ったTabletに集中保存されることになります。
そのため高頻度でアクセスを行うとホットスポットが生じてしまうわけです[^9]。

更なる余談ですが、[Firestoreのストレージ料金表](https://firebase.google.com/docs/firestore/storage-size?hl=ja#index-entry-size)を見ると、インデックス毎に別途ストレージ容量分、お金が取られると明記されています。

```
コレクションのスコープを使用する単一フィールド インデックスのエントリのサイズは、以下の合計値となります。

インデックス付きドキュメントのドキュメント名のサイズ
インデックス付きドキュメントの親ドキュメントのドキュメント名のサイズ
インデックス付きフィールド名の文字列サイズ
インデックス付きフィールド値のサイズ
追加の 32 バイト
```

インデックステーブルの行キーが「インデックス付きドキュメントのドキュメント名のサイズ」「インデックス付きドキュメントの親ドキュメントのドキュメント名のサイズ」「インデックス付きフィールド名の文字列サイズ」「インデックス付きフィールド値のサイズ」を表しており、「追加の 32 バイト」がデータへの参照を表しているのかな、と思われます。
不必要なインデックスは消した方が良さそうですね。

### まとめ

このように、**Tabletの構造を理解した上でKey Visualizerを見返してみると、ヒートマップの縦軸がTabletを表しているように感じられ「ヒートマップ上距離が近いTabletが明るくなっていてヤバいな」みたいな考え方ができるようになります**。
一段階、Key Visualizerを見る際の解像度が上がります！

:::note info
Firestoreの前身であるDatastoreの裏側はMegastoreで構成されています。MegastoreではFirestoreのパスとほぼ対応する「Ancestorパス」がBigtableの行キーとして使われていると明記されています。また、インデックスについても「行キー + インデックスに指定したフィールド値」を行キーにしたインデックステーブルを作成すると書かれています。しかしFirestoreについてはストレージレイヤがSpannerと同様のもので構築されていると言われていますが、公式にはどのようにデータを持っているか明示されていないため断定口調は避けました（詳しい方、情報お持ちでしたら教えてください🙇‍♂️）。

参考：
・ https://www.school.ctc-g.co.jp/columns/nakai2/nakai208.html 
・ https://qiita.com/1amageek/items/175305687acbe39b47d9
:::

## 最後に

ちなみに余談ですが、私の環境でKey Visualizerを確認したところ、一部でシーケンシャルなヒートマップが発生していました🤔
ID設計には気を使って先頭にハッシュを振る等していたのですが...（ハッシュを振ったものに対してただただシーケンシャルにアクセスする実装だった、という子どもみたいなオチ。Key Visualizerで見ないと気付けなかった）。
Firestoreはマネージドなサービスな分、運用する上で可視化ツールがあるのは非常にありがたいですね。

今後も使っていこうと思います！

## 参考リンク

https://cloud.google.com/firestore/docs/key-visualizer

https://docs.google.com/presentation/d/11Jp1gt-n8LxVgrHBRy1ym6iJMsKww-mit1A00IS-oHk/htmlpresent

https://www.school.ctc-g.co.jp/columns/nakai2/nakai207.html

https://www.ianlewis.org/jp/cloud-bigtable

https://speakerdeck.com/sakajunquality/cloud-spanner-monitoring-introduction

[^1]: [公式ドキュメント](https://cloud.google.com/firestore/docs/key-visualizer)の公開も2021年12月17日。以前から一部ユーザでは使えてたっぽい（コンソールにリンクだけあった）
[^2]: https://cloud.google.com/bigtable/docs/overview#architecture
[^3]: 正確にはドキュメントではなくキーバケットです。https://cloud.google.com/firestore/docs/key-visualizer#key-buckets
[^4]: 転送要求を出してから実際にデータが送られてくるまでに生じる通信時間
[^5]: プライマリーキーの役割を持っている
[^6]: 正確にはGoogle File System
[^7]: Firestoreの場合、データを投入するとき以外にも、500/50/5ルールに従ってアクセスすると良いことが多い。Tabletを管理するサーバはアクセスが増えるに従いスケーリングしていく。例えばスパイク的に読み取りを行うとサーバの処理が追いつかなくなってしまうので
[^8]: 正確にはGoogle Cloudプロジェクト名やデータベース名も含みます。https://pkg.go.dev/cloud.google.com/go/firestore@v1.2.0#DocumentRef
[^9]: 特にFirestoreはインデックスの更新を同期的に行なっているので