Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 

2016年12月23日

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

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

ZFS と EXT4 でスナップショットが木構造になるのはメモリ中に取り込んでいる間で、 ストレージ上では単に昇順リストに展開して保存するようにしているようです。 メモリ中でだけ木構造として扱うことから、 メモリに向いた 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;
    }
}

2016年12月22日

[][]非カーネル用のスラブ・アロケータ

オペレーティング・システムのカーネルのオブジェクト・キャッシュとして利用されているスラブ・アロケータは、 単なる高速なアロケータではなく、 割付・初期化済みのオブジェクトを alloc して、 free の時点ではデストラクタを動かさずに、 次の alloc で free 時点の内容のまま返す働きがあります。 そのために、 フリー・リストをオブジェクトの外に作ったり、 alloc 中のオブジェクトも強制的にデストラクタを摘要してメモリを解放できるようにリストを辿って場所を求められるようになっています。 これは、 カーネルが扱うデータ型が限られている割に、 大きなオブジェクトを頻繁に割付・解放を繰り返し、 初期化結果は同じ内容になっていることが多い、 といったカーネル特有の事情に合わせてあるためです。

一方、 アプリケーションでは、 カーネルに比べると扱うデータ型が増える上に、 同じ内容のオブジェクトを使いまわす利点が減る傾向があります。 たいていの場合は割り付け時にコンストラクタを動かす方が都合が良いですし、 memchached のようにプレーンなデータの割付に使うときは前の内容を使えることの方が少なくて、 全部書き直してしまうことを前提にしても負荷が増えない傾向があります。 アプリケーションで、 スラブ・アロケータを使うときは、 同じサイズのオブジェクトを同じページに固めてフラグメンテーションがおきにくくするというメリットだけが欲しい場合がほとんどです。

free 後のデータを破壊してもかまわないとなると、 フリー・リストのリンクポインタ置き場に廃棄したオブジェクトの領域を直接使っても問題ありません。 さらに、 デスタラクタを動かしてから free するので、 生存しているデータをリストにつなげて管理しておく必要もなくなります。

以上から非カーネル用のスラブ・アロケータを考えてみます。

スラブ中にバッファ管理情報をオブジェクト外に持つ必要がなくなるので単純になります。 フリー・リストはスラブごとに別々にもたせておいた方が、 リストの更新でページのヒット率が悪化することがなくなるので、 この点はカーネル用と同じとします。 スラブ間のリンクは、 空になったスラブを廃棄するときにスラブを空きありスラブのリストから削除することがあるので、 相変わらず必要です。 ただし、 キャッシュで管理するスラブのリストは、 空きありリストだけでかまいません。 そういえば、 もはや利用中のオブジェクトを残しておくことがないので、 キャッシュという呼び方はふさわしくありませんし、 スラブ・リストと呼び変えることにしましょう。 そうなると、 データ構造は次のようになるのでしょう。 さらに、 オブジェクトの型ではなく、 サイズ単位でスラブのリストを作ることにすると、 スラブのリストが何本必要かはあらかじめ求めておくことができるので、 スラブ・リストのヘッダの個数は固定されて動的に管理する必要がなくなります。

enum { PAGESIZE = 4096 };   // 物理ページサイズ、およびファイル・システムのブロックサイズの典型値

union slab_type {
    struct {
        slab_type* linkprev;         // 空きを持つスラブのリスト用リンク
        slab_type* linknext;
        std::size_t obj_size;        // オブジェクトのサイズ
        std::size_t count;           // スラブ内の割り当て中オブジェクト個数
        std::uint32_t* freecell;     // スラブ内のフリー・リストはオブジェクト
    } h;                             // 領域にリンクを置き、 バッファ・コントロール
    std::uint32_t u32[PAGESIZE / 4]; // を省きます。
    std::uint8_t u8[PAGESIZE];
};

struct slablist_type {
    slab_type* linkprev;             // 空きを持つスラブだけをリストにします
    slab_type* linknext;
    std::size_t obj_size;            // オブジェクトのサイズ slab の同名メンバの初期値
    std::size_t count;               // このサイズのオブジェクトの全割り当て個数
};

2016年12月20日

[]動的ハッシュ表: W. Litwin の線形ハッシュ法

