2022-03-04

DBMSを作りました

セキュリティキャンプ2021のY-IIトラックに参加して簡単なDBMSを0から作りました。

概要

DataBase Management System略してDBMSです。

Key-value store (KeyとValueはどちらもC++のstd::stringのみ)
select, insert, update, deleteができる。
S2PL(Strict two phase lock)でTransactionの並行実行制御ができる。

のようなDBMSを作りました。またB-treeを実装する時に可変長のデータに対応するのが難しかったのでKeyとValueは長さが400-8=392以下のみしか対応していません。

リポジトリはこちら

github.com

実装したこと

Write ahead logging
Crash recovery
Buffer manager
Disk manager
B-tree
S2PLとC++20 co_routineを用いた並行実行制御(Single threadで)
Deadlock preventionのためのWait-dieアルゴリズム

当初の自分の目標はIn-memoryではないファイル上のB-treeを実装することとC++20のco_routineを用いた並行実行制御でした。それらが動くところまで実装することができました。

ちなみに https://github.com/kappybar/mydb/blob/main/examples/example1.cpp こんな感じで動きます。

my_task transaction1(Table *table) {
    Transaction txn(&table);
    co_yield txn.begin();
    std::optional<std::string> value = co_await txn.select("key");
    co_yield txn.commit();
    co_return;
}

上のようなTransactionがあったときにco_yield,co_awaitのところで実行が中断されて、他のTransactionに処理が移ります。こうすることでSingle threadで並行実行制御を試すことができます。

全体の構成

f:id:kapibara100:20211003152915p:plain Data operation(select, insert, update, delete)は最初にWrite-setに入れられます。 Transactionのすべての操作が終わって、Commitすると、Logを書いた後に、B-treeに反映されます。そしてプログラムが終了する前にCheckpointingをして、B-treeの内容をData-fileに書き込みます。Data fileはただKeyとValueが並んだだけのファイルです。

B-tree

ファイル上のB-treeを実装しました。

B-treeひとつのノードを4Kibのページとして実装しています。In-memoryではないインデクスを作ろうと思うとメモリとファイルの間でpageをやり取りする必要があるので、メモリ上のレイアウトとファイル上のレイアウトを共通化する必要があります。

このレイアウトの方法はSlotted pageなどの効率の良い方法が存在しているのですが、自分はそれをするのが面倒だったのでKeyとValueに使われている文字列の長さに制限をつけて、ただそれらを並べただけのレイアウトにしました。ちなみに文字列の長さを制限することによってKeyやValueが複数のページにまたがることも防げて、実装が簡単になります。

またメモリ上のページがいっぱいになってしまった時に、どのページを退避するか選択するページ置換アルゴリズムを考える必要があります。 OSの仮想メモリのページ置換アルゴリズムと同じようによくアクセスするページをメモリ上に残しておくと効率が良くなります。自分は実装が簡単そうだったので、Clockアルゴリズムを採用しました。 Clockアルゴリズムは時計の針のようにページを見ながら、Access bitがたっていないページがあればそのページを置換対象にするアルゴリズムです。

並行実行制御

S2PLを実装しました。必要になるたびにLockを獲得していき、一度獲得したLockを解放することなく、最後にcommitした後にすべてのLockを解放します。こうしてできた操作の列はConflict serializabilityを満たしていて、直列に実行したTransactionと、ある意味で等価な操作列と見なすことができます。

なお単純にS2PLを実装すると簡単にDeadlockが起きるのでDeadlock preventionなりDeadlock detectionのアルゴリズムを何か考える必要があります。自分はDeadlock preventionのアルゴリズムを実装しました。No-waitというWaitしたらそのTransactionをAbortするアルゴリズムが一番簡単そうだったのですが、つまらなそうだったのでWait-dieというアルゴリズムを実装しました。

