テストステ論

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

dm-lcの紹介 (4) ロック

今回はdm-lcで採用しているロック設計について話します.

dm-lcは現実的なソフトウェアです. write backキャッシュということもあり, ここでのバグは確実なデータロストに繋がります. 従って, まず根本的に「複雑なことをやるくらいなら性能を多少犠牲にすることは厭わない」というスタンスです. ただし, あまりにも理不尽な犠牲は避けなければなりません. 例えば, dm-lcはwrite時には内部状態を変化させますが, read時にはこのような副作用を一切排除出来ます. 従って, 本質的には, readにおけるペナルティは, writeによるものより小さくなるはずです.

現実的なソフトウェアという言葉は, バグがない(あるいは極端に少ない)ということ以外に, 運用の面でも充実しているという意味を含みます. 開発を進めていく上で, ロックの設計が極端に複雑になることによって, ユーザランドとの協調が難しくなったりしてはいけないと思いました. カーネルのテストはそのものが難しいですが, ユーザランドとの協調をテストするとなるとより一層難しくなります. また, ロックの複雑さが原因して, 開発のスピードが落ちるのも避けるべきと思いました. また, 順調でないコーディングはほぼ間違いなく, どうしようもないバグを含みます. 設計が関係してくるようなバグは一般に, 絶望的です.

dm-lcのロック設計を難しくしている要因は, 以下のようなことです.
1. DRAMバッファの制御. writeを, バッファに対して書き込んでいき, 最後にログ書きするという, (OSではしょうがないのでしょうが)「結局出口は一つ」な構造.
2. キャッシュのhit/miss判定に, 「単一の」ハッシュテーブルを使っている. キャッシュ制御において問題なのは, 「二重登録」です. ある瞬間において「登録する」と決断したキャッシュについては二重登録してはいけません. 同じキャッシュラインへのwriteが短時間に連続した場合にも破綻してはなりません. ただし, 「登録」しか起こらないのであればロック設計は簡単になります. しかし, キャッシュの問題は, 固定空間を使い回す, すなわち「削除」が発生するということです. 登録と削除という逆方向の副作用が同時に起こり得るものを競合制御するというのは難しいと言うのが定性的な説明です.
3. flush daemonがI/Oを完了していない領域では, バッファへの書き込みが出来ない. 書き込みに利用しているバッファが上書きされるとデータロストするため.
4. ロックをとったままI/Oを出して眠らないといけないケースがある.

