LISPUSER

CL-PREVALENCELisp isn't a language, it's a building material.

(Top Page) (Lisp Memo)

公式ページhttp://common-lisp.net/project/cl-prevalence/

翻訳

CL-PREVALENCE

CL-PREVALENCE とは Sven Van Caekenberghe 氏による ObjectPrevalence の Common Lisp 実装です。 CL-PREVALENCE は S-XML を使用した XML シリアライズプロトコルを用いています。 また、より Lisp ライクな S 式ベースのシリアライズプロトコルも存在します。

Object Prevalence 2001 年に Klaus Wuestefeld によって提案された、シンプルでかつ興味深いコンセプトを持った技術です。 IBM developerWorks にわかりやすい 入門記事 があります。 Java による主な実装は Prevayler と呼ばれており、Wiki サイト（雑然としています）に多くの情報と活発な議論があります。 Object Prevalence の主要な特徴のほとんどは学術論文 A Simple and Efficient Implementation for Small Databases (Birrell, Jones, and Wobber 1) で説明されています。 基本的なアイデアは以下のようなものです。

  • ほとんどのデータベースは、数百メガバイト程度のサイズしかないか、それよりも小さい
  • ほとんどのコンピュータは数百メガバイトのデータを RAM 上で操作できる。（大きなサーバなら数ギガバイト程度のデータを扱える）
  • オブジェクトをデータベースにマッピングするのは退屈で時間の無駄であるばかりか、複雑になったりエラーがでたりしやすい
  • データベースを捨てて、ドメインモデルオブジェクトをデーターベースとして使用することにしましょう
  • オブジェクトをファイルシステムのような永続領域にシリアライズしたり、デシリアライズして永続領域からオブジェクトを取り出せるようにしましょう
  • もしドメインモデルオブジェクトの完全な集合を永続領域の保存したいなら、スナップショットを作りましょう
  • クエリーとしてプログラム言語のデータ構造操作機能を使います。RAM 内のデータに対しては非常に高速ですから。
  • データとトランザクションを実行する関数を結びつけたトランザクションオブジェクトを使ったオブジェクトモデルを理解してください
  • ACID 属性を確保するために、それぞれのトランザクションを実行した後に、シリアライズして永続化します。これを **トランザクションログ** と呼びます。
  • 意図したか意図していないかに関わらず、システムがシャットダウンした時には、最初に最新のスナップショットをロードし、それぞれのトランザクションログを再実行してリストアします
  • トランザクションは決定的で、かつ、リエントラントでなければなりません (そして、必要ならば時刻を記録しておく必要があります)
  • マルチスレッドシステムでは、トランザクションはグローバルにシリアライズされます

これで Object Prevalence のコンセプトはすべてです。利点と制限事項の詳細は以下の通りです。

  • 最近のコンピュータの実装は優れているため、一秒間に数千トランザクションを実施し、また同じ速度でそれをリカバリーできます
  • トランザクションはシステムをブロックするため、短時間で完了しなければなりません - 全てが RAM 上にある間は対した問題ではありません
  • 完全に一貫したシテム状態を必要とするクエリーは、システムをブロックしなければなりません - さほどクリティカルでないクエリーは並列に実行できます
  • 実用上、トランザクションを実行する時にはまずシステムの状態をチェックし、必要ならエラーを返す必要があります。全てが一貫している時にのみシステムに変更を加えるようにします。トランザクション中は単独のスレッドのみがアクティブにならなければなりません。クエリーは可能なかぎり高速にデータを取得できます。この実装ではトランザクションは実行が成功した後に記録されます。
  • この実装ではトランザクション中に予期しないエラーに遭遇した場合に、（システムをリストアする事による）ロールバックが選択できます。トランザクション中でエラーが発生した場合に false を返す（ もしくは no-rollback-error や、それを継承する事により）ロールバックするかどうかの条件を指定する事ができます。
  • 長時間に渡るトランザクションは問題となります
  • マスタとなるトランザクションログをレプリカに送ることにより、簡単にレプリケーションやクエリーのロードバランシングが可能です。また、バックアップやフェイルオーバーも実現できます。しかし、この実装はレプリケーションをまだ含んでいません。

CL-PREVALENCE のコードは Sven Van Caekenberghe によって書かれました。

