普段あまりこういう誰の役に立つのか分からない記事は書かないのですが、解析をするまでの背景がOSSに関するとても良い話なので重い腰を上げて書きました。

概要

古のアプリケーション組み込み型のデータベースとしてBerkeley DBがあります。元々はカリフォルニア大学バークレー校によって開発され、その後Oracleによって買収されています。データ操作にSQLは使えず、アプリケーションに埋め込んで使用します。RDBまでは必要ないけどちょっとしたDBが必要みたいな時に使われているようです。機能はシンプルで組み込みのため性能も良いとのこと。詳しくは以下に書いてます。

docs.oracle.com

本記事ではそのBerkeley DBの中身がどのように実装されているのかの雰囲気を記します。Berkeley DBはBtree accessやHash access, Queue/Recno accessなどがサポートされていますが、今回はその中でもHash accessの場合にDBがどのようにデータを保存しているのかを説明しています。恐らくこの内容を知りたい人は日本に数人しかいないと思いますが、自分がすぐ忘れそうなのでメモとして残します。Berkeley DBのライブラリをRustに移植したい！という人がいたら役に立つかもしれません。

Hash accessの中でも必要な処理しか説明していません。ただ、大枠が理解できれば細かいところはBerkeley DBのソースコード読めば理解できるので、まず最初に雰囲気を掴むためには適した内容だと思います。

ソースコードは以下にあります。

github.com

あと上にも書いたように実装はシンプルですし似たような構造になっているDBは多いので、Berkeley DBを触ることが一生なくても知っておくと何か役立つかもしれません。

背景

ただの背景なので読み飛ばして実装に行って良いですが、良い話なので暇なら見てみて下さい。

Red Hat系のOSには /var/lib/rpm/Packages というファイルが存在し、この中にインストールされたRPMパッケージの情報などが保存されています。rpm コマンドや dnf, yum はこのファイルからデータを読み出して表示しているわけですが、このファイルはBerkeley DBになっています。libdb を使えば普通に読み出せるのですが、自分の用途ではGoからこのファイルを読み出す必要がありました。libdb はCで実装されていてGoから使うためには cgo が必要になります。実際ライブラリを見つけたのですがやはり cgo を使っていました。そもそもメンテナンスされていなくてアーカイブされています。

github.com

仕方ないのでforkしていくつか機能を足して使っていたのですが、やはり cgo がネックになりました。色んな環境で動くバイナリを提供したかったのですがcgoのせいでそれが困難になりました。一応頑張ってクロスコンパイル環境を用意したりしたのですが、これを今後メンテナンスすることを考えると負荷が高すぎるなと思ってやめました。

github.com

さらにもう一つ問題がありました。試しに cgo を使って上の /var/lib/rpm/Packages からデータを読みだしたところ、その中の値も何とバイナリになっていました。独自の形式でシリアライズされているという感じです。他のディストリビューションが分かりやすい形式で保存しているのに比べてBerkeley DBを使い、さらにその上に独自フォーマットということでさすがRed Hatだなと思ったりはしたのですが、気合でrpmをリバース・エンジニアリングしました（この話もいつか書くかもしれません）。調べた限りではドキュメントも見つからなかったですし、ソースコードを読んだ方が早いし確実だなということで。

github.com

そしてGoに移植して必要な情報が取り出せるようなライブラリを実装しました。

github.com

さて次はBerkeley DBを倒すぞ〜と意気込んだのですが、本来自分が作りたかったソフトウェアから大分遠のいていることに気づきました。このヤクの毛刈りこそがプログラミングの楽しいところだとは思いつつも、GWの10日間で元々のソフトウェアを完成させたかったのでBerkeley DBのGo移植は一旦断念しました。そして悔し涙を流しながらrpmのOSコマンドを呼び出すように実装しました。Go移植は次の長期休暇に絶対やることとして掲げていたのですが、その直後にイスラエルに引っ越して長期休暇がないまま1.5年が経過しました。イスラエルの祝日はユダヤ暦ベースなので今年はグレゴリオ暦の週末とぶつかってほとんど消滅しました。

