豪鬼メモ

一瞬千撃

再構築しない復旧処理

データベースファイルを開いたプロセスが突然死した場合、次回にそのファイルを開いた際には自動的に復旧処理が走るようになっている。従来のバージョンでは、復旧に際して、データベース内の全レコードをスキャンして、データベースを再構築するのが専らであった。これは確実な方法だが、データベースの規模に応じた時間がかかってしまう。実際にはファイルを閉じなくても不整合は起きないことが多いので、その場合には再構築をしなくても復旧できる。よって、整合性の検査をした上で復旧処理を省略して高速化する機能を追加した。
f:id:fridaynight:20210701230246p:plain

続きを読む

BtrFSのスナップショットによるオンラインバックアップ

止められないオンラインサービスでデータベースを運用している場合、バックアップデータをどうやって作るかには頭を悩ませられる。Tkrzwにはバックアップのための手段がいくつかあるが、ファイルシステムのcopy-on-writeスナップショットを簡単に利用する機能を追加したので紹介する。また、通常のread/writeによるユーザ空間内コピー、sendfileによるカーネル空間内コピー、copy-on-writeによる擬似コピーの性能を比較する。BtrFSとEXT4の性能比較も行う。
f:id:fridaynight:20210628014442p:plain

続きを読む

ハッシュデータベースの互換的フォーマット変更

HashDBMの信頼性向上と性能向上を図るためにデータベースフォーマットを変更したのだが、後方互換性を持たせつつフォーマットを変更するのには苦労した。それをどうやって進めたかという話。ユーザにとっては、すげー地味でどうでもいい話ではあるが、開発者視点では、1ビットも無駄のない戦いが行われていた。
f:id:fridaynight:20210626015222p:plain

続きを読む

各種エラー検出符号のエラー検出率

データベースにエラー検出符号を組み込んだはいいが、実際にどの程度の確率でエラーを検出できるだろうか。単純なチェックサムAdlerチェックサムCRCを比較してみた。実際にランダムに文字列を書き換えて、それがきちんと検出できるかどうかの統計を取った。以下は、各種エラー検出符号の、エラーの長さ(バイト数)とエラー検出率のグラフである。
f:id:fridaynight:20210623011220p:plain

続きを読む

圧縮データベースの性能評価

各種圧縮アルゴリズムの性能について前回の記事で検討したが、それを実際にデータベースライブラリに組み込んだ。Tkrzw-0.9.30から利用できる。今回は、実際に英和辞書のデータベースを圧縮してみて、どのくらい効果があるのかを確かめてみる。

f:id:fridaynight:20210619140642p:plain
f:id:fridaynight:20210619145258p:plain

続きを読む

圧縮アルゴリズムの事前調査

データベースにレコードを格納する際に可逆圧縮をかけると便利なことがある。 データベースファイルが小さくなり、また入出力のデータ量が減るので早くなることすらある。圧縮アルゴリズムを自分で実装するのは手に余るので、既存の実装を組み込むのが現実的だ。そうなると、数多ある実装からどれを選ぶかが重要になる。なので、圧縮率や処理速度について調査してみた。結論としては、LZ4とZSTDが非常に素晴らしいので、組み込む方向で検討する。

続きを読む

マルチシャードのトランザクション

TkrzwにはShardDBMというクラスがあり、シャーディングで分割した複数のデータベースファイルをあたかも単一のデータベースであるかのように透過的に扱うことができる。複数マシンに分散しないローカル環境でも、シャーディングを施すと、並列処理性能や再構築処理等の効率の点で有利な点が多々ある。レイテンシが重要課題となるオンライン系での運用では特にシャーディングは有用だ。シャーディングによって複数のデータベースファイルが関わるとなると、トランザクションの独立性(Isolation)をどうやって実現するかが課題となる。今回は、トランザクションをコールバック関数の連続呼び出しとしてモデル化したProcessMultiメソッドと、任意の外部処理とCompare-and-Swapによって実現するためのCompareExchangeMultiメソッドの実装について説明する。

続きを読む

CRCをデータベースに内蔵する

データベースにレコード単位のCRCを内蔵することで、データが破損した際の検出率を高められるようにした。ハッシュ関数の性能測定とそれを組み込んだ際のデータベースの性能測定もして、実用になることを確かめた。

これにより、Synchronizeを呼ばない運用でも、レコード単位の一貫性を向上させることができる。アプリケーションの責任でCRCをレコードのデータに付随させれば良いとも考えたが、面倒なことはやらない人が多いだろう。なので、やはりデータベース側で面倒を見ることにした。PostgreSQLMySQLなどでもCRCは内蔵しているので、データベース側で一貫性の向上策を持つのは一般的とも言える。「はじめてのDBM」スライドにCRCを使った運用についても書いておいたので、ご覧いただきたい。
f:id:fridaynight:20210613205027p:plain

続きを読む

壊れないデータベースと壊れにくいデータベース

前回までの議論で、Tkrzwを追記更新モードで運用した場合、トランザクションのACID特性を満たすデータベースとして機能することを確かめた。Synchronizeした時に状態が決定してファイルに固定され、次にSynchronizeするまでにプロセスが死んだなら、直前にSynchronizeした状態に自動的にロールバックしてくれる。その意味で、Tkrzwは壊れないデータベースと言える。今回は、Synchronizeしないで運用した場合に、ベストエフォートで、できるだけ多くのレコードを取り出す機能について検討する。
f:id:fridaynight:20210611161052p:plain

続きを読む

トランザクションのACID特性と自動リストア機能

Tkrzwにトランザクション機能を実装したので、ACID特性について確認しておきたい。AとCとIは正常系のみを検討するのであれば容易に達成されるのだが、問題はDだ。Durability=耐久性=耐障害性がちゃんと確保されているかどうか、仕様を説明しながら確認してみる。
f:id:fridaynight:20210605021155p:plain

続きを読む