テストステ論

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

dm-lc紹介 (6) migration

今まで, dm-lcのI/O処理について話してきました. dm-lcのように多重な層を制御するキャッシュソフトウェアを実装する上の問題や, それに対するdm-lcの姿勢を紹介してきました. いい加減, みなさんもカーネルは疲れたかも知れません. 私も疲れました. というわけで今日は休肝日ならぬ「休KERN日」にしようかと思います*1. 今日の話題の多くは, ユーザランドです.

dm-lcでは, ダーティキャッシュをbacking storeにライトバックする処理をmigrationと呼んでいます. そして, migrationは, 通常のI/O処理とは全く非同期に実行されています. 実装としてはほぼほぼflush daemonと同様です.

        /*
         * For Migration daemon
         */
        bool allow_migrate;
        bool force_migrate;
        struct workqueue_struct *migrate_wq;
        struct work_struct migrate_work;

詳しくは話しませんが, dm-lcはmigrationに対して情熱を注いでいます. dm-lcではmigration I/Oについて, 以下のようなメンバを制御して, I/O努力をしています. migrationは, write backキャッシュにおいて, I/O処理と同様のコア技術だと私は思います. migrationに対して努力する必要があるのは, 1-segment内のwrite backを非同期I/Oしているためです. これは主に, 先日話したwrite barrierと関係があります. それらの非同期I/Oはアトミックであり, すべてが成功しなければ, そのsegment単位でwrite backをやり直すということにしています. これは, backing storeのwrite性能が一般的に低い*2ため, 場合によってはエラーを返してくることもあるためです.

        /*
         * For migration I/O
         */
        wait_queue_head_t migrate_wait_queue;
        atomic_t migrate_fail_count;
        atomic_t migrate_io_count;
        u8 dirtiness_snapshot[NR_CACHES_INSEG];
        bool migrate_dests[LC_NR_SLOTS];
        void *migrate_buffer;

migrate daemonがループ実行している処理が以下です.

static void migrate_proc(struct work_struct *work)
{
        struct lc_cache *cache = container_of(work, struct lc_cache, migrate_work);

        while(true){

                /*
                 * reserving_id > 0 means
                 * that migration is immediate.
                 */
                bool allow_migrate =
                        cache->reserving_segment_id || cache->allow_migrate; (1)

                if(! allow_migrate){
                        DMDEBUG("migration not allowed");
                        schedule_timeout_interruptible(msecs_to_jiffies(1000));
                        continue;
                }

                bool need_migrate = (cache->last_migrated_segment_id < cache->last_flushed_segment_id); (2)
                if(! need_migrate){
                        DMDEBUG("migration not needed");
                        schedule_timeout_interruptible(msecs_to_jiffies(1000));
                        continue;
                }

                // (3)
                struct segment_header *seg =
                        get_segment_header_by_id(cache, cache->last_migrated_segment_id + 1);

                migrate_whole_segment(cache, seg);

                /*
                 * (Locking)
                 * Only this line alter last_migrate_segment_id in runtime.
                 */
                cache->last_migrated_segment_id++;

                complete_all(&seg->migrate_done);
        }
}

大体, 以下のようなSimpleな考え方で処理を行なっています.
- (1) もし, 「今すぐmigrateする必要がある」ならばやる. これは, キャッシュが一杯になってしまい, 早急にmigrateが必要な場合など. あるいは, allow_migrateがtrueならば, 早急な場合でなくてもmigrateをする.
- (2) もし, 最後にmigrateしたsegment idよりも新しいsegment idを持つログがflushされているならば, migrationを開始する. ようするに, migrationする「モノがあるか」を調べている.
- いずれにしろ, migrationしないなら1秒眠る.
- (3)以下では, migrate対象のsegmentを取得し, migrateを行う. 終わったらmigrate_doneをnotifyする.

すでにお気づきかと思いますが, (1)の部分でcache->allow_migrateがfalseであれば, 早急な場合以外にmigarateされることはありません. そしてこの値は, sysfsで制御可能にしています. このようにmigrationは, カーネル空間においても, 別スレッドで非同期的に動かすため疎結合であり, かつ, ユーザランドとも疎結合であるという設計になっています. dm-lcの内部では, ログを書き出すためのflush daemonと, migrationを行うためのmigrate daemonと, ユーザ分のforegroundプロセスが非同期的に動いています*3.

