データ特性に基づくデータベース設計指針：頻繁な読み書きが発生するデータへの対応

## 目次

- [頻繁な読み書きに強いデータベース設計とは？](#頻繁な読み書きに強いデータベース設計とは)
- [インデックスについての予備知識](#インデックスについての予備知識)
    - [例：データベースのログ構造](#例データベースのログ構造)
    - [インデックスは読み取り性能を向上させる](#インデックスは読み取り性能を向上させる)
    - [インデックスは書き込み性能低下とのトレードオフ](#インデックスは書き込み性能低下とのトレードオフ)
- [インメモリインデックスは、書き込みトレードオフを最小にする](#インメモリインデックスは書き込みトレードオフを最小にする)
- [インメモリインデックスに不向きなデータ特性](#インメモリインデックスに不向きなデータ特性)
    - [大規模なデータレコードの新規作成のみで更新機会がないデータ](#大規模なデータレコードの新規作成のみで更新機会がないデータ)
- [インメモリインデックスを活用するDBアプリケーション・エンジン一覧](#インメモリインデックスを活用するdbアプリケーションエンジン一覧)
- [まとめ](#まとめ)
- [参考](#参考)


## 頻繁な読み書きに強いデータベース設計とは？

- インメモリインデックスを持つデータベースエンジンは、頻繁な読み書きが発生するデータに有効である
    - インメモリインデックスとは、インデックス構造をメモリに持たせる特徴を指す

## インデックスについての予備知識

### 例：データベースのログ構造

- インデックスを説明する例として、下記のようなシンプルなデータログを考える※
※ あくまでインデックスの説明としての例であり、特定のデータベースのログ構造を示しているわけではない

```
Offset    データログ内容

0         PUT user:123 → {"name": "Alice", "age": 25}
58        PUT user:456 → {"name": "Bob", "age": 30}
112       PUT user:123 → {"name": "Alice", "age": 26} ← 上書き
168       DEL user:456                               ← 削除マーカー（Tombstone）
```

- これは、ユーザーIDに対するユーザーデータのログである
    - ログには、追記のみが可能
        - ユーザーデータ更新時は、更新後のデータの状態を保存
        - ユーザー削除時は、専用の削除ログを末尾に追加する
    - 特定のユーザーIDのデータを確認したい場合は、そのユーザーIDの最新のログを読み出す

### インデックスは読み取り性能を向上させる

- インデックスがない場合
    - ログから目的のユーザーデータを探索する計算量は、O(N)
        - すべてのログをシークする必要がある

- インデックスがある場合
    - 下記のようにユーザーIDに対応する最新のログが格納されたオフセットを、持っているとする
        - この場合、ログから目的のユーザーデータを探索する計算量は、O(1)となる※

※ 目的のユーザーIDのインデックスを探索する計算量は、ログから目的のユーザーデータを探索する計算量より大幅に小さいものとする。

```
{
  "user:123": 112
  "user:456": 168
}
```

上記のように、インデックスがあることで、目的のキーに対する読み取り性能を大幅に向上させることができる。

### インデックスは書き込み性能低下とのトレードオフ

- インデックスの主なデメリットは、書き込み性能を低下させること
    - インデックスがない場合は、書き込みの際に必要なことは、データログの末尾にデータを追加するだけだった
    - これに対し、インデックスがある場合、インデックスの更新操作が追加で発生する

## インメモリインデックスは、書き込みトレードオフを最小にする

- インデックスを追加することは、書き込み時にインデックスを更新作業をしなければならない
- この書き込みコストの増大というデメリットを最小限に抑えるのが、インメモリインデックスである
    - インメモリインデックスとは、すべて（または頻繁にアクセスされる一部）のキーに対するインデックス情報をメモリ上に保持する手法
        - 高速なメモリアクセスで、インデックスを更新できる

## インメモリインデックスに不向きなデータ特性

### 大規模なデータ・レコードの新規作成のみで、更新機会がないデータ

- インメモリインデックスは、メモリにすべてのキーのインデックスを格納する必要がある
    - メモリに保存できない程インデックスが大きくなるとスワップ領域を使わなければならない
    - そのため、レコードの新規作成が多く、キー数が多くなる（インデックスが膨れる）ような特性を持つデータは、インメモリインデックスの恩恵を十二分に得ることができない

## インメモリインデックスを活用するDBアプリケーション・エンジン一覧

| 名前                   | 種類             | 主なインデックス構造                           | 特徴                                     | 用途例                                  |
| -------------------- | -------------- | ------------------------------------ | -------------------------------------- | ------------------------------------ |
| **Bitcask**          | KVS / Log構造    | メモリ上のハッシュマップ                         | 単一キー読み書きに超高速。インメモリインデックスで高速アクセス        | Riak（旧）で使用。アクセス頻度が高く、キー数が限定的な用途      |
| **Redis**            | KVS / データ構造DB  | 辞書（hash table）、スキップリスト（Sorted Set）など | データ全体またはホットデータをRAMに保持。構造ごとに最適化されたインメモリ表現  | キャッシュ、セッション、リアルタイム分析                 |
| **RocksDB**          | KVS / LSMツリー   | MemTable（skiplist or hash table）     | 書き込みはまずRAM上のインデックス構造に蓄積、定期的にディスクへフラッシュ | 高スループットなストレージエンジン。Kafka Streamsなどで利用 |
| **LMDB**             | KVS / B+木      | メモリマップトB+木（仮想メモリにマップ）                | ディスクをメモリに直接マッピングする設計。高速読み取り            | 高速読み取り用途、Python環境、機械学習DB（Chromaなど）   |
| **LevelDB**          | KVS / LSMツリー   | MemTable（スキップリスト）                    | RAM上で高速なキー挿入、定期的にSSTable化              | 組み込み用途、ブロックチェーン系（Bitcoin Core）       |
| **FoundationDB**     | 分散KVS          | ハッシュ＋B木                              | 分散型ながら高速で一貫性保証。内部はRAMに強く依存             | 大規模トランザクションシステム。Appleが活用             |
| **DuckDB**           | カラム指向RDB       | B+木（メモリ常駐前提）                         | 分析系に特化したRDB。ワークセットはRAM想定               | ローカルOLAP分析。Pandas/Arrow連携            |
| **Tair**（by Alibaba） | 拡張KVS（Redis派生） | SkipList/Hash                        | Redis互換。インメモリインデックス活用＋持続化設計            | 大規模リアルタイムアプリケーション                    |
| **SAP HANA**         | インメモリRDB       | カラムストア＋辞書圧縮                          | すべてのデータをメモリ上で保持。高性能クエリ処理               | エンタープライズ級リアルタイム分析                    |
| **VoltDB**           | インメモリRDB       | B+木 / Hash                           | 分散インメモリRDB。高いスループット                    | Telco/IoT 分野の高速トランザクション              |


## まとめ

- インデックスはデータの読み取り性能を大幅に向上させる反面、書き込みコストの増加というトレードオフがある
- インメモリインデックスはこのトレードオフを最小限に抑えるアプローチであり、頻繁な読み書きが発生するユースケースに特に有効
- ただし、全キーをメモリに載せる必要があるため、インデックスが肥大化するようなデータには不向き
- インメモリインデックスを採用する代表的なデータベースとして、Bitcask・Redis・RocksDB・SAP HANA などがある
- ユースケースやデータ特性に応じて、適切なインデックス方式とストレージエンジンの選択が重要

## 参考

- [データ指向アプリケーションデザイン ―信頼性、拡張性、保守性の高い分散システム設計の原理](https://www.amazon.co.jp/%E3%83%87%E3%83%BC%E3%82%BF%E6%8C%87%E5%90%91%E3%82%A2%E3%83%97%E3%83%AA%E3%82%B1%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%83%87%E3%82%B6%E3%82%A4%E3%83%B3-%E2%80%95%E4%BF%A1%E9%A0%BC%E6%80%A7%E3%80%81%E6%8B%A1%E5%BC%B5%E6%80%A7%E3%80%81%E4%BF%9D%E5%AE%88%E6%80%A7%E3%81%AE%E9%AB%98%E3%81%84%E5%88%86%E6%95%A3%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0%E8%A8%AD%E8%A8%88%E3%81%AE%E5%8E%9F%E7%90%86-Martin-Kleppmann/dp/4873118700)