それが僕には楽しかったんです。

僕と MySQL と時々 MariaDB

Redis を Docker 環境でいい感じに使うためのメモ

Redis

はじめに

どうも、最近メイドインアビスが「ポップな絵柄で描かれたダークソウル」と聞いて見てみたら想像以上にダークソウルだったのではまりそうなけんつです。

結構、Redis をいい感じに docker-compose とかで使いたい時があるのでこの際にまとめてしまおうといったノリで書いていく。
絶対こういう設定を本番環境で使うべきではないと思う。あくまでも開発時に欲しい設定をまとめている。

前提として、ジョブワーカーの MQ に使う

環境

  • Redis 5.0.1
  • docker-compose version 1.23.0
  • docker 19.03.5

上での構築を前提としている。

データの永続化

Redis のデータ永続化には AOF と RDB というタイプが存在する。
AOF は fsync ポリシーを選択した上で使用される追記専用のログ。AOF で選択できる fsync ポリシーは以下の通り。

  • no: fsync を利用しない。OS が都度データをフラッシュする。
  • always: 追加に関するログが書き込まれる度に fsync を実行する
  • everysec: 毎秒無条件に fsync を実行する。

AOF が肥大化すると、Redis はバックグランドでリライトを行う。この時、新しいファイルにはその時点のデータ・セットを再現するために必要な最小限の手順を記録した情報が付与される。
この肥大化に関わる設定は auto-aof-rewrite-percentage, auto-aof-rewrite-min-size を設定することで定義出来る。

欠点としては、AOF は RDB*1 を利用して永続化するよりもファイルサイズが大きくなりやすい。
他には、fsync ポリシーによっては全体的な性能低下を招くことがある。反対に RDB では、書き込み負荷が高い場合でも最大レイテンシを保証することが出来る。そのため、AOF はパフォーマンスが要求されるような箇所に everysec で使われるべきではない。*2

普段 Redis を使うときはメッセージキューとして利用することが多く、キューのデータをロストすると困るため AOF でデータを永続化させている。
これがクエリのキャッシュだったりする場合は、そもそも永続化とかしなくてもよいかなと思う。

設定は以下の通り。

dir /data
appendonly yes
appendfsync everysec
auto-aof-rewrite-percentage 100
auto-aof-rewrite-min-size 8mb

dir でデータを保持するディレクトリを設定する。これは Redis の docker コンテナ*3を利用するとき、何故か /data がデフォルトで aof を吐く。
aof ファイルは 8mb*4を最小サイズとして aof ファイルサイズが倍増した段階でリライトするようになっている。これはキューを２つしか使わない場合が多いからこうなっている。

ログ

開発時に見たい情報が多々あるので、ログレベルも設定して置きたい。基本的には debug としている。
また、Redis では logfile "" がデフォルトとなっているためログは /dev/null に吐かれるらしい。*5
STDOUT にログが吐かれるので docker-compose 側で fluentd や syslog とかを使っても面白そうだけど今回はやっていない。

loglevel debug
logfile ""

メモリ周り

Redis は基本的にオンメモリ KVS のため、利用できる最大メモリ量や仮にメモリを確保できなくて書き込めない場合にどのような挙動をするか設定することができる。

メモリ解放ポリシーは以下の通り。

  • volatile-lru: 期限切れのものを LRU によって削除する
  • allkeys-lru: 全てのキーを対象に LRU に基づいて削除する
  • volatile-ramdom: 期限切れのキーをランダムに削除する
  • allkeys-random: 全てのキーをランダムに削除する
  • volatile-ttl: TTL を比較して小さい順に削除する
  • noeviction: 削除せずに書き込みエラーとして返す

ジョブワーカー用のキューを作ることがおおいので、どのようなポリシーであっても削除されるとジョブの情報が失われるので noeviction を設定する。

最大メモリ使用量は 100MB 程度としておく。あまり利用されてホストマシンに影響がでても困るので。

maxmemory 100mb
maxmemory-policy noeviction

おわりに

とりあえず開発用にいつも使いたい設定たちはこんな感じだろうか。
書いていてログ周りが docker 環境ではやや面倒くさいのでレプリケーションやクラスタを組んだ時にでも fluentd か syslog を使っていい感じにするやつをまとめる

*1:リレーショナル・データベースのことではなく、Redis の永続化手法の一つ。

*2:と、思う。

*3:redis:latest で振ってくるもの

*4:Redis での 8mb は 1024 * 1024 * 8 byte。 8m だと 8 * 10^6 byte となる

*5:これ結構びっくりした

MySQL 8.0.18 の実装を読み解きながら簡単なストレージエンジンを自作する

MySQL

はじめに

卒論書くのに飽きてきて何かやりたくなったので急にストレージエンジンを書くことにしてみた。
MySQL のストレージエンジンを実装していく中で、色々できるかなと思っていたけど、やってみると MySQL の内部実装について色々知らないといけないことが多くインデックスとかトランザクションとかそういうところは実装できなかった。

github.com

MySQL をビルドする

ストレージエンジンを開発するためにはまずソースコードをビルドする必要がある。

$ cd /tmp
$ wget  https://dev.mysql.com/get/Downloads/MySQL-8.0/mysql-boost-8.0.18.tar.gz
$ tar xzvf mysql-boost-8.0.18.tar.gz

ビルドに必要なパッケージを引っ張ってくる。

$ sudo apt-get install -y cmake libncurses5-dev libssl-dev build-essential

ビルドする。

$ cd mysql-8.0.18/
$ cmake . -DWITH_BOOST=./boost -DFORCE_INSOURCE_BUILD=1
$ make

ビルドまでしたら次は make install をするべきなのだけど、ストレージエンジンのプラグインは make すれば共有ライブラリ(.so) として吐かれるため
それを MySQL の docker コンテナ内に突っ込んで適用する。

ストレージエンジンを自作する

Example エンジンをベースにする

MySQLのストレージエンジンを自作してみる - 備忘録の裏のチラシ
↑この記事と

第84回 ストレージエンジンをビルドしてみる：MySQL道普請便り｜gihyo.jp … 技術評論社
この記事を参考にしている。

まず storage ディレクトリ以下にストレージエンジンのコードがエンジン別のディレクトリに分かれているので作成する。
ここでは、example エンジンをベースにする。

$ cd mysql-8.0.18
// cp -R storage/example/ storage/gambit ここで自分は gambit という名前にしている
$ cp -R storage/example/ storage/{好きな名前}

ここまでやると storage/gambit が次の様な構成になっているはず。

mysql-8.0.18/storage/gambit$ ls
CMakeFiles      CTestTestfile.cmake  cmake_install.cmake  ha_example.h
CMakeLists.txt  Makefile             ha_example.cc

このあとが少し面倒で、コピーした example エンジンのコード内にある example, EXAMPLE を gambit, GAMBIT に修正する必要がある。

まず修正するのは Makefile。
Makefile 内の example -> gambit に置換する。

次に CMakeList.txt をひらいて、 example -> gambit, EXAMPLE->GAMBIT に置換する。
それが終わったら ha_example.* を ha_gambit.* に置換して、そのコード内の Example, EXAMPLE, example を置換する。

ここまでおわったら MySQL のプロジェクトルートに cd して

$ cmake . -DWITH_BOOST=./boost -DFORCE_INSOURCE_BUILD=1
$ make