static struct cache_sysfs_entry allow_migrate_entry = {
        .attr = { .name = "allow_migrate", .mode = S_IRUGO | S_IWUSR },
        .show = allow_migrate_show,
        .store = allow_migrate_store,
};

このように, ユーザランドとカーネルをallow_migrateという一つのsysfs attributeのみを口として隔離したのは, migrationのON/OFF制御処理をユーザランドで行おうと思ってたからです. migrationを行う基準は複雑な計算が必要となる可能性があり, それは, カーネルに実装すべきではないという考えです. カーネルは出来るだけ小さく保つ, これが, dm-lcの設計思想です. 両刃の剣であるwrite backキャッシュを間違いなく動かすためには, カーネルは小さく保ち, バグレスを目指さなければなりません. ユーザランドのごときは, ぶっ飛んだところでシステムには何の影響もないですから.

dm-lcでは, ユーザランドのプログラムはすべてPythonで実装しています. Pythonは, Linuxに標準で付属しており, システムをいじるために必要なライブラリが豊富です. もともと, Rubyの方が得意だったのですが, Rubyはこれらの用途にはあまり合いません. また, Pythonの方が, リポジトリにアクセスするためのプログラム(Pythonであればpip, RubyならばGem)を利用出来るまでの手数が少ないと思います.

bin
|-- lc-admin
|-- lc-attach
|-- lc-create
|-- lc-daemon // ☆
|-- lc-detach
|-- lc-format-cache
|-- lc-remove
`-- lc-resume-cache

このうち, lc-daemonというのが, システムの状況に応じてmigrationのON/OFFを切り替える(allow_migrateをON/OFFする)デーモンプログラムです*4. python-daemonというライブラリを利用して実装されています.

現在採用している, migrationがONになる条件は, 「そのキャッシュを利用しているbacking storesについて, すべてのutil(%)が設定しきい値以下になる」です*5.

utilの計算は, 本当はsysstatなどで取得されるものを簡単に利用出来ると良かったのですが, やり方が分からなかったのでpsutilというライブラリを使って実装しています. 以下が, utilを計算するコードです. intervalごとにBackingオブジェクトのもつutilメンバを更新するという実装になっています. 時々, サンプリング区間の具合なのか, utilが100%を超えることがありますが, 実用上は問題ありません. そのような詳しい値が必要なのでなく, 「負荷が低い時にmigarateする」という大まかな制御が出来れば良いです. 一般的なストレージでは, 時間によってはI/Oが極めて少ないということがあり得ます.

    def update(self, interval):
        print("backing update interval:%d" % (interval))
        name = dirnode.name(self.block_node)
        data_new = psutil.disk_io_counters(perdisk=True)[name]

        print(self.data_old)

        if self.data_old:
            print("compute new util. new, old")
            print(data_new)
            print(self.data_old)
            diff_r = data_new.read_time - self.data_old.read_time
            diff_w = data_new.write_time - self.data_old.write_time
            self.util = 100 * float(diff_r + diff_w) / (interval * 1000)
            print("computed util %d" % (self.util))

        self.data_old = data_new

以上です. 今回は, dm-lcがmigrationをどうやって制御しているかについて説明しました. 内容としては, (過去の, 特にロックとwrite barrierの話に比べると)平易だったと思います. dm-lcを設計するに当たって, 結合度の観点から工夫がなされており, それがユーザランドへのコード分離に貢献していることがお分かりいただいたかと思います. ソフトウェア設計というのは非常に苦しいものですが, 楽しいものです. それは, 芸術です. 私が, 現在のソフトウェア開発をするに必要な基礎的な素養を身につけたのは学生時代の修練が大きいです. みなさんも修練を積んで, カーネルと闘ってください. 二度とうんコードを書かないでください.

*1:散歩していたら突然閃きました. ふつうのオヤジギャグではないですね. カーネル親父ギャグとでも言いましょうか. ワンランク上の男になってしまったようです

*2:RAIDペナルティのためです

*3:このようなクリーンな考え方をするためには, Haskellを勉強すればよろしい. 逆にいうと, Haskellプログラマ以外がカーネルの設計をしてはならぬ. 私は分離主義者です. 疎結合的な意味で

*4:他にも, super blockを定期的に吐く, ログを定期的にflushすることも出来ます

*5:実は, dm-lcの原理を示したDCDの論文では, キャッシュデバイスのutilでmigrationを制御するとなっています. また, キャッシュが共有されることは想定されていません. 些細な違いですが, SSDをキャッシュデバイスとして使うことを考えると, dm-lcのPolicyの方が妥当と思います