現代のデータベース・マネジメント・システムがハッシュ索引に利用している線形ハッシュ法 (Linear Hashing) のさわりを、 Ruby で遊んでみます。 線形ハッシュ法は、 外部記憶装置上へ動的にハッシュ表を作製する方法の一つで、 1980 年に W. Litwin が発見しました。 なお、 線形ハッシュの実例のソースコードを読むなら、 PostgreSQL のハッシュ索引がこの手法を広めた P. Larson の論文通りでわかりやすいかもしれません。

動的ハッシュ表では、 他にハッシュ値のトライを使うやりかたがあり、 こちらは gdbm が採用しています。 どちらもビット・パターンの一部が同じハッシュ値のレコードをバケットにまとめて格納していきます。 違いはバケットがあふれたときの扱いで、 トライ法では、 あふれた時点で即座にトライの枝を伸ばしてバケットを分割します。 線形ハッシュ法では、 バケットの分割はラウンド・ロビンで先頭から順番におこなっていき、 分割の順が回ってくるまでは、 あふれたままにします。 大雑把には、 挿入時にバケット分割の負荷をかけるのがトライ法で、 読み出し時にあふれた分の探索で負荷をかけるのが線形ハッシュ法と言えるのでしょう。 初期の K. Thompson の dbm から線形ハッシュまでを眺めるには次のレビューがわかりやすいです。

http://www.eecs.harvard.edu/margo/papers/usenix91/paper.pdf

線形ハッシュ法の仕組みがわかりやすいのは、 初期時のバケットの個数が 2 のべき乗の場合なので、 今回は 4 つのバケットから始めることにします。 さらに、 バケットのあふれの扱いを考えるが面倒なので、 あふれを気にせずに配列に突っ込んでいくことにします。 バケットが 4 つのときはハッシュ値の下位 2 ビットを使って、 レコードをバケットへ push します。 使っているビット数は level 変数で表します。 例えば、 原子番号 10 までの元素名をキーとして、 4 つのバケットに突っ込んでいった結果は次のようになりました。 なお、 レコードは安直にキーと値のペアの配列にしています。

    assert @bucket[0] == [["Hydrogen", 1], ["Carbon", 6], ["Nitrogen", 7], ["Neon", 10]]
    assert @bucket[1] == [["Beryllium", 4]]
    assert @bucket[2] == [["Helium", 2]]
    assert @bucket[3] == [["Lithium", 3], ["Boron", 5], ["Oxygen", 8], ["Fluorine", 9]]
    assert @level == 2 && @step_ptr == 0

この次のレコードを追加した時点で最初のバケット分割がおこるものとします。 レコードは 2 番目のバケットへ追加するのですが、 追加場所に関係なく分割がおこなわれ、 バケットの数が 5 つに増えます。 分割対象のバケットはステップ・ポインタ step_ptr が示しており、 ゼロに初期化するので、 まず先頭のバケットが分割されます。 分割が終わると step_ptr は 1 に変化します。

    assert @level == 2 && @step_ptr == 0
    # split_bucket で分割実行
    assert @bucket[0] == [["Carbon", 6], ["Nitrogen", 7], ["Neon", 10]]
    assert @bucket[1] == [["Beryllium", 4], ["Sodium", 11]]
    assert @bucket[2] == [["Helium", 2]]
    assert @bucket[3] == [["Lithium", 3], ["Boron", 5], ["Oxygen", 8], ["Fluorine", 9]]
    assert @bucket[4] == [["Hydrogen", 1]]
    assert @level == 2 && @step_ptr == 1

さらにバケットの分割が進んで、 step_ptr が 2 になりました。 ここまでで、 バケット 0 は 0 と 4 に分割され、 1 は 1 と5 に分割されています。 2 と 3 は分割前のままです。

    assert @bucket[0] == [["Carbon", 6], ["Nitrogen", 7], ["Neon", 10]]
    assert @bucket[1] == [["Beryllium", 4]]
    assert @bucket[2] == [["Helium", 2], ["Aluminum", 13], ["Phosphorus", 15]]
    assert @bucket[3] == [["Lithium", 3], ["Boron", 5], ["Oxygen", 8], ["Fluorine", 9]]
    assert @bucket[4] == [["Hydrogen", 1]]
    assert @bucket[5] == [["Sodium", 11], ["Magnesium", 12], ["Silicon", 14]]
    assert @level == 2 && @step_ptr == 2