ということでずっとしこりとして残っていたのですが、先日Anchoreというセキュリティ企業（自分の務めている企業の競合企業）がSyftとGrypeというOSSをリリースしました。

www.opensourceforu.com

このOSSは自分が開発したものと似ているのですが、Red HatのRPM実装がどうなっているのか気になりました。そして Syft の中で自分の go-rpmdb をforkしたものを使っていることがわかりました。そのコミットを見ると何とCバインディングを排除することに成功していました！どうやらBerkeley DBのGo移植に成功したようです。おいおいそんな凄いことやったならPRくれよ〜〜〜と思ったのですが、普通に送ってくれていました。

github.com

何かGitHubのWatchingが勝手に外れて通知来ないことがあるんですが自分だけでしょうか...。最近通知に気づけなくて放置になってしまっていることが多くて大変申し訳無い気持ちです。何はともあれせっかくBerkeley DBのGo移植をしてくれたので自分も送ってもらったPRを読みつつlibdbのコードを読みました。その中で得た知識を速攻忘れそうだったので今回まとめておこう、という背景です。

それにしてもこれだけの機能を外部の人、それどころかバリバリの競合企業の社員が実装してPRを送ってくれるなんてOSSは本当に素晴らしいなと思いました。恐らく彼もrpmの解析が面倒で困っていたら既に自分が解析してGo移植済みだったので、それならということで残タスクのBerkeley DB対応をしてくれたのだと思います。助け合いの精神ですね。PRに気づいた時に喜びのあまりドッグランで「う、うおおぉぉぉ！！！」と大声を出してしまいました。イスラエルでは路上で歌ったりしている人も多いのでちょっと大声を出しても変人扱いはされません。

ちなみに実装してくれた人はdiveという有名なツールの開発者です。もしかしたら知らない人もいるかも知れないので宣伝しておきます。GitHubのスター数が23kで化け物ですね。

github.com

彼は最近Anchoreに入社したようです。入社してからSyftやGrype作ったりBerkeley DB移植したりと大活躍です。AnchoreはあまりOSSに力を入れてこなかったので今まで意識していなかったのですが、彼の入社によって今後は脅威となりそうです。

ちなみにGrypeもバージョン比較のためにClair同様自分のライブラリを使っています。

実装

背景で話した感動が一番伝えたかったことなので長くなりましたが、実装の説明に入ります。上にも書きましたがHashのみの話ですし、その中でもTypeがたくさんあるのですが実装に必要なところしか説明しません。

何かドキュメントを読み解いたわけではなくソースコードを読んで解析しただけなので嘘を言っている可能性もあると思いながら見ていただければと思います。

全体

まずDB全体はPage単位で区切られています。それぞれのPageの先頭にはPageのTypeを識別したりするためのHeaderが入っています。

0       PageSize                       LastPageNo * PageSize
+----------+----------+----------+----------------+
|   Page   |          |          |     ......     |
+----------+----------+----------+----------------+

このPageSizeは可変な値で後述するGeneric Metadataの中に含まれています。値は512, 1024, 2048, ... 65536が許されています。512が最小なのは各Access methodのMetadataの最小サイズが512だからです（後で説明します）。そして同様にLastPageNoもMetadata内に含まれており、LastPageNo * PageSizeがDB全体のサイズとなります。

Metadata

上で説明した各PageのHeaderとは別にDBの一番最初にはMetadataが含まれています。こちらは72バイトで固定になっており、ソースコード上で _dbmeta33 として定義されています。Generic Metadataと呼ばれています。

