Go to Qiita Advent Calendar 2024 Top
LoginSignup
13
12

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

ErlangAdvent Calendar 2015Day 6
@sile

ETSの(read|write)_concurrencyオプションについて調べてみた

Posted at

Erlangではプロセス間通信はメッセージパッシングを通して行うのが基本だが、それだとやりとりをするプロセス同士が一対多の関係(便宜上、前者を__サーバプロセス__、後者を__クライアントプロセス(群)__と呼ぶことにする)にある場合に、サーバプロセスのメッセージキューが詰まってしまい、スケーラビリティの阻害要因となることがある。

そういった時には以前の記事で書いたように、__protected__ないし__public__なアクセス権限のETSを使って、クライアントのリクエスト時にサーバプロセスとの間でメッセージパッシングが行われないようにする、のが定番の対策だと思っている。

そして自分のこれまでの用途では、ETSを使う場合、読み込み操作が(書き込み操作に対して)圧倒的に多いことがほとんどだったので、特に深く考えずにets:new(Id, [protected, {read_concurrency, true}])といったオプションでテーブルを作成することが多かった。

ただ最近、書き込み操作が読み込み操作と同程度に発生するようなケースに遭遇し{write_concurrency, true}を指定するかどうかを検討する機会があったのだが、公式ドキュメントを読んだだけでは、今一つその効果が(特にread_concurrencyと併用した場合)不明瞭だったので、ソースコードを追いつつ軽く調べてみた。

※ なお、そこまで詳細に調べた訳でもないので間違っていることを書いている可能性もあるため、参考程度として読んで貰えると助かります。
※ そして無計画に書いていたら異様に長くなってしまった...

公式ドキュメント

最初にetsのドキュメントからread_concurrencyおよびwrite_concurrencyについての記述を引用しておく。

read_concurrencyオプション

Performance tuning. Default is false. When set to true, the table is optimized for concurrent read operations. When this option is enabled on a runtime system with SMP support, read operations become much cheaper; especially on systems with multiple physical processors. However, switching between read and write operations becomes more expensive. You typically want to enable this option when concurrent read operations are much more frequent than write operations, or when concurrent reads and writes comes in large read and write bursts (i.e., lots of reads not interrupted by writes, and lots of writes not interrupted by reads). You typically do not want to enable this option when the common access pattern is a few read operations interleaved with a few write operations repeatedly. In this case you will get a performance degradation by enabling this option. The read_concurrency option can be combined with the write_concurrency option. You typically want to combine these when large concurrent read bursts and large concurrent write bursts are common.

結構長いので重要そうなところだけを意訳:

  • デフォルトはfalse
  • trueが指定された場合は、作成されるテーブルは__並列読み込み操作__に最適化される
  • 「__並列読み込み操作__が、__書き込み操作__よりも頻繁に行われる」ケースで有効
  • 「__少数の読み込み操作__と__少数の書き込み操作__が繰り返し発生する」ケースでは逆に性性能が劣化する
    • 読み込み操作と書き込み操作の切り替えのコストがfalseの場合より高くなるため
  • write_concurrencyオプションとの併用も可
    • __大量の並列読み込み操作のバースト__と__大量の並列書き込み操作のバースト__の両方が発生する場合に有用

write_concurrencyオプション

Performance tuning. Default is false, in which case an operation that mutates (writes to) the table will obtain exclusive access, blocking any concurrent access of the same table until finished. If set to true, the table is optimized towards concurrent write access. Different objects of the same table can be mutated (and read) by concurrent processes. This is achieved to some degree at the expense of memory consumption and the performance of sequential access and concurrent reading. The write_concurrency option can be combined with the read_concurrency option. You typically want to combine these when large concurrent read bursts and large concurrent write bursts are common (see the documentation of the read_concurrency option for more information). Note that this option does not change any guarantees about atomicy and isolation. Functions that makes such promises over several objects (like insert/2) will gain less (or nothing) from this option.

In current implementation, table type ordered_set is not affected by this option. Also, the memory consumption inflicted by both write_concurrency and read_concurrency is a constant overhead per table. This overhead can be especially large when both options are combined

こちらも重要そうなところだけを意訳:

  • デフォルトはfalse
    • 書き込み(更新)操作時には、テーブル全体が対象の排他ロックが取得される
    • その間、他のプロセスによる並列アクセス(read or write)はブロックする
  • trueが指定された場合は、作成されるテーブルは__並列書き込み操作__に最適化される
    • 同じテーブル内の異なるオブジェクトの並列操作(読み書き)が可能となる
    • 代償: メモリ消費量の増加、逐次アクセスおよび並列読み込みの性能劣化
  • read_concurrencyオプションと併用可
  • write_concurrency=trueが無意味なケース:
    • insert/2等で複数オブジェクトを同時に書き込もうとした場合は効果が薄い(or 無い)
    • ordered_setの場合は効果が無い (ハッシュテーブル系のみがサポート)
  • メモリ消費量(の増加)について:
    • read_concurrencyおよびwrite_concurrencyの指定による増加分はテーブル毎に一定
    • 両方を同時にしていたら、かなりオーバヘッドが大きくなり得る

これらのドキュメントから、それぞれのオプションの効果が何となくはわかるけど、やはりいまいち釈然としない。

内部実装

