普段あまりこういう誰の役に立つのか分からない記事は書かないのですが、解析をするまでの背景がOSSに関するとても良い話なので重い腰を上げて書きました。
概要
古のアプリケーション組み込み型のデータベースとしてBerkeley DBがあります。元々はカリフォルニア大学バークレー校によって開発され、その後Oracleによって買収されています。データ操作にSQLは使えず、アプリケーションに埋め込んで使用します。RDBまでは必要ないけどちょっとしたDBが必要みたいな時に使われているようです。機能はシンプルで組み込みのため性能も良いとのこと。詳しくは以下に書いてます。
本記事ではそのBerkeley DBの中身がどのように実装されているのかの雰囲気を記します。Berkeley DBはBtree accessやHash access, Queue/Recno accessなどがサポートされていますが、今回はその中でもHash accessの場合にDBがどのようにデータを保存しているのかを説明しています。恐らくこの内容を知りたい人は日本に数人しかいないと思いますが、自分がすぐ忘れそうなのでメモとして残します。Berkeley DBのライブラリをRustに移植したい!という人がいたら役に立つかもしれません。
Hash accessの中でも必要な処理しか説明していません。ただ、大枠が理解できれば細かいところはBerkeley DBのソースコード読めば理解できるので、まず最初に雰囲気を掴むためには適した内容だと思います。
ソースコードは以下にあります。
あと上にも書いたように実装はシンプルですし似たような構造になっているDBは多いので、Berkeley DBを触ることが一生なくても知っておくと何か役立つかもしれません。
背景
ただの背景なので読み飛ばして実装に行って良いですが、良い話なので暇なら見てみて下さい。
Red Hat系のOSには /var/lib/rpm/Packages
というファイルが存在し、この中にインストールされたRPMパッケージの情報などが保存されています。rpm
コマンドや dnf
, yum
はこのファイルからデータを読み出して表示しているわけですが、このファイルはBerkeley DBになっています。libdb
を使えば普通に読み出せるのですが、自分の用途ではGoからこのファイルを読み出す必要がありました。libdb
はCで実装されていてGoから使うためには cgo
が必要になります。実際ライブラリを見つけたのですがやはり cgo
を使っていました。そもそもメンテナンスされていなくてアーカイブされています。
仕方ないのでforkしていくつか機能を足して使っていたのですが、やはり cgo
がネックになりました。色んな環境で動くバイナリを提供したかったのですがcgo
のせいでそれが困難になりました。一応頑張ってクロスコンパイル環境を用意したりしたのですが、これを今後メンテナンスすることを考えると負荷が高すぎるなと思ってやめました。
さらにもう一つ問題がありました。試しに cgo
を使って上の /var/lib/rpm/Packages
からデータを読みだしたところ、その中の値も何とバイナリになっていました。独自の形式でシリアライズされているという感じです。他のディストリビューションが分かりやすい形式で保存しているのに比べてBerkeley DBを使い、さらにその上に独自フォーマットということでさすがRed Hatだなと思ったりはしたのですが、気合でrpm
をリバース・エンジニアリングしました(この話もいつか書くかもしれません)。調べた限りではドキュメントも見つからなかったですし、ソースコードを読んだ方が早いし確実だなということで。
そしてGoに移植して必要な情報が取り出せるようなライブラリを実装しました。
さて次はBerkeley DBを倒すぞ〜と意気込んだのですが、本来自分が作りたかったソフトウェアから大分遠のいていることに気づきました。このヤクの毛刈りこそがプログラミングの楽しいところだとは思いつつも、GWの10日間で元々のソフトウェアを完成させたかったのでBerkeley DBのGo移植は一旦断念しました。そして悔し涙を流しながらrpm
のOSコマンドを呼び出すように実装しました。Go移植は次の長期休暇に絶対やることとして掲げていたのですが、その直後にイスラエルに引っ越して長期休暇がないまま1.5年が経過しました。イスラエルの祝日はユダヤ暦ベースなので今年はグレゴリオ暦の週末とぶつかってほとんど消滅しました。
ということでずっとしこりとして残っていたのですが、先日Anchoreというセキュリティ企業(自分の務めている企業の競合企業)がSyftとGrypeというOSSをリリースしました。
このOSSは自分が開発したものと似ているのですが、Red HatのRPM実装がどうなっているのか気になりました。そして Syft の中で自分の go-rpmdb
をforkしたものを使っていることがわかりました。そのコミットを見ると何とCバインディングを排除することに成功していました!どうやらBerkeley DBのGo移植に成功したようです。おいおいそんな凄いことやったならPRくれよ〜〜〜と思ったのですが、普通に送ってくれていました。
何かGitHubのWatchingが勝手に外れて通知来ないことがあるんですが自分だけでしょうか...。最近通知に気づけなくて放置になってしまっていることが多くて大変申し訳無い気持ちです。何はともあれせっかくBerkeley DBのGo移植をしてくれたので自分も送ってもらったPRを読みつつlibdbのコードを読みました。その中で得た知識を速攻忘れそうだったので今回まとめておこう、という背景です。
それにしてもこれだけの機能を外部の人、それどころかバリバリの競合企業の社員が実装してPRを送ってくれるなんてOSSは本当に素晴らしいなと思いました。恐らく彼もrpmの解析が面倒で困っていたら既に自分が解析してGo移植済みだったので、それならということで残タスクのBerkeley DB対応をしてくれたのだと思います。助け合いの精神ですね。PRに気づいた時に喜びのあまりドッグランで「う、うおおぉぉぉ!!!」と大声を出してしまいました。イスラエルでは路上で歌ったりしている人も多いのでちょっと大声を出しても変人扱いはされません。
ちなみに実装してくれた人はdiveという有名なツールの開発者です。もしかしたら知らない人もいるかも知れないので宣伝しておきます。GitHubのスター数が23kで化け物ですね。
彼は最近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
)をパースする- Pageの先頭26バイトにHeaderが入っているのでパースし、26バイト目の
PageType
を確認する PageType
がHash Main PageならNumEntries
を取り出す。異なればskip。NumEntries
はkey/dataのペア数を指しており、Headerの後ろにkey/dataの実際の値へのindexが保存されている- Indicesの処理
- keyとdataのindexは2バイトでペアで4バイトになっているので、Headerの後ろから
4 * NumEntries
を取り出す - 2バイトずつkey, dataそれぞれのIndexとして解釈する
- keyとdataのindexは2バイトでペアで4バイトになっているので、Headerの後ろから
- Hash Pageの処理
- このIndexは現在のPage内のオフセットになっているため、そのオフセット分ずらしてHash Pageを読み込む
- 先頭1バイトがHash PageのTypeとなっているためその値を見て処理を変える
H_KEYDATA
であれば実際の値がそのHash Pageに入っているので、lengthを取得してその後ろのデータを読み込むH_OFFPAGE
であればさらに別のPageに実際の値が入っているため、5バイト目から4バイト読み込みPage番号(pgno
)を取得する- Hash Off Pageの処理
pgno * PageSize
の位置にあるHash Pageを読み込み、TypeがP_OVERFLOW
であることを確認する- 先程同様に先頭の26バイトがHeaderなので読み込み
NextPageNo
の値を確認する NextPageNo
がPGNO_INVALID
ならそのPageが最後なのでHeaderの後ろからFreeAreaOffset
分読み込み値とするNextPageNo
に値入っている場合は後ろにPageが続くため、Headerの後ろからPageの最後まで読み込みNextPageNo
の指すPageも同様に読み込み値を結合するNextPageNo
が空でない限り繰り返す
- Indicesの処理
- Pageの先頭26バイトにHeaderが入っているのでパースし、26バイト目の
- ここまででページを1つ処理出来たので次のページに移動して繰り返す
書いてみましたが自分で改めて読むと文字だけだとさっぱり意味わからないですね。上の図を見ながらだと分かるかと思います。
まとめ
伝えたかったのは背景に書いた良い話であとの内部実装は蛇足です。
とはいえ他の小さいDBも似たような実装になっていることが多いので、雰囲気だけでも知っておくと今後何かのDBのソースコード解析をする際に役立つかもしれません。また、Berkeley DBを他の言語に移植したい人も役立ててください。