テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

dm-lcの紹介 (3) メタデータ

dm-lcは, キャッシュを4KBごとに管理します. このキャッシュを管理するデータ構造をmetablockと呼んでいます. dm-lcでは, metablockをすべてメモリ上に配置します. つまり, RAM使用量は, SSDキャッシュデバイスの大きさに比例します. 以下が, メモリ上のmetablockのコードです*1. このうち, (1) - (4)についてのみ説明します.

struct metablock {
        sector_t sector; // (1)
        cache_nr idx; /* const. 4B. */
        struct hlist_node ht_list; // (2)
        u8 dirty_bits; /* eight bit flags */ // (3)
        device_id device_id; // (4)
};

dm-lcは, 一つのキャッシュデバイスを複数のbacking storeに共有させることが出来ます. (4)は, 「どのキャッシュデバイスのものか」というIDです. マックス255個のbacking storesに共有可能であり, ほとんどのケースでは十分でしょう*2. (1)は, このキャッシュが, backing store上のどの4KBに相当するものかを示します. (1), (4)をまとめると, 「このmetablockは, backing store ID ${device_id}上の, ${sector}セクタから始まる4KBを管理している」ということになります. 以下のmb_hit関数は, キャッシュ探索時のhit判定をします.

static bool mb_hit(struct metablock *mb, struct lookup_key *key)
{
        return (mb->sector == key->sector) && (mb->device_id == key->device_id);
}

(2)について. dm-lcは, メモリ上のキャッシュ探索をチェイン法を使ったハッシュテーブルで行なっています. このhlist_nodeというのが16byteと大きいため, 将来的には別のデータ構造で管理することもあり得ますが, dm-lcはあくまでもwriteキャッシュであり, スパイク的なwrite負荷をしのげればいいくらいの楽観的な視点に立つと(例えばRAIDキャッシュの10倍でも効果あると思います),「とにかくデータを投機的に貯めこんで将来のキャッシュヒットを待つ」しかないreadキャッシュに比べると, キャッシュデバイスはそれほど大きくなくても良いということになるため, メモリ量に関してはある程度富豪的に使っても実用上問題ないという見方が出来ます. それよりはむしろ, オーバーヘッドの少なさを採用する方が良い. キャッシュを削除したりすることもあるため, この点で有利なチェイン法を採用しています.

(3)は, 4KBキャッシュ中の512Bセクタ * 8のdirtinessを管理するための値です. dm-lcでは, 512B単位でのパーシャルライトを, DRAMバッファ上で吸収します. そのあとでディスクに対して, ログ書きするため, パーシャルライトのためにRead-Modify-Writeをするなどのペナルティが(少なくともその瞬間は)ありません. Linuxでは, ファイルシステムからのwriteはほとんどが4KB単位で降ってきますが, 中には, メタデータ書き出しなどでそれより小さいものもあります. これらのために大きなパナルティを食うのは合理的ではないため, このような実装にしています.

dm-lcでは, キャッシュデバイスをsegmentという単位に切って管理しています. これがログの大きさです. segmentは, 最大1MB大です. 簡単のため, 以下では, 1MBとして話をします. ソースコードのコメントでも, 1MBとして話をしています. 実際は調節可能であり, 例えば, ログ大が64KBと小さくすることも可能です. この場合も, キャッシュデバイスを一周するまでmigrateを強制されないという性質によって, 高writeスループットが実現出来ます.

dm-lcの大まかな動作は以下のようになります.

  1. write I/Oをバッファに格納する. // repeat
  2. バッファがいっぱいになる (255個 = (1MB - 4KB) / 4KB が最大格納個数).
  3. ログ書き出し用のメタデータ(A)を作成して, リストにつなぐ. flush daemonが非同期でI/O処理する.

このうち, (A)に相当するものが以下のsegment_header_deviceです. segmentは, メモリ上ではsegment_headerという構造体で管理しており, ログ書き出しの時に, せっせとこの構造体を作成します(prepare_segment_header_device). そして, 1MBバッファ(writebuffer)の先頭4KBにヘッダをコピーして, ログとして完成させます. 残り(1MB-4KB)には最大255個のキャッシュデータが入っています.

struct segment_header_device {
        /* --- at most 512 byte ---*/
        size_t global_id;
        u8 length;
        u32 color; /* initially 0. 1 for first turn. */
        /* -----------------------*/
        struct metablock_device mbarr[NR_CACHES_INSEG]; /* This array must locate at the tail */
} __attribute__((packed));
static void prepare_segment_header_device(
                struct segment_header_device *dest,
                struct lc_cache *cache, struct segment_header *src)
static void prepare_meta_writebuffer(void *writebuffer, struct lc_cache *cache, struct segment_header *seg)
{
        struct segment_header_device *header = kmalloc_retry(sizeof(*header), GFP_NOIO);
        prepare_segment_header_device(header, cache, seg);
        void *buf = kmalloc_retry(1 << 12, GFP_NOIO);
        memcpy(buf, header, sizeof(*header));
        kfree(header);
        memcpy(writebuffer, buf, 1 << 12);
        kfree(buf);
}

その他, segment_header_deviceのうち,
lengthは, このログが未熟(255個のキャッシュを格納出来なかった)ままログ書きされることを許すため(永続性への対処です)の値であり,
colorというのは, ログがキャッシュデバイスを一周してきた時のために, 「何周目か」を覚えておくためのものです*3. これによって, クラッシュリカバリ時に, 「全ログの中でどのログが本当の一番古いものなのか」というスキャンが正常に動作します.

"at most 512 byte"というコメントについて説明すると, メタデータメタデータたる, global_idからcolorまでの部分は, atomicである必要があります. Facebookによるflashcacheではコード上, キャッシュデバイスへのwriteについて, 512Bのatomicityを利用している箇所があります(以下のコメント). 強い確証はないですが, 私も, 512Bのatomicityは保証されているのだという前提の下で実装をしています.

 * Note: When using larger flashcache metadata blocks, it is important to make 
 * sure that a flash_cacheblock does not straddle 2 sectors. This avoids
 * partial writes of a metadata slot on a powerfail/node crash.

(訳) 大きなmetadata blocksを使う時には, flash_cacheblockが2セクタをまたがないようにすることが重要です. これにより, 電断やノードクラッシュ時に, metadata slotがパーシャルライトされてしまうことを回避することが出来ます.

listに繋ぐ構造体が以下のflush_contextです. flush daemonは, こいつをリストからpopして, I/O処理を行います. segment_headerを保持しており, I/O処理が終わったあとに, データを変更します. 例えば, completionなどです.

struct flush_context {
        struct list_head flush_queue;
        struct segment_header *seg;
        struct writebuffer *wb;
        struct bio_list barrier_ios; // 永続性に関係している. 後々話す.
};

以上が, dm-lcにおけるメタデータ設計の概要です. writeデータがバッファに格納され, ログとして書き出される仕組みが理解出来たかと思います. 理解出来ないぞここもっとkwskということがあれば, twitter(@akiradeveloper)まで.

*1:将来的に改良の余地がありますが, 概念的には変更ないでしょう

*2:ほとんどのケースでは, backing storeは1つだと思います

*3:名前は, 前の実装の名残であり, turnあたりに変更しようかと思っています