豪鬼メモ

一瞬千撃

DBMの設計と実装 その10 LRUキャッシュ

B+木をファイル上で実現するにあたり、個々のノードのデータをシリアライズしてハッシュテーブルのDBMに格納するということを前回述べた。そして、個々のノードにアクセスする度にハッシュDBMの読み書きをすると遅すぎるので、キャッシュ機構が求められる。そのキャッシュ機構の設計をしてみたい。


まずは、順序つきの連想配列が必要である。ここで言う順序とは、基本的には格納した順序だ。これは、ハッシュテーブルで連想配列を実装した上で、個々のレコードを双方向連結リストで繋ぐことで実現できる。キーと値には任意の型のオブジェクトを入れたいので、テンプレートクラスとして実装することになるだろう。こんなAPIになるかな。

template <typename KEYTYPE, typename VALUETYPE,
          typename HASHTYPE = std::hash<KEYTYPE>,
          typename EQUALTOTYPE = std::equal_to<KEYTYPE>>
class LinkedHashMap final {
 public:
  struct Record {
    /** The key. */
    KEYTYPE key;
    /** The value. */
    VALUETYPE value;
    /** The child record. */
    Record* child;
    /** The previous record. */
    Record* prev;
    /** The next record. */
    Record* next;
  };
  enum MoveMode {
    /** To keep the current position. */
    MOVE_CURRENT = 0,
    /** To move to the first. */
    MOVE_FIRST = 1,
    /** To move to the last. */
    MOVE_LAST = 2,
  };

  Record* Get(const KEYTYPE& key, MoveMode mode = MOVE_CURRENT);
  Record* Set(const KEYTYPE& key, const VALUETYPE& value,
              bool overwrite = true, MoveMode mode = MOVE_CURRENT);
  bool Remove(const KEYTYPE& key);
  Record* Migrate(const KEYTYPE& key, LinkedHashMap* dest, MoveMode mode);

  Record& front();
  Record& back();
  Iterator begin();
  Iterator end();
  size_t size();
};

キーと値を指定してSetを呼ぶと、そのキーと値の組がレコードとして内部に保存される。格納されたレコードはキーを指定してGetで取得したりRemoveで消したりすることができる。新たに格納されたレコードは連結リストの末尾に位置するのだが、modeをMOVE_FIRSTにすると、先頭にすることもできる。同様に、Getの際にmodeでMOVE_FIRSTを指定すると取得したレコードが先頭に移動し、MOVE_LASTを指定すると末尾に移動する。frontメソッドは先頭のレコードを参照し、backメソッドは末尾のレコードを参照する。イテレータを返すbeginやendも実装する。

中身はハッシュテーブルと単方向リンクリストで実装される典型的な連想配列だ。HASHTYPEパラメータで受け取ったハッシュ関数バケットを決定し、連結リストを辿りつつ、個々のレコードについて調べる。EQUALTOTYPEで受け取った一致判定関数の値が真であれば、そのレコードを該当とみなして、GetやSetやRemoveの操作を行う。このクラスはスレッドセーフではない。順序の概念があるので、全く並列化する余地がないのだ。よって、マルチスレッド環境で使う場合、呼び出し側に排他制御の責任を持ってもらう。

順序つきの連想配列があると、LRUキャッシュが簡単に実現できる。LRUとは、Least Recent Used、つまり最も昔に最後に使われたという意味だ。LRU要素を削除することでサイズを一定に保つキャッシュがLRUキャッシュで、最近使ったデータほど再利用される確率が高いという仮定に基づく戦略だ。さて、Getでデータにアクセスする際にmodeをMOVE_LASTで順序を最後にすると決めておく。とすると、必然的にLRUな要素は先頭に集まる。なので、サイズが一定を超えたら、それをfrontで取得して、消せば良い。

多くの場合にうまいこと働くLRUキャッシュにも欠点がある。利用頻度を全く考慮していないところだ。「最近使ったレコードは再利用されやすい」というのは事実かもしれないが、「頻繁に使われるレコードは再利用されやすい」という仮定の方がマシなケースも多そうだ。マシかどうかは、キャッシュのヒット率で判断する。実際のところ、何が最善かはユースケースによるので正解がない議論なのだが、ここでは両者の折衷案として、二層LRUキャッシュというのを考える。頻度を数えてレコードを並び替える処理はコストが高いので、ここは思い切って2段階に単純化する。キャッシュ内に存在する期間に一度でも再利用されたレコードは、ホットなキャッシュとして格上げする。それ以外はウォームなキャッシュと呼ぶ。ホットなキャッシュにもサイズ制限があり、それを超えたら、ホットキャッシュ中でLRUのレコードがウオームの末尾に格下げされる。ウォームキャッシュのサイズ制限を超えた場合、ウォームの中のLRUレコードは捨てられる。ホットキャッシュとウォームキャッシュの割合は1対2とかにしておくと良いだろう。上記のAPIでMigrateというのがあるが、それはホットからウォームへ、またウォームからホットへ、キャッシュからキャッシュにレコードを移動させるメソッドだ。複製して削除するよりもメモリ確保等のコストが少ないので移動専用のメソッドを用意した。