これで再度適用して、 show engines で該当するストレージエンジンがあれば問題ない。
ストレージエンジンのコードを修正した場合は、make すれば、 plugin_output_directory にビルドされる。

handlerton の作成とインスタンス化

handlerton (handler singleton の略らしい)は、ストレージエンジンの定義と諸々の処理に対するメソッドポインタを持っている。
これを作成し、インスタンス化することで MySQL はストレージエンジンを使用することができる。
また、ストレージエンジンのハンドラを作成しているのは 

handlerton *gambit_hton
static int gambit_init_func(void *p) {
  DBUG_TRACE;

  gambit_hton = (handlerton *)p;
  gambit_hton->state = SHOW_OPTION_YES;
  gambit_hton->create = gambit_create_handler;
  gambit_hton->flags = HTON_CAN_RECREATE;
  gambit_hton->is_supported_system_table = gambit_is_supported_system_table;

  return 0;
}

に含まれる gambit_hton->crate = gambit_create_handler が行う。

この gambit_create_handler は以下処理を行う。

static handler *gambit_create_handler(handlerton *hton, TABLE_SHARE *table,
                                       bool, MEM_ROOT *mem_root) {
  return new (mem_root) ha_gambit(hton, table);
}

またここで呼ばれる ha_gambit は以下の通り。

ha_gambit::ha_gambit(handlerton *hton, TABLE_SHARE *table_arg)
    : handler(hton, table_arg) {}

以下のドキュメントとは微妙にこのハンドラの特に定義部分が異なるが、メソッドポインタなどの登録は初期化関数内で行った方が良さそう。
また、これはどういうことなのかまだわかっていないがストレージエンジンのメタ情報は以下の mysql_declare_plugin で定義するようになっているみたい。*1

mysql_declare_plugin(gambit){
    MYSQL_STORAGE_ENGINE_PLUGIN,
    &gambit_storage_engine,
    "GAMBIT",
    "lrf141",
    "Gambit simple storage engine",
    PLUGIN_LICENSE_GPL,
    gambit_init_func, /* Plugin Init */
    NULL,              /* Plugin check uninstall */
    NULL,              /* Plugin Deinit */
    0x0001 /* 0.1 */,
    func_status,              /* status variables */
    gambit_system_variables, /* system variables */
    NULL,                     /* config options */
    0,                        /* flags */
} mysql_declare_plugin_end;

この mysql_declare_plugin の実体はマクロ。
mysql-server/plugin.h at 4869291f7ee258e136ef03f5a50135fe7329ffb9 · mysql/mysql-server · GitHub
mysql-server/plugin.h at 4869291f7ee258e136ef03f5a50135fe7329ffb9 · mysql/mysql-server · GitHub



ドキュメントは以下を参照している。
dev.mysql.com

テーブルを作成する

ここまでで、前提となるストレージエンジンの大まかな解説は終わりにして、早速実装していく。
まずはテーブルを作るところから。
基本的には ha_gambit.cc の ha_gambit::create メソッドを実装していく形になる。
公式ドキュメントは以下のページ。
MySQL :: MySQL Internals Manual :: 23.8 Creating Tables

この関数はテーブルを作る際に呼ばれるとなっていて、基本的には my_create を呼び出すことでファイルを作成するようになっている。
ただ、その前にドキュメントには記載されていない create メソッドにあるこの存在。
まずはこれが何か読み解く。

int ha_gambit::create(const char *name. TABLE *, HA_CREATE_INFO *. dd::Table) {
...

  /*
    It's just an gambit of THDVAR_SET() usage below.
  */
  THD *thd = ha_thd();
  char *buf = (char *)my_malloc(PSI_NOT_INSTRUMENTED, SHOW_VAR_FUNC_BUFF_SIZE,
                                MYF(MY_FAE));
  snprintf(buf, SHOW_VAR_FUNC_BUFF_SIZE, "Last creation '%s'", name);
  THDVAR_SET(thd, last_create_thdvar, buf);
  my_free(buf);

  uint count = THDVAR(thd, create_count_thdvar) + 1;
  THDVAR_SET(thd, create_count_thdvar, &count);

  return 0;
}

MySQL: THD Class Reference
THD はクライアントの接続毎に、Thread/Connction ディスクリプタとして動作する個別のスレッドを作成するクラス。
このクラスがもつメソッド達をみても間違いないはず。

一度スレッドを取得したあとは、メモリを確保してバッファにログ(?)を書き込む。
そのあとはスレッドローカルの値を buf に更新する。
そして、スレッド数を１加算してからスレッドローカルに同様に保存している。

このスレッドに何の意味があるかわからなかったので InnoDB の ha_innobase::create を読んでみると trx とあったのでおそらくトランザクションを実装するときに使うのだろうと思った。ここはトランザクション関連をやるまでわからない。
それか、PSI とあるので性能計測系のスレッドかもしれない。
mysql-server/ha_innodb.cc at 91a17cedb1ee880fe7915fb14cfd74c04e8d6588 · mysql/mysql-server · GitHub

その前にいくつか前提を抑えておく。
この create メソッドでは基本的に my_craate 関数を使ってデータを保存するファイルを作るっぽいが、my_create が何を引数にして何を返すかがドキュメントにはないので以下の MySQL のコードとコードドキュメントを読む。
mysql-server/my_create.cc at 91a17cedb1ee880fe7915fb14cfd74c04e8d6588 · mysql/mysql-server · GitHub
MySQL: Mysys - low level utilities for MySQL

my_create の引数は FileName, CreateFlags, access_Flag, MyFlags とある。
FileName はそのままだが、問題は CreateFlags と access_Flag、 MyFlags。
CreateFlags は O_CREAT と OR が計算されるようになっている。これは open システムコールを呼ぶときにファイルが存在しない場合はそのファイルを作成することが前提となるため。なのでここでは、open システムコールに渡すのと同じものを渡せば確実にそれと同一の挙動を取る。
access_flag は O_CREAT が前提になっているため、どのような権限をそのファイルに付与するかどうかを決定付ける。

問題は MyFlags。
ここで special flag と書かれた myf という型は int のエイリアスとなっている。
MySQL: include/my_inttypes.h File Reference
で、結局これが何者なのかというとさっきの my_create のコードを見てみると明らかにエラーの場合に呼ばれている。
なにやらしらべてみると my_funcs に紐付いた値らしくなんらかの関数を呼ぶのに使用されているみたい。よくわからない。


この my_create では該当ファイルを開いたあと、ディレクトリ情報を同期する。*2
そのあと、ファイル情報を内部的に保持する。
また、ファイルを開く段階で該当ファイルが存在しない場合は作成されるようになっている。
mysql-server/my_create.cc at 91a17cedb1ee880fe7915fb14cfd74c04e8d6588 · mysql/mysql-server · GitHub

ここまで読んで気がついたけど、おそらく my_create は open システムコールのラッパーになっているっぽい。

これで実装していく。

int ha_gambit::create(const char *name, TABLE *, HA_CREATE_INFO *,
                       dd::Table *) {
  DBUG_TRACE;
  File create_file;
  DBUG_ENTER("ha_gambit::create");
  if ((create_file=my_create(name, 0, O_RDWR | O_TRUNC, MYF(0))) < 0)
      DBUG_RETURN(-1);
  if ((my_close(create_file, MYF(0))) < 0)
      DBUG_RETURN(-1);

  /*
    It's just an gambit of THDVAR_SET() usage below.
  */
  THD *thd = ha_thd();
  char *buf = (char *)my_malloc(PSI_NOT_INSTRUMENTED, SHOW_VAR_FUNC_BUFF_SIZE,
                                MYF(MY_FAE));
  snprintf(buf, SHOW_VAR_FUNC_BUFF_SIZE, "Last creation '%s'", name);
  THDVAR_SET(thd, last_create_thdvar, buf);
  my_free(buf);

  uint count = THDVAR(thd, create_count_thdvar) + 1;
  THDVAR_SET(thd, create_count_thdvar, &count);

  return 0;
}