Wait-dieはそれぞれトランザクションに優先度を割り振っておいて、Waitできるのは優先度が高いトランザクションが優先度の低いトランザクションの持っているLockを要求した場合のみで、そうでない場合はAbortするというアルゴリズムです。こうすることで循環したWaitが発生しないのでDeadlockに陥ることはありません。

f:id:kapibara100:20211003154357p:plain:w300

Coroutine

並行実行制御といいつつSingle threadで動かしているので、同時に複数のTransactionが動いているわけではありません。 C++20のco_routineを用いて、Transactionの操作をインターリーブして実行できるようにしています。C++20のco_routineはライブラリ実装者向けの低レベルな機能しかないため、もし使いたければ自分でco_routineを使えるようにランタイムライブラリをつくるか、boostやcppcoroなどのすでに実装されているライブラリなどを使うかどちらかになります。

f:id:kapibara100:20211004211702p:plain:w500

自分はco_routineの勉強も兼ねて自分でランタイムライブラリ(もどき)を実装しました。リポジトリのdb.hppのmy_task構造体がそれにあたります。たいしたことはできていないですが、co_routineの動くコードがあまりネット上に落ちていなくて、動くまでにちょっと苦労しました。一番詳しく書かれていたのはコルーチン - cpprefjp C++日本語リファレンスです。(当たり前ですが)説明が形式的な感じで自分はちょっと分かりづらかったです。でも参考になるコードがここに載っているのでそれらをいじって、どういうふうに動いているのか理解しました。

改善点

B-treeのコードを書いていて、とても複雑になってしまった。特に他の人にソースコードを見せたりするつもりもなかったので、自分一人で書いていて、コードが汚くなりがちだった。
B-treeの真面目な永続化をサボってしまったので、データベースの実行に必要なファイルがB-tree, Data, Logの3種類になってしまって、奇妙なアーキテクチャになってしまった。
co_routineのライブラリを作ったとは言ったもののたいしたことはできていない。Waitとかもco_routineのライブラリの方で処理できるといいかなと思いました。

感想

授業とかでもともとの雛形があるところから、なにか機能を追加したことはありましたが、自分で0から設計を考えて、ソフトウェアをつくっていくのは初めてだったので新鮮でした。自分はC++で競技プログラミングしかやってこなかったけれど、競プロで培われた、コーナーケースを考える力というかすべてのケースを考える力みたいなのがバグのないソフトウェアの開発にも通ずるところがすこしはあるなあと思いました。 B-treeとかは競プロやってなかったらもっとバグらせたと思います。

今回簡単なDBMSを実装してみて、既存のDBMSとかに尊敬の感情しか湧きませんでした。なんだかんだDBMS作るの楽しかったです。いろいろと時間を割いてくださったりアドバイスをくださった講師、チューターの方、ありがとうございました。

2021-09-24

添字and,or畳み込み

概要

添字andとorの畳み込みの計算方法について勉強したことを書きます。勉強したことと書いてある通り、自分自身が勉強したばかりなので誤り等あるかもしれません。

仕組み

まず畳み込みの定義をします。

数列 $a,b$ が与えられた時に

$\displaystyle c_k = \sum_{ i\ and\ j\ =\ k} a_i * b_j$

$\displaystyle d_k = \sum_{ i\ or\ j\ =\ k} a_i * b_j$

で定義される数列 $c,d$ がそれぞれ、添字andと添字orの畳み込みです。添字に関してandとorで畳み込んでいますね。まずandの畳み込みについて考えます。andの畳み込みができてしまえば、orの畳み込みもほぼ同じ方法でできます。この計算をするために次のような数列の変換 $f$ を考えます。

$\displaystyle f(x)_k = \sum_{i\ or\ k\ =\ i} x_i$

このとき数列の変換 $f$ を行うことによって、

$\displaystyle f(c)_k = f(a)_k * f(b)_k \tag{1}$

となります。つまりもともと畳み込みの計算だったものが各点積という簡単な計算に変化しています。