B+木のノードのアクセス頻度には確実に偏りが生じる。根ノードは常にアクセスされるが、末端に近い内部ノードはあまりアクセスされない。また、一部のリーフノードをその他のリーフノードより頻繁にアクセスするユースケースの方が一般的には多いだろう。むしろ全てのノードを満遍なくアクセスする真面目なユースケースを考える方が難しい。なので、単なる経験則ではあるが、二層LRUキャッシュの方が普通のLRUキャッシュよりは実用的だと思われる。ただし、二層LRUキャッシュでも困る問題がある。イテレータによる全体的な横断操作だ。例えば一部の進学校では全学年のテスト結果を降順に並べて廊下に張り出すだろう。その場合、インデックス全体がスキャンされる。そういった横断操作をされた場合、普通のLRUキャッシュだとキャッシュが全部流れ、二層LRUキャッシュだとホットに格上げされた一部だけが生き残ることになる。なので、横断的なアクセスであると考えられる場合には、ホットへの格上げをしないという運用をしたい。より具体的に言えば、リーフノードの双方向連結リストを辿って別のリーフノードを読み込む場合には、ホットへの格上げを抑制すればよい。そうすれば、横断操作を何度やられようが、ホットキャッシュの中身は流れなくなる。

以上の議論をもとに、二層LRUキャッシュのAPIを設計する。こんな感じになるかな。

template <class VALUETYPE>
class DoubleLRUCache final {
public:
  DoubleLRUCache(size_t hot_capacity, size_t warm_capacity);
  std::shared_ptr<VALUETYPE> Add(int64_t id, VALUETYPE* value);
  void Add(int64_t id, std::shared_ptr<VALUETYPE>&& value);
  std::shared_ptr<VALUETYPE> Get(int64_t id, bool promotion);
  std::shared_ptr<VALUETYPE> RemoveLRU(int64_t* id = nullptr);
  size_t Size() const;
};

このクラスは、キャッシュの要素となるオブジェクトの所有権も管理する機能を持つ。newしたオブジェクトをAddで渡すと、その所有権はキャッシュに移され、共有所有権を備えるshared_ptrが返される。なぜこうするかというと、キャッシュの中身はいつだって消される可能性があるが、キャッシュから取り出して使っている最中のオブジェクトがdeleteされると困るので、たとえキャッシュから消されても自分が使っている間はそのオブジェクトが生きながらえるようにしたいからだ。Addの実装で注意すべきは、新しいレコードをウォームキャッシュに加える前に、ホットキャッシュとウォームキャッシュの双方を調べて、既存のレコードがあれば、新しいレコードを破棄して、既存のレコードへのポインタを返すということだ。キャッシュ内に重複レコードを許すというバグは気付きにくくて非常に危険だ。GetはIDを指定してキャッシュの中身を取り出す。promotionパラメータが真であれば、ホットからウォームへの格上げをさせ、偽ならさせない。RemoveLRUはウォームのLRUか、それが空ならホットのLRUを取り出す。Sizeが0になるまでRemoveLRUを呼び続ければキャッシュを空にすることができる。

キャッシュから削除されて、どこからも参照されなくなり、すなわちshared_ptrの参照カウントがゼロになったオブジェクトは、deleteされてデストラクタが呼ばれる。その際に、ロードされてから一度でも変更操作を受けたオブジェクトは、自身のデータをハッシュDBMに書き戻す。つまりデータベース内のレコードとキャッシュ内のオブジェクトの一貫性に対する責任はキャッシュ機構ではなく中身のレコードのクラスが持つ。この分業をすることで、同一のキャッシュクラステンプレートでいかなるクラスのオブジェクトも扱えるようになる。

ところで、上記のDoubleLRUCacheクラスもスレッドセーフではない。やはり順序の概念があるものは並列化できないのだ。でも、この順序はリソース管理の都合で生じているだけだ。よって、順序の制約を少し弱めて、スロット分割してしまおう。全てのノードをIDのハッシュ値で32個くらいのスロットに分類して、その個々のスロットでLRUによるリソース管理を行う。個々のスロットのキャッシュを操作している間は、そのスレットのmutexのみをロックする。そうすればキャッシュの操作が最大32スレッドで並列化できることになる。さらに、内部ノード用のキャッシュとリーフノード用のキャッシュも分けて管理する。となると、B+木のデータベースであるTreeDBMの実装クラスはこんな感じのデータを持つことになる。

typedef DoubleLRUCache<LeafNode> LeafCache;
typedef DoubleLRUCache<InnerNode> InnerCache;

struct LeafSlot {
  std::unique_ptr<LeafCache> cache;
  std::mutex mutex;
};

struct InnerSlot {
  std::unique_ptr<InnerCache> cache;
  std::mutex mutex;
};