さて、 step_ptr がゼロでないときは、 分割されたバケットと、 分割前のバケットが混在しています。 分割前のバケットに使うハッシュ値のビット数は level で、 分割済みのバケットに使うのは level + 1 ビットです。 この事情を考慮して、 キーからバケット番号を求めるメソッドは次のようになります。

#@<キーからバケット番号を求めます@>=
  def bucket_address(key)
    x = key.hash & ((1 << (@level + 1)) - 1)
    if x < (1 << @level) + @step_ptr
      x                   # バケットの個数より少ないとき
    else
      x ^ (1 << @level)   # @level + 1 ビット目をゼロに潰す
    end
  end

バケットにキーを持つレコードが含まれているかどうかは、 Array の assoc メソッドで調べることができるので、 ハッシュ表にキーが含まれているかどうかを調べるのは簡単です。

#@<キーがハッシュ表に含まれているかどうか調べます@>=
  def key?(key)
    x = bucket_address(key)
    not @bucket[x].assoc(key).nil?
  end

さらにバケットの分割を進めていくと、 level が 2 のときは 3 のバケットの分割で、 すべてのバケットを分割してしまったことになります。 この場合、 level を増やして 3 にし、 step_ptr をゼロに戻します。

    assert @bucket[0] == [["Carbon", 6], ["Nitrogen", 7], ["Neon", 10], ["Chlorine", 17]]
    assert @bucket[1] == [["Beryllium", 4]]
    assert @bucket[2] == [["Helium", 2], ["Phosphorus", 15], ["Sulfur", 16]]
    assert @bucket[3] == [["Lithium", 3], ["Boron", 5], ["Fluorine", 9], ["Argon", 18]]
    assert @bucket[4] == [["Hydrogen", 1]]
    assert @bucket[5] == [["Sodium", 11], ["Magnesium", 12], ["Silicon", 14]]
    assert @bucket[6] == [["Aluminum", 13]]
    assert @bucket[7] == [["Oxygen", 8], ["Potassium", 19]]
    assert @level == 3 && @step_ptr == 0

バケットの分割をおこなうタイミングは、 あふれ分を勘定にいれない収録可能なレコード数に対する、 収録されている全レコード数の割合がしきい値を越えたところとするのが良く使われているやりかたのようです。 ここでは、 75% をしきい値に選ぶことにします。 バケットの収録可能レコード数が少ないときは、 このしきい値だと激しくあふれることがあるのですが、 多くなると、 おとなしくなっていく傾向があります。

# Linear Hashing by W. Litwin (1980)
class LinearHashing
  BUCKET_SIZE = 4
  UTILIZATION = BUCKET_SIZE * 256 * 75 / 100

  attr_reader :size, :level, :step_ptr, :bucket

  def initialize
    @level = 2      # ハッシュ値の利用ビット数
    @step_ptr = 0   # 次に分割するバケット番号
    @size = 0       # レコード数
    @bucket = Array.new(1 << @level) { Array.new }
  end

#@<キーからバケット番号を求めます@>
#@<キーがハッシュ表に含まれているかどうか調べます@>

  def store(key, value)
    x = bucket_address(key)
    r = @bucket[x].assoc(key)
    if not r.nil?
      r[1] = value
    else
      @bucket[x].push [key, value]
      @size += 1
      n = (1 << @level) + @step_ptr
      if (@size << 8) > n * UTILIZATION
        split_bucket    # 全収容可能レコード数の 75% を越えたら分割をします
      end
    end
  end

#@<step_ptr のバケットを分割します@>

end

バケットの分割は、 分割対象のバケット中に登録済みのレコードのハッシュ値から level + 1 ビット分を取り出して、 それの最上位がゼロなら元の場所のバケットへ、 1 なら新しいバケットへ push していきます。

#@<step_ptr のバケットを分割します@>=
  def split_bucket
    bucket_lower = []  # 元の場所のバケット用
    bucket_upper = []  # 新しく追加するバケット用
    hash_mask = (1 << (@level + 1)) - 1
    n = 1 << @level
    @bucket[@step_ptr].each do |r|
      x = r[0].hash & hash_mask
      if x < n
        bucket_lower.push r    # 最上位ビットがゼロ
      else
        bucket_upper.push r    # 最上位ビットが 1
      end
    end
    @bucket[@step_ptr] = bucket_lower
    @bucket.push bucket_upper

    @step_ptr += 1
    if @step_ptr >= n
      @step_ptr = 0
      @level += 1
    end
  end