ISUCON本の内容をまとめてみた キャッシュ編

# はじめに
この記事は[isucon本](https://www.amazon.co.jp/%E9%81%94%E4%BA%BA%E3%81%8C%E6%95%99%E3%81%88%E3%82%8BWeb%E3%83%91%E3%83%95%E3%82%A9%E3%83%BC%E3%83%9E%E3%83%B3%E3%82%B9%E3%83%81%E3%83%A5%E3%83%BC%E3%83%8B%E3%83%B3%E3%82%B0-%E3%80%9CISUCON%E3%81%8B%E3%82%89%E5%AD%A6%E3%81%B6%E9%AB%98%E9%80%9F%E5%8C%96%E3%81%AE%E5%AE%9F%E8%B7%B5-%E8%97%A4%E5%8E%9F-%E4%BF%8A%E4%B8%80%E9%83%8E-ebook/dp/B0B1Z9ZMY6/ref=sr_1_1?crid=3VFKVU9V3LQ4D&dib=eyJ2IjoiMSJ9.Fqg1BYtrQnEUkAI-Nz64Vlht-4b2gmnfCNzmBcYOOLrGjHj071QN20LucGBJIEps.ihawrCdi4UxmgZ_Xbpwz0kJimoBykcQ7nS9WIqRl40U&dib_tag=se&keywords=isucon&qid=1732981401&sprefix=isucon%2Caps%2C178&sr=8-1)の7章の内容をまとめたものになります。要点を抑えている(つもり)なので是非ご覧ください
# キャッシュとは
AWSのページにおいては以下のように説明されています。
> コンピューティングにおいて、キャッシュは、データのサブセットが保存される高速のデータストレージレイヤーで、通常は一時的な性質のものです。これにより、それ以降に同じデータのリクエストが発生した場合、データのプライマリストレージロケーションにアクセスするよりも高速にデータが供給されます。キャッシュにより、以前に取得または計算されたデータを効率的に再利用できるようになります。

引用元: [AWS キャッシュ](https://aws.amazon.com/jp/caching/)
webアプリケーションにおいてはレスポンスに用いるデータをミドルウェア等に保存して再利用することを指します。
webアプリケーションでは大きく2種類のキャッシュ方法があります

- Webアプリケーション上で作ったキャッシュをミドルウェアなどに保存して利用する方法
- HTTPのレスポンス全体をキャッシュする方法

本記事では「Webアプリケーション上で作ったキャッシュをミドルウェアなどに保存して利用する方法」に着目し、解説します。


## キャッシュを用いるメリット
キャッシュには以下のようなメリットがあります
- 負荷がかかる処理の実行回数を抑えられる
- インフラコストの低下
- 外部APIの呼び出し回数の低下
- 大量リクエストに耐えやすくなる

同じデータを再利用することで様々なものの実行回数や処理を減らすことができます
## キャッシュを用いるデメリット
  - 古いデータや想定外のデータが表示されてしまうリスクがある
  - キャッシュを保存するミドルウェアが新しい障害点になる
  - 実装の複雑化
  - Thundering herd problemの発生

データを使い回す都合上、正しく実装しないと古いデータを用いてしまったり、それがデータ不整合の原因となってしまいます。また、ミドルウェアを増やすということはその部分が新しい障害点にもなるということです。また、後に詳しく解説しますがThundering herd problemという問題も発生してしまいます。

### キャッシュを用いる実装の不都合
以下にキャッシュを用いた場合とそうでない場合のコードを示します。
```python:キャッシュを用いないコード
const db = require('./db'); // ダミーのデータベースモジュール

async function getUser(userId) {
    console.log('データベースにアクセスします...');
    const user = await db.findUserById(userId); // データベースに直接アクセス
    return user;
}

// 使用例
(async () => {
    const user = await getUser('123');
    console.log(user);
})();

```

```python:キャッシュを用いたコード
const db = require('./db'); // ダミーのデータベースモジュール
const Redis = require('ioredis');
const redis = new Redis(); // Redisクライアントを作成

async function getUserWithCache(userId) {
    const cacheKey = `user:${userId}`;
    
    // キャッシュを確認
    const cachedUser = await redis.get(cacheKey);
    if (cachedUser) {
        console.log('キャッシュからデータを取得します...');
        return JSON.parse(cachedUser);
    }

    // キャッシュがない場合はデータベースにアクセス
    console.log('データベースにアクセスします...');
    const user = await db.findUserById(userId);

    // データをキャッシュに保存（有効期限10分）
    await redis.set(cacheKey, JSON.stringify(user), 'EX', 600);

    return user;
}

// 使用例
(async () => {
    const user = await getUserWithCache('123');
    console.log(user);
})();

```
明らかに実装負荷が増したことが確認できるかと思います。DBからのRead処理の際にいちいちキャッシュに問い合わせたり保存が必要なのでその分実装負荷が増してしまいます。

## キャッシュを用いる際の観点
これらの点を踏まえて書籍では以下の観点でキャッシュの有無を考慮するといいことを解説してくれています。
### データの不整合がどこまで許されるか
キャッシュを用いた場合、古いデータや意図しないデータを表示してしまう可能性があります。ですので **仮にキャッシュしたいデータが意図しない表示をしても問題がないか** 考える必要があります。
例えば **決済情報など重要なデータは不整合が致命的になるので、キャッシュを使うべきではありません。** また、更新したはずのデータが更新されないとユーザーからバグを疑われるのでそれも覚えておきましょう。

```mermaid
graph TD
    A[データのリクエスト]
    B[キャッシュが存在するか確認]
    C[キャッシュに古いデータが存在]
    D[古いデータを表示]
    E[データを更新]
    F[新しいデータを取得]

    A --> B
    B -->|キャッシュあり| C
    C -->|古いデータ| D
    D -->|ユーザーに表示| D
    B -->|キャッシュなし| F
    F --> E
    E -->|新しいデータを表示| D
```

### データの特性上、本当にキャッシュを使う必要があるか
ユーザー情報などはユーザー毎にキャッシュが分散してしまいます。そのため、有効にキャッシュを使えない可能性があります。また、ユーザー情報を取り違えると、重大なセキュリティリスクに繋がる可能性があるので注意が必要です。その他、有効に使えないキャッシュが増えると、キャッシュを保存するミドルウェアの容量が足りなくなる可能性があるので注意してください。

### データの更新頻度はどの程度か
データが頻繁に更新される場合、キャッシュをしても有効に活用できない可能性があります。キャッシュをしてもすぐにデータが更新されてしまうのでキャッシュを使わなくなってしまうためです。また、データの鮮度が重要な機能の場合に更新頻度が低いとユーザー体験が悪化するので注意しましょう。


### データの生成コストを考えているか
**データの生産コストが低い場合と高すぎる場合においてはキャッシュを使うべきではない**とされています。生成コストが低い場合にはそもそもキャッシュを使う必要性は薄く、むしろデメリットの方が大きくなってしまいます。また、生成コストが高すぎる場合、キャッシュデータが失われると長時間データの復旧ができません。そのため生成結果をRDBMSなどデータが失われにくいデータベースに保存する必要があります。
### キャッシュにおいては十分短いTTLを設定する必要がある
TTL(Time to Live)とはキャッシュが作成されてから更新されるまでの期間のことです。この期間が短いと、すぐにデータを更新しなくてはならないため、キャッシュの旨みが減ってしまいます。一方TTLが大きすぎると古いデータを表示する確率が高くなってしまうため注意が必要です。
### データが更新されたときにキャッシュも同時に更新するようにする
データの鮮度を保つためにはデータが更新された際にキャッシュの方も更新する必要があります。

# キャッシュデータ保存に利用されるミドルウェア
キャッシュを用いる際には以下の二つの機能があれば問題ないとされています。
- keyからvalueが取得できるKVSとしての機能 
- TTLを定められ、TTLがすぎたらexpireしてデータを削除する機能

## プロセス処理のアーキテクチャ
キャッシュに用いられるミドルウェアのアーキテクチャについて少し紹介します。しっかり紹介するとそれだけで記事が書けそうなのでここではキャッシュ実装の観点だけ説明します。
### シングルプロセス・マルチスレッド
一つのプロセス内で複数のスレッドをもちいて処理をするアーキテクチャーです。並行に読み込み・書き込みができるように適切なロックを取る必要があります。

### マルチプロセス・シングルスレッド
複数のプロセスで動作しますがスレッドが一つで処理をするアーキテクチャです。プロセス間でメモリを共有するのが簡単ではないため注意が必要です。

## ミドルウェアの特徴
webアプリケーションのキャッシュとして用いられることの多いmemcachedとredisについてここでは紹介します。
### memcached
>Memcached は使いやすく、高パフォーマンスなインメモリデータストアです。ミリ秒未満の応答時間を実現する、スケーラブルかつオープンソースの成熟したソリューションで、キャッシュやセッションストアとして役立ちます。Memcached は、ウェブ、モバイルアプリケーション、ゲーム、アドテクノロジー、e コマースの分野のリアルタイムアプリケーションを稼動させるためによく使われています。

引用元: [AWS Memcached](https://aws.amazon.com/jp/memcached/)

memcachedは、KVSとして必要な機能を持っており、非常に高いパフォーマンスを出せるミドルウェアです。非常に広く使われており、各言語のライブラリも充実しています。

  - メリット
    - KVSとして必要な機能を持っている
    - パフォーマンスが非常に高い
    - 特にPHP接続を永続化できるなど、非常に工夫されている
  - デメリット
    - ストレージを永続化できない
    - レプリケーション機能がないため再起動や障害などで簡単にデータが失われてしまう
  - 消えても困らないキャッシュとして以外の用途は想定されていない
### Redis
### memcached
>Redis は RAM にデータを保存するので、メモリから直接データにアクセスできます。これにより、低レイテンシーのレスポンスを提供しますが、保存できるデータ量も制限されます。Redis は、スナップショットと追加専用ファイル (AOF) ロギングによってデータセットをディスクに保存します。これにより、データの耐久性が確保されます。 

>Redis はデータを key-value ペアとして格納し、各データエントリには固有のキーがあります。ソートされたセット、ハッシュ、セット、リスト、文字列などのさまざまなデータタイプをサポートしています。キーの長さは任意で、合計 512 MB までです。

引用元: [AWS Redis と MongoDB はどのように異なりますか?](https://aws.amazon.com/jp/compare/the-difference-between-redis-and-mongodb/)

RedisはKVSとしての機能以外にもさまざまな機能があります。コマンドや扱えるデータ構造も多く、データの永続化やレプリケーションも可能です。

 - メリット
      - KVSとしての機能以外にもさまざまな機能を持っている
      - コマンドや扱えるデータ構造も多い
      - データの永続化やレプリケーションの機能もある
      - Redis ClusterやRedis Sentinelなどを使用することでクラスター構成に組むことも可能
- デメリット
     - 基本的にシングルスレッドで動作する
     -  単純なGET/SET以外のコマンドを実行する場合に、1クライアントの処理で長時間全体の処理がブロックしてしまう可能性がある
         -  単純なKVSではない使い方をする場合は、発行するコマンドによってパフォーマンスを出しにくいことがある

# Thundering herd problem
Thundering herd problem とはキャッシュがない段階でサーバーに大量にリクエストを投げることで高負荷になってしまう問題のことです。
キャッシュが作成されていない状態で大量にリクエストを投げるのでキャッシュが活用できずに高負荷になってしまいます。

```mermaid
sequenceDiagram
    participant Client1 as Client 1
    participant Client2 as Client 2
    participant ClientN as Client N
    participant Server as Server/Resource
    
    Note over Client1,ClientN: 多数のクライアントがリソースを待機中
    Client1->>Server: リソースをリクエスト
    Client2->>Server: リソースをリクエスト
    ClientN->>Server: リソースをリクエスト
    Note over Server: サーバーが高負荷状態に
    Server-->>Client1: リソース提供(キャッシュなし)
    Server-->>Client2: 処理待ち(キャッシュなし)
    Server-->>ClientN: 処理待ち(キャッシュなし)
    Server-->>Server: キャッシュを作成
    ClientN->>Server: リソースをリクエスト
    Server-->>ClientN: リソース提供(キャッシュあり)
```
# インメモリを用いたキャッシュ
webアプリケーションのインメモリを用いてキャッシュを実装することもできます。ミドルウェアとの通信が不要な分高速ですがデメリットもあります。
- 実装によってはTTLの実装を自分でする必要がある
- デプロイした直後のパフォーマンス劣化や、デプロイ直後にThundering herd problemが発生する
- サーバーを追加すると状況を悪化させる可能性がある
- 問題のあるデータをキャッシュしたときに簡単に消せないことが多い

デプロイした時やサーバー追加時にキャッシュがないため、デプロイした直後のパフォーマンス劣化や、デプロイ直後にThundering herd problemが発生してしまいます。また、サーバーをキャッシュがない状態で追加するとそのサーバーへのリクエストではキャッシュがないのでパフォーマンスが大幅に低下します。また、言語やフレームワークによってはTTLを自分で実装しなくてはならない点にも注意です。

# キャッシュの実装方法
## キャッシュの再生成
キャッシュのもっともベーシックな方法はキャッシュを定期的に再生成することです。
まず、キャッシュの残り時間も取得します。そのキャッシュの残り時間が指定した時間を下回っている場合は一定の確率でexpireしているとみなしてキャッシュの再構築をします。
```mermaid
sequenceDiagram
    participant Client as クライアント
    participant Cache as キャッシュサーバー
    participant DB as データベース
    
    Client->>Cache: キャッシュをリクエスト
    alt キャッシュが有効な場合
        Cache-->>Client: キャッシュされたデータを返す
    else キャッシュが期限切れの場合
        Cache->>Cache: 再構築チェック
        alt 再構築の必要あり
            Cache->>DB: データを取得
            DB-->>Cache: データを返す
            Cache->>Cache: キャッシュを再生成
            Cache-->>Client: 再生成したデータを返す
        else 再構築の必要なし
            Cache-->>Client: 古いキャッシュデータを返す
        end
    end
```
- メリット
    - 実装が単純でデータの整合性も保ちやすい
    - アクセスがあったものだけキャッシュを生成するため効率的
- デメリット
    - キャッシュのないタイミングでリクエストした場合のレスポンスは遅い
    - Thundering herd problemが発生する
    - 再起動すると保存したデータが消えるミドルウェアにキャッシュを保存している場合、再起動してキャッシュが消えたときにOriginに対してリクエストが集中する
    - 実装方法によってはデプロイやサーバー投入時などにキャッシュがなくなるため、キャッシュがなくなった時にOriginに対してリクエストが集中する

この手法はデータの生合成が保ちやすく効率的にキャッシュを用いることができるため、最もよく使われます。しかしデメリットもあります。というのもキャッシュがない場合にパフォーマンス上の問題が多く発生します。Thundering herd problemも発生しますし、キャッシュがない場合にはその分レスポンスが遅くなります。また、また、memcachedのように再起動すると保存したデータが消えるミドルウェアでは、再起動してキャッシュが消えたときにリクエストが集中してしまいます。同様にインメモリキャッシュなど実装方法によってはデプロイやサーバー投入時などにキャッシュがなくなってしまうのでリクエストが集中する恐れがあります。

## 非同期にキャッシュを更新する
最新のキャッシュがない場合にはデフォルト値や古いキャッシュを返し、非同期にキャッシュ更新処理を実行することよって処理を高速化することができます

- メリット
    - レスポンスはほとんどのケースで高速に返せる
    - アクセスがあったものだけキャッシュを生成するため効率的
- デメリット
    - ロジックが複雑
    - ジョブキューなどの非同期に処理を実行できる仕組みが必要
    - キャッシュがないタイミングでリクエストした人には適切なレスポンスを返せない
    - Thundering herd problemは解決していない

この手法で高速化が見込めますがいくつかデメリットがあります。キャッシュを非同期的に更新するということはジョブやキューといった仕組みが必要になります。これによりロジックも複雑になってしまいます。また、キャッシュがない場合や古い場合には勿論適切なレスポンスを返せません。なお、この手法は根本からThundering herd problemを解決できているわけではないことにも注意してください。
          
## バッチ処理などで定期的にキャッシュを更新する
バッチ処理などで定期的にキャッシュを更新することもできます。この手法は比較的実装が簡単ですが以下のような問題があります。

- バッチで生成できるデータにしか使えない
- ほぼ使われないキャッシュも管理する必要がある
- 障害でキャッシュが揮発したときに復旧に時間がかかる

バッチ処理を用いる都合上、バッチで生成できるデータにしか使うことができません。また、事前にキャッシュを用意する都合上、データの資料率に関わらずキャッシュを生成する必要があります。ですのでほぼ使われないキャッシュも管理する必要性が出てきてしまいます。
障害がおこってしまった場合のデメリットとして復旧に時間がかかる可能性がある点が挙げられます。キャッシュ前提のシステムなのでキャッシュが揮発するとデータを取得できずにエラーになってしまいます。また、バッチの量によっては復旧に時間がかかってしまいます。

# キャッシュの監視
キャッシュの監視においては以下の二つを監視する必要があります
- evicted items
- キャッシュヒット率(cache-hit ratio)
## evicted items
evicted itemsとはexpireしていないのにキャッシュから追い出されたアイテム数のことです。このアイテム数が多い場合、適切にキャッシュを運用できていない可能性があります。evicted itemsが高い場合、必要だから生成されたキャッシュが使えない場合が多いということです。ですのでキャッシュの容量が足りずにうまく運用できていない可能性があります。
## キャッシュヒット率(cache-hit ratio)
キャッシュがどれだけ利用されているかを示す割合のことです。この値が高ければ高いほどキャッシュを活用できているということです。逆に低ければキャッシュを活用できていないので実装の見直しが必要です。
# まとめ
以上がisucon本7章まとめです。チューニングに必須な項目を要約したので是非ご活用ください！
その他の章の記事はこちらから
[ISUCON本の内容をまとめてみた DB編](https://qiita.com/Atkiyama/items/e9429910a17fa749e243)
[ISUCON本の内容をまとめてみた リバースプロキシ nginx編](https://qiita.com/Atkiyama/items/2dcfa7a3147368da6cec)
[ISUCON本の内容をまとめてみた キャッシュ編](https://qiita.com/Atkiyama/items/91a1c2924f15f29264cc)
[ISUCON本の内容をまとめてみた 高速化に必要なその他技術編](https://qiita.com/Atkiyama/items/8de9f6e5db5c6a4384c4)
[ISUCON本の内容をまとめてみた OS Linux編](https://qiita.com/Atkiyama/items/32bdc11ea631fe1c1820)