日本語情報

CL勉強会向けの資料の下書き。サボっていたらスライドに起こす時間がなくなっちゃったのでこっちで公開。

CL-PREVALENCE による永続化入門 - 前篇 (CL勉強会2008/10/25)

仕組みの説明

CL-PREVALENCE の仕組みは以下の通りです。

  1. メモリ上にルートオブジェクトを用意
  2. 管理したいオブジェクトはルートオブジェクトから参照する
  3. 管理下オブジェクトのスナップショットをファイルに書き出す
  4. オブジェクトへの変更をトランザクション単位にする
  5. CL-PREVALENCE がトランザクションを実行することで、オブジェクトを変更する (このとき、トランザクションをログファイルに書き出しておく)
  6. 適当なときにスナップショットを取る

これだけで、シンプルなオブジェクトデータベースの完成です。

万が一、作業中にプロセスが中断された場合でも、スナップショットをロードしたあとトランザクションログをリプレイすることで復帰することができます。

メリットデメリット

  1. 簡単
  2. オブジェクトがそのままつかえる
  3. 途中で中断しても大丈夫

概要

(make-prevalence-system [ディレクトリへのパス])指定したディレクトリを使った永続化システムを作成する
(snapshot [システム])スナップショットをとる
(restore [システム])スナップショットとトランザクションログから復元
(make-transaction [関数名] [引数…])トランザクションオブジェクトを作成する
(execute [システム] [トランザクション])トランザクションを実行する
(get-root-object [システム] [キ−])ルートオブジェクトハッシュからキーに対応する値を取得
(setf (get-root-object [システム] [キ−]) [値])ルートオブジェクトハッシュのキーに対応する値を設定

さらにマクロや関数として次のようなものがある。