続いてETSの内部実装を軽く(?)追ってみる。
(かなり長くなってしまったこともあり、内部実装に興味のない人は、この節を丸ごと飛ばしてしまっても問題はない

ソースコードはOTP-18.1のものを参照する。

またErlang/OTPはSMPを有効にしてビルドされることを前提とする。
(非SMPの場合は、そもそも並列アクセスされる可能性がなくなるので、ソースコード中でも並列系の処理や関数の大半が#ifdef等によって無効化されている)

関連ファイル群

今回、主に参照したのは以下のファイル群:

  • lib/stdlib/src/ets.erl
  • erts/emulator/beam/erl_db.c
  • erts/emulator/beam/erl_db_hash.c
  • erts/lib_src/common/ethr_mutex.c

__ets.erl__は、(今回の話に関係する関数群については)単にErlang用のインタフェースを提供しているだけで、関数の実装のほとんどはerlang:nif_error(undef)となっており、実際の処理はCで書かれたBIF(built-in function)に委譲されている。
__erl_db.c__は、ETSのBIFインタフェース提供、テーブルに関する共通処理の実装、全体的な調整処理、等を担当している。
__erl_db_hash.c__は、__erl_db_util.h__で定義されたDbTableMethodインタフェース(構造体)を備えており、ハッシューテーブルに基づいたテーブルの実装を提供している（他にツリーを用いた実装を提供する__erl_db_tree.c__というファイルもあるが、公式ドキュメントに記載の通り、こちらはwrite_concurrencyオプションには非対応なので、今回は割愛する)。
__ethr_mutex.c__は、相互排他用の各種関数を提供しており、erl_db系のソースコードから利用されている。

以降では__erl_db.c__、erl_db_hash.c、__ethr_mutex.c__を中心として、ボトムアップに(read|write)_concurrencyオプションの使われ方を見ていくことにする。

ethr_mutex.c

ETSとは独立した各種相互排他アルゴリズムの実装関数群を提供するファイル。

(今回の話に関係する範囲では)__erl_db.*c__のファイルからは、リーダー/ライター・ロック(以降は__RWロック__と表記)系の関数が使用される。
※ 補足: RWロックでは__並列読み込み__が許容される (書き込みは直列のみ)

このレイヤーではread_concurrencyオプションの値のみが影響する。

read_concurrencyオプションの使われ方

初期化時

ethr_rwmutex_opt構造体

read_concurrencyという名前が直接__ethr_mutex.c__内で出現することはなく、上位層(__erl_db.c__内)で、以下のethr_rwmutex_opt構造体のtypeフィールドの値にマッピングされてから渡されている。

ethr_mutex.h
typedef enum {
    ETHR_RWMUTEX_TYPE_NORMAL,  // read_concurrency=false、に対応
    ETHR_RWMUTEX_TYPE_FREQUENT_READ,  // read_concurrency=true、に対応
    ETHR_RWMUTEX_TYPE_EXTREMELY_FREQUENT_READ // ethr_mutex.c内部利用用
} ethr_rwmutex_type;

typedef struct {
    ethr_rwmutex_type type; 
    ethr_rwmutex_lived lived;
    int main_spincount;
    int aux_spincount;
} ethr_rwmutex_opt;
ethr_rwmutex構造体

ethr_rwmutex_opt.typeの値は、最終的にはethr_rwmutex.tdataの値を決定するために使用される。

ethr_mutex.h
#ifdef ETHR_USE_OWN_RWMTX_IMPL__

// RWロック実装用の構造体
typedef struct ethr_rwmutex_ ethr_rwmutex;
struct ethr_rwmutex_ {
    struct ethr_mutex_base_ mtxb;
    ethr_rwmutex_type type;
    ethr_ts_event *rq_end;
    
    // ethr_rwmutex_opt.typeの値に応じて、以下のどちらのフィールドが使われるかが決定する:
    // - ETHR_RWMUTEX_TYPE_NORMALの場合:
    //    - `rs`が使われる
    //    - ロック獲得待機中のリーダー数を管理するために使用される
    //      - つまり`ethr_rwmtx_readers_array__.waiting_readers`に対応する
    // - それ以外の場合(並列読み込みに最適化される):
    //    - `ra`が使われる
    //    - 並列リーダー群は`ethr_rwmtx_readers_array__`という配列によって管理される(詳細は後述)
    union {
        ethr_rwmtx_readers_array__ *ra;
        int rs;
    } tdata;
};

// リーダーを管理するためのデータ構造
typedef union {
    struct {
        ethr_atomic32_t readers;
        int waiting_readers;
        int byte_offset;
        ethr_rwmutex_lived lived;
    } data;
    char align__[ETHR_CACHE_LINE_SIZE];
} ethr_rwmtx_readers_array__;

#else /* pthread_rwlock */
/***
 * NOTE:
 * ビルド時に以下のオプションを指定することで、pthreadの実装を使用することができる。 
 * (その場合、おそらく`read_concurrency`オプションは無効となる(無視される))
 * $ ./configure force_pthread_rwlocks=yes
 ***/
ethr_rwmutex_init_opt関数

ethr_rwmutex.tdataの初期化はethr_rwmutex_init_opt関数の中で行われる。

細かい調整処理はいろいろあるが、基本的にはtypeの値に応じて「単一のカウンタでリーダ群を管理する」あるいは「利用可能なスレッド数に応じた配列(tdata.ra)でリーダー群を管理する」のどちらになるかが決定される。

ethr_mutex.c
int
ethr_rwmutex_init_opt(ethr_rwmutex *rwmtx, ethr_rwmutex_opt *opt)
{
    int res;
    ethr_rwmtx_readers_array__ *ra = NULL;
    rwmtx->rq_end = NULL;
    rwmtx->type = opt ? opt->type : ETHR_RWMUTEX_TYPE_NORMAL;
    
    /***
      * NOTE: `type`の値に応じて、リーダー群管理用のフィールドの初期化方法が分岐
      ***/
    switch (rwmtx->type) {
    case ETHR_RWMUTEX_TYPE_FREQUENT_READ:
        if (main_threads_array_size <= reader_groups_array_size) {
            /* No point using reader groups... */

          rwmtx->type = ETHR_RWMUTEX_TYPE_EXTREMELY_FREQUENT_READ;
        }
        /* Fall through */
    case ETHR_RWMUTEX_TYPE_EXTREMELY_FREQUENT_READ: {
        int length;

        length = (rwmtx->type == ETHR_RWMUTEX_TYPE_EXTREMELY_FREQUENT_READ
                  ? main_threads_array_size
                  : reader_groups_array_size);

        if (length == 1) {
            /* No point using a frequent reader type... */
            rwmtx->type = ETHR_RWMUTEX_TYPE_NORMAL;
        }
        else {
            /***
             * NOTE: 並列読み込みを最適化する場合(read_concurrency=true)は、ここに来る
             ***/
            int ix;
            
            // `ethr_rwmtx_readers_array__`を`length`分だけ確保。
            // `length`の値は、`main_threads_array_size`か`reader_groups_array_size`のどちらかで、
            // それらの値は`erl_init.c:early_init`関数内で定まる。
            ra = alloc_readers_array(length,
                                     (opt
                                      ? opt->lived
                                      : ETHR_RWMUTEX_UNKNOWN_LIVED));

            rwmtx->tdata.ra = ra;

            for (ix = 0; ix < length; ix++) {
                // 最初のリーダー数は0
                ethr_atomic32_init(&rwmtx->tdata.ra[ix].data.readers, 0);
                rwmtx->tdata.ra[ix].data.waiting_readers = 0;
            }
            break;
        }
    }
    case ETHR_RWMUTEX_TYPE_NORMAL:
        /***
          * NOTE: 並列読み込みを最適化しない場合(read_concurrency=false)は、ここに来る
          ***/
        rwmtx->tdata.rs = 0; // 最初のリーダー数は0
        break;
    }
    // 内部で使用するロックを初期化
    res = mtxb_init(&rwmtx->mtxb,
                    default_rwmtx_main_spincount,
                    opt ? opt->main_spincount : -1,
                    default_rwmtx_aux_spincount,
                    opt ? opt->aux_spincount : -1);

    return res;
}

ロック操作時

__erl_db.c__等から(主に)利用されるRWロック系の関数には、以下の四つがある:

  • ライター(書き込み)用ロック操作:
    • ロック獲得: ethr_rwmutex_rwlock
    • ロック解放: ethr_rwmutex_rwunlock
  • リーダー(読み込み)用ロック操作:
    • ロック獲得: ethr_rwmutex_rlock
    • ロック解放: ethr_rwmutex_runlock

全て取り上げると分量が多くなりすぎてしまうので、今回はより特徴的なリーダー用の関数のみを見ていくことにする。

ステートやロック獲得中リーダー数の管理方法

各関数の実装に入る前に、まずはロックのステートやロック獲得中のリーダー数の管理方法を見てみる(結構特殊なので)。

基本的にこれらの情報はethr_rwmutex.mtxb.flgsという32bitのフィールドで管理されているのだが、並列読み込みに最適化されているかどうかで、このフィールドの扱い方が変わってくる。

まずread_concurrency=falseの場合は、以下のように解釈される:

  • 上位3bitは、ロックのステート管理用のフラグとして使用される:
    • 31bit目: ロック獲得ライターの存在を示すフラグ (マクロ名はETHR_RWMTX_W_FLG__)
    • 30bit目: ロック待機ライターの存在を示すフラグ (マクロ名はETHR_RWMTX_W_WAIT_FLG__)
    • 29bit目: ロック待機リーダーの存在を示すフラグ (マクロ名はETHR_RWMTX_R_WAIT_FLG__)
  • それ以下のbit群は、ロック獲得リーダー数を保持するためのカウンタ用に使われる

次にread_concurrency=trueの場合:

  • 上位3bitに関してはread_concurrency=falseの場合と同様
  • 加えて、その次の2bitが、以下のフラグ用に使用される:
    • 28bit目: ロック獲得リーダーの存在(の可能性)を示すフラグ (マクロ名はETHR_RWMTX_R_FLG__)
    • 27bit目: アンロック処理がアボートしたことを示すフラグ (マクロ名はETHR_RWMTX_R_ABRT_UNLOCK_FLG__)
  • それ以下のbit群は、保留中のアンロック処理の数を保持するために使用される (不確か)

read_concurrency=trueの場合は、ロック獲得中のリーダー数は、(ロック内で)グローバルなカウンタではなく、スレッド(or スレッドグループ)にローカルなethr_rwmutex.tdata.ra[i].readersフィールドを使って管理されている。

ethr_rwmutex_rlock関数

以下は、読み込み用ロック関数を実装。

ethr_mutex.c
void
ethr_rwmutex_rlock(ethr_rwmutex *rwmtx)
{
    ethr_sint32_t act;
    switch (rwmtx->type) {
    case ETHR_RWMUTEX_TYPE_NORMAL: {
        /***
         * NOTE: read_concurrency=false、の場合
         ***/
        ethr_sint32_t exp = 0;  // 最初は現在のリーダー数は0と仮定 (複数いる場合は一回無駄なループが走る)
        while (1) {
            // CASを使って、リーダーロックの取得(リーダーカウントの増加)を試みる
            act = ethr_atomic32_cmpxchg_acqb(&rwmtx->mtxb.flgs, exp+1, exp);
            if (act == exp)
                break;  // 無事にカウントを増やせたので、ロック獲得

            // ライターがロック獲得中(or 獲得待機中)かどうかをチェック
            if (act & (ETHR_RWMTX_W_FLG__|ETHR_RWMTX_W_WAIT_FLG__)) {
                // 競合するライターがいる場合は、そのライターがロックを解放するまで待機する。
                //
                // `rwmutex_normal_rlock_wait`内では、大雑把に言えば以下の処理が行われている:
                //   - 一定回数だけスピン(ビジーループ)して、ロック解放をチェック
                //   - 規定回数を超えた場合は`event_wait`関数を用いて、ロック解放まで待機する
                rwmutex_normal_rlock_wait(rwmtx, act);
                break;
            }
            
            // 他のリーダーとCASが競合したので、リトライする
            // NOTE: 並列読み込みの競合度が高いと、ここに来る(= 性能が劣化する)可能性が高くなる
            exp = act;
        }
        break;
    }

    case ETHR_RWMUTEX_TYPE_FREQUENT_READ:
    case ETHR_RWMUTEX_TYPE_EXTREMELY_FREQUENT_READ: {
        /***
          * NOTE: read_concurrency=true、の場合
          ***/
        ethr_ts_event *tse = ethr_get_ts_event();  // スレッド固有データ(?)を取得
        rwmutex_freqread_rlock(rwmtx, tse, 0); // リーダーロックの取得を試みる
        ethr_leave_ts_event(tse);
        break;
    }
    }
}

typeがETHR_RWMUTEX_TYPE_NORMALの場合は、(ライターとの競合を考えなければ)単にmtxb.flgsで管理されているロック獲得中リーダー数をCASを使ってインクリメントするだけ。
ただしmtxb.flgsは単一の変数なので、並列リーダーが数が多い場合には、CASの実行が競合してしまい、(リトライが多くなり)性能が劣化してしまう可能性がある。

並列読み込み最適化版で、その問題にどう対処しているかはrwmutex_freqread_rlock関数の実装を読めば分かる。

rwmutex_freqread_rlock関数
ethr_mutex.c
static int
rwmutex_freqread_rlock(ethr_rwmutex *rwmtx, ethr_ts_event *tse, int trylock)
{
    // NOTE: 
    // `tse`は、(おそらく)スレッド固有のデータなので、これに対する読み書きは他のスレッドには影響を与えない。
    //  => CPUキャッシュのフラッシュ等に繋がるスレッド間同期が不要となるので、スケーラビリティを阻害しない
    int res = 0;
    ethr_sint32_t act;

    // 1. 自スレッド(に対応する添え字)が管理するリーダー数をインクリメントする。
    // 概ね右の通り: ethr_atomic32_inc(rwmtx->tdata.ra[自スレッド用の添え字].data.readers)
    rwmutex_freqread_rdrs_inc(rwmtx, tse);

    ETHR_MEMORY_BARRIER; // ethr_atomics.h:#define ETHR_MEMORY_BARRIER ETHR_MEMBAR(ETHR_LoadLoad|ETHR_LoadStore|ETHR_StoreLoad|ETHR_StoreStore)

    // 2. 現在のフラグを取得する
    act = ethr_atomic32_read_acqb(&rwmtx->mtxb.flgs);

    // 3. 別のリーダーがいるかをチェック (もし存在するなら、ここで獲得処理が完了)
    if (act != ETHR_RWMTX_R_FLG__) {
        // ロック獲得中のリーダーは存在しないので、自分が諸々の初期処理を担当する
        int wake_other_readers;

        while (1) {
            ethr_sint32_t exp, new;

            wake_other_readers = 0;

            if (act == 0)
                // 4-a. ライターもいない => 末尾のCASに成功すれば、リーダーロック獲得成功
                new = act | ETHR_RWMTX_R_FLG__;
            else if (act == ETHR_RWMTX_R_FLG__)
                // 4-b. 別の新規リーダーと競合した => 並列リーダーは許可されるのでロック獲得成功
                break; /* Got it */
            else if (act & (ETHR_RWMTX_W_FLG__|ETHR_RWMTX_W_WAIT_FLG__)) {
                // 4-c. ライターと競合した
                rwmutex_freqread_restore_failed_tryrlock(rwmtx, tse);
                if (trylock)
                    res = EBUSY; // trylock(= waitしないモード)なら失敗(競合)ステータスで終了
                else
                    rwmutex_freqread_rlock_wait(rwmtx, tse); // ライターの終了を待機
                break;
            }
            else if (act & ETHR_RWMTX_R_ABRT_UNLCK_FLG__) {
                // 4-d. アボートしたアンロックがあるらしい (未調査なので詳細不明)
                if ((act & ETHR_RWMTX_R_FLG__) == 0)
                    ETHR_FATAL_ERROR__(EFAULT);
                /*
                 * An aborted runlock, not write locked, and no write
                 * waiters, i.e., we got it...
                 */
                if (act & ETHR_RWMTX_R_WAIT_FLG__)
                    wake_other_readers = 1;
                break;
            }
            else {
                // 4-e. それ以外のケース (未調査なので詳細不明)
                new = act | ETHR_RWMTX_R_FLG__;
                if (act & ETHR_RWMTX_R_PEND_UNLCK_MASK__) {
                    /*
                     * Someone is doing tryrwlock (no writer and no
                     * write waiters); we will try to abort that...
                     */
                    new |= ETHR_RWMTX_R_ABRT_UNLCK_FLG__;
                }

                if (act & ETHR_RWMTX_R_WAIT_FLG__)
                    wake_other_readers = 1;
            }

            exp = act;
            act = ethr_atomic32_cmpxchg_acqb(&rwmtx->mtxb.flgs, new, exp);
            if (act == exp)
                break;
        }

        if (wake_other_readers) // 他のリーダーがロック獲得を待機(wait)中なら起こす
            rwmutex_transfer_read_lock(rwmtx, act, 0);
    }

    return res;
}

この関数を見ると、ロック獲得リーダー数を管理する場所が、ロックで共通のrwmtx.flgsから、スレッド(or スレッドグループ)にローカルなrwmtx.tdata.ra[i].data.readersに移っていることが分かる。
(rwmtx.flgsは、「ロック獲得中リーダーがいるか」や「ロック獲得中ライターがいるか」といったステート管理のみに利用されている)

この実装では、並列リーダーの競合度が高い場合が一番コストが安く、以下のステップでロックが獲得可能となっている:

  1. スレッド(グループ)ローカルなリーダー数カウンタをインクリメント
  2. メモリバリア
  3. rwmtx.flgsの値をアトミックに読み込む
  4. リーダーロック用のフラグが立っていれば、そこで獲得完了
  • 既に別のリーダーがロック獲得中なら、このフラグが立つ
  • そのようなリーダーがいない場合はrwmtx.flgsに対するCASの発行が一回余分で必要となる

read_concurrency=falseの場合と異なり、ライターと競合しない限りは、常に定数ステップでロックが獲得できるので、かなり効率が良い。

ethr_rwmutex_runlock関数

最後はリーダーロックの解放処理。

read_concurrency=trueの場合、自スレッド(or スレッドグループ)が管理するリーダー数はデクリメントするが「全体でロック獲得リーダー数が0になったかどうか」は確認していないのが特徴的 。
つまり全体でリーダーが一人もいなくなった場合でもETHR_RWMTX_R_FLAG__フラグが立ったままとなり、そのチェックを行うコストは、今回は割愛されたライターロック獲得関数(ethr_rwmutex_rwlock)に押し付けられる形となっている。
(ETHR_RWMTX_R_FLAG__フラグが立っている場合、check_readers_array関数内でtdata.ra配列の全要素が走査され、リーダーの存在判定が行われている)

ethr_mutex.c
void
ethr_rwmutex_runlock(ethr_rwmutex *rwmtx)
{
    ethr_sint32_t act;

    switch (rwmtx->type) {
    case ETHR_RWMUTEX_TYPE_NORMAL:
        // NOTE: read_concurrency=false、の場合
        act = ethr_atomic32_dec_read_relb(&rwmtx->mtxb.flgs); // リーダー数をデクリメント
        if ((act & ETHR_RWMTX_WAIT_FLGS__)
            && (act & ~ETHR_RWMTX_WAIT_FLGS__) == 0) {
            // 待機中のライターがいるなら起こす
            rwmutex_unlock_wake(rwmtx, 0, act, 0);
        }
        break;

    case ETHR_RWMUTEX_TYPE_FREQUENT_READ:
    case ETHR_RWMUTEX_TYPE_EXTREMELY_FREQUENT_READ: {
        // NOTE: read_concurrency=true、の場合
        ethr_ts_event *tse = ethr_get_ts_event();
 
        // スレッド(or スレッドグループ)毎に管理しているリーダー数をデクリメント
        act = rwmutex_freqread_rdrs_dec_read_relb(rwmtx, tse);

        ETHR_MEMORY_BARRIER;

        if (act == 0) {
            // 自スレッド(or スレッドグループ)が管理するリーダー数が0になった
            act = ethr_atomic32_read(&rwmtx->mtxb.flgs);
            if (act != ETHR_RWMTX_R_FLG__)
                // 解放中にフラグの値が変わった場合は、他の待機者(競合者)がいるので、後処理をする
                rwmutex_freqread_rdrs_dec_chk_wakeup(rwmtx, tse, act);
        }

        ethr_leave_ts_event(tse);
        break;
    }
    }
}

ここまでのまとめ

今回調べた範囲での__ethr_mutex.c__に対するread_concurrencyおよびwrite_concurrencyの影響のまとめ(長い...):

  • __erl_db.c__等は、(主に)__ethr_mutex.c__が提供するRWロック系の関数を使用する
    • 両オプションの値が、使用するロックの種類に影響を与えることはない
      • i.e. read_concurrency=falseの場合でも、リーダーロックの並列獲得自体は許可される
    • RWロックなので、ロックは常に以下の性質を持つ:
      • リーダーロックの並列(複数)獲得は許可される
      • ライターロックの並列(複数)獲得は禁止される
      • ライターロックとリーダーロックの同時獲得は禁止される
  • write_concurrencyの値は、このファイル内の関数群に対して影響を与えない
  • read_concurrencyの値に応じて、使用される内部実装が「並列リーダー」に最適化されたものになるかどうかが変わる:
    • falseの場合 (並列リーダーに最適化されない):
      • ロック獲得中のリーダー数のカウントが、ロック内でグローバルな単一変数で管理される
      • リーダーロック獲得時には、その変数に対するCAS(インクリメント)が発行される
      • 競合度が高くなるほど、CASに失敗して、リトライが走る可能性が高くなる
        • 欠点: リーダーロックの獲得競合度が高くなるほど、性能が劣化する
    • trueの場合 (並列リーダーに最適化される):
      • ロック獲得中のリーダー数のカウントを、スレッドローカルな変数に分散している
        • 他スレッドとのCASの競合(and リトライ)がなくなり、定数ステップでリーダーロックが獲得可能となっている
          • ※ ライターロックと競合している場合は除く
        • 利点: リーダーロックの獲得競合度が高くなっても、性能がほとんど劣化しない
      • ただし、その代償として、以下の二つの欠点がある:
        • 欠点: メモリ使用量が増加する
          • (若干不正確だが大雑把に言えば)論理コア数 * キャッシュラインサイズ程度のメモリが追加で必要となる
          • 例: コア数=8、キャッシュラインサイズ=64byteなら、__512byte__が追加で必要
        • 欠点: リーダーロックからライターロックへの切り替わりのコストが増える
          • ライターロック獲得時に「本当にリーダーが一人もいないか」を調べるために、全てのスレッドの固有データを操作して、リーダー数を確認する必要がある(場合がある)
          • read_concurrency=falseの場合は、単一の変数を参照すれば、リーダー数が把握できるので、このような走査は不要

erl_db_hash.c

ハッシュテーブルを用いたETSテーブルの実装。

このテーブル実装は__erl_db_util.h__て定義されているDbTableMethodインタフェース(構造体)を備えており、そのインタフェースを通して__erl_db.c__から使用される。

また__erl_db_hash.c__は、内部ロック用にethr_mutex.cが提供するRWロックを利用している。

粗粒度ロックと細粒度ロック

まず最初に__erl_db_hash.c__のモジュールドキュメント(コメント)の__SMP__の部分を引用する。

erl_db_hash.c
/* SMP:
** The hash table supports two different locking "modes",
** coarse grained and fine grained locking.
**
** Coarse grained locking relies entirely on the caller (erl_db.c) to obtain
** the right kind of lock on the entire table depending on operation (reading
** or writing). No further locking is then done by the table itself.
**
** Fine grained locking is supported by this code to allow concurrent updates
** (and reading) to different parts of the table. This works by keeping one
** rw-mtx for every N'th bucket. Even dynamic growing and shrinking by
** rehashing buckets can be done without exclusive table lock.
**
** A table will support fine grained locking if it is created with flag
** DB_FINE_LOCKED set. The table variable is_thread_safe will then indicate
** if operations need to obtain fine grained locks or not. Some operations
** will for example always use exclusive table lock to guarantee
** a higher level of atomicy.
*/

これを読むと__erl_db_hash.c__はハッシュテーブルの実装として、粗粒度ロック(Coarse grained lock)と細粒度ロック(Fine grained lock)、の二つに基づくものを提供していることが分かる。

そして「DB_FINE_LOCKEDフラグがセットされている場合は細粒度ロックが使用される」とあるが、これはwrite_concurrency=trueのケースに対応する。

粗粒度ロックの場合(つまりwrite_concurrency=false)は、このハッシュテーブル自体はロックの管理を一切行わずに、その利用側(erl_db.c)が読み込み/書き込み時に適切にロックを確保しているものとして動作する。
(そして__erl_db.c__は、テーブル毎に単一のRWロックを使用するので、書き込み競合に弱い)

それに対して細粒度ロックの場合は、ethr_mutex.cが提供するRWロックを使って、要素の更新や検索時に自前でロックを管理する (こちらは逆に__erl_db.c__側では不要なロックを獲得しないことが期待される。__erl_db.c__と__erl_db_hash.c__の協調方法の詳細に関しては後述)。
具体的には、次のような動作となる:

  • テーブルがDB_HASH_LOCK_CNT個の領域に(論理的に)分割される
    • DB_HASH_LOCK_CNTの値はデフォルトでは64
    • configure時にwith_ets_write_concurrency_locksオプションを指定することで変更可能
  • それぞれの領域に対して一つのRWロックが割り当てられる
  • その領域に属する要素にアクセスする場合は、事前に対応するRWロックを獲得する
    • 更新系ならライターロック、参照系ならリーダーロック

細粒度ロックでは、テーブルへの更新アクセスが競合した場合でも、領域が被らなければ別々のロックが使用されるので、互いを邪魔することがなく、並列度が高まることが期待される。

つまりwrite_concurrencyオプションのtrueとfalseが、それぞれ__細粒度ロック__と__粗粒度ロック__に対応し、前者であれば書き込み競合にも強いであろう、というのが__erl_db_hash.c__の基本方針となる。

なおread_concurrencyオプションの値に関しては、write_concurrency=trueのケースでだけ参照される(詳細は後述)。

実装

以降では__erl_db_hash.c__の実装コードを見ていく(オプション関連部分のみ)。

変数やフラグ

まずは(read|write)_concurrencyオプションに関連する、__erl_db_hash.c__内で参照される変数やフラグについての説明。
なお、以下の変数やフラグの設定および更新自体は__erl_db.c__内で行われる。__erl_db_hash.c__は渡された値を参照するのみで"(read|write)_concurrency"といった文言がこのファイル内に直接出てくることもない。

  • 変数: DbTable.common.type
    • テーブルのタイプを表す変数
    • (read|write)_concurrencyの値に応じて、以下のフラグがセットされる
      • read_concurrency=trueの場合: DB_FREQ_READフラグ
      • write_concurrency=trueの場合: DB_FINE_LOCKEDフラグ
  • 変数: DbTable.common.is_thread_safe
    • __erl_db_hash.c__が、自前ロックを使う必要があるかどうかを判定するための変数
      • 値がtrueの場合は、前段で安全性が保障されているので、自前ロックは不要
    • write_concurrency=falseの場合は、常にtrueとなる
    • write_concurrency=trueの場合でも、__erl_db.c__が適切なロックを獲得している場合はtrueになる
      • 例えば__erl_db.c__内でテーブル全体ロックが獲得されている状態で、ハッシュテーブルの各種操作が行われる場合
    • DbTable.common.typeと異なり、実行中に値が変動する

上記を踏まえた上で、次に関連する各関数のコードを見ていく。

基本的に(read|write)_concurrencyオプションは、ハッシュテーブルの生成と要素へのアクセス時の前処理、くらいにしか影響を与えないので、見るべきコードの量は少ない。

ハッシュテーブル生成: db_create_hash関数

ハッシュテーブルの生成時に(read|write)_concurrencyの値に(間接的に)応じて、自前ロックを使用するかどうかが決定される。

erl_db_hash.c
int db_create_hash(Process *p, DbTable *tbl)
{
    DbTableHash *tb = &tbl->hash;

    erts_smp_atomic_init_nob(&tb->szm, SEGSZ_MASK);
    erts_smp_atomic_init_nob(&tb->nactive, SEGSZ);
    erts_smp_atomic_init_nob(&tb->fixdel, (erts_aint_t)NULL);
    erts_smp_atomic_init_nob(&tb->segtab, (erts_aint_t)NULL);
    SET_SEGTAB(tb, alloc_ext_seg(tb,0,NULL)->segtab);
    tb->nsegs = NSEG_1;
    tb->nslots = SEGSZ;

    erts_smp_atomic_init_nob(&tb->is_resizing, 0);
    
    // `(write|read)_concurrency`が関係してくるのは、この中
    if (tb->common.type & DB_FINE_LOCKED) {
        /***
          * NOTE: write_concurrency=true、の場合
          ***/
        erts_smp_rwmtx_opt_t rwmtx_opt = ERTS_SMP_RWMTX_OPT_DEFAULT_INITER;
        int i;
        if (tb->common.type & DB_FREQ_READ)
            /***
              * NOTE: read_concurrency=true、の場合
              * 各領域を用のRWロックが、並列読み込み時にスケールするようにする(詳細は「ethr_mutex.c」を参照)
              ***/
            rwmtx_opt.type = ERTS_SMP_RWMTX_TYPE_FREQUENT_READ;
        if (erts_ets_rwmtx_spin_count >= 0)
            rwmtx_opt.main_spincount = erts_ets_rwmtx_spin_count;

        // 各領域用のRWロックを`DB_HASH_LOCK_CNT`分だけ確保(and 初期化)する
        tb->locks = (DbTableHashFineLocks*) erts_db_alloc_fnf(ERTS_ALC_T_DB_SEG, /* Other type maybe? */
                                                              (DbTable *) tb,
                                                              sizeof(DbTableHashFineLocks));
        for (i=0; i<DB_HASH_LOCK_CNT; ++i) {
            erts_smp_rwmtx_init_opt_x(&tb->locks->lck_vec[i].lck, &rwmtx_opt,
                                      "db_hash_slot", make_small(i));
        }
    }
    else { /* coarse locking */
        /***
          * NOTE: write_concurrency=false、の場合
          ***/
        tb->locks = NULL;  // 内部ロックは使用しない
    }
    ERTS_THR_MEMORY_BARRIER;
    return DB_ERROR_NONE;
}

自前ロックを管理する場合は、read_concurrencyの値がtrueなら、その各RWロックが並列読み込みに最適化されたものとなる。
「ethr_mutex.c」の節の最後に「(大雑把に言えば)論理八コアなら、読み込み最適化RWロックの所要メモリはおよそ512KB」と書いたが、それが全領域分(DB_HASH_LOCK_CNT個)必要になるので、合計で32MB、と意外と馬鹿にならないメモリ領域を消費することになるので、両オプションの併用には若干注意が必要そう。

要素アクセス時に呼ばれる関数群

ハッシュテーブル内の要素にアクセスする際のロックの使い方の一例として、以下に要素検索用の関数の実装コードを掲載する。

erl_db_hash.c
static int db_member_hash(DbTable *tbl, Eterm key, Eterm *ret)
{
    DbTableHash *tb = &tbl->hash;
    HashValue hval;
    int ix;
    HashDbTerm* b1;
    erts_smp_rwmtx_t* lck;

    hval = MAKE_HASH(key);  // 1. ハッシュ値を求める
    ix = hash_to_ix(tb, hval);
    lck = RLOCK_HASH(tb, hval);  // 2. 要素アクセス前に対応するロックを確保
    
    // 3. 要素アクセス (バケットの検索およびバケット内の要素の走査)
    b1 = BUCKET(tb, ix);
    while(b1 != 0) {
        if (has_live_key(tb,b1,key,hval)) {
            *ret = am_true;
            goto done;
        }
        b1 = b1->next;
    }
    *ret = am_false;
done:
    RUNLOCK_HASH(lck);  // 4. ロックを解放
    return DB_ERROR_NONE;
}

流れとしては、次のようになっており、このパターンは他の要素アクセス関数でも同様となる:

  1. 最初のキーのハッシュ値を計算 (MAKE_HASH)
  2. そのハッシュ値に対応するロックを獲得
  • 更新系ならWLOCK_HASH関数を使用
  • 参照系ならRLOCK_HASH関数を使用
  1. 要素にアクセスして、その関数固有の処理を実行
  2. アクセスが終わったら、ロックを解放
  • WUNLOCK_HASH or RUNLOCK_HASH

要はアクセスの前後で、対応するロックの獲得と解放を行っているだけ。

次はWLOCK_HASH等のロック系の関数の実装:

erl_db_hash.c
#  define DB_HASH_LOCK_MASK (DB_HASH_LOCK_CNT-1)
#  define GET_LOCK(tb,hval) (&(tb)->locks->lck_vec[(hval) & DB_HASH_LOCK_MASK].lck)

/* Fine grained read lock */
static ERTS_INLINE erts_smp_rwmtx_t* RLOCK_HASH(DbTableHash* tb, HashValue hval)
{
    if (tb->common.is_thread_safe) {
        // erl_db.c内で、既にロックが獲得されている場合は、ここでの処理は不要
        return NULL;
    } else {
        // ハッシュ値に対応する領域用のロックを取得
        erts_smp_rwmtx_t* lck = GET_LOCK(tb,hval);
        erts_smp_rwmtx_rlock(lck);
        return lck;
    }
}
/* Fine grained write lock */
static ERTS_INLINE erts_smp_rwmtx_t* WLOCK_HASH(DbTableHash* tb, HashValue hval)
{
    if (tb->common.is_thread_safe) {
        return NULL;
    } else {
        erts_smp_rwmtx_t* lck = GET_LOCK(tb,hval);
        erts_smp_rwmtx_rwlock(lck);
        return lck;
    }
}

static ERTS_INLINE void RUNLOCK_HASH(erts_smp_rwmtx_t* lck)
{
    if (lck != NULL) {
        erts_smp_rwmtx_runlock(lck);
    }
}

static ERTS_INLINE void WUNLOCK_HASH(erts_smp_rwmtx_t* lck)
{
    if (lck != NULL) {
        erts_smp_rwmtx_rwunlock(lck);
    }
}

特に難しいところもなく素直な実装となっている。

その他

(read|write)_concurrencyに関連する話題としては、ここまで取り上げたもの以外にも「アトミック操作の実行時のメモリバリアを要不要を判定するためのDB_USING_FINE_LOCKINGマクロ」とか「テーブルリサイズを全体ロックを使わずに実行する工夫」とかの話が挙げられるが、全体の論旨に大きな影響を与えるものでもないので、今回は割愛する。

ここまでのまとめ

今回調べた範囲での__erl_db_hash.c__に対する(read|write)_concurrencyオプションの影響のまとめ(長い...):

  • __erl_db_hash.c__は、ハッシュテーブルを用いたETSテーブルの実装を、__erl_db.c__に提供している
    • __erl_db.c__との協調が前提のコード
  • write_concurrencyの値に応じて、要素アクセス時に__粗粒度ロック__と__細粒度ロック__のどちらを使うかが決定される
    • write_concurrency=falseなら__粗粒度ロック__が使われる:
      • この場合、全てのロック関連処理は__erl_db.c__に一任される
      • __erl_db.c__は、テーブル全体で一つのRWロックを使用する
        • 更新系操作は直列化され、参照系操作のスケール性はread_concurrencyの値に依存
        • 欠点: 並列書き込みが多い場合に(直列化されて)性能が劣化する
    • write_concurrency=trueなら__細粒度ロック__が使われる:
      • __erl_db_hash.c__が自前のロックを管理
      • テーブル全体をDB_HASH_LOCK_CNT個の領域に(論理的に)分割し、それぞれに一つのRWロックを割り当てる
      • 異なる領域に属する要素に対するアクセスでは、ロックが競合することはない
        • 利点: 並列書き込みが多い場合でも、ある程度まではスケールしやすい
      • 細粒度ロックの場合でも__erl_db.c__の層でのロック獲得は行われる (詳細は後述)
        • 欠点: 要素アクセス時のロック獲得回数が一回増えるので、オーバヘッドは増す
      • 欠点: DB_HASH_LOCK_CNT個だけRWロックが必要になるので、メモリ使用量が増す
  • __細粒度ロック__で使われるRWロックは、read_concurrency=trueなら並列読み込みに最適化されたものになる
    • RWロックでのread_concurrencyオプションの効果に関する詳細は「ethr_mutex.c」を参照のこと
    • 利点: 大量の更新と参照が交互に行われるようなケースでは、性能が向上する可能性がある
      • 同じ領域のRWロックに対する並列参照が大量に走った場合に有効
      • ただし細粒度ロックの時点で、すでにある程度アクセスが分散しているはずなので「同じ要素に対して大量の並列参照が実行される」といったような状況でもなければ効果は薄そう
      • ets:select/2のような全体参照が頻繁に実行されるようなケースならもしかしたら有効？
    • 欠点: 少数の更新と参照が交互に行われるようなケースでは、性能が劣化する可能性がある
    • 欠点: メモリ使用量がさらに(大幅に)増す
      • 概ね論理コア数 * キャッシュラインサイズ(e.g. 64B) * DB_HASH_LOCK_CNTだけ必要
      • コア数によっては、一つのテーブルで100MB程度のメモリを消費してしまう可能性もある

__erl_db.c__は全体的な調整処理が主なので、(read|write)_concurrencyオプションの値が性能に与える影響に関しては、この時点でほぼ情報が出揃ったことになる。

erl_db.c

最後は__erl_db.c__。

ここまでで取り上げた__ethr_mutex.c__および__erl_db_hash.c__が提供する構成要素を、どのように利用しているか、を中心に見ていく。

関連する変数

(read|write)_concurrencyオプションに関連する変数は(主に)以下の四つ。
前者二つは__erl_db_hash.c__で既出なので、説明は割愛する。

  • DbTable.common.type
  • DbTable.common.is_thread_safe
  • DbTable.common.rwlock
    • テーブルでグローバルな(全体ロック用の)RWロック
  • DbTable.common.meth
    • DbTableMethodインタフェースの実装モジュールのデータが保持される
    • 今回でいえば__erl_db_hash.c__のデータとなる

初期化処理

ets_new_2関数

ets:new/2に対応するBIF。
(read|write)_concurrencyオプションが直接参照されるのはここだけ。
内容的にはオプションの値に応じたフラグの調整処理が主。

erl_db.c
BIF_RETTYPE ets_new_2(BIF_ALIST_2)
{
/*** 省略 ***/
                else if (tp[1] == am_write_concurrency) {
                    // `write_concurrency`オプションのハンドリング
                    if (tp[2] == am_true) {
                        is_fine_locked = 1;  // 細粒度ロックを使用する
                    } else if (tp[2] == am_false) {
                        is_fine_locked = 0;
                    } else break;
                }
                else if (tp[1] == am_read_concurrency) {
                    // `read_concurrency`オプションのハンドリング
                    if (tp[2] == am_true) {
                        frequent_read = 1; // 並列読み込み最適化を有効にする
                    } else if (tp[2] == am_false) {
                        frequent_read = 0;
                    } else break;
                }
/*** 省略 ***/
    if (IS_HASH_TABLE(status)) {
        meth = &db_hash;
        if (is_fine_locked && !(status & DB_PRIVATE)) {
            // ハッシュテーブル and 細粒度ロック、なら`DB_FINE_LOCKED`フラグをセット
            status |= DB_FINE_LOCKED;
        }
    }
/*** 省略 ***/
    if (frequent_read && !(status & DB_PRIVATE))
        status |= DB_FREQ_READ;  // `DB_FREQ_READ`フラグをセット
/*** 省略 ***/
    tb->common.type = status & ERTS_ETS_TABLE_TYPES;
    /* Note, 'type' is *read only* from now on... */
/*** 省略 ***/
    // db_init_lock関数で、テーブル全体ロックを初期化
    db_init_lock(tb, status & (DB_FINE_LOCKED|DB_FREQ_READ),
                 "db_tab", "db_tab_fix");
/*** 省略 ***/
}

db_init_lock関数

テーブル全体用のRWロックであるDbTable.common.rwlockの初期化を行う関数。

erl_db.c
static ERTS_INLINE void db_init_lock(DbTable* tb, int use_frequent_read_lock,
                                     char *rwname, char* fixname)
{
    erts_smp_rwmtx_opt_t rwmtx_opt = ERTS_SMP_RWMTX_OPT_DEFAULT_INITER;
    
   // NOTE: 
   // use_frequent_read_lock = status & (DB_FINE_LOCKED|DB_FREQ_READ)
   // => `(read|write)_concurrency`のどちらかが`true`なら、全体RWロックは並列読み込みに最適化される (理由は後述)
    if (use_frequent_read_lock)
        rwmtx_opt.type = ERTS_SMP_RWMTX_TYPE_FREQUENT_READ;
    if (erts_ets_rwmtx_spin_count >= 0)
        rwmtx_opt.main_spincount = erts_ets_rwmtx_spin_count;
    // 全体RWロックを初期化
    erts_smp_rwmtx_init_opt_x(&tb->common.rwlock, &rwmtx_opt,
                              rwname, tb->common.the_name);
    erts_smp_mtx_init_x(&tb->common.fixlock, fixname, tb->common.the_name);
    
    // is_thread_safe変数も初期化:
    // - DB_FINE_LOCKEDフラグが立っているなら`false`になる
    //   => 実装モジュール(ex. erl_db_hash.c)側でのロック管理が必要なことを示す
    tb->common.is_thread_safe = !(tb->common.status & DB_FINE_LOCKED);
}

(read_concurrencyの場合だけでなく)write_concurrencyがtrueの場合でも、全体RWロック(common.rwlock)を並列読み込みに最適化する理由は以下の通り:

  • まずはwrite_concurrency=falseの場合を考える:
    • 実装モジュールはロック管理を行わず__erl_db.c__がロック周りの一切の責任を持つ
    • __erl_db.c__はcommon.rwlockを用いて粗粒度ロックを実現する
      • 要素更新時にはライターロックを獲得 (並列アクセス不可)
      • 要素参照時にはリーダーロックを獲得 (並列アクセス可能)
  • 次にwrite_concurrency=trueの場合を考える:
    • 実装モジュールが粗粒度ロックを実現する
    • 並列更新(書き込み)を実現するのが主目的
    • ただし、この場合でも__erl_db.c__が要素アクセス時にcommon.rwlockを使うのは変わらない
    • 「実装モジュールが細粒度ロックに対応しても、その前段の__erl_db.c__が粗粒度ロックを使うのでは意味がないのでは？」という疑問が出てくる。
    • 解決策:
      • __erl_db.c__レイヤーでは、要素更新の場合でもリーダーロックを獲得するようにする(例外は後述)
        • __erl_db.c__レイヤーでの書き込み直列化が防げる
        • 適切なロックを管理する責任は、実装モジュールに移る
      • 要素の更新・参照の両方で、リーダーロックが使われるので、それがスケールするように読み込み最適化を常に有効にする
      • => これがwrite_concurrency=trueの場合でも全体ロックの読み込み最適化を有効にしている理由

つまりwrite_concurrency=trueの場合は、更新か参照かに関わらずcommon.rwlockでは、常にリードロックが獲得され、実際の整合性保証の責任は実装モジュールに委譲されることになる。

このような挙動であるなら細粒度ロックの場合は、そもそもcommon.rwlockを使わなくても良いように思えるが、例えばテーブル全体が操作対象になる場合(ex. ets:delete/1)や複数要素をアトミックに処理した場合(ex. ets:insert/2の第二引数がリスト)は、整合性を担保するためにcommon.rwlockを使ってテーブル全体のライターロックを獲得する必要があるので、完全に不使用とすることはできなくなっている。

要素アクセス時のロック獲得および解放

テーブル内の要素を操作する場合はdb_lock(); tb->common.meth->操作関数(); db_unlock();といったパターンが定番となる。

db_lockおよびdb_unlockは、全体RWロック(tb->common.rwlock)の獲得・解放を行うための関数で、実装は次のようになっている。

erl_db.c
typedef enum {
    LCK_READ=1,     /* read only access */
    LCK_WRITE=2,    /* exclusive table write access */
    LCK_WRITE_REC=3, /* record write access */
    LCK_NONE=4
} db_lock_kind_t;

static ERTS_INLINE void db_lock(DbTable* tb, db_lock_kind_t kind)
{
    if (tb->common.type & DB_FINE_LOCKED) {
       /***
         * NOTE: write_concurrency=true、の場合 (細粒度ロック)
         ***/
        if (kind == LCK_WRITE) {
            // テーブル全体の排他が必要な場合にのみライターロックを獲得
            erts_smp_rwmtx_rwlock(&tb->common.rwlock);
            tb->common.is_thread_safe = 1;
        } else {
            // 参照(kind=LOCK_READ) or 単一要素更新(kind=LOCK_WRITE_REC)の場合は、リーダーロックを獲得
            erts_smp_rwmtx_rlock(&tb->common.rwlock);
            ASSERT(!tb->common.is_thread_safe);
        }
    }
    else
    {
        /***
         * NOTE: write_concurrency=false、の場合 (粗粒度ロック)
         ***/
        switch (kind) {
        case LCK_WRITE:
        case LCK_WRITE_REC:
            // 更新系の場合はライターロックを獲得
            erts_smp_rwmtx_rwlock(&tb->common.rwlock);
            break;
        default:
            // 参照系の場合はリーダーロックを獲得
            erts_smp_rwmtx_rlock(&tb->common.rwlock);
        }
        ASSERT(tb->common.is_thread_safe);
    }
}

static ERTS_INLINE void db_unlock(DbTable* tb, db_lock_kind_t kind)
{
    // NOTE: リーダーロックとライターロックの使い分けは、db_lock関数と同様
    if (tb->common.type & DB_FINE_LOCKED) {
        if (kind == LCK_WRITE) {
            ASSERT(tb->common.is_thread_safe);
            tb->common.is_thread_safe = 0;
            erts_smp_rwmtx_rwunlock(&tb->common.rwlock);
        }
        else {
            ASSERT(!tb->common.is_thread_safe);
            erts_smp_rwmtx_runlock(&tb->common.rwlock);
        }
    }
    else {
        ASSERT(tb->common.is_thread_safe);
        switch (kind) {
        case LCK_WRITE:
        case LCK_WRITE_REC:
            erts_smp_rwmtx_rwunlock(&tb->common.rwlock);
            break;
        default:
            erts_smp_rwmtx_runlock(&tb->common.rwlock);
        }
    }
}

最後にdb_lockとdo_unlockの実際の使用例としてets:member/2とets:insert/2のBIF関数を載せておく。

erl_db.c
BIF_RETTYPE ets_member_2(BIF_ALIST_2)
{
    DbTable* tb;
    int cret;
    Eterm ret;

    CHECK_TABLES();

    // 要素アクセス前にロックを獲得
    // NOTE: gb_get_tableの中で`db_lock(tb, LCK_READ)`が呼ばれる
    if ((tb = db_get_table(BIF_P, BIF_ARG_1, DB_READ, LCK_READ)) == NULL) {
        BIF_ERROR(BIF_P, BADARG);
    }

    // メンバー判定の実際の処理は、DbTableMethの実装モジュールに委譲
    cret = tb->common.meth->db_member(tb, BIF_ARG_2, &ret);

    // アクセスが終わったのでロックを解放
    db_unlock(tb, LCK_READ);

    switch (cret) {
    case DB_ERROR_NONE:
        BIF_RET(ret);
    case DB_ERROR_SYSRES:
        BIF_ERROR(BIF_P, SYSTEM_LIMIT);
    default:
        BIF_ERROR(BIF_P, BADARG);
    }
}

BIF_RETTYPE ets_insert_2(BIF_ALIST_2)
{
    DbTable* tb;
    int cret = DB_ERROR_NONE;
    Eterm lst;
    DbTableMethod* meth;
    db_lock_kind_t kind;

    CHECK_TABLES();
 
    // 使用するロックの種類を決定:
    // - 挿入要素が単一なら`LCK_WRITE_REC` (細粒度ロック時にはリーダーロックとなる)
    // - 挿入要素が複数なら`LCK_WRITE` (常にライターロックとなる)
    /* Write lock table if more than one object to keep atomicy */
    kind = ((is_list(BIF_ARG_2) && CDR(list_val(BIF_ARG_2)) != NIL)
            ? LCK_WRITE : LCK_WRITE_REC);

   // 要素アクセス前にロックを獲得
   // NOTE: gb_get_tableの中で`db_lock(tb, kind)`が呼ばれる
    if ((tb = db_get_table(BIF_P, BIF_ARG_1, DB_WRITE, kind)) == NULL) {
        BIF_ERROR(BIF_P, BADARG);
    }

    // 実際の要素挿入処理は、DbTableMethの実装モジュールに委譲
    meth = tb->common.meth;
    if (is_list(BIF_ARG_2)) {
        for (lst = BIF_ARG_2; is_list(lst); lst = CDR(list_val(lst))) {
            cret = meth->db_put(tb, CAR(list_val(lst)), 0);
            if (cret != DB_ERROR_NONE)
                break;
        }
    } else {
        cret = meth->db_put(tb, BIF_ARG_2, 0);
    }

    // アクセスが終わったのでロックを解放
    db_unlock(tb, kind);

    switch (cret) {
    case DB_ERROR_NONE:
        BIF_RET(am_true);
    case DB_ERROR_SYSRES:
        BIF_ERROR(BIF_P, SYSTEM_LIMIT);
    default:
        BIF_ERROR(BIF_P, BADARG);
    }
}

その他

ets:select/2のようなテーブル全体を走査する関数の場合は、DB_FINE_LOCKEDフラグの有無やis_thread_safeの値に応じて、若干処理が変わってくるのだが本筋の話には影響がない(と思う)ので割愛する。

ここまでのまとめ

今回調べた範囲での__erl_db.c__に対する(read|write)_concurrencyオプションの影響のまとめ:

  • __erl_db.c__は__テーブル全体が対象のRWロック__と保持している
  • (read|write)_concurrencyのいずれかがtrueの場合は、このRWロックは読み込み性能に最適化されたものが使用される
  • 要素アクセス時には、このRWロックが獲得されるが、write_concurrencyの値によって獲得するロックの種類が変わってくる:
    • write_concurrency=falseの場合 (粗粒度ロック):
      　 - 適切なロック管理の責任は__erl_db.c__にある
      • 更新系の操作の場合にはライターロックを、参照系操作の場合はリーダーロックを、獲得する
    • write_concurrency=trueの場合 (細粒度ロック):
      • 適切なロック管理の責任は(ほぼ)実装モジュール(ex. erl_db_hash.c)にある
      • 参照系および単一要素が対象の更新系の場合は、リーダーロックを獲得する
        • 更新系操作の場合に、適切なロックを獲得するのは、その先の実装モジュールの責任
      • テーブル全体や複数要素のアトミック更新が関わる操作の場合は、ライターロックを獲得する

以上で(read|write)_concurrencyオプションに関わる主要なファイルのコードは一通り読み終わった。

まとめ

オプションの効果

これまでの話を踏まえて(read|write)_concurrencyの値の組み合わせによる効果をまとめてみた。
(公式ドキュメントの説明と結構内容が被っている気がする)

両方がfalse (デフォルト)

  • 並列書き込みには非対応 (アクセスが直列化される)
  • 並列読み込みに対応
    • ただし競合度が高い場合には、性能が劣化する可能性がある
  • メモリ使用量のオーバヘッドは一番小さい

read_concurrency=true

  • 並列書き込みには非対応 (アクセスが直列化される)
  • 並列読み込みに対応
    • 競合度が高い場合でも、性能が劣化しない(しにくい)
  • 書き込みと読み込みが交互に発生する場合は、性能が劣化しやすい
    • 両者の切り替えコストがread_concurrency=falseに比べて高いため
  • 論理コア数 * キャッシュラインサイズ程度のメモリオーバヘッドがある

write_concurrency=true

  • 並列書き込みに対応
  • 並列読み込みに対応
  • テーブルは64個の領域に(論理的に)分割される:
    • 異なる領域に属する要素群に対する操作は、並列実行が可能となる
      • 書き込み同士 or 書き込みと読み込み、が同時に実行できる
      • 競合度が高い場合の並列読み込みの性能劣化も少ない (領域分割により)
        • read_concurency=false < write_concurrency=true < read_concurrency=trueといった感じ
    • 同じ領域に属する要素群に対する操作はread_concurrency=falseの場合と同じ性能特性となる
      • 書き込みは直列化され、高い並列読み込み競合には弱い
  • オーバーヘッドが少ない分、直列アクセス時の性能はwrite_concurrency=falseの方が良い
  • 64 * RWロックのサイズ程度のメモリオーバヘッドがある

両方がtrue

  • 並列書き込みに対応
  • 並列読み込みに対応
  • 基本的にはwrite_concurrency=trueのみを指定した場合と同じ特性を備えるので、以降は差分のみを記述する
  • テーブルは64個の領域に(論理的に)分割される:
    • 異なる領域に属する要素群に対する操作は、並列実行が可能となる
    • 同じ領域に属する要素群に対する操作はread_concurrency=trueの場合と同じ性能特性となる
      • 高い並列読み込み競合には強いが、読み込みと書き込みの切り替わりに弱い
        • write_concurrency=trueを指定している以上、一定数の書き込みはあると予想されるので、後者の特性は結構痛い
      • 並列読み込みと並列書き込みのバーストが交互にあるような状況に向いている可能性がある
  • 64 * 論理コア数 * キャッシュラインサイズ程度のメモリオーバヘッドがある
    • コア数が多い環境では、普通に数十MBとか行きそう

個人的な結論

基本的にはテーブルのアクセス権限に応じて「privateなら指定なし」、「protectedならread_concurrency=true」、「publicならwrite_concurrency=true」をベースとするのが良さそうに思う。

後は、実際の使用用途に応じて調整をする。
例えばprotectedでも、自プロセスによる書き込みが常時発生するようならwrite_concurrency=trueにしてみるとか。

read_concurrencyとwrite_concurrencyの両方をtrueに設定する組み合わせは、有効に働く場面がかなり限られており、かつメモリオーバヘッドも大きいので、基本的には使わない方針となりそう。

13
12
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
13
12

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?