全体としてはこんな感じ。
TABLE, HA_CREATE_INFO. dd::Table は今回使用してない。dd::Table に至っては Internal Manual には記載されていないのでまたコードを追う必要がある。
TABLE は frm に吐かれる情報をもっているとあるのでおそらく sdi に統合されている。 HA_CREATE_INFO もテーブルのメタデータを持っているが今回はとくにそれらをいじったりしないので使っていない。


ここまでやって、make, ストレージエンジンの適用をやったら試してみる。

mysql [sample]> create table test_table(id int, name varchar(255)) engine=gambit;
Query OK, 0 rows affected (0.19 sec)

テーブルをストレージエンジンを指定した状態で作成する。
そうして /var/lib/mysql 以下の sample という DB のディレクトリ以下に次のファイルが存在した。

$ ls
test_table  test_table_339.sdi

できたっぽい。
この sdi ファイルというのは ver 8.0.3 で追加されたものらしく、 serialized dictionary information というもの。
中身は json 形式になっていて、 従来の frm などメタデータを保持していたものの代替となっている。
これは一時的なテーブルスペースと UNDO テーブルスペースを除く全てのテーブルスペースに存在する。
MySQL :: MySQL 8.0 Release Notes :: Changes in MySQL 8.0.3 (2017-09-21, Release Candidate)

余談・気になったところ

これ CREATE TABLE 文使ったら即時、ファイルが生成されたけどチェックポイントとか関係なく動作しているのかどうなのか。

テーブルを開く

テーブルを作成することはできたが問題は、その次に待っているテーブルをオープンするところ。
これはドキュメントがめちゃくちゃ薄い。もっというなら、テーブルを開くことなのにファイルロックを調べてねとしか書いていない。
おそらくそれ以外は本当に特に決まっていなくて、ファイルロックさえ考慮すればどう実装してもいいと思われる。

それではまず、ここでやるべき事を考えていく。
テーブルを SELECT, INSERT などの時に開く処理を ha_gambit::open に実装するのがここでの一番大きな目標。

そのメソッドは次のように宣言されている。

int ha_gambit::open(const char *, int, uint, const dd::Table *)

MySQL Internal のドキュメントとは異なるが、 int はおそらく mode で O_RDONLY, O_RDWR を渡すことを想定していて、 uint はテーブルを開く前にロックをどのようにチェックするかが渡されるはず。

#define HA_OPEN_ABORT_IF_LOCKED   0   /* default */
 #define HA_OPEN_WAIT_IF_LOCKED    1
 #define HA_OPEN_IGNORE_IF_LOCKED  2
 #define HA_OPEN_TMP_TABLE         4   /* Table is a temp table */
 #define HA_OPEN_DELAY_KEY_WRITE   8   /* Don't update index */
 #define HA_OPEN_ABORT_IF_CRASHED  16
 #define HA_OPEN_FOR_REPAIR        32  /* open even if crashed */

MySQL :: MySQL Internals Manual :: 23.9 Opening a Table

そして、EXAMPLE エンジンをベースにしているため、以下の実装が追加されている。

int ha_gambit::open(const char *, int, uint, const dd::Table *) {
  DBUG_TRACE;

  if (!(share = get_share())) return 1;
  thr_lock_data_init(&share->lock, &lock, NULL);

  return 0;
}

get_share を使って、share lock info を取得している。これは get_share() と ha_gambit.h のメンバを見ればわかる。

share という Gambit_share 型のメンバはヘッダーファイルで宣言されていて、 get_share の振る舞いは ha_gambit.cc に存在する。

Gambit_share *ha_gambit::get_share() {
  Gambit_share *tmp_share;

  DBUG_TRACE;

  lock_shared_ha_data();
  if (!(tmp_share = static_cast<Gambit_share *>(get_ha_share_ptr()))) {
    tmp_share = new Gambit_share;
    if (!tmp_share) goto err;

    set_ha_share_ptr(static_cast<Handler_share *>(tmp_share));
  }
err:
  unlock_shared_ha_data();
  return tmp_share;
}

get_share ではまず get_ha_share_ptr で ha_share ポインタを初期化、取得している。
MySQL: handler Class Reference

この ha_share が何者なのかというと Handler_share ポインタを格納・取得するポインタみたい。
そのポインタを取得して Gambit_share 型としてキャストしている。この Gambit_share 型は ha_gambit.h で定義されている。

/** @brief
  Gambit_share is a class that will be shared among all open handlers.
  This gambit implements the minimum of what you will probably need.
*/
class Gambit_share : public Handler_share {
 public:
  THR_LOCK lock;
  Gambit_share();
  ~Gambit_share() { thr_lock_delete(&lock); }
};

でも結局この share とは何なのかという肝心なところがドキュメント*3に書いてない。
なので、ちょっと戻って MySQL Internal Manual の Overview を読んでみる。
MySQL :: MySQL Internals Manual :: 23.2 Overview

The MySQL server is built in a modular fashion:

The storage engines manage data storage and index management for MySQL. The MySQL server communicates with the storage engines through a defined API.

Each storage engine is a class with each instance of the class communicating with the MySQL server through a special handler interface.

Handlers are instanced on the basis of one handler for each thread that needs to work with a specific table. For example: If three connections all start working with the same table, three handler instances will need to be created.

Once a handler instance is created, the MySQL server issues commands to the handler to perform data storage and retrieval tasks such as opening a table, manipulating rows, and managing indexes.

Custom storage engines can be built in a progressive manner: Developers can start with a read-only storage engine and later add support for INSERT, UPDATE, and DELETE operations, and even later add support for indexing, transactions, and other advanced operations.

意訳)
MySQL はモジュールベースで構築されている。

...(中略)...

各ストレージエンジンはクラスであって、そのクラスは handler インターフェースを介してサーバと通信する。
ハンドラーは特定のテーブルを操作する必要があるスレッド毎に１つのハンドラーインスタンスを生成する。例：3つの接続が全て同じテーブルで動作する場合は 3 つのハンドラインスタンスが生成される。

...(中略)...

つまり各コネクション毎にハンドラインスタンスを生成し、それらのハンドラ間ではこの share を共有しているということだった。
また、 ha_share はパーティション化されていないハンドラ*4の場合は TABLE_SHARE::ha_share が呼ばれるらしくその情報を見ると合点がいった。

TABLE_SHARE というものは、テーブル毎に生成され前述の通りテーブル間で共有されるインスタンスでテーブルのメタデータを持っている。
そのため、テーブルファイルの読み込みにはこの share を取得するべきだったらしい。
ここでようやく get_share の話に戻ってくる。 get_share では、この share を取得し、存在する場合はそれを返し存在しない場合は新たに share を生成し該当するポインタに代入して返している。

次に、また話は戻り get_share の後に何が起こるか。
その次は以下の処理が行われる。

thr_lock_data_init(&share->lock, &lock, NULL);