(execute-on ([トランザクション] [システム] [引数…])execute + make-transaction の省略形
object-with-idオブジェクトIDカウンタで管理されたクラス
(tx-create-id-counter [システム])オブジェクトIDカウンタ作成用のトランザクション
(tx-create-object [システム] [クラス] …)オブジェクト作成用トランザクション
(tx-delete-object [システム] [オブジェクトの削除])オブジェクト削除用トランザクション
(tx-change-object-slots [システム] [オブジェクト] [(スロット名 値) のリスト]オブジェクトのスロット更新用トランザクション

ルートオブジェクトとスナップショット

まず下記コードをコンパイル & ロードします。 

(defpackage :tutorial (:use :cl :cl-prevalence))
(in-package :tutorial)

(defvar *datastore* #P"/tmp/prevalence-db/")
(defvar *system* (make-prevalence-system *datastore*))

(defun step1 ()
  (setf (get-root-object *system* :fixnum) 1024
         (get-root-object *system* :string) "初期値"
         (get-root-object *system* :list)   '(1 2 3 4)))

(defun step2 ()
  (setf (get-root-object *system* :string) "失敗するよ"))

では、ルートオブジェクトに値を入れてみましょう。 

CL-USER> (in-package :tutorial)
#<PACKAGE TUTORIAL>
TUTORIAL> (step1)
NIL
TUTORIAL> (get-root-object *system* :fixnum)
1024
T
TUTORIAL>

設定できたようです。ここでスナップショットを取ってみます。 

CL-USER> (snapshot *system*)
NIL

すると /tmp/prevalence-db/snapshot.xml というファイルが作成されます。 この XML は直接人間が読むためのものではなく非常に読み難いので、 整形したものを次に示します。 

<HASH-TABLE ID="1" TEST="EXT::FASTHASH-EQ" SIZE="3">
  <ENTRY>
    <KEY><SYMBOL>:LIST</SYMBOL></KEY>
    <VALUE><SEQUENCE ID="2" CLASS="CL:LIST" SIZE="4"><INT>1</INT><INT>2</INT><INT>3</INT><INT>4</INT></SEQUENCE></VALUE>
  </ENTRY>
  <ENTRY>
    <KEY><SYMBOL>:STRING</SYMBOL></KEY>
    <VALUE><STRING>&#x521D;&#x671F;&#x5024;</STRING></VALUE>
  </ENTRY>
  <ENTRY>
    <KEY><SYMBOL>:FIXNUM</SYMBOL></KEY>
    <VALUE><INT>1024</INT></VALUE>
  </ENTRY>
</HASH-TABLE>

中身はこのように XML 形式でシリアライズされたルートオブジェクト（ハッシュ）になっています。

注意点

次に良くある間違いを紹介しましょう。 

(defun step2 ()
  (setf (get-root-object *system* :string) "失敗するよ"))

このようなルートオブジェクトを変更する関数を呼び出してみます。 

TUTORIAL> (step2)
失敗するよ
TUTORIAL> (get-root-object *system* :string)
"失敗するよ"

一見、ちゃんと書き換えられてるように見えるが実はこれには大きな問題があります。 一体なにがおかしいのでしょう？

[考える時間]

最初に紹介したときの PREVALENCE の紹介を覚えていますか？ 再掲しましょう。 

   4. オブジェクトへの変更をトランザクション単位にする
   5. CL-PREVALENCE がトランザクションを実行することで、オブジェクトを変更する (このとき、トランザクションをログファイルに書き出しておく)

そう、この setf はトランザクションではないのです。 あなたの setf は更新時にトランザクションログに出力しますか？ 大抵はメモリ上の値を設定しておわりでしょう…少なくとも標準では。

つまり CL-PREVALENCE の関知しない操作であるため、 4. を満たしておらず、結果的に 5. が実行されないということです。 結果としてこの操作 (setf) は永続化されておらず、何がおこるのでしょうか？ 

TUTORIAL> (restore *snapshot*)
NIL
TUTORIAL> (get-root-object *snapshot* :string)
"初期値"

このとおり、restore を呼ぶと初期値に戻ってしまい変更は失なわれました。 大事なデータじゃなくて幸いでしたね。

加えた変更を記録するには、スナップショットを取るか、あるいはトランザクション機能を使います。 スナップショットは今みたとおり、ルートオブジェクトから参照されているオブジェクトをシリアライズして snapshot.xml に出力する機能でした。次に紹介するトランザクションはもっと細かい単位での制御を可能とします。

トランザクション

オブジェクトへの操作はすべてトランザクションを通じて実施します。 次のようなコードを定義してみましょう。 

(defun tx-test-1 (system text)
  (setf (get-root-object system :string) text))

(defun step3 ()
  (execute *system*
    (make-transaction 'tx-test-1 "今度はうまくいく")))

これを使ってルートオブジェクトを書きかえてみます。 

TUTORIAL> (step3)
"今度はうまくいく"
TUTORIAL> (get-root-object *system* :string)
"今度はうまくいく"
T
TUTORIAL> (restore *system*)
NIL
TUTORIAL> (get-root-object *system* :string)
"今度はうまくいく"
T

今度はうまくいったようです。ヒマな人は一旦 LISP プロセスを再起動して確認してみるといいでしょう。 続いて、 CL-PREVALENCE の本領であるオブジェクトのシリアライズも見ておきましょう。 

(defclass Person ()
  ((name :initarg :name :accessor name-of)
   (address :initarg :address :accessor addres-of)))

(defun tx-test-2 (system name address)
  "オブジェクトを作成する"
  (setf (get-root-object system :person) (make-instance 'person :name name :address address)))

(defun tx-test-3 (system name address)
  "オブジェクトを更新する"
  (let ((object (get-root-object system :person)))
    (setf (name-of object)    name
          (address-of object) address)))

(defun step4 ()
  (execute *system*
     (make-transaction 'tx-test-2 "タナカ" "ニホン"))
  (execute *system*
     (make-transaction 'tx-test-3 "タナカ（更新）" "ニホン（更新）")))

オブジェクトを作って、更新してみます。 

 TUTORIAL> (step4)
 "ニホン（更新）"
 TUTORIAL>

この状態で datastore のディレクトリを参照すると以下にようになっています。 

  -rw-r--r-- 1 onjo lambda 455 2008-10-25 19:53 snapshot.xml
  -rw-r--r-- 1 onjo lambda 302 2008-10-25 19:53 transaction-log-20081025TXXXXX.xml
  -rw-r--r-- 1 onjo lambda 972 2008-10-25 19:53 transaction-log.xml

transaction-log.xml がその名の通りトランザクションログです。 中をのぞくとトランザクションオブジェクトがシリアライズされたものになっています。 

<OBJECT ID="1" CLASS="CL-PREVALENCE::TRANSACTION">
  <SLOT NAME="CL-PREVALENCE::ARGS">
    <SEQUENCE ID="2" CLASS="CL:LIST" SIZE="1">
      <STRING>&#x4ECA;&#x5EA6;&#x306F;&#x3046;&#x307E;&#x304F;&#x3044;&#x304F;</STRING>
    </SEQUENCE>
  </SLOT>
  <SLOT NAME="CL:FUNCTION"><SYMBOL>TUTORIAL::TX-TEST-1</SYMBOL></SLOT>
</OBJECT>
<OBJECT ID="1" CLASS="CL-PREVALENCE::TRANSACTION">
  <SLOT NAME="CL-PREVALENCE::ARGS">
    <SEQUENCE ID="2" CLASS="CL:LIST" SIZE="2">
      <STRING>&#x30BF;&#x30CA;&#x30AB;</STRING>
      <STRING>&#x30CB;&#x30DB;&#x30F3;</STRING>
    </SEQUENCE>
  </SLOT>
  <SLOT NAME="CL:FUNCTION"><SYMBOL>TUTORIAL::TX-TEST-2</SYMBOL></SLOT>
</OBJECT>
<OBJECT ID="1" CLASS="CL-PREVALENCE::TRANSACTION">
  <SLOT NAME="CL-PREVALENCE::ARGS">
    <SEQUENCE ID="2" CLASS="CL:LIST" SIZE="2">
      <STRING>&#x30BF;&#x30CA;&#x30AB;&#xFF08;&#x66F4;&#x65B0;&#xFF09;</STRING>
      <STRING>&#x30CB;&#x30DB;&#x30F3;&#xFF08;&#x66F4;&#x65B0;&#xFF09;</STRING>
    </SEQUENCE>
  </SLOT>
  <SLOT NAME="CL:FUNCTION"><SYMBOL>TUTORIAL::TX-TEST-3</SYMBOL></SLOT>
</OBJECT>

これをS式風に解釈すると次にような「関数呼び出し」をシリアライズしたものである事がわかります。 

 (tx-test-1 "今度はうまくいく")
 (tx-test-2 "タナカ" "ニホン")
 (tx-test-3 "タナカ（更新）" "ニホン（更新）")

これはトランザクションにいくつかの制限がある事を意味するんですね。

  1. 乱数など非決定的な関数は意図しない結果を引き起す
  2. トランザクション関数が変更になった場合には、正常に復元できない

続いて上記の制限を解説しましょう。

execute + make-transaction == execute-transaction

ちょっとその前に。

ここまでに出てきた execute -> make-transaction の組み合わせは非常に良く使われるため、 execute-transaction というマクロが用意されています。 

(execute *system*
   (make-transaction 'tx-test-2 "タナカ" "ニホン"))
↓
(execute-transaction
  (tx-test-2 *system* "タナカ" "ニホン"))

この execute-transaction マクロは system の持ち周りと make-transaction の追加をおこなってくれます。 execute-transaction のほうが defun tx-test-2 (system name address) の引数リストとの 1:1 に対応して見やすいため、今後はこちらを使うことにします。

トランザクションの動作は決定的でなければならない

まずは、トランザクションが決定的でなければならないという点について。 例としては次のようなものがあります。tx-test-4 は乱数を含んでいます。 

(defun tx-test-4 (system n m)
  "ダメな例"
  (setf (get-root-object system :bug-random) (loop repeat (random n) collect (random m))))

(defun step6 ()
  (execute-transaction
   (tx-test-4 *system* 10 100)))

では動作を見ていきましょう。 

TUTORIAL> (step6)
(13 46 64 81 22 32 85)
TUTORIAL> (get-root-object *system* :bug-random)
(13 46 64 81 22 32 85)
T

更新されました。この時のトランザクションログは (tx-test-4 10 100) です。では、このログをリプレイすると どうなるでしょうか？ 

TUTORIAL> (restore *system*)
NIL
TUTORIAL> (get-root-object *system* :bug-random)
(42 26)
T

あー、やはり乱数ですので前回と値がかわってしまいました。 さらにもう一度ダメ押しでリプレイ。 

TUTORIAL> (restore *system*)
NIL
TUTORIAL> (get-root-object *system* :bug-random)
(17 21 70 30 67 63 65)
T

ということで、トランザクションは「決定的」なものでないといけないという例でした。 本当のデータじゃなくて良かったですね。うん。

この例だとランダムなリストの生成をトランザクション外に移動して、結果を トランザクション内で設定するように修正するのがいいでしょう。 

(let ((random-list (....))) ;; 先に計算して
  (execute-transaction
    (tx-save-bug-random *system* random-list))) ;; 結果を保存
トランザクションの変更はデータを破壊する可能性がある

では、この状態で REPL から次のコードを入力してみましょう。 

TUTORIAL> (defun tx-test-4 (system n m)
           (setf (get-root-object system :bug-random) (format nil "~A - ~A" n m)))
TX-TEST-4

ランダムなリストを返すはずだった tx-test-4 は今や文字列を一つ返す関数になっています。

この状態でトランザクションログをリプレイすると… 

TUTORIAL> (restore *system*)
NIL
TUTORIAL> (get-root-object *system* :bug-random)
"10 - 100"
T

はい、この通り。型からして違うデータができてしまいました。 こちらは気をつけるしかありまん。影響の大きい変更を行う場合には慎重さとバックアップを準備しておきましょう。

原稿が尽きたので、今回はここまでです。

CL-PREVALENCE による永続化入門 - 後編 (CL勉強会2008/11/XX)

前回の復習

  1. CL-PREVALENCE はルートオブジェクトから参照させるオブジェクトのスナップショットを保存する
  2. トランザクションは (tx-hogehoge param1 param2 …) のように関数呼び出しの形式でシリアライズされる
  3. シリアライズされたトランザクションは、トランザクションログに追記されていく
  4. スナップショットからルートオブジェクトを復元し、トランザクションログからトランザクションを再生する

    Atomic : まぁ、だいたいアトミックです (ディスクにログを書いてる最中にクラッシュとかすると、そのトランザクションは読めない場合があります) Consistency : まぁ、だいたい一貫しています（トランザクションの関数が決定的で、かつ意味がかわってなければ） Isolation : Lisp レベルでは、だいたい一貫しています。基本的にトランザクション中は他のスレッドはブロックされます。 Durability : これも、だいたい永続してます。

特徴

  1. ○最近のマシンなら秒間数千トランザクションが可能、リカバリも同じ速度で可能。
  2. ×トランザクションはなるべく短い時間でおわらせよう（システムをブロックするので…）
  3. ○一貫性が必要なクエリはシステムをブロックする必要がある。あんまり一貫性が重要じゃなければ、並列実行も可能。
  4. ×実用的には、トランザクションは事前に状態をチェックし、必要ならエラーを通知する。すべてが一貫性を保てるように更新する必要がある。トランザクション中に動作するスレッドは一つだけのほうがいいだろう。現在の実装では、トランザクションが実行された後にログが記録される実装になっている。
  5. ○現在の実装では、トランザクション実行中に予期しないエラーが発生した場合に、オプションで「ロールバック」が可能だ。これはリストアすることで実現される。ロールバックが不要な場合にはトランザクションの initiates-rollback が偽を返すようにするか、no-rollback-error を使うこと。
  6. ×長時間実行されるトランザクションは…未解決の問題
  7. ○一つの PREVALENCE システムに複数のクライアントアクセス機能を提供するためにアプリケーションサーバーの技法が使われている
  8. △マスタのトランザクションログを配信してのレプリケーション（と分散クエリ）、バックアップ、ホットフェイルオーバーなどが比較的簡単に実現可能だろう。しかしまだレプリケーションは実装されてはいない。

Baptism Problem

管理されたオブジェクト

オブジェクトデータベースという単語がでてきました。

オブジェクトID / インデックス

ちょっと応用

ふれなかった事

  • シリアライズの方式について (標準では XML 形式です)
  • マスタ - スレーブ構成 (あんま使ってないもんで…)

$Last Upda-te: 2008/10/25 19:19:25 $

Footnotes:

1 FOOTNOTE DEFINITION NOT FOUND: 1987

Powered by Emacs + OrgMode