ストレージ・アロケータのエクステント・ツリー操作

最近の巨大ストレージ対応ファイル・システムは、 フリー領域の管理をエクステント・ツリーでおこなうようになっています。 現在入手が容易な数 TB のディスクの場合、 伝統的なビットマップでフリー領域を管理しようとすると、数十から数百 MB が必要で、 まだ扱おうと思えば扱えるサイズですが、 ファイル・システム開発者は数 PB のストレージの実現を想定して、 スケールアウト可能な方法を取り入れつつあるわけです。 例えば、 この分野の開拓者である ZFS では、 数 PB クラスのストレージを数百の単位に分割し、 それぞれで、 エクステント・ツリーのスナップショットと、 スナップショット作成時点以降のアロケートとフリーをおこなったエクステントをリストアップしたログを組み合わせて管理しています。 ファイル・システムではメモリにスナップショットを読み込み、ログの内容を反映させて、 現在のストレージ内のフリー領域を利用しています。 LinuxEXT4 も類似の方法を利用できるように開発が進められています。

ZFSEXT4 でスナップショットが木構造になるのはメモリ中に取り込んでいる間で、 ストレージ上では単に昇順リストに展開して保存するようにしているようです。 メモリ中でだけ木構造として扱うことから、 メモリに向いた AVL 木を ZFS が、 同じく赤黒木は EXT4 が採用しています。 エクステントは、 いろんな大きさの重複のない連続領域のことで、 開始位置と長さのペアで表すことが多いようです。 エクステントを木構造に登録するとき、 キーに開始位置を選ぶようです。

C++STL の std::map は赤黒木で実装してあるので、 フリー領域のエクステントを木に入れておいて、 そこから切り出して領域に割り付けたり、 逆に解放して木に戻したりといった処理をどうするのか試してみることにします。

#include <map>
#include <cstdint>

struct extent_type {
    std::uint64_t start;
    std::uint64_t length;
};

割付、つまり木からエクステントを取り除いたり、縮めたりするのは、 比較的簡単です。 木のキーを変えずに縮めるために、 空きエクステントの後ろ側からエクステントを切り出すようにすると、 さらに簡単になります。

void
extent_alloc (std::map<std::uint32_t,extent_type>& tree, extent_type const& extent)
{
    // next.start <= extent.start となるエントリを lower_bound で探します。
    auto next = tree.lower_bound (extent.start);
    if (next == tree.end ())
        return;  // 既存のフリー領域は木に登録してあるので、 ここはおこりえません。

    if (next->second.start == extent.start) {
        // エクステントをまるごと割り当てるとき
        tree.erase (next);
    }
    else if (next != tree.begin ()) {
        // 必ずエクステントの後ろ側から切り出すようにします
        auto prev = next;
        --prev;
        if (prev->second.start + prev->second.length == extent.start + extent.length) {
            tree[prev->second.start].length = prev->second.length - extent.length;
        }
    }
}

解放、 つまり木へエクステントを加えるには、 隣接するエクステントを統合したいので、 おこりうる場合を列挙します。 直前の空き領域と隣接しているときは 1 のビットを立て、 直後の空き領域と隣接するときに 2 にビットを立てます。 これでおこりうる 4 通りのどれなのかが決まります。

void
extent_free (std::map<std::uint32_t,extent_type>& list, extent_type extent)
{
    auto next = list.lower_bound (extent.start);
    auto prev = next;
    int merge_to = 0; // 1:prev+extent, 2:extent+next, 3:prev+extent+next
    if (! list.empty ()) {
        if (prev != list.begin ()) {
            --prev;
            merge_to = prev->second.start + prev->second.length == extent.start ? 1 : 0;
        }
        if (next != list.end ()) {
            merge_to |= extent.start + extent.length == next->second.start ? 2 : 0;
        }
    }
    switch (merge_to) {
    case 0:   // 統合なし
        list[extent.start] = extent;
        break;
    case 1:   // 直前の空き領域に統合
        prev->second.length += extent.length;
        break;
    case 2:   // 直後の空き領域に統合
        extent.length += next->second.length;
        list.erase (next);
        list[extent.start] = extent;
        break;
    case 3:   // 両脇の空き領域に統合
        prev->second.length += extent.length + next->second.length;
        list.erase (next);
        break;
    }
}