typedef struct _dbmeta33 {
    DB_LSN    lsn;      /* 00-07: LSN. */
    db_pgno_t pgno;     /* 08-11: Current page number. */
    u_int32_t magic;   /* 12-15: Magic number. */
    u_int32_t version; /* 16-19: Version. */
    u_int32_t pagesize;    /* 20-23: Pagesize. */
    u_int8_t  encrypt_alg; /*    24: Encryption algorithm. */
    u_int8_t  type;        /*    25: Page type. */
    ...

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

一番最初のPageに入っているので以下のようになります。

0                 72            PageSize
+------------------+---------------+
| Generic Metadata |               |
+------------------+---------------+

Generic Metadata

Generic Metadataのレイアウトは以下のようになっています。

0       12      16      20       24           25         26  32       36                  72
+--------+-------+-------+--------+------------+----------+---+--------+-------------------+
|        | Magic |       |  Page  | Encryption | PageType |   |  Last  |      .......      |
|        |       |       |  Size  | Algorithm  |          |   | PageNo |                   |
+--------+-------+-------+--------+------------+----------+---+--------+-------------------+

既にお気づきだと思いますが、上の図は雰囲気理解するために書いているので長さとかは適当です。文字数の関係で1バイトのほうが4バイトより長かったりまちまちです。あまり図を信じ過ぎないで下さい。

ここにあるMagicがMagic numberで、最初にDBのAccess methodをを判断するために使われています。Hashの場合は 0x061561 になっています。

#define DB_HASHMAGIC    0x061561

libdb/db.in at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

ところでなぜこのような大きい値が使われているのかよく分かっていません。0,1,2,...などだとDB破損時に隣接したAccess methodと誤って判別されてしまうからなのでしょうか。こういう細かいテクニックは地味ですが重要だと思うので知っている人がいたら教えてほしいです。

Access methodは全部で5種類あるようです。UNKNOWNを入れると6種類。

/*******************************************************
 * Access methods.
 *******************************************************/
/*
 * Any new methods need to retain the original numbering.  The type
 * is written in a log record so must be maintained.
 */
typedef enum {
    DB_BTREE=1,
    DB_HASH=2,
    DB_HEAP=6,
    DB_RECNO=3,
    DB_QUEUE=4,
    DB_UNKNOWN=5           /* Figure it out on open. */
} DBTYPE;

libdb/db.in at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

他にもPageTypeなどが含まれているため、ここでHash metadata pageであること（=P_HASHMETA）を確認したりする必要もあります。

#define P_HASHMETA  8  /* Hash metadata page. */

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

Encryption Algorithmもあることから暗号化にも対応していることが分かります。RPM DBでは暗号化されていない想定なので、この値が0（つまり暗号化されていない）であることを確かめる必要があります。

NextPageNoは後々出てきます。

そして最初の説明に出てきたPageSizeやLastPageNoもここに含まれています。最初の72バイトをパースすることでDBの全体像を最初に掴めるということです。

Magicの話に戻りますが、Access methodごとにMetadataの構造体が用意されており、B-Tree用、Hash用、Heap用、などなど複数存在するのですが、全て先頭72バイトは上のGeneric Metadataになっており73バイト目以降が各method固有の値になります。Hashの場合は以下に _hashmeta33 として定義されています。コメント内にもMinimum page size is 512 と書いてあり最初に述べたように512バイトになっているのが分かると思います。

/************************************************************************
 HASH METADATA PAGE LAYOUT
 ************************************************************************/
typedef struct _hashmeta33 {
    ...

    /*
    * Minimum page size is 512.
    */
} HMETA33, HMETA;

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

Hash Metadataの場合は以下のようになります。先頭の72バイトは共通で、そこから512バイトまで固有のMetadataになっています。

0                 72                       512
+------------------+------------------------+
| Generic Metadata |    Hash Metadata   ... |
+------------------+------------------------+

B-TreeなどのMetadataも全て512バイトになっています。

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

Hash Metadata

最初に説明したようにDBは全てPageで区切られているためHash MetadataであってもPageに含まれています。単に先頭512バイトにHash Metadataがあるということです。

0              512              PageSize
+---------------+------------------+
| Hash Metadata |    ......        |
+---------------+------------------+

Hash Metadataの中身は大きいので割愛します。上のソースコードに書いてある通りです。

Page

最初に述べたように、各PageにはHeaderが含まれています。このHeaderは26バイトなのですが、26バイト目にTypeが含まれています。上のGeneric Metadataの26バイト目もTypeにしてあるなど、1ページ目を特別扱いせずにTypeが判別できるように配置がある程度共通化されています。

0       26                     PageSize
+--------+-------------------------+
| Header |                         |
+--------+-------------------------+

PageのHeaderレイアウトは_db_pageとして定義されています。

typedef struct _db_page {
    DB_LSN    lsn;      /* 00-07: Log sequence number. */
    db_pgno_t pgno;     /* 08-11: Current page number. */
    db_pgno_t prev_pgno;    /* 12-15: Previous page number. */
    db_pgno_t next_pgno;    /* 16-19: Next page number. */
    db_indx_t entries;  /* 20-21: Number of items on the page. */
    db_indx_t hf_offset;    /* 22-23: High free byte page offset. */
    ...
    u_int8_t  level;   /*    24: Btree tree level. */
    u_int8_t  type;        /*    25: Page type. */
} PAGE;

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

PageTypeが13の場合はHash pageになります。

#define P_HASH      13 /* Sorted hash page. */

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

上の定数定義を見ると他にもPageTypeが複数あることが分かりますが、今回はHashがターゲットなのでHash Pageを見ていきます。他のAccess methodに対応したい場合はそれに応じたstructを追っていけば良いです。

ややこしいですが他にもHash Pageという概念が出てくるので、ここではHash Main Pageと呼びます。

Hash Main Page

とは言ってもHeaderのレイアウトは共通で、以下のようになっています。先述したとおり、26バイト目がPageTypeになっています。

       10           20           22                25         26
+-------+------------+------------+-----------------+----------+
|       | NextPageNo | NumEntries |      ...        | PageType |
+-------+------------+------------+-----------------+----------+

NumEntriesはこのページ内に含まれているアイテム数です。Hashなのでkey/valueのペア数になります。このkey/valueはHeader直後などに保存されているわけではなく、基本的にはポインタを辿ってアクセスします。ただややこしいのですが、データサイズが大きい場合はkey/valueの指す先がHashOffPageという形式でさらに別のPageにデータを格納している場合もあります。ポインタのポインタみたいなやつです。

ソースコード上にHash Pageのレイアウトが書いてあったので一応そちらも載せておきます。

/************************************************************************
 BTREE/HASH MAIN PAGE LAYOUT
 ************************************************************************/

+-----------------------------------+
|    lsn    |   pgno    | prev pgno |
+-----------------------------------+
| next pgno |  entries  | hf offset |
+-----------------------------------+
|   level   |   type    |   chksum  |
+-----------------------------------+
|    iv     |   index   | free -->  |
+-----------+-----------------------+
|    F R E E A R E A            |
+-----------------------------------+
|              <-- free |   item    |
+-----------------------------------+
|   item    |   item    |   item    |
+-----------------------------------+

これを見るとlsnやpgnoが同じサイズのように表現されていますがそれぞれ8バイトと4バイトですし、自分の図以上に長さ適当な気がします。

コメントには以下のようにあります。

sizeof(PAGE) == 26 bytes + possibly 20 bytes of checksum and possibly

16 bytes of IV (+ 2 bytes for alignment), and the following indices

are guaranteed to be two-byte aligned. If we aren't doing crypto or

checksumming the bytes are reclaimed for data storage.

key/valueへのポインタが入っているといいましたが、ここではindexと呼ばれています。そしてindexは現在のPage内でのオフセットを指しています。なのでポインタとは異なりますが、一旦ジャンプする必要があるということでポインタとして説明しています。

26バイトのHeaderのあとにchksumとivが入り、アラインメントのために2バイトが入ってそのあとにindicesが入るようです。ただし暗号化されていない場合はこれらchksumやivは含まれないと思います。ちゃんとソースコード上で見つけてないのですが、中身のバイナリを見る限りでは詰めて値が保存されていました。英語でもpossiblyと言っているので恐らくあってると思うのですが若干自信なしです。

ということで26バイトのMetadataのあとにNumEntries分のkey/valueペアのindexが保存されていることになります。keyとvalueのindexはともに2バイトなので、1ペアにつき4バイトです。つまり、26バイトから26+4*NumEntriesバイトのところまでパースし、2バイトずつ解釈すればkey/valueのindexが得られます。

          26    26+4*NumEntries       PageSize
+----------+---------+-------------------+
| Metadata | Indices |                   |
+----------+---------+-------------------+

上の説明で既にわかったかと思いますが、一応key/valueのレイアウトも載せておきます。

              2             4            6              8          4*NumEntries
+-------------+-------------+-------------+-------------+----------------+
|  Key Index  | Value Index |  Key Index  | Value Index |      ...       |
+-------------+-------------+-------------+-------------+----------------+

このindexは現在のPageの後ろの方に含まれるHash Pageへのポインタとなっています。ソースコードを読む感じだとこのPage全体のことをHash Main Pageと呼び、このPageの中に入っている小さいPageのことをHash Pageと呼んでいそうです。両方Pageと書いてあったので最初かなり混乱しました。つまり以下のような図になります。IndexとIndex2の間は連続しているかはわからないです。

          26   26+2*NumEntries   Index      Index2           PageSize
+----------+---------+-------------+----------+----------+-------+
| Metadata | Indices |             | HashPage | HashPage |  ...  |
+----------+---------+-------------+----------+----------+-------+

このHash Pageのところにkey/valueの値が入っているということになります。

Hash Page

Hash Pageについてのレイアウトはソースコード上にありました。

 *   +-----------------------------------+
 *  |    type   | key/data ...          |
 *  +-----------------------------------+

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

最初の1バイトがTypeになっており、この値を見て判断します。Typeは以下のようなものがあります。

/* Each index references a group of bytes on the page. */
#define    H_KEYDATA   1  /* Key/data item. */
#define    H_DUPLICATE 2  /* Duplicate key/data item. */
#define    H_OFFPAGE   3  /* Overflow key/data item. */
#define    H_OFFDUP    4  /* Overflow page of duplicates. */

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

上では自分が慣れているkey/valueという呼び方をしていましたが、Berkeley DB上ではkey/dataと呼ばれています。H_KEYDATA の場合は実際のデータがそのHash Page内に含まれているため、2バイト目のデータ長を使ってデータを取り出せるようになっています。

typedef struct _hkeydata {
    u_int8_t  type;        /*    00: Page type. */
    u_int8_t  data[1];    /* Variable length key/data item. */
} HKEYDATA;

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

そして上のType内に H_OFFPAGE がありますが、これはOverflowと書いてあることから察するようにHash Pageで表現できないような値を保存するためのTypeになります。どちらかと言うとこちらがメインです。

Hash Off Page

Hash Off Pageは _hoffpage というstructで定義されています。pgnoというのが重要で、これは値が実際に保存されているPageの番号になります。ここでいうPageはMain Page相当のもので、現在のHash Main Pageの外側にあるということになります。

typedef struct _hoffpage {
    u_int8_t  type;        /*    00: Page type and delete flag. */
    u_int8_t  unused[3];  /* 01-03: Padding, unused. */
    db_pgno_t pgno;     /* 04-07: Offpage page number. */
    u_int32_t tlen;        /* 08-11: Total length of item. */
} HOFFPAGE;

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

つまり以下の図のようにDBの先頭から見た際にpgno * PageSizeの場所に求めているHashのkey/dataが保存されているということです。

0                 pgno*PageSize        LastPageNo * PageSize
+----------+----------+----------+----------------+
|   Page   |          | HashPage |     ......     |
+----------+----------+----------+----------------+

Hash Main Page (Overflow)

pgno * PageSizeの場所を読めばいいのですが、ここに保存されているのは上で説明したHash Main Pageと同じレイアウトです。ただし、Typeが P_OVERFLOW になっています。

/* Page types. */
...
#define P_OVERFLOW  7   /* Overflow. */

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

Overflow Pageのレイアウトについての説明は以下にありますが、Headerの後ろにデータがあるだけのシンプルなものです。

libdb/db_page.h at 5b7b02ae052442626af54c176335b67ecc613a30 · berkeleydb/libdb · GitHub

図にすると以下のようになります。

        26                     PageSize
+--------+-------------------------+
| Header |        key/data         |
+--------+-------------------------+

ただし、データサイズが大きいとこのPageでも収まらないかもしれません。そういう場合にHeader内にはNextPageNoが含まれています。上の方の図で出てきましたがまだ使われていませんでした。このNextPageNoがPGNO_INVALID(=0)の場合はそのPageが最後になりますが、0以上の値が入っている場合はそちらのPageにも続きのデータが入っているのでそちらのPageに含まれるデータもパースして結合する必要があります。

PGNO_INVALIDの場合はデータが途中で終わっているということなので、Header内に含まれるFreeAreaOffsetを使ってデータの長さ分を取り出します。

ということでデータが取り出せたので終了です。

処理の流れ

改めてHash accessでデータを取り出すまでの流れを簡略化したものを説明します。

先頭512バイトのHash Metadata（そのうちの72バイトがGeneric Metadata）をパースし、Magic, PageSize, Encryption Algorithm, PageType, LastPageNoを取得する
Magic numberを見てHash accessであることを確認。異なれば終了。
1ページ目は上のMetadata用なので2ページ目（2 * PageSize）から最後のページ（LastPageNo * PageSize）をパースする
1. Pageの先頭26バイトにHeaderが入っているのでパースし、26バイト目のPageTypeを確認する
2. PageTypeがHash Main PageならNumEntriesを取り出す。異なればskip。
3. NumEntriesはkey/dataのペア数を指しており、Headerの後ろにkey/dataの実際の値へのindexが保存されている
  1. Indicesの処理
    1. keyとdataのindexは2バイトでペアで4バイトになっているので、Headerの後ろから4 * NumEntriesを取り出す
    2. 2バイトずつkey, dataそれぞれのIndexとして解釈する
  2. Hash Pageの処理
    1. このIndexは現在のPage内のオフセットになっているため、そのオフセット分ずらしてHash Pageを読み込む
    2. 先頭1バイトがHash PageのTypeとなっているためその値を見て処理を変える
    3. H_KEYDATAであれば実際の値がそのHash Pageに入っているので、lengthを取得してその後ろのデータを読み込む
    4. H_OFFPAGEであればさらに別のPageに実際の値が入っているため、5バイト目から4バイト読み込みPage番号（pgno）を取得する
    5. Hash Off Pageの処理
      1. pgno * PageSizeの位置にあるHash Pageを読み込み、TypeがP_OVERFLOWであることを確認する
      2. 先程同様に先頭の26バイトがHeaderなので読み込みNextPageNoの値を確認する
      3. NextPageNoがPGNO_INVALIDならそのPageが最後なのでHeaderの後ろからFreeAreaOffset分読み込み値とする
      4. NextPageNoに値入っている場合は後ろにPageが続くため、Headerの後ろからPageの最後まで読み込みNextPageNoの指すPageも同様に読み込み値を結合する
      5. NextPageNoが空でない限り繰り返す
ここまででページを1つ処理出来たので次のページに移動して繰り返す

書いてみましたが自分で改めて読むと文字だけだとさっぱり意味わからないですね。上の図を見ながらだと分かるかと思います。

まとめ

伝えたかったのは背景に書いた良い話であとの内部実装は蛇足です。

とはいえ他の小さいDBも似たような実装になっていることが多いので、雰囲気だけでも知っておくと今後何かのDBのソースコード解析をする際に役立つかもしれません。また、Berkeley DBを他の言語に移植したい人も役立ててください。

knqyf263's blog

自分のためのメモとして残しておくためのブログ。

Berkeley DB (Hash) の実装

概要

背景

実装

全体

Metadata

Generic Metadata

Hash Metadata

Page

Hash Main Page

Hash Page

Hash Off Page

Hash Main Page (Overflow)

処理の流れ

まとめ