この thr_lock_data_init のドキュメントは以下のリンクにある。
MySQL: include/thr_lock.h File Reference

そもそも、この thr_lock_data_init は thr_lock.h|.cc に実装されているものなのだが、この thr_lock では Posix thread *5を扱う場合の R/W ロックを提供するものが実装されている。thr_lock_data_init はその機能の一部。

MySQL の thr_lock では 2 種類のロックを持つ。
マスターロック(THR_LOCK)とロックインスタンス(THR_LOCK_DATA)があり、任意のスレッドは任意の数だけロックインスタンスを持つことができる。また当然の如く使い終わったら、解放する必要がある。

ここまで来るとなにをやっていたかが分かってきて、 ha_gambit::open メソッドではそれが呼ばれる度に THR_LOCK_DATA インスタンスを生成する処理がなされるということになる。

既存の実装は理解したので、ようやくファイルを開く処理を書く。
まず、ロックなどなどは置いといてまずファイルディスクリプタをどこかで保持する必要がある。ファイルを開いてファイルディスクリプタを取るには my_open を使用する。おそらく my_open もシステムコールの open のラッパーだと思う。
実装は以下の通り。

int ha_gambit::open(const char *name, int, uint, const dd::Table *) {
  DBUG_TRACE;

  File open_file;

  if (!(share = get_share())) return 1;
  thr_lock_data_init(&share->lock, &lock, NULL);
  
  if (!(open_file = my_open(name, O_RDWR, MYF(0))))
      return 1;
  share->table_file = open_file;
  return 0;
}

class Gambit_share : public Handler_share {
 public:
  THR_LOCK lock;
  File table_file;
  Gambit_share();
  ~Gambit_share() { thr_lock_delete(&lock); }
};

テーブル毎に share がひとつ存在するので、ファイルディスクリプタを share で持つようにしている。
スレッドのロックを扱うには thr_multi_lock を使う必要があるのだが、ここではまだ使っていない。

INSERT の実装

ここで本来は SELECT がドキュメントの順番では来るが SELECT するためのデータが無いので先に INSERT を実装する。

INSERTを実装するには ha_gambit::write_row を実装する。
ただここは、本当に実装の例が無いので以下の２つの記事を参考にする。

MySQL - 自作ストレージエンジンで初音ミクさんに歌っていただきましょう - こんぶのつけもの
MySQLのストレージエンジンを自作してみる - 備忘録の裏のチラシ

今回はまず先に実装を載せる。そのあとでなぜそれがそのようなコードになったか書いていく。
というのも、ドキュメントからでは何をしたらよいのかわからなかったため。

まずha_gambit.h に以下のを追加した。

#include "sql_string.h"

class Gambit_share : public Handler_share {
  ...
  const char *name
  File write_file;
  ...
};

class ha_gambit : public handler {
...
  String buffer;
public:
...

まず、share にテーブル名を保持するメンバと書き込み用のディスクリプタを保持するメンバを追加した。
読み込み用のディスクリプタと同じにしてしまうと、ひとつのディスクリプタを R/W で共有することになってしまうのであまりやりたくない。

次に行を格納するためのバッファを handler に追加している。この型は string でなく String *6である。
このクラスは Java で言うところの String, StringBuffer がいい感じに合体したクラスに近い。
MySQL: String Class Reference

次に問題の ha_gambit.cc の実装。

int ha_gambit::write_row(uchar *) {
  ha_statistic_increment(&System_status_var::ha_write_count);

  share->write_file = my_open(share->name, O_RDWR | O_APPEND, MYF(0));

  char att_buf[1024];
  String attribute(att_buf, sizeof(att_buf), &my_charset_bin);
  my_bitmap_map *org_bitmap = tmp_use_all_columns(table, table->read_set);
  buffer.length(0);

  for (Field **field = table->field; *field; field++) {
    const char *p;
    const char *end;
    (*field)->val_str(&attribute, &attribute);
    p = attribute.ptr();
    end = attribute.length() + p;
    buffer.append('"');
    for (; p < end; p++)
        buffer.append(*p);
    buffer.append('"');
    buffer.append(',');
  }
  buffer.length(buffer.length() - 1);
  buffer.append('\n');
  tmp_restore_column_map(table->read_set, org_bitmap);
  int size = buffer.length();
  my_write(share->write_file, (uchar *)buffer.ptr(), size, MYF(0));
  return 0;
}

ha_statistic_increment とは、table が保持する THR 構造体のステータスを加算するもので今回は ha_write_count がインクリメントされている。
これはテーブルのステータス系表示に使われる。ので、最悪なくてもよさ気？
my_bitmap_map の tmp_use_all_columns は読み取りフラグを立てているがそのフラグが一体どこで利用されているかはわからない。

その次は、前述の書き込み用のファイルディスクリプタを取得するやつ。
attribute はこんな書き方があるのかと驚いている、これは C++ 独自の書き方なのかわからないがやっていることは char 型の配列を sql_string.h の String に直してかえしてくれるやつぐらいのイメージしかないが全くわからない。

そのあとはドキュメントに書いてあるように、 Field をループして、 String として値を取得したら 1 文字ずつ取り出して buffer に append している。
これをあとは最初に取得したファイルディスクリプタに登録するだけ。

ha_tina の存在

ha_tina という CSV ストレージエンジンが MySQL のコードにあるがこれを参考にして作られているものが多いのでこれをみるべきだったかもしれない。

テーブルスキャン

いよいよラスト、だがこれが一番面倒。
実装する関数が以下のように複数ある。

