dps

dpsとは、Demi-Persistent Storageの略(仮名)。

将来に名前を変更する可能性がある。

• 目的
• 要求される仕様
• 概要
• 詳細
• 書きかけのメモ
• インターフェース
• ライブラリ仕様
• ロードマップ
• 関連

子ページ

• dps:interpreter
• dps:old
• dps:swmflrr

目的

• 某プロジェクトでの使用に耐えうるデータストレージエンジンを実装する。

要求される仕様

概要

• トポロジー構造(要はcons cell等の構造)を維持したまま、オブジェクトを保存できる事
  • トポロジー構造を維持できるストレージエンジンで有名なものとしてmetakitがあるが、某プロジェクトでの用途には向かなさそうなので自前で用意する
• エントリはpersistent、つまり一度値を入れたら二度と値の変更はできないものとする
  • つまり、これはthcompのようなものに近い
• ポインタの代用品として、uuidを利用する
• 全体として、robustである必要がある
• 実際にデータをストレージするバックエンドは、暗号化等ができた方がよい(だが必須ではない)
• 最終的には、portableなものにする必要がある(最初の内はportableでなくてok)

詳細

• エントリ自体はpersistentだが、環状構造を作る必要があるので、通常のエントリ作成とは別に、「エントリのみ生成(valueはまだundefined)」「valueがundefinedのエントリに記入」の二つのmethodを用意する
• 以下の記憶領域を用意する
  • uuid->valテーブル
    • メインの記憶領域。
    • 前述の通り、基本的にpersistentなデータを入れるものである(例外は値がundefinedの場合)、が、メインのデータとは別にメタ情報も一緒に保存され、このメタ情報は更新されうる、という点に注意。
    • dbm系、もしくはnosql系のストレージエンジンである事が望ましい。
  • key->uuidテーブル
    • 前述の通り、データがpersistentかつkeyがuuidなので、例えば「(1 2 3)」のようなデータ(リストの全ての要素が確定している)が頻出する場合、それらは同一のデータを指し示すようにしたい(毎回新しいエントリを作りたくない)。その為に、このテーブルを用いる。keyは、(cute write-to-string <> write/ss)された内部形式。
  • systemテーブル
    • システム的な、雑多なメタ情報を記憶しておく為の記憶領域。gc用の一時情報もここに記録しておく。
      • dbm系が望ましい
  • journalログ
    • gcや整合性チェック等の為に、このシステムへの読み書きの履歴を記録する為のログ。
    • rotate, purgeが可能である必要がある。ファイルに追記する形でよい？
      • gauche.logger等が利用可能か調べてみる