4について, 具体的なコードを紹介します.

                }else{

                        u8 dirty_bits = atomic_read_mb_dirtiness(seg, mb);

                        /*
                         * First clean up the previous cache.
                         * Migrate the cache if needed.
                         */
                        bool needs_cleanup_prev_cache =
                                !bio_fullsize || !(dirty_bits == 255); // (1)

                        if(unlikely(needs_cleanup_prev_cache)){
                                wait_for_completion(&seg->flush_done); // (2)
                                migrate_mb(cache, seg, mb, dirty_bits, true); // (3)
                        }

                        /*
                         * Fullsize dirty cache
                         * can be discarded without migration.
                         */
                        bool b = false;
                        lockseg(seg, flags);
                        if(mb->dirty_bits){
                                mb->dirty_bits = 0;
                                b = true;
                        }
                        unlockseg(seg, flags);

                        if(b){
                                dec_nr_dirty_caches(mb->device_id);
                        }

                        ht_del(cache, mb); /* Delete the old mb from hashtable. */ // (4)

                        atomic_dec(&seg->nr_inflight_ios);
                        goto write_not_found;

このコードは, 「write」「キャッシュhit」「しかしDRAMバッファにはなく, 既にディスクに対してI/O発行された」という条件分岐のコードです. このように, さまざまな条件制御が必要です. それぞれのコードについて説明します.

  • (1) もしそのキャッシュがpartialではなく4KBフルであれば, 何のペナルティもなくinvalidateすることが出来ます. ここで問題にしているのは, キャッシュがpartialであり, かつ, これから書き込むwrite自体もpartialという異常な場合です. それが, needs_clean_prev_cacheの意味するboolです. このケースは極めて稀ですから, キャッシュを全部migrateして「クリーンな状態に戻し」てから, partial I/Oの処理に移るという動作をします. このようにdm-lcでは, 滅多に起こらない(unlikely)なコードについては冗長な処理をとって, その分本線である4KB writeの処理を簡潔にそして高速にするというバランス感覚を採用しています. 大事なところに注力して, そうでないところは適当な実装で済ますというバランス感覚は, あらゆるエンジニアリングで必要だと思います.*1*2
  • (2) そのキャッシュは, 既にI/O発行がなされたということしか分かりませんから, 本当にキャッシュ(キャッシュディスクのRAMキャッシュ)に書かれるのを待つ必要があります. migrateは, キャッシュからダーティデータをreadしてbacking storeにwrite backするという処理です.
  • (3) migarate_mbは, そのmb(metablock)について, dirtyなデータをすべてmigrateします. 底では, dm_io関数が呼ばれており(そしてdm_ioは底でgeneric_make_requestを呼びます), つまり, may sleepです.
  • (4) ht_del(hashtable deletion)は, hashtableからそのキャッシュに関するmetablockを削除します.

色々と厄介であるということは分かっていただけたかと思います. この前には, hashtableのlookupがあり, この後には, hashtableへの登録があります. このように, hashtableへの登録の合間にmay sleepな処理(他にもあります)が挟まってくるため, dm-lcでは, 一番大きなロックとして, mutexを採用しています. mutexのドキュメントによると,

  "Why on earth do we need a new mutex subsystem, and what's wrong
   with semaphores?"

firstly, there's nothing wrong with semaphores. But if the simpler
mutex semantics are sufficient for your code, then there are a couple
of advantages of mutexes:

 - 'struct mutex' is smaller on most architectures: E.g. on x86,
   'struct semaphore' is 20 bytes, 'struct mutex' is 16 bytes.
   A smaller structure size means less RAM footprint, and better
   CPU-cache utilization.

 - tighter code. On x86 i get the following .text sizes when
   switching all mutex-alike semaphores in the kernel to the mutex
   subsystem:

(訳) 一体なぜ我々には新しいmutexサブシステムが必要なのか?そして, 旧来のsemaphoreは何がいけなかった?まず, semaphoreは何も悪くない. しかし, 単にシンプルなmutexをあなたのコードが欲しているならば, 新しいmutexには以下に挙げるような利点がある. (以下略)

とのことで, mutexを使うと速いということが書かれています. 私はこのドキュメントを信用して, シンプルなmutexを採用しました. rw_semaphoreなどを使うと, 少しは工夫出来る余地もあると思いますが, 些細なことですし, writeパスにはベネフィットがないと思うので採用しませんでした. writeが生命線です. いつか詳しく書きますが, dm-lcでは, SSDキャッシュが十分に速い(PCI-e SSDなど)場合には, CPUネックに追い込まれます. CPUネックに追い込まれた時, ロックが重いということが問題になってくる可能性もあります.*3 ロックをシンプルにするという方針を守るためにも, mutexを採用しています. ユーザランドからの非同期的な操作のためdm-lcの動きを止める場合にも, mutexをとればOKというシンプルな設計です.

mutexを全面的にとるという設計にすれば, とりあえず動くものは出来そうです. 例えば, writeパスについて以下のような設計はどうでしょうか.

  1. mutex lock
  2. ht_lookup (htはhashtableの意味)
  3. ht_register
  4. バッファに書く
  5. mutex unlock

もっとも最初のバージョンでは, 私はこういう設計を導入していました(しかも, 今の実装のように, ログ書きを非同期化するということはしていませんでした. まず動かしてから育てていく方針だからです). しかし, この実装にはいちゃもんが入ります. 「どこに書くか決まったのだったら, バッファに書く部分はロックの外に出せるのではないの?」. また, この設計をreadにも適用すると, readの並列性が不必要に失われます. readは副作用がないため, このうちであれば, ht_lookupの部分だけロックをとれば終わりで良いはずです.

そこで, 私は, nr_inflight_iosというatomic値を導入しました. この値はdm-lcがキャッシュに関連して処理するI/Oの数を表しています. これが0より大きいということは, 処理が全部終了していないということです. ようするに, Reference Countingです. この工夫によって, 以下のように, ht_register(上記3)のあとでlockを抜けることが出来ています.

        if(refresh_segment){
                queue_current_buffer(cache);
        }

        cache->cursor = (cache->cursor + 1) % cache->nr_caches;
        update_mb_idx = cache->cursor; /* Update the new metablock. */

        seg = cache->current_seg;
        atomic_inc(&seg->nr_inflight_ios);

        struct metablock *new_mb = seg->mb_array + (update_mb_idx % NR_CACHES_INSEG);
        new_mb->dirty_bits = 0;
        ht_register(cache, head, &key, new_mb);
        mutex_unlock(&cache->io_lock);
        size_t start = s << SECTOR_SHIFT;
        void *data = bio_data(bio);

        memcpy(cache->current_wb->data + start, data, bio->bi_size);
        atomic_dec(&seg->nr_inflight_ios);

readパスでは効果はより顕著です. lookupの直後にmutex_unlockをしてすぐに抜けることが出来ます.

        mutex_lock(&cache->io_lock);
        mb = ht_lookup(cache, head, &key);
        if(mb){
                seg = ((void *) mb) - ((mb->idx % NR_CACHES_INSEG) * sizeof(struct metablock));
                atomic_inc(&seg->nr_inflight_ios);
        }

        bool found = (mb != NULL);
        DMDEBUG("found: %d", found);
        bool on_buffer = false;
        if(found){
                on_buffer = is_on_buffer(cache, mb->idx);
        }
        DMDEBUG("on_buffer: %d", on_buffer);
        inc_stat(cache, rw, found, on_buffer, bio_fullsize);

        if(! rw){
                mutex_unlock(&cache->io_lock);

では, 一体, どこでこのnr_inflight_iosをチェックしているのかというと, 以下のqueue_flushingは, ログを作ってそれをリストにキューするという処理であり, ログが発行されるタイミングにのみmutexの中で実行される処理ですが, この中でnr_inflight_iosが0でなければ待つという処理をしています. しかし, この条件は, 現実的には滅多に真になりません. 結果として, nr_inflight_iosというReference Countを導入したことによって, 「常に背負っていたペナルティ」を「現実的にゼロのペナルティ」に変換出来たことになります.

static void queue_flushing(struct lc_cache *cache)
{
        unsigned long flags;
        struct segment_header *current_seg = cache->current_seg;

        DMDEBUG("flush current segment. nr_dirty_caches_remained: %u", count_dirty_caches_remained(current_seg));

        size_t n1 = 0;
        while(atomic_read(&current_seg->nr_inflight_ios)){
                n1++;
                if(n1 == 100){
                        DMWARN("Too long to wait for current_seg ios to finish.");
                }
                schedule_timeout_interruptible(msecs_to_jiffies(1));
        }

また, この実現のためには, キャッシュのdirtinessについても工夫を行なっています. それは, 「キャッシュdirtinessはログ書きまでは単調増加させる」ということです. ロックというのは, 守るべき値が上がったり下がったりすると難しいのですが, 単調であれば簡単になるという性質が一般にあります. dm-lcの場合では, 「read」「キャッシュhit」「キャッシュはバッファ」にある滅多(もしかしたら絶対)にない場合には*4, 先ほどと同様に, 一度migrateしてしまってからbacking storeに対してI/Oを発行するという処理にしています(以下のコード). この時, キャッシュのdirtinessを0に出来るのですが, 「敢えて下げない」という設計にしています. DRAMバッファ上にあるキャッシュのdirtinessがfluctuateすることを嫌ったからです. キャッシュは, 本来ダーティである部分がクリーンになっていると問題ですが, 余計にダーティな分には何の問題もないという性質があります. この性質を利用したうまい*5事例です.

                if(unlikely(on_buffer)){

                        if(dirty_bits){
                                migrate_buffered_mb(cache, mb, dirty_bits);
                        }

                        atomic_dec(&seg->nr_inflight_ios);
                        bio_remap(bio, orig, bio->bi_sector);
                        return DM_MAPIO_REMAPPED;
                }

以上です.

この記事では, dm-lcが性能と実装の簡潔さのトレードオフにおいて, どのようなバランス感覚を持っているかという視点からロック設計を説明しました. バランス感覚というのは, エンジニアリングにおいてとても重要だと思っています. エンジニアリングに必要なバランス感覚については, 以下の図書を参考にしてください. プログラミングも碁も人生もすべて根本的には全く同じです. また, ロックの基本的な考え方は, 関数型言語の考え方が応用出来ます. Haskellを学びましょう.

*1:私はあらゆるエンジニアリングを経験しているわけではないですが

*2:こういうバランス感覚を持った人間のみが上に行くべきということです. あれもやるこれもやるみたいな発想では開発が遅くなるし, 糞しか生まれない

*3:実用的には, こんなI/O環境への導入は想定していません. しかし, ピーク性能が低いということはセールスにおいて欠陥になります

*4:そんなケースはふつう, ページキャッシュでヒットしますからね

*5:あるいは天才的な