  • store_lock
  • external_lock
  • rnd_init
  • info
  • extra
  • rnd_next

実際に CSV ストレージエンジンで 9 行スキャンする場合はこう呼び出される。

ha_tina::store_lock
ha_tina::external_lock
ha_tina::info
ha_tina::rnd_init
ha_tina::extra - ENUM HA_EXTRA_CACHE   Cache record in HA_rrnd()
ha_tina::rnd_next
ha_tina::rnd_next
ha_tina::rnd_next
ha_tina::rnd_next
ha_tina::rnd_next
ha_tina::rnd_next
ha_tina::rnd_next
ha_tina::rnd_next
ha_tina::rnd_next
ha_tina::extra - ENUM HA_EXTRA_NO_CACHE   End caching of records (def)
ha_tina::external_lock
ha_tina::extra - ENUM HA_EXTRA_RESET   Reset database to after open

store_lock の実装

MySQL :: MySQL Internals Manual :: 23.10.1 Implementing the store_lock() Method
このメソッドは R/W の実行前に呼ばれる。行レベルロックやテーブルレベルロックなど内部ロックに関する実装をする。

ロックは今回実装しないので EXAMPLE からいじらない。

THR_LOCK_DATA **ha_gambit::store_lock(THD *, THR_LOCK_DATA **to,
                                       enum thr_lock_type lock_type) {
  if (lock_type != TL_IGNORE && lock.type == TL_UNLOCK) lock.type = lock_type;
  *to++ = &lock;
  return to;
}

やってることは、ハンドラのもつロックインスタンスがアンロック状態で ignore しないなら SELECT 時に共有ロック、 INSERT 系の場合は排他ロックをセットする。

external_lock の実装

これは外部ロックに関する実装。具体的にはデータファイルに対するファイルロックを実装する。
これも今回は実装しないのでそのまま。

int ha_gambit::external_lock(THD *, int) {
  DBUG_TRACE;
  return 0;
}

rnd_init の実装

テーブルスキャンでしようする変数などを初期化するメソッド。
stats.record とポジションに関する情報を初期化しておく。

class ha_gambit : public handler {
...
  off_t current_position;
...

int ha_gambit::rnd_init(bool) {
  current_position = 0;
  stats.records = 0;
  return 0;
}

info の実装

これは先に実装を載せる。

int ha_gambit::info(uint) {
  if (stats.records < 2)
    stats.records= 2;
  return 0;
}

レコード数が 2 未満の場合にオプティマイザの処理が変わるらしく、この場合はレコードが読み込まれない可能性があるため if 文を追加しないといけない。
これはソースコードのコメントの注意書きにあった。

extra の実装

これはストレージエンジンに対してヒントを送るための関数らしいので return 0 のみの状態で今回は放置する。

rnd_next の実装

これがファイルからレコードを読み込むメソッドとなる。書き込みの時とほぼ同じ処理をする。

int ha_gambit::rnd_next(uchar *buf) {
  DBUG_TRACE;
  int err;

  ha_statistic_increment(&System_status_var::ha_read_rnd_next_count);
  err = find_current_row(buf);
  if (!err) 
      stats.records++;
  return err;
}

int ha_gambit::find_current_row(uchar *buf) {
  DBUG_TRACE;

  my_bitmap_map *org_bitmap = tmp_use_all_columns(table, table->write_set);
  uchar read_buf[IO_SIZE];
  bool is_end;
  uchar *p;
  uchar current_char;
  uint bytes_read;

  memset(buf, 0, table->s->null_bytes);
  for (Field **field = table->field; *field; field++) {
    bytes_read = my_pread(share->table_file, read_buf, sizeof(read_buf), current_position, MYF(0));
    if (!bytes_read) {
      tmp_restore_column_map(table->write_set, org_bitmap);
      return HA_ERR_END_OF_FILE;
    }
    p = read_buf;
    current_char = *p;
    buffer.length(0);
    is_end = false;

    for (;;) {
      if (current_char == '"') {
        if (is_end) {
          current_position += 2;
          break;
        }
        is_end = true;
      } else {
        buffer.append(current_char);
      }
      current_char = *++p;
      current_position++;
    }
    (*field)->store(buffer.ptr(), buffer.length(), buffer.charset());
  }
  tmp_restore_column_map(table->write_set, org_bitmap);
  return 0; 
}

memset は今回は null を許容していないため、 先頭にあるカラム分の NULL ビットマップを 0 で埋めている。
この書き込み時の話は度々参考にしている以下のブログによくまとまっている。
MySQLのストレージエンジンを自作してみる - 備忘録の裏のチラシ

おわりに

INSERT, SELECT に関することは調べることが多すぎてめちゃくちゃ駆け足になってしまったのでまたこの手のブログを書くときに実装を追っていきたい。
次、やるときはそのあたりと index or トランザクション周りでもやろうかな
あと、C++ 今回はじめて書いたけどわからない文法が多すぎるからそっちもやらねば。

卒論執筆のいい気分転換になった

*1:ストレージエンジンに限らず、プラグインはこのような定義をソースコード末尾に持っている。

*2:Linux でのみこの動作が発生する

*3:ここで指すドキュメントとは MySQL 8.0.18 の Source Code DOcumentation のこと

*4:何を言っているかわからないがおそらくやっていない

*5:POSIX Thread はスレッドの POSIX 標準。スレッドの生成や操作などの API を定義している。

*6:sql_string.h の String クラス

MySQL のレプリケーション実装

MySQL

はじめに

どうも、年明けおもしろ荘を見ながらブログを書いているけんつです。
前にMySQL 8 と docker-compose を使ってレプリケーションを構築する記事を書いたのだけど、そこではただバイナリログのポジションベースのレプリケーションを構築しただけだったので
この記事でその実装と仕組みを追っていく。

前のレプリケーション構築記事
GTID ベースのレプリケーションには触れていない。
rabbitfoot141.hatenablog.com

レプリケーション実装

レプリケーションはマスターが DB の全ての更新や削除といった変更をバイナリログベースで追跡することがベースとなっている。
このバイナリログはサーバが起動した瞬間からデータ変更以外にもデータベースの構造が変わるなどのイベントを全て記録する。また変更が伴わない SELECT 等はバイナリログ上で追跡されない。

MySQL のレプリケーションは、マスタに変更があった場合にスレーブにデータをプッシュするのではなく、マスターからデータをプルするという表現が近い。
また実際に送信されるデータはバイナリログであり、スレーブはこのバイナリログのイベントを再現することで、マスターと同様のデータを再現する。

また各スレーブは独立しているため、スレーブはデータベースのコピーを独自のペースで読み取り、更新できレプリケーションプロセスを他のレプリケーションプロセスに影響を与えることなく開始、停止することが可能となっている。

実装の詳細

MySQL のレプリケーションはマスタサーバに１つ、スレーブサーバに２つのスレッドを使用することで実装されている。

サーバ側

  • Binlog dump thread: マスターがスレーブに接続するときにバイナリログの内容をスレーブに送信するスレッドを作る。これがそれ。マスター側で SHOW PROCESSLIST で binlog dumo thread を確認できる。このスレッドはスレーブに送信される各イベントの読み取りの

スレーブ側

  • Slave I/O Thread: START SLAVE がスレーブ側で実行され、マスターに接続した段階でバイナリログの更新記録の送信を要求する I/O スレッドを要求する。このスレッドは Binlog dump Thread が送信するバイナリログの各イベントを読み取るためにマスターのバイナリログでロックを取る。*1
  • Slave SQL Thread: スレーブは Slave I/O Thread によって書き込まれたリレーログを読み取るこのスレッドを作成し、そこに含まれるイベントを実行する。

スレーブは２つのスレッドを使用して、マスターからの更新を読み取ることと、それらを実行することを独立タスクに分類する。
そのため、ステートメント実行が遅い場合でもステートメントを読み取るタスクが遅くなることはない。

SQL スレッドがかなり遅れている場合でも、全てのバイナリログを起動時にフェッチ出来る。またSQL スレッドがフェッチ済みのステートメントの実行を完了する前にスレーブが停止した場合でも安全なコピーがリレーログとしてスレーブローカルに保存されているため次の起動時に実行を開始することができる。これによってバイナリログは送ってさえしまえばマスターで長時間保持する必要がない。

おわりに

MySQL 8 のドキュメント翻訳みたいになってきた。

*1:イベントがスレーブに送信される前でも

docker-compose を使って MySQL8 の レプリケーションを構築する

MySQL

はじめに

どうも、最近アローを見ていてフラッシュに出てくるアローのキャストと同じで感動してるけんつです。フェリシティいいよね。
ようやくアドカレが終わったので、気分転換にやろうやろうと思っていた MySQL のレプリケーションを docker-compose で構築する方法でもまとめます。

qiita とかみたら実例があるけども、それを見たらあまり勉強にならないのでなるべく MySQL 8 の公式ドキュメントを見ながら構築していく。

今回はいつの間にか降ってきていた MySQL 8.0.18 の docker コンテナを使ってやっていく。

MySQL のレプリケーション

そもそも MySQL におけるレプリケーションとはそもそも何なのかと言うと、Master のデータを１つ以上の Slave にコピーできる機能。
そしてこのレプリケーション機能は、デフォルトで非同期なので Slave は Master からのデータを受け取るために永続的に接続している必要がない。
また構成に応じて全てのデータベース、選択したデータベース、テーブルなどを選択して複製することができる。

レプリケーションを取る利点しては以下の通り。