(1)の証明のようなもの

$\begin{eqnarray} f(a)_k * f(b)_k &=& \sum_{i\ or\ k\ =\ i} a_i * \sum_{j\ or\ k\ =\ j} b_j \\ &=& \sum_{i\ or\ k\ =\ i}\ \sum_{j\ or\ k\ =\ j} a_i * b_j \\ &=& \sum_{s\ or\ k\ =\ s}\ \sum_{i\ and\ j\ =\ s} a_i * b_j \\ &=& \sum_{s\ or\ k\ =\ s} c_s \\ &=& f(c)_k \\ \end{eqnarray}$

2行目から3行目が一番わかりづらいです。 $i\ or\ k\ =\ i,j\ or\ k\ =\ j$ から $i,j$ は $k$ を完全に含んでいるので、 $i\ and\ j\ =\ s$ も $k$ を完全に含んでいるので、えいっとシグマの取り方を変えられます。

fの逆変換

ところでこの計算で求めることができたのは、求めたかった $c$ ではなく $f(c)$ です。もし $f$ の逆変換のようなものがあれば $f(c)$ から $c$ を得ることができます。実はそのような変換は存在します！！

次の変換 $g$ は $f$ の逆変換になっています。

$\displaystyle g(x)_k = \sum_{i\ or\ k\ =\ i} (-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)} x_i$

popcount(i)はiの立っているビットの数を表しています。つまりiを立っているビットが表す集合とみたときの集合の要素と等しいです。ちなみに先程の $f$ と異なる部分は-1の累乗をかけている部分だけです。

gとfが互いに逆変換であることの証明のようなもの

$g(f(x)) = x, f(g(x)) = x$ を示せばいいはず。

$\begin{eqnarray} g(f(x))_k &=& \sum_{i\ or\ k\ =\ i} (-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)} f(x)_i \\ &=& \sum_{i\ or\ k\ =\ i} (-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)} \sum_{j\ or\ i\ =\ j} x_j \\ &=& \sum_{i\ or\ k\ =\ i} \sum_{j\ or\ i\ =\ j} (-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)} x_j \\ \end{eqnarray}$

二つのシグマの条件式をみると $k,i,j$ はビットの集合の包含関係として $k \subseteq i \subseteq j$ となっていることがわかります。

[1] $j = k$ のとき

$i = k$ しかないから $x_k$ の係数は $(-1)^{\mathrm{popcount}(k)-\mathrm{popcount}(k)} = 1$ です。

[2] $j \supset k$ のとき

$k \subseteq i \subseteq j$ である $i$ について $(-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)}$ の総和をとったものが $x_j$ の係数になります。これは包除原理でよくあるやつで、 $m = \mathrm{popcount}(j)-\mathrm{popcount}(k)$ とすると、

$\begin{eqnarray} \sum_{l=0}^m (-1) ^ l\ _m C_l = \sum_{l=0}^m (1)^{m-l} (-1)^l\ _m C_l = (1-1)^m = 0\ (m > 0) \end{eqnarray}$

が成り立つので $x_j$ の係数は $0$ になります。

よって $g(f(x))_k = x_k$ が成り立つことが示せました。これの逆 $f(g(x))_k = x_k$ も同じ感じで示せます。

添字and畳み込み　

まとめると次の計算をするとandの畳み込みが計算できます。

数列 $a,b$ に変換 $f$ をかける。
それらの数列の各点積を取る。
できた数列に $f$ の逆変換 $g$ をかける。

ちなみにこの $f,g$ には名前がついています。 $f$ をゼータ変換、 $g$ をメビウス変換といいます。ちなみにゼータ変換には上位集合と下位集合のゼータ変換があって、この変換は上位集合のゼータ変換です。メビウス変換も同様でこれは上位集合のメビウス変換です。

下のようなゼータ変換やメビウス変換をよく見ると思うんですが、

