DBDB: ドッグベッドデータベース
DBDB (Dog Bed Database) は単純なキーバリューデータベースを実装する Python ライブラリである。DBDB はキーをバリューに結び付け、その結び付きを後から読み込める形でディスクに保存する機能を持つ。
DBDB はマシンのクラッシュやエラーが発生したとしてもデータを破損させずに保持する。また、全てのデータを一度に RAM に読み込まないので、DBDB は RAM 容量より大きいデータを管理できる。
メモリ
どうしても理解できないバグに初めて直面したときのことを私は今でも覚えている。BASIC プログラムを入力して実行すると、スクリーンにチカチカした奇妙なピクセルが表示されてプログラムが途中で終了してしまう。さらに、その後コードを編集しようとするとプログラムの最後の数行が消去されている！
母親の知り合いにプログラミングが分かる人がいて、私は電話越しにバグを相談できた。彼女と数分間通話すると、バグは見つかった: プログラムが大きすぎて、ビデオメモリに踏み込んでいたのである。このときスクリーンをクリアするとプログラムの末尾も削除される。また、Applesoft BASIC は RAM 上でプログラムの直後にプログラムの状態を保存するので、それがチカチカした奇妙なピクセルとして表示される。
このときから、私はメモリの割り当てを意識するようになった。ポインタとは何かを学び、malloc でメモリをアロケートする方法も学んだ。自分が書いたデータ構造がメモリ上にどのように並べられるかを理解し、データ構造を変更するときは格段の注意を払って行うようになった。
それから数年後、Erlang というプロセス指向言語に関する文章を読んだとき、Erlang では全てが不変 (immutable) なためにプロセス間メッセージを送信するときデータのコピーが必要にならないことを知った。その後 Clojure で不変データ構造に触れたとき、この事実を本当の意味で理解できるようになった。
2013 年に CouchDB に関する文章を読んだとき、変化を続ける複雑なデータを管理するためのデータ構造と仕組みが分かって、私は笑顔でうなずいた。
私は不変データ構造を中心としてシステムが設計できることを学んだ。
そして私は本章の執筆を承諾した。
CouchDB のデータストレージにおける中心的な概念を説明する文章は楽しいものになるだろう、と私は考えた。
データをその場で改変する二分木を書いてみたところ、アルゴリズムやコードがあまりにも複雑で挫折しかけた。ある部分への変更が木の他の部分に及ぼす影響やコーナーケースの多さを考えると頭が痛む。こんなものを読者に説明するなど想像もできなかった。
この教訓を胸に、不変二分木を更新する再帰的アルゴリズムに目をやると、こちらは比較的単純なように思えた。
こうして私はもう一度、変更されないものは理解しやすいと学んだ。
そろそろ本題に入ろう。
なぜ面白いのか？
たいていのプロジェクトは何らかのデータベースを必要とする。しかしデータベースを自分で書くのは御法度である。JSON をディスクに書き出すだけの処理であっても、踏み抜きかねないコーナーケースは多くある:
- ファイルシステムの容量が足りなくなったら？
- 書き込み中にノートパソコンのバッテリーが切れたら？
- データのサイズが利用可能なメモリより大きかったら？ (この状況はモダンなデスクトプコンピューターで実行されるアプリケーションでは考えにくいものの、サーバーサイドのウェブアプリケーションやモバイルデバイスでは発生する可能性がある。)
しかし、データベースがこういった問題にどう対処するかを理解したいなら、自分でデータベースを書いてみるのは良いアイデアである。
本章で議論するテクニックや概念は、障害に直面したときに予測可能で合理的な振る舞いが求められる任意の場面に適用できるだろう。
障害と言えば...
障害の特徴付け
データベースは ACID と呼ばれる四つの性質のどれを持っているかによって特徴付けられる:
- 不可分性 (atomicity)
- 一貫性 (consistency)
- 独立性 (isolation)
- 永続性 (durability)
DBDB における更新は不可分性と永続性を持つ。この二つの性質は後で詳しく説明する。DBDB は保存されるデータに制約を一切課さないので、一貫性を保証しない。同様に独立性も実装されない。
アプリケーションコードが独自に一貫性を保証することは当然できる。しかし、完全な独立性にはトランザクションマネージャが必要になる。本章はトランザクションマネージャに触れないものの、CircleDB の章に解説がある。
システムの管理に関して考える必要のある問題は他にもある。DBDB は利用されなくなったデータを解放しないので、同じキーのバリューを何度も更新し続けるといずれディスク空間が足りなくなる (なぜそうなっているかはすぐに分かる)。未使用のデータを解放する処理は通常のデータベースには存在する。 PostgreSQL は古い行空間を再利用可能にする処理を「バキューミング (vaccuming)」と呼び、CouchDB はデータの「生きている」部分だけを新しいファイルに書き出し、古いファイルを新しいファイルでアトミックに置き換える処理を「コンパクション (compaction)」と呼ぶ。
DBDB にコンパクションの機能を追加することはできるものの、これは読者への練習問題とする1。
DBDB のアーキテクチャ
DBDB には物理層、論理層、そしてパブリック API が存在する。つまり、ディスク上のファイルにおけるデータの配置、二分木 (などのデータ構造) の実装、そしてキーとバリューの関連付けが個別に実装される。
多くのデータベースでも論理層と物理層は分離される。異なるパフォーマンス特性を持つ様々な環境に向けた代替実装を提供する上でこの分離が有用となるためである。例えば DB2 には SMS (ファイルシステム上のファイル) と DMS (ローブロックデバイス) という二つの異なるテーブル空間が存在し、MySQL には代替エンジンの実装がいくつか存在する。
設計
本書のほとんどの章はプログラムをゼロから書き始めて完成するまでを解説する。しかし、これは読者が普段プログラムに触れるときの状況とは異なるはずである。他の人物によって書かれたコードを見つけ、異なるタスクに使うためにそれを改変・拡張する方法を見つけようとする状況の方が多い。
本章では DBDB を完成済みのプロジェクトとみなし、その構成要素を見ていきながら動作を解説する。まずはプロジェクト全体の構造を見る。
構成要素
DBDB の構成要素をエンドユーザーからの距離が近い順に次に示す。つまり、DBDB のユーザーは一つ目の構成要素を最もよく知る必要があり、最後の構成要素を知る必要はほとんどない。
tool.pyはターミナルウィンドウからデータベースを操作するためのコマンドラインツールを定義する。interface.pyはDBDBクラスを定義する。DBDBは具象クラスBinaryTreeを使って Python の辞書 API を実装する。Python プログラムから DBDB を使うときはDBDBが使用される。-
logical.pyは論理層を実装する。キーバリューストアの抽象インターフェースが定義される。LogicalBaseは論理的更新 (取得、設定、コミットなど) の API を提供する。論理更新の実装は具象子クラスが行う。ストレージのロックと内部ノードの参照削除もLogicalBaseが担当する。ValueRefはデータベースに格納されたバイナリブロブを参照する Python オブジェクトである。この間接参照のおかげで、データストア全体をメモリ上に読み込む必要はなくなる。
-
binary_tree.pyはlogical.pyが定義するインターフェースを満たす二分木アルゴリズムを実装する:BinaryTreeは二分木の具象実装を提供する。キーとバリューの組の取得、挿入、削除がサポートされる。BinaryTreeが表す木は不変である: 更新メソッドは古い木と一部を共有する新しい木を返す。BinaryNodeは二分木のノードを実装する。BinaryNodeRefはValueRefの特殊化であり、BinaryNodeをシリアライズおよびデシリアライズする方法を知っている。
physical.pyは物理層を定義する。Storageクラスが (ほぼ) 追記専用の永続レコードストレージを提供する。
これらの構成要素はそれぞれのクラスに単一の責務を持たせるように試行錯誤した結果として生まれた。言い換えれば、それぞれのクラスは変更が必要になる理由を一つしか持たない。
バリューの取得
最初は最も単純なケースから始める: データベースからバリューを一つ取得する処理を考える。example.db でキー foo に関連付くバリューを取得するコマンドを次に示す。このコマンドの動作を追いかけよう:
$ python -m dbdb.tool example.db get foo
このコマンドは dbdb.tool モジュールにある main 関数を実行する:
# dbdb/tool.py
def main(argv):
if not (4 <= len(argv) <= 5):
usage()
return BAD_ARGS
dbname, verb, key, value = (argv[1:] + [None])[:4]
if verb not in {'get', 'set', 'delete'}:
usage()
return BAD_VERB
db = dbdb.connect(dbname) # データベースのオープン
try:
if verb == 'get':
sys.stdout.write(db[key]) # バリューの取得
elif verb == 'set':
db[key] = value
db.commit()
else:
del db[key]
db.commit()
except KeyError:
print("Key not found", file=sys.stderr)
return BAD_KEY
return OK
connect 関数はデータベースファイルをオープン (存在しなければ作成) し、DBDB クラスのインスタンスを返す:
# dbdb/__init__.py
def connect(dbname):
try:
f = open(dbname, 'r+b')
except IOError:
fd = os.open(dbname, os.O_RDWR | os.O_CREAT)
f = os.fdopen(fd, 'r+b')
return DBDB(f)
# dbdb/interface.py
class DBDB(object):
def __init__(self, f):
self._storage = Storage(f)
self._tree = BinaryTree(self._storage)
DBDB のコンストラクタは Storage クラスのインスタンスを作成し、そのインスタンスに対する参照を self._storage に記録する。ただ、その参照は self._tree と共有される。なぜだろうか？ self._tree がストレージへのアクセスを独自に管理してはいけないのだろうか？
プログラムの設計ではリソースを誰が「所有」するのかという問題が重要になることが多い。この問題への解答は、安全でない可能性がある変更を見つける上で役立つためである。この疑問を念頭に置いて、今は先に進もう。
DBDB インスタンスが作成されると、key に関連付くバリューの取得は辞書風のルックアップ db[key] で行われる。この式は Python インタープリタによって DBDB.__getitem__ 関数の呼び出しと解釈される:
# dbdb/interface.py
class DBDB(object):
# ...
def __getitem__(self, key):
self._assert_not_closed()
return self._tree.get(key)
def _assert_not_closed(self):
if self._storage.closed:
raise ValueError('Database closed.')
__getitem__ メソッドは最初に _assert_not_closed 関数を呼び出してデータベースが現在オープンされていることを確認する。なるほど！ これで DBDB が Storage クラスのインスタンスに対するアクセスを必要とする理由が一つ分かった: 事前条件を保証するためである。 (この設計をどう思うだろうか？ 同じことを行う他の方法を考えられるだろうか？)
その後 DBDB は key に関連付いたバリューをプライベート変数 _tree のメソッド get で取得する。このメソッドは LogicalBase によって提供される:
# dbdb/logical.py
class LogicalBase(object):
# ...
def get(self, key):
if not self._storage.locked:
self._refresh_tree_ref()
return self._get(self._follow(self._tree_ref), key)
get メソッドは最初にストレージがロックされているかどうかを確認する。このメソッドが呼ばれたときロックされている可能性がある理由を私たちは完全に理解できるわけではないものの、書き込み時のデータへのアクセスを直列化しているのだろうと推測できる。ストレージがロックされていないと何が起きるだろうか？
# dbdb/logical.py
class LogicalBase(object):
# ...
def _refresh_tree_ref(self):
self._tree_ref = self.node_ref_class(
address=self._storage.get_root_address())
_refresh_tree_ref メソッドはデータの「ビュー」を現在ディスク上にあるデータを使ったものに更新する。これで最新のバリューが取得されるようになる。
get メソッドが呼び出されたときストレージがロックされていたら何が起きるのだろうか？ ストレージがロックされているなら、おそらく他のプロセスが取得したいデータベースを現在変更している。そのため、この状態でデータベースを使うと最新のバリューを読み込めないと考えらえる。この現象を「ダーティリード (dirty read, 汚れた読み込み)」と呼ぶ。ロックを使ったこのパターンを使うとき読み込まれるバリューがダーティリードによって最新ではなくなる可能性が生まれるものの、同時に複数の読み込みが実行される状況でもブロックを気にする必要はない。
続いて、実際にデータを取得する部分を見よう:
# dbdb/binary_tree.py
class BinaryTree(LogicalBase):
# ...
def _get(self, node, key):
while node is not None:
if key < node.key:
node = self._follow(node.left_ref)
elif node.key < key:
node = self._follow(node.right_ref)
else:
return self._follow(node.value_ref)
raise KeyError
これは標準的な二分木の探索であり、ノードに格納された参照を追って次のノードに移動している。BinaryTree のドキュメントを読めば、Node と NodeRef が値オブジェクトだと分かる: 言い換えれば不変であり、その内容は変化しない。Node はキーとバリュー、そして左の子と右の子を持った状態で作成され、この関連付けも変化しない。BinaryTree 全体の内容が外から見て変化するのは、ルートノードが置き換えられたときに限る。そのため、BinaryTree の探索中に木が変更される可能性に対処する必要はない。
key に関連付くバリューが見つかると、main はそのバリューを stdout に書き出す。ユーザーのデータをそのまま表示するために、このとき最後に改行を加えることはしない。
挿入と更新
続いて、examle.db でキー foo にバリュー bar を設定する次のコマンドの実行を追いかけよう:
$ python -m dbdb.tool example.db set foo bar
ここでも dbdb.tool モジュールの main 関数が最初に実行される。この関数は以前に示したので、ここでは重要な部分だけを示す:
# dbdb/tool.py
def main(argv):
...
db = dbdb.connect(dbname) # データベースのオープン
try:
...
elif verb == 'set':
db[key] = value # バリューの設定
db.commit() # 変更のコミット
...
except KeyError:
...
db[key] = value を実行するとき、Python のインタープリタは DBDB.__setitem__ を呼び出す:
# dbdb/interface.py
class DBDB(object):
# ...
def __setitem__(self, key, value):
self._assert_not_closed()
return self._tree.set(key, value)
__setitem__ メソッドはデータベースが現在オープンされていることを確認し、プライベート変数 _tree の set メソッドを呼び出して key と value の関連付けを格納する。
_tree.set は LogicalBase によって提供される:
# dbdb/logical.py
class LogicalBase(object):
# ...
def set(self, key, value):
if self._storage.lock():
self._refresh_tree_ref()
self._tree_ref = self._insert(
self._follow(self._tree_ref), key, self.value_ref_class(value))
set は最初にストレージのロックを確認する。lock は自分が現在ロックを持っているなら False を返し、持っていないならロックを取得した上で True を返す:
# dbdb/storage.py
class Storage(object):
# ...
def lock(self):
if not self.locked:
portalocker.lock(self._f, portalocker.LOCK_EX)
self.locked = True
return True
else:
return False
この lock メソッドには重要な点が二つある:
- DBDB のロックは、portalocker と呼ばれるファイルロックを提供するサードパーティのライブラリによって提供される。
lockメソッドはデータベースが既にロックされているならFalseを返し、そうでないならロックを取得した上でTrueを返す。
LogicalBase.set に戻ろう。lock の実装を見たことで、set で lock の返り値が確認される理由が理解できた: _refresh_tree_ref を最新のルートノードの参照に対して呼び出し、自身がディスク上の二分木を最後に参照した時点から現在までの間に他のプロセスが加えた変更が失われないようにするためである。その後、引数に受け取ったキーとバリューの組が挿入 (または更新) された新しい二分木でルートノードが置き換えられる。
_insert() は新しい二分木を返すので、挿入・更新は二分木のいずれのノードも変更しない。新しい二分木は変更されていない部分を一つ前の二分木と共有することで、メモリと実行時間を節約する。このアルゴリズムは再帰を使えば自然に実装できる:
# dbdb/binary_tree.py
class BinaryTree(LogicalBase):
# ...
def _insert(self, node, key, value_ref):
if node is None:
new_node = BinaryNode(
self.node_ref_class(), key, value_ref, self.node_ref_class(), 1)
elif key < node.key:
new_node = BinaryNode.from_node(
node,
left_ref=self._insert(
self._follow(node.left_ref), key, value_ref))
elif node.key < key:
new_node = BinaryNode.from_node(
node,
right_ref=self._insert(
self._follow(node.right_ref), key, value_ref))
else:
new_node = BinaryNode.from_node(node, value_ref=value_ref)
return self.node_ref_class(referent=new_node)
_insert はどんな場合でも新しいノード (を NodeRef で包んだもの) を返す点に注目してほしい。ノードを改変して新しい部分木を指すようにするのではなく、変更されていない部分木を指す新しいノードを作成している。このアルゴリズムによって二分木 BinaryTree は不変データ構造となる。
奇妙なことに気が付いたかもしれない: この時点ではディスク上のデータに何もしていない。_insert は二分木のノードをいじってディスク上のデータに対するビューを操作するだけに過ぎない。
ビューに対する変更を実際にディスクに書き込むには、最初に示した tool.py の main 関数のように set に続いて commit を呼び出す必要がある。
コミットを実行するとメモリ上に存在するダーティな (汚れた) 状態が全てディスクに書き込まれ、二分木の新しいルートノードのディスクアドレスが保存される。
パブリック API は次のメソッドを呼び出す:
# dbdb/interface.py
class DBDB(object):
# ...
def commit(self):
self._assert_not_closed()
self._tree.commit()
_tree.commit は LogicalBase が実装する:
# dbdb/logical.py
class LogicalBase(object)
# ...
def commit(self):
self._tree_ref.store(self._storage)
self._storage.commit_root_address(self._tree_ref.address)
NodeRef をディスクにシリアライズする store メソッドは、自身の子にシリアライズを指示する prepare_to_store メソッドの呼び出しから始まる:
# dbdb/logical.py
class ValueRef(object):
# ...
def store(self, storage):
if self._referent is not None and not self._address:
self.prepare_to_store(storage)
self._address = storage.write(self.referent_to_string(self._referent))
今考えている例で LogicalBase の self._tree_ref は実際には BinaryNodeRef (ValueRef の子クラス) なので、prepare_to_store の具象実装は次のメソッドとなる:
# dbdb/binary_tree.py
class BinaryNodeRef(ValueRef):
def prepare_to_store(self, storage):
if self._referent:
self._referent.store_refs(storage)
注目している _referent は BinaryNode であり、store_refs は自身が持つ参照をストレージに保存する:
# dbdb/binary_tree.py
class BinaryNode(object):
# ...
def store_refs(self, storage):
self.value_ref.store(storage)
self.left_ref.store(storage)
self.right_ref.store(storage)
この呼び出しは書き込まれていない変更がある (_address を持たない) 全ての NodeRef に対して再帰的に呼び出される。
ValueRef の store メソッドに戻ろう。store は最後に自身をシリアライズし、そのストレージアドレスを保存する:
# dbdb/logical.py
class ValueRef(object):
# ...
def store(self, storage):
if self._referent is not None and not self._address:
self.prepare_to_store(storage)
self._address = storage.write(self.referent_to_string(self._referent))
prepare_to_sotre が返った時点で NodeRef の _referent が持つ全ての参照にアドレスが設定されるので、このノードのシリアライズが可能になる。シリアライズは pickle.dumps 関数を使ってノードを表現するバイト列を作成することで行う:
# dbdb/binary_tree.py
class BinaryNodeRef(ValueRef):
# ...
@staticmethod
def referent_to_string(referent):
return pickle.dumps({
'left': referent.left_ref.address,
'key': referent.key,
'value': referent.value_ref.address,
'right': referent.right_ref.address,
'length': referent.length,
})
store メソッド内でアドレスを更新することは厳密に言えば ValueRef の改変と言える。ただ、この改変はユーザーから見える値に影響しないので、ValueRef は不変ともみなせる。
LogicalBase.commit によって呼び出されたルートの _tree_ref に対する store が完了すると、全てのデータがディスクに書き込まれたと確信できる。その後、次のコードでルートのアドレスをコミットする:
# dbdb/physical.py
class Storage(object):
# ...
def commit_root_address(self, root_address):
self.lock()
self._f.flush()
self._seek_superblock()
self._write_integer(root_address)
self._f.flush()
self.unlock()
最初にファイルハンドルをフラッシュして、データをキャッシュではなく SSD などの安定したストレージに書き込むよう OS に指示する。最後のルートアドレスの書き込みは _seek_superblock メソッドによってファイルの先頭にシークされてから実行されるので、必ずアトミックになる: ファイルの先頭はセクタのサイズに関係なくセクタ境界であり、単一セクタに対する書き込みはアトミックだとディスクハードウェアによって保証される。
ディスク上に存在するルートノードのアドレスは古い値または新しい値のいずれかであり、二つが混ざった値が存在する瞬間は存在しない。そのため他のプロセスはロックを取得せずにデータベースを読み込める。そのプロセスが読み込むのは古い値または新しい値であり、それ以外の値を読み込む可能性はない。つまり DBDB のコミットは不可分性を持つ。
DBDB は新しいデータをディスクに書き込んだ後、ルートノードのアドレスを書き込む前に fsync システムコール2を呼び出す。そのため、しばらくの間コミットされていない到達不可能なデータがディスク上に存在することになる。逆に、ルートノードのアドレスが更新されたときルートノードが参照するデータは全てディスクに存在する。つまり DBDB のコミットは永続性も持つ。
これで終わりだ！
NodeRef によるメモリの節約
木構造全体を同時にメモリ上に保持することを避けるために、論理ノードをディスクから読み込むとノードの値の他には左右の子のアドレスだけが読み込まれる。子にアクセスするには NodeRef.get 関数を呼び出して参照をたどる (実際にデータを読み込む) 必要がある。
NodeRef を構築するとき必要なのはアドレスだけである:
+---------+
| NodeRef |
| ------- |
| addr=3 |
| get() |
+---------+
この NodeRef の get メソッドを呼び出すと具象ノードが返る。その具象ノードが参照するノード (左右の子ノード) も NodeRef で表される:
+---------+ +---------+ +---------+
| NodeRef | | Node | | NodeRef |
| ------- | | ------- | +-> | ------- |
| addr=3 | | key=A | | | addr=1 |
| get() ------> | value=B | | +---------+
+---------+ | left ----+
| right ----+ +---------+
+---------+ | | NodeRef |
+-> | ------- |
| addr=2 |
+---------+
二分木への変更がコミットされていないとき、その変更に影響を受ける全てのノード (ルートノードを含む) はメモリ上だけに存在する。言い換えればディスク上に存在せず、それらのノードにはキーとバリューが含まれるだけでディスクアドレスは含まれない。書き込んでいるプロセスからはコミットされていない変更が見え、コミットする前にさらに書き込んでも構わない: なぜなら NodeRef.get は未コミットのノードへの参照を返せるからである。API を使ってノードにアクセスするとき、それがコミットされているかどうかは影響を及ぼさない。新しいルートアドレスがディスクに書き込まれて初めて変更があったノードに到達可能となるので、全ての変更は他のプロセスにアトミックに伝わる。同時に試みられた複数の更新は、ディスク上のロックファイルを通して逐次化される。ロックは最初の更新の前に取得され、コミットの後に解放される。
読者への練習問題
DBDB では複数のプロセスがロックを取らずに同じデータベースを読み込める。その代わり、読み込みが古いデータを取得する可能性がある。データを一貫して読み込める必要がある場合はどうするべきだろうか？ データベースの典型的な利用シナリオとして「値を読み、その値を使って新しい値を計算して書き戻す」というものがある。この処理を行うメソッドを DBDB に追加できるだろうか？ こういった機能の代償として何が犠牲になるだろうか？
interface.py に含まれる文字列 BinaryTree を置き換えれば、データストアが利用するデータ構造とアルゴリズムを完全に変更できる。現実のデータストアは B-木や B+木といった高度なデータ構造を利用して高いパフォーマンスを達成している。平衡二分木は値の読み込みに平均で \(O(\log_2 n)\) 回のランダムノードアクセスを必要とするのに対して、例えば各ノードが 32 個の子を持つ B+木は \(O(\log_{32} n)\) 回しか必要としない。エントリー数が 40 億だとすれば、B+木を使うことで値の読み込みごとのランダムノードアクセスの回数が \(\log_2 2^{32} = 32\) から \(\log_{32} 2^{32} \approx 6.4\) に減少するので、現実のデータでとても大きな違いを生む。木構造のノード探索はランダムアクセスが多く、回転プラッタを利用するハードディスクでは非常に時間がかかる。SSD を使えばレイテンシは改善するものの、I/O を減らすことの重要性は変わらない。
デフォルトで ValueRef は格納される値がバイト列だと仮定する (そして Storage はそのバイト列を「そのまま」書き込む)。二分木のノードは ValueRef の子クラスに過ぎない。JSON や MessagePack を利用してリッチなデータを書き込むには、適切なクラスを value_ref_class に設定するだけで済む。BinaryNodeRef は pickle を使ってデータをシリアライズする例である。
データベースのコンパクションも興味深い練習問題である。コンパクションは木を通りがけ順に走査しつつノードを書き出すことで行える。二分木はデータの読み書きで必ず利用されるので、コンパクションは全てのノードに対してまとめて実行するのが最善だろう。一つのディスクセクタに可能な限り多くの中間ノードを収めるようにすると、少なくともコンパクション直後はパフォーマンスの向上が見込める。自分で実装しようと思っているなら、注意すべき点 (メモリ使用量など) は他にもある。それと、次の点を忘れてはいけない: 変更の前後でパフォーマンスのベンチマークを必ず行うこと！ 驚くような結果が得られる場合も多い。
パターンと原則
実装ではなくインターフェースをテストすべきである。DBDB の開発中、私は書いているコードをどのように使いたいかを表現したテストを数多く書いた。最初に書いたのはインメモリバージョンのデータベースに対するテストであり、その後ディスクに書き出す機能や NodeRef の概念を追加していった。テストのほとんどには変更が必要にならず、この事実によって自分が過去に書いたコードが正しく動作していることへの自信が増した。
単一責任原則を順守するべきである。クラスに変更が生じる理由は多くとも一つにしなければならない。DBDB の全てのクラスがそうなっているわけではないものの、局所的な変更だけで拡張できる機能はいくつも存在する。機能を追加しながらリファクタリングを行うのは楽しかった！
まとめ
DBDB は単純な保証を持った単純なデータベースである。しかし、その実装はすぐに複雑化した。この複雑性を管理するために私が利用した最も重要なテクニックは、表向きには改変可能なオブジェクトを不変データ構造を使って実装することだった。手に負えないほど多くのコーナーケースを持つように思える厄介な問題に直面したときは、このテクニックを試してみることを読者にも勧める。