  • スケールアウト： 複数のスレーブに負荷を分散する。書き込みに関することはマスターで行う必要があるが。読み込みに関してはスレーブを利用させることで負荷を減らす。
  • データセキュリティ: データはスレーブに複製され、スレーブはレプリケーションプロセスを一時停止させることができるためマスターデータを壊すこと無くスレーブでバックアップを実行することができる。
  • 分析; 理由はスケールアウトと似ている。負荷の高い情報の読み取りを行うような分析に関することではマスターの負荷を上げることなくスレーブで実行できる。
  • 長距離データ配布: マスターへの永続的なアクセスを必要とせず、レプリケーションを使用してデータをローカルコピーできる。

レプリケーション形式

MySQL には 3 つのレプリケーション形式が存在する。
ひとつは Statement Based Replication(SBR) と呼ばれるもので、 SQL ステートメント全体を複製する。
もうひとつは Row Based Replication(RBR) と呼ばれるもので、変更があった行だけを複製する。
３つ目として、これら２つを状況に応じてキリ開ける Mixed Based Replication というものがある。

デフォルトでは SBR が有効になる。

目的とする構成

まず、Master 1 台に対して Slave 1 台の構成を目指す。
Slave2 という設定が github レポジトリにはあるがそれは今後 GTID レプリケーションを構成する用の設定なので無視していい

成果物

github.com

Binary Log File Position Based Replication の構築

Master サーバの設定

レプリケーションを構築するためにはマスターでバイナリロギングが有効になっている必要がある。MySQL 8ではデフォルトで有効になっている。MySQL 5.7 以下ではデフォルトで有効にならないため、設定する必要がある。
バイナリログはデフォルトで /var/lib/mysql/ に binlog*** という命名で作成される。これは log_bin_basename で変更可能。
また、server_id という 1~2^32 - 1 の正の整数値で指定するサーバを一意に求めることの出来る ID を設定する必要がある。また、これは設定しない場合はデフォルトで 0 が設定されているがその状態だとマスターはスレーブからの接続を拒否するため必ず設定する必要がある。
それらを踏まえて my.cnf(master.cnf) に以下の設定を追加する。

[mysqld]
...
server_id=1

確認する。

MySQL [(none)]> select @@global.log_bin;
+------------------+
| @@global.log_bin |
+------------------+
|                1 |
+------------------+
1 row in set (0.00 sec)

MySQL [(none)]> select @@global.server_id;
+--------------------+
| @@global.server_id |
+--------------------+
|                  1 |
+--------------------+
1 row in set (0.00 sec)

おっけーっぽい。

Slave の設定

こちらも同様に server_id を設定する必要がある。
レプリケーションを取りたい MySQL サーバ同士で ID が被らないように以下の様に設定を追加する。

slave1.cnf

[mysqld]
...
server_id=2

設定を確認する。

MySQL [(none)]> select @@global.log_bin;
+------------------+
| @@global.log_bin |
+------------------+
|                1 |
+------------------+
1 row in set (0.00 sec)

MySQL [(none)]> select @@global.server_id;
+--------------------+
| @@global.server_id |
+--------------------+
|                  2 |
+--------------------+
1 row in set (0.00 sec)

一応 log_bin の設定値を確認したが Slave でバイナリロギングを有効にする必要は実はない。
有効になっていれば、データバックアップとクラッシュリカバリに Slave のバイナリロギングを利用することができるらしい。

レプリケーションユーザを作成する

必ずレプリケーション専用のユーザを作らないといけないわけではないが、レプリケーションのユーザ名とパスワードは mysql.slave_master_info にプレーンテキストとして保存されるため必要最低限の権限を与えた専用ユーザを作成するべきらしい。
といってもやることはユーザを作成して REPLICATION SLAVE の GRANT を付与するだけ。

以下のシェルスクリプトを slave 用 mysql コンテナの docker-entrypoint-initdb.d 以下にマウントする。
またレプリケーション専用アカウントの情報は適宜 docker-compose yaml に追加する

#!/bin/sh

mysql -u root -v mysql <<SQL
        CREATE USER '${MYSQL_REPLICATION_USER:+repl}'@'%' IDENTIFIED BY '${MYSQL_REPLICATION_PASSWORD:+repl}';
        GRANT REPLICATION SLAVE ON *.* TO '$MYSQL_REPLICATION_USER'@'%';
SQL
余談

MySQL のコンテナを使う場合に、MYSQL_USER 等が設定されていると自動でユーザが作成されるが
MySQL_DATABASE が設定されていない場合は USAGE が、設定されている場合はその Database に対して ALL が GRANT として設定されるらしい。

レプリケーションマスターバイナリログのポジション取得

まず、レプリケーションを構築するにはやることがある。
初回起動時は docker-compose yaml の値をもとにユーザなどが作成されるがバイナリログを有効にしているためこれらのログが存在する。
そのため、master のバイナリログをリセットする必要がある。*1

その前提の元に、データスナップショットを取るために必要な手順を追っていく。

まずはバイナリログのどこからレプリケーションを開始するのが正しいかを判断するためにバイナリログのポジションを取得する。
この際に、更新が走ってしまうとバイナリログの位置が変わってしまうため READ LOCK をかける。

この２つを行うため、さっきのシェルスクリプトに以下の SQL を追加する。

#!/bin/sh

...

mysql -u root -v mysql <<SQL
    RESET MASTER;
    FLUSH TABLES WITH READ LOCK;
SQL

次に SHOW MASTER STATUS を参照してバイナリログファイルとポジションを取得する。
それらの情報は Slave を Master に接続するために必要となる。

#!/bin/sh
...

binlogfile=`mysql -u root -h master -e "SHOW MASTER STATUS\G" | grep File: | awk '{print $2}'`
position=`mysql -u root -h master -e "SHOW MASTER STATUS\G" | grep Position: | awk '{print $2}'`

mysqldump を使って master のスナップショットを作成する

次に、スナップショットを作成する。今回は全てのデータベースを対称にするため以下のようにする。
めんどうなのでついてに master のスナップショットを slave に突っ込む。

#!/bin/sh
...
mysqldump -u root -h master --all-databases --master-data > /tmp/master.sql
mysql -u root < /tmp/master.sql

slave1.cnf

[mysqld]
...
skip-slave-start
    • skip-slave-start が無いと、この mysqldump を実行した段階でスレーブが開始してしまうためスレーブ側で STOP SLAVE を実行する必要がある。

Slave を開始する

CHANGE MASTER TO で、接続先と開始するログファイルにポジションを指定して START SLAVE によって開始する。
そのあとで Master の READ LOCK を取っているからそれをアンロックする。

なぜか skip-slave-start が有効にならなかったので STOP SLAVE をしている

#!/bin/sh
...

mysql -u root -v -e "STOP SLAVE";
mysql -u root -v -e "RESET SLAVE";
mysql -u root -v -e "CHANGE MASTER TO MASTER_HOST='master', MASTER_USER='root', MASTER_PASSWORD='', MASTER_LOG_FILE='${binlogfile}', MASTER_LOG_POS=${position};"
mysql -u root -v -e "START SLAVE;"

mysql -u root -h master -v -e "UNLOCK TABLES;"

動作確認

$ docker-compose exec slave1 mysql -e 'show slave status \G'
...
             Slave_IO_Running: Yes
            Slave_SQL_Running: Yes
...
$ docker-compose exec slave1 mysql -e "select * from sample.hello;"
+----+--------+
| id | lang   |
+----+--------+
|  1 | Golang |
|  2 | SQL    |
|  3 | PHP    |
|  4 | Java   |
|  5 | C      |
+----+--------+
$ docker-compose exec master mysql -e "insert into sample.hello(lang) values ('Scala')"
$ docker-compose exec slave1 mysql -e "select * from sample.hello;"+----+--------+
| id | lang   |
+----+--------+
|  1 | Golang |
|  2 | SQL    |
|  3 | PHP    |
|  4 | Java   |
|  5 | C      |
|  6 | Scala  |
+----+--------+

できてるっぽい。

おわりに

もう少しこのレプリケーション周りのオプションだったり、バイナリログ周りは追っていく必要がありそうだけどとりあえずできた。

*1:MySQL :: MySQL 8.0 Reference Manual :: 13.4.1.2 RESET MASTER Statement https://dev.mysql.com/doc/refman/8.0/en/reset-master.html

アドカレを通して CMU Database Systems をひたすら追ってみて

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 25 日目の記事です。

はじめに


以下の記事に触発されて CMU Database Systems を追っていって途中から DBMS の自作に切り替えてアドカレにしてみて、色々と思うところやどこまでできたのかをまとめられたらいいなと思う。

buildersbox.corp-sansan.com

題材

　
www.youtube.com

なにをやったか

CMU Database Systems を追った

DBMS について体系的に学習するために以下の講義を追った。