$\begin{eqnarray} f(S) = \sum_{T \supseteq S} f(T) \end{eqnarray}$

$\begin{eqnarray} f(S) = \sum_{T \supseteq S} (-1) ^ {|T| - |S|}f(T) \end{eqnarray}$

これは最初に紹介した変換のゼータ変換の添字をビットが表す集合と思うと同じになります。

添字or畳み込み

ここまでandの畳み込みしか書いてきていませんがorの畳み込みも同様にできます。じつは先程の上位集合のゼータ変換、メビウス変換を下位集合ののゼータ変換、メビウス変換に変えるとorの畳み込みになります。下位集合のゼータ変換、メビウス変換は次のような式で表されます。

$\displaystyle f(x)_k = \sum_{i\ or\ k\ =\ k} x_i$

$\displaystyle g(x)_k = \sum_{i\ or\ k\ =\ k} (-1)^{\mathrm{popcount}(k)-\mathrm{popcount}(i)} x_i$

証明もほぼ同じ感じでできると思います。一応集合の形でも書いておきます。

$\begin{eqnarray} f(S) = \sum_{T \subseteq S} f(T) \end{eqnarray}$

$\begin{eqnarray} f(S) = \sum_{T \subseteq S} (-1) ^ {|S| - |T|}f(T) \end{eqnarray}$

高速ゼータ変換、メビウス変換

ゼータ変換やメビウス変換を愚直にやると数列の長さをNとして $\mathcal{O} (N ^ 2)$ かかります。これを $\mathcal{O}(Nlog(N))$ で行うのが高速ゼータ変換、メビウス変換です。高速ゼータ変換、メビウス変換ができればandとorの畳み込みは $\mathcal{O}(Nlog(N))$ で計算することができます。説明は省略しますが、下のようなコードで実現できます。bitdpのようなことをやっているらしい。それぞれのbitについて累積和をしているといってもいいかも。配列の長さは2の冪乗にしておくといいと思います。

コード

間違っている可能性があります。

上位集合のゼータ変換

void zeta_sup(vector<int> &f) {
    int n = (int)f.size();
    for (int i = 1;i < n;i <<= 1) {
        for (int j = 0;j < n; j++) {
            if (!(j&i)) f[j] += f[j|i];
        }
    }
}

上位集合のメビウス変換

void mebius_sup(vector<int> &f) {
    int n = (int)f.size();
    for (int i = 1;i < n;i <<= 1) {
        for (int j = 0;j < n; j++) {
            if (!(j&i)) f[j] -= f[j|i];
        }
    }
}

下位集合のゼータ変換

void zeta_sub(vector<int> &f) {
    int n = (int)f.size();
    for (int i = 1;i < n;i <<= 1) {
        for (int j = 0;j < n; j++) {
            if (j&i) f[j] += f[j^i];
        }
    }
}

下位集合のメビウス変換

void mebius_sub(vector<int> &f) {
    int n = (int)f.size();
    for (int i = 1;i < n;i <<= 1) {
        for (int j = 0;j < n; j++) {
            if (j&i) f[j] -= f[j^i];
        }
    }
}

andの畳み込み

vector<int> and_convolution(vector<int> a,vector<int> b) {
    assert(a.size() == b.size());
    zeta_sup(a);
    zeta_sup(b);
    int n = (int)a.size();
    for(int i = 0;i < n; i++) a[i] *= b[i];
    mebius_sup(a);
    return a;
}

orの畳み込み

vector<int> or_convolution(vector<int> a,vector<int> b) {
    assert(a.size() == b.size());
    zeta_sub(a);
    zeta_sub(b);
    int n = (int)a.size();
    for(int i = 0;i < n; i++) a[i] *= b[i];
    mebius_sub(a);
    return a;
}

参考

https://misteer.hatenablog.com/entry/zeta-moebius

https://kazuma8128.hatenablog.com/entry/2018/05/31/144519