• uuid->valテーブルの値として、以下を設定可能とする
  • #,(undef)
    • 前述の通り、上書き可能な唯一のvalue
    • この値はキャッシュしてはならない
  • #,(uuid c91032c9-9daf-42cd-b3ba-88332543ffaa)
    • uuidオブジェクト
      • この値そのものがvalueとして保存されていた場合、それはnueの「見えないリファレンス」のように扱うものとする
        • schemeでのdelayオブジェクトのような、遅延評価リファレンスとすべきかも
      • もしかしたら、この機構は不要かもしれない？
  • pairを除いた、nil、真偽値、数値、文字、文字列といった、gaucheで利用可能な、write/read invarianceが保たれたオブジェクト
    • pairに関しては、後述の#,(pair ...)を使う事
    • 尚、文字列以外のnil、真偽値、数値、文字については、uuid-ref化せずに、直に埋め込んだものをuuid-refとみなす、という手法を使って簡略化する
  • #,(pair 123 456)
    • pairの代用品
    • eagerなリストではなく、遅延リスト(仮)であるという点に注意が必要
    • car部及びcdr部には、uuidオブジェクトの外部表現(つまり、#,(uuid ...))か、前述の、nil等の外部表現が入る
  • #,(op args body ...) #,(fn args body ...)
    • 適用可能なオペレータ、および、手続き
      • オペレータは、特殊形式やマクロのように、引数がevalされないもの。手続きは、引数がevalされるもの
    • レキシカルクロージャが持つべき「環境」も一緒に持つ必要があるが、それはどう表現されるべき？
      • レキシカルクロージャが参照する外部変数という意味なら、uuidオブジェクトでいいのでは
  • mapもしくはhash-table相当
    • なくてもどうにかなるものなので、とりあえず後回しにする

書きかけのメモ

• 前述の「S式逆rfc822書式(仮名)」は、「sexpr with metadata format like reversed rfc822」の略として、「swmflrr」という名前とする事にした。あとで子ページを作る事。

• dpsの「環境」は、plan9モデルが参考になるかも
• 「計算」は「クライアント側で行う」事に。クライアントが多少信頼できなくても、それは「量子ゆらぎ」的な扱いとする。有意な不正があるかどうかは、journalログで判断する。
  • つまり、journalログ処理プロセスは、gcだけでなく、検証も行う必要がある、という事
    • この不正検証には、自システムを再帰的に利用したい、が、あとまわしで
• ストレージもバージョン情報を持つ必要あり
  • systemテーブルのversionエントリあたりに入れておき、これをチェックできるAPIを用意する
  • ストレージのバージョンアップは別途スクリプトを用意する。
    • このバージョンアップは、元ストレージを破壊しないように、「別pathに、バージョンが新しくなった複製を作る」ようなロジックとする事。
• op/fnも、内部にバージョン情報を持つ必要あり
  • おそらく確実に、あとで構造をより良くしたくなると思われる為。
  • 要は、実行ファイルがa.out形式だったりELF形式だったりするような感じに近い。
  • 古いバージョンの実行形式もサポートする必要あり
• op/fnは、実行タイミングについての何らかの指示ができるようにする必要がある
  • 要は、perlでのBEGINブロックのようなもの
  • op/fnは、そのままでは、評価タイミングは通常の手続きと同じタイミングになる。しかし、マクロのような事をしたい場合、それでは困る。なので、これが必要という事。どうする？
• undefの扱いについての変更点
  • セキュリティ的な観点より、値がundefのエントリを作ったら、そのエントリを作ったプロセス(もしくはその親類)からしか更新できないように工夫する必要がある
  • でも、エントリのkeyはuuidで返されるので、それが漏れない限りは、既にそうなっているのでは？
• uuid->valテーブルのvalの書式は、S式逆rfc822書式(仮名)とする
  • 行指向のデータであり、最初の一行目にデータ本体をwrite/ssしたものを置き、二行目以降はメタデータをkeywords書式で記述していくものとする
  • このフォーマットを採用する事により、dpsプロトコルで巨大なデータを送る際に、データ本体をparse/deparseする事なく、直に送信できる可能性が高い(zmqのインターフェースによってはできないかもしれないが)
• ロジックはなるべく、ハードコーディングせずに、さっさとインタプリタ上のコードとすべき
• systemテーブルに、ストレージ全体のcorrupt度を示すエントリを用意する？
  • gc/検証プロセスが、このエントリを更新する？

インターフェース

以下の下位APIを用意する。この上に上位APIを構築する

• key->uuidテーブルからのread問い合わせ
• key->uuidテーブルへのwriteリクエスト
• uuid->valテーブルからのread問い合わせ
• uuid->valテーブルへのエントリ作成
• uuid->valテーブルへのwriteリクエスト(値がundefのエントリのみ許可)
• システムテーブルへのアクセス

ライブラリ仕様

• テーブル類について
  • 今のところはgdbmを使う
    • fsdbmはキー長に制約がある、qdbmはクラッシュ時に高確率で破損する為
    • 他にdbm系で良い選択肢があれば、そっちがいい
      • 将来的には、memcached等のnosql系にする予定
        • でもnosql系でも、ラッパーとしてdbmモジュールを経由させるなら、流用可能
    • 具体的には、以下の構成とする
      • key->uuidテーブルはdbm。keyはS式(:key-convert #t)。valはuuid文字列。
      • uuid->valテーブルはdbm。keyはuuid文字列。valは前述のS式逆rfc822書式(仮名)。
      • systemテーブルはdbm。keyは文字列、valはS式(:value-convert #t)。
      • journalログは指定ディレクトリ内の複数ファイル。書式は行指向S式。ファイル名は一定サイズになったらrotateされる(rotateのルールはカスタマイズ可能としておく事)

ロードマップ

1. まずライブラリとして実装
   • 実ストレージ操作モジュール
   • 抽象クラス定義モジュール
2. 実ストレージおよび抽象クラス定義ができた段階で、格言管理を作り、動かす
3. 通信プロトコルを確定し、デーモン化
   • 実通信ドライバとして、zeromqを採用予定(仮)
4. dps:interpreter作成
5. 某プロジェクト作成

関連

• wdsm(仮)
  • 以前に考えた仕様
• rdmms
  • zeromqを使う練習を兼ねて作る、リモート動的モジュール管理サーバ