  • 01 Relational Data Model
  • 02 Advanced SQL
  • 03,04 Database Storage
  • 05 Buffer Pools
  • 06 Hash Tables
  • 07, 08 Tree Indexes
  • 09 Index Concurrency Control
  • 10 Query Processing
  • 16 Concurrency Control Theory
  • 17 Two-Phase Locking
  • 19 Multi-Version Concurrency Control
  • 20 Logging Schemes
  • 21 Database Recovery

ほとんどが DBMS の中でも DB Storage に関する内容。
ところどころ抜けている部分は JOIN アルゴリズムだったり、内部的にクエリで得た検索結果をソートしたりといった内容で、後半で行った DBMS の実装に含めないことにした部分。

DBMS の実装の一部

Database Storage については実装を進めた。やってくるクエリを直列で捌くぐらいなら問題内程度の実装にはなっている。
そのあたりは 11 ~ 18 日あたりの雑な記事を参照するとわかりそう。

クエリのパーサ何かはこの後書くけど諸事情で断念したので、終盤のトランザクション周りとクエリあたりは実装できていない。

既存の実装を調べた

途中で、実際に MySQL, PostgreSQL ではどのように実装されているのかというところも諸々調べてみた。

rabbitfoot141.hatenablog.com
rabbitfoot141.hatenablog.com
rabbitfoot141.hatenablog.com

ストレージだけ実装した

前述の通り、トランザクションは実装できていないけどひとまずストレージだけは実装した。
構成要素としては以下の通り

  • Catalog
  • Tuple
  • Page
  • Buffer Pool
  • B Tree Index
  • Clock Sweep Cache
  • LRU Cache
  • Disk Manager

Page, Tuple は Protocol Buffer を使わず、 gob も使わず自前で byte 列にシリアライズしている。
Buffer Pool 周りは PostgreSQL 8*1を参考に実装している。
ひとまず、ページに対してタプル*2の追加はできるし、テーブルという単位でそれらを管理することもできる
あとは B Tree では int32 相当の値と string の検索に対応することもできた。

やってみて

辛さ半分、楽しさ半分

辛いところ

最初にあげた記事にもあるようにコンピュータ・サイエンスの基本的な知識が要求されるため、現役学部生といえど情報工学を専攻している身には新しく学ぶことになる前提知識が多くてかなり大変だった。
この一連の流れを通して学習することが、CS の基本知識 + DBMS の理論についてなのでかなり盛りだくさんだったのは言うまでもなく苦労の連続だった。

そして最も厳しかったのは B Tree や Buffer Pool の実装で、これはデータ構造とアルゴリズムの実装が連続するため知識としてもっていても
またそれらを実装できるのは全く別の話なのでかなり時間を食ってしまったし、わかるとできるを結びつけるのを締め切りに迫られながらやるのはかなりメンタルに来るものがある。

楽しかったところ

まず、DBMS に関して体系的に学べたのは新しい発見の連続でこれはかなりワクワクする内容だった。特にストレージ周りは新しく学ぶことばかりで、日々の勉強が楽しかった。このワクワク、なかなか伝わりにくいとは思うが新しく学んだことを試行錯誤しながら実装するのはめちゃくちゃ楽しい。


以前、 Linux Kernel モジュールを書いていたことがあるのだけど講義内で出てくる仮想記憶や mmap などのシステムコールについても解説があり
自分のなかで断片として持っていた知識が「あぁ実際にはこういう実装に使えるのか。それでこの DBMS はこういう実装になっているのか」とつながっていく感覚もさらに実装の幅が広がったのもワクワクの連続だった。


また、既存の DBMS についての実装もかなり追ったので MySQL*3 の binlog, LRU Cache や PostgreSQL の BufferPool に関連する本来ブラックボックスのようになっているものの裏側をきちんと理解することが出来てので当初の目的通り最低限そういった知見が得られたのは非常に良かったと思う。

Golang 力があがった

これは sansan の荒川さんのレポジトリを参考にして作っていたというのが関係している。
github.com

例えば、Slice と Array の使い方だったり、 B Tree のような構造の実装であったりとすごく得るものがあった。
B Tree で Node がもつ Item で Interface を使っていたが、interface の使い方で普段は迷うことが多いのですごく参考になった。

また実装に入った段階で出来るだけ異なるアプローチや仕組みを実装しようと思っていたので、常に試行錯誤の連続も何度も書いて消してを繰り返したので必然的に Golang 力があがった。

あとは Goroutine 周り。あまりヘビーな使い方をしたことがなかったが、ラッチ相当の機能を実装するために sync.RWMutex なんかを多用したため、そのあたりの排他制御に関する知見と実装方法にたいする理解も深まった。

既存の実装への理解が深まった

楽しかったところにもあったが、これもひとつ大きな副次的効果だと思う。めちゃくちゃ調べて

blog.jcole.us
blog.jcole.us

こういった Page の物理的構成に関する記事を見て参考にしたり

http://www.interdb.jp/pg/pgsql08.html

こういったものも参考にしたので、自然と既存の実装について理解がかなり深まった。
MySQL のドキュメントもかなり参照した。

反省点

SQL に対する理解と見通しが甘かった

今回はこれに尽きる。

後々、JOIN やサブクエリ等の実装もしたかったので、再帰降下構文解析でなく goyacc で実装しようとは最初から思っていたのだが
簡単に出来ると思っていて*4、ストレージの実装にかなりの時間を使ったのだが実際やってみると B Tree や Buffer Pool の実装の比にならないほど難航した。
そのため、その後に控えていたトランザクションの実装をする時間がなくなってしまったという事態になってしまった。

めちゃくちゃ見通しが甘かった。

CS の基礎が不足している

これも想像以上に時間がかかった理由になっている。
本来 DBMS の理論の学習に時間を割くべきだが、そこで前提とされている CS に関する基礎知識が不足していたためにところどころで遅れを招いた。
これは普段から、如何にライブラリ何かがいい感じにしてくれるバックグラウンドにあるものを理解できていないかというところが露呈したと思っている。
どうにかそのあたりも勉強しないといけないと痛感した。

終わりに

これでひとまずアドカレは終わりとするが、いい感じのところまで行っているから実装を続けていきたい。
あと、作っていて思ったけどオンメモリ KVS みたいな NoSQL の実装をやってみたくなったり
既存の実装を追っている内に MySQL についてもっと勉強したくなったので、今回学んだことを活かして何かしらデータベース周りを勉強していきたい。

あとこれは必ずやっていきたいが、そういう実装や学習を通して特にトランザクションやロギング、リカバリあたりを簡単にまとめるのではなくしっかり理解して行きたい

それではこれで一人アドカレを終わりにする。

*1:たまたま有志による内部構成のドキュメントが見つかった

*2:いわゆる列というやつ

*3:正確には InnoDB

*4:これが無謀な見通しだった

CMU Database Systems をひたすら追っていく ~21 Database Recovery~

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 24 日目の記事です。

はじめに

今回は実際にリカバリをどのように行うかという話。

Aries

Algorithm for Recovery and Isolation Exploiting Semantics の略で IBM が 1990 年代に研究したもの。
これを完全に採用しているものは少ないが、この手法に類似した方法を取っている。

ARIES の処理手順