class TreeDBMImpl {
 private:
  constexpr size_t NUM_PAGE_SLOTS = 32;
  LeafSlot leaf_slots_[NUM_PAGE_SLOTS];
  InnerSlot inner_slots_[NUM_PAGE_SLOTS];
};

上で、「たとえキャッシュから消されても自分が使っている間はそのオブジェクトが生きながらえるようにしたい」と書いたが、実際は逆だ。キャッシュを消す操作をする際に、そのオブジェクトの参照カウントを調べて、他にそのオブジェクトを使っているスレッドがいれば、そのオブジェクトはキャッシュに書き戻して、削除を遅延させる。各ノードのキャッシュオブジェクトは唯一であるべきという制約を守るためだ。そうでないと場合、一貫性が破綻するシナリオが考えられる。

  • スレッドAはノード1のキャッシュオブジェクトを取得し、レコードXを加える。キャッシュオブジェクトの参照は保持したままである。
  • スレッドBはノード2をロードしてキャッシュに入れた結果、キャッシュの容量が制限を超える。
  • スレッドBによってキャッシュの整理が行われ、ノード1はキャッシュから削除される。
  • スレッドCはノード1をロードしてキャッシュに入れるとともに、ノード1にレコードYを加える。キャッシュオブジェクトの参照は保持したままである。
  • スレッドAは各種の処理を終え、参照を破棄する。その結果、デストラクタが走り、レコードXを持ったノードが書き戻される。
  • いつしかスレッドCが作ったキャッシュオブジェクトもキャッシュから削除され、レコードYを持ったノードが書きも戻される。
  • 結果として、Aの変更はなかったものになり、レコードXは消失する。

ということで、利用者がいるオブジェクトは消さないという選択をせざるを得ない。キャッシュオブジェクトのユニーク性を保証するには、「ノードの情報のロードとキャッシュへの登録とその参照の取得」および「参照カウントの確認とオブジェクトの再登録もしくは削除」は全てスロットキャッシュに紐づけられたロックの中で行われねばならない。したがって、あるスロットのキャッシュの容量調整をするコードは以下のようになるはずだ。

Status TrimLeafSlot(LeafSlot* slot) {
  std::lock_guard<std::mutex> lock(slot->mutex);
  std::vector<std::shared_ptr<LeafNode>> deferred;
  // キャッシュが飽和している限り続ける。
  while (slot->cache->IsSaturated()) {
    // LRUレコードをキャッシュから消して、取り出す。
    auto node = slot->cache->RemoveLRU();
    // 誰かがそのレコードをまだ使っていたら、退避させる。
    if (node.use_count() > 1) {
      deferred.emplace_back(node);
    } else {
      // 誰も使っていなければ、必要に応じて保存して、自然消滅させる。
      const Status status = SaveLeafNode(node.get());
      if (status != Status::SUCCESS) {
        return status;
      }
    }
  }
  // 退避させたレコードを再登録する。
  while (!deferred.empty()) {
    auto node = deferred.back();
    deferred.pop_back();
    slot->cache->Add(node->id, std::move(node));
  }
  return Status(Status::SUCCESS);
}

キャッシュ機構を利用する際に最も重要かつ難題なのは一貫性の保証である。そのためには、あるリソースのオブジェクトは唯一でなければならない。一方で、個々のリソースのオブジェクトを構築する処理と、それに付随するデータの読み込み処理は、キャッシュオブジェクトのロックの外側で行いたい。そうでないとデータベースの並列性がキャッシュ機構の並列性に足を引っ張られてしまう。したがって、あるリソースのデータをロードしてキャッシュに入れたオブジェクトを返すという一連の処理は以下のようなフローになる。オブジェクトの構築処理がロックの外なので同一IDのオブジェクトの構築を複数スレッドが同時に行う可能性があるのだが、Addメソッドが内部で重複の回避と必要に応じたオブジェクトの破棄を行ってくれるので、最後に一貫性が回復される。この手の投機的並列処理の実装には本当に気を遣う。

std::shared_ptr<Object> DBM::LoadObject(int64_t id, CacheSlot* slot) {
  {
     // スコープロック内で既存のレコードを調べて、あれば返す。
     std::lock_guard<std::mutex> lock(slot->mutex);
     auto obj = slot->cache->Get(id);
     if (obj != nullptr) return obj;
  }
  // データベースを読んで、オブジェクトを構築する。
  Object* obj = ReadDatabaseAndCreateObject(id);
  // スコープロック内で、構築したオブジェクトを登録し、そのポインタを返す。
  std::lock_guard<std::mutex> lock(slot->mutex);
  return slot->cache->Add(id, obj);
}

これで行けるはずだ。B+木を支えるのがキャッシュ層とストレージ層の二つのハッシュテーブルであるというあたりがちょっと面白くはないだろうか。ところで、この基本的な構造はKCと一緒なのだが、KCでは手抜きしてテーブル単位のreader-writerロックをかけていた。今回はキャッシュはスロットロックで並列化して、個々のノードの操作は各ノードが持つreader-writerロックで並列化する。ノードの操作の並列化に関しては次回以降に論じることになるだろう。