  • WAL: ディスクに変更が書き込まれる前に変更をストレージに書き込む。
  • Repeating History during redo: 再起動時にアクションをリトレースし、クラッシュ前の正確な状態に戻す。
  • Logging Changes during undo: UNDO アクションを記録して、処理に失敗した場合はそのアクションを再度繰り返さないようにする。

WAL Records

ログレコード形式を拡張して、追加情報を持つ必要がある。全てのログレコードに LSN*1を追加することで対応する。

  • 各ページには Page LSN が含まれ、最新の更新を示す。
  • またフラッシュされた最大の LSN も持つ
  • ディスクに書き込まれる前に、 page LSN <= flushed LSN となるようにログをフラッシュする

Normal Execution

Transaction Commits

  • COMMIT レコードをログに追加する。
  • トランザクションの COMMIT レコードへの全てのログはディスクにフラッシュされる。
  • コミットに成功すると TXN-END レコードを書き込む。これは内部でのみ使用されるためすぐにフラッシュする必要がない。

Transaction Abort

Compensation Log Record

  • CLR という更新レコードのアクションを取り消すためのアクションを記述する
  • 次に取り消される LSN も undo Next ポインタとして持っておく

アルゴリズム

  • ABORTレコードを書き込む
  • 更新を逆順い再生して、変更を削除する。更新毎に CLR エントリを書き込み以前の値を復元する
  • 最後に TXN-END ログレコードを書き込む

ARIES Recovery

ARIES は 3 つのフェーズで構成されている。
クラッシュ後は起動時にそのフェーズを逐次実行していく。

  • Analysis: WAL を読んでバッファプール内のダーティページとクラッシュ時のアクティブなトランザクションを確認する
  • Redo: ログ内の適切なポイントから始める全てのアクションを繰り返す
  • Undo: クラッシュする前にコミットしなかったトランザクションのアクションを元に戻す

おわりに

簡単にまとめたけど、これを一つずつちゃんとまとめないと理解できない気がしてきた

*1:ログシーケンス番号

CMU Database Systems をひたすら追っていく ~20 Logging Schemes~

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 23 日目の記事です。

はじめに

今日はログ周りの話。
WAL とか、ACID の原子性、耐久性、一貫性などを担保するための重要な要素。

Logging Schemes

リカバリアルゴリズムはデータベースに置いて一貫性、原子性、耐久性を確保する上で需要な要素となっている。
このリカバリアルゴリズムで行う大きく分けて２つにわかれる。

  • DBMS が障害から回復するために通常のトランザクション処理中に行うアクション
  • データベースの原子性、一貫性、耐久性を保証する状態に回復できなかった場合のアクション

またここのでキーワードとして以下の２つがある。

Failure Classification

DBMS で起こる障害は大きくわけて 3 つに分類できる。

Transaction Failures
System Failure
  • Software Failure: DBMS のソフトウェア的な問題でシステムを終了する必要がある場合
  • Hardware Failure: DBMS をホストしているマシンがクラッシュするなど
Storage Media Failure:
  • Non-Repairable Hardware Failure: ディスク障害、不揮発性ストレージの一部がクラッシュする。これから回復するにはアーカイブバージョンから復元するしかない。

Buffer Pool Management Policies

バッファプールを管理するポリシーの２つを紹介する。

例えば、No-Steal + Force で実装するなら。
変更がディスクに書き込まれなかった場合は、中止されたトランザクションによる変更を元に戻す必要はない。
また、コミット時に全ての変更がディスクに書き込まれることが保証されているため変更をやり直す必要はない。
ただし、トランザクションが変更する必要のある全てのデータがメモリに収まらない場合、トランザクションがコミットする前のダーティページをディスクに書き込まないため、そのトランザクションを実行できないという制限がある。

Steal Policy

DBMS がコミットされていないトランザクションが不揮発性ストレージ内のオブジェクトに対して最新のコミットを上書きするかどうか

  • Steal: 許可する
  • No-Streal: 許可しない
Force Policy

トランザクションがコミットされる前に DBMS がトランザクションによって行われた全ての更新がストレージに反映されることを保証するかどうか。

  • Force: 保証される
  • No-Force: 保証されない

Write-Ahead Logging

ディスクページに変更が加えられる前にデータベースに加えられた全ての変更のログをログファイルに記録する手法。
殆どの DBMS で使用されているが、リカバリするためにはログを追う必要があるので処理に時間が掛かる。
ログはDBを復旧するための UNDO, REDO に必要な全ての情報を持っている。
Steal + No-Force システムを例に解説する。

Implementation

更新されたページの関連する全てのログレコードはページ自体がストレージに書きこまれるよりも前に永続化される。

Deferred Updates

  • トランザクションがコミットされるまで DBMS がダーティレコードをディスクに書き込むのを防ぐ場合、変更前の値を保持する必要はない。
  • トランザクションのメモリ使用量が DBMS 側の使用可能なメモリ量より大きい場合は機能しない。
  • ログに元の値がない場合は UNDO することができない(Steal ポリシーはこのために使用する)

Checkpoint

WAL の大きな問題としログファイルが肥大化するという問題がある。
クラッシュ時にこのログファイルが肥大化していると、ログを追ってリカバリする処理に時間がかかることがある。
そのため、チェックポイントを設け定期的にバッファの持つ情報をディスクにフラッシュする必要がある。

チェックポイントはどの程度設けるのが良いという基準はなく、チェックポイントが多すぎるとパフォーマンスが低下し、少なすぎるとその意味が薄れてしまう。
そのため、DBMS が担う役割や要求パフォーマンスに左右される。

Blocking Checkpoint の実装
  • 新たなトランザクションの生成を止め、アクティブなトランザクションが全て完了するのを待つ
  • メモリに存在するログレコードとダーティブロックをストレージにフラッシュする。
  • ログにチェックポイントエントリを書き込みストレージにフラッシュする。

おわりに

次はリカバリについて