ircのログ見ちゃったのでDripの言い訳をしますね

Dripのときのircログ見てました。なんというか、ちゃんとした話されててうれしい。

Dripの完成度

Dripの今の実装は、今私があつかっているデータ量で困らないようなものを選んでます。

現在のDripで自慢したいのは選択した少ないAPIです。RMIでコストがかからなくて、計算量がひどい目に合わなくて、並列処理のイヤなことから逃げ出せるようなAPIを選んでます。TwitterのAPIなんかも似たようなのあるんでそんなにはずしてないんじゃないかと思ってます。

計算量はだいたいO(log N)

Rindaの反省から線形探索はしなくてよいような外部仕様にしてあります。
read系はキーの2分探索のコストで見つかります。read_tagはタグの2分探索のコストで見つかります。
現在の実装は赤黒木の外部ライブラリRBtreeを使ったものとArrayを使ったものがありますがどちらにしろ二分探索です。
readの際はキーの整数で並べてる列を調べ、read_tagでは[タグ, キー]をキーとした列を調べます。[キー,タグ]でないところがミソ。タグの最新はタグの次のタグ（タグ + "\n"）の直前の要素を返します。この実装だとtagsも簡単にできるんだけど、イヤな予感がするので一度実装してから削除しました。

ここでRindaのときのように任意のオブジェクト、例えば正規表現なんかと===でマッチングさせたりすると、かっこいいけど線形探索になっちゃうので単純な比較としました。

もしもDripのユーザが私以外にも存在して、タグを==以外で検索したいってなったら、外部の検索エンジンに入れちゃおうかと思ってます。

キーはだいたい時刻

キーは時刻から作られた整数です。64bitマシンならFixnumみたいです。

  def time_to_key(time)
    time.tv_sec * 1000000 + time.tv_usec
  end

もしコリジョン(?)が発生した場合は、後から来た方に1足します。
というよりも、コードでは現在時刻から作ったキーと自分が知ってる最新のキー+1を比べて大きい方を採用します。
「パソコンの時刻設定しちゃった。えへ」みたいなときに困りそうだったのでこういう安易な実装にしました。

  def make_key(at=Time.now)
    synchronize do |last|
      key = [time_to_key(at), last + 1].max
      yield(key)
      key
    end
  end

キーはイベントが発生した時刻ではなく、Dripがそれを受け付けた時刻と考えます。世界では同時にいろんなことが起きるけど、自分のメモ帳にメモできるのは一本のペンだけなのです。

メモリに入るのはどこか

今の実装では赤黒木はメモリに置いてあります。TokyoCabinetみたいなのもあるから外に追い出せなくもないと思うけど、今はそうなってます。「値」は最新の数個（設定可能）だけメモリにあって、それ以前のはプレーンなファイルから読み出します。

過去の情報は変化がないのでプロセス（マシン）わけるのも簡単なので、必要になったら書きます。

削除について

稼働中のDripから要素を削除したり更新したりする機能はつけないつもりです。停まってるDripからある時刻以前の要素を削除することは可能（というかできちゃう）ので旧すぎるのは忘れていくこともできると思います。

削除がないのは、「削除したと思え」って追記すれば良いから要らないじゃん。CVSもgitも実質的には追記だもんね。

今後の展開

とりあえず本を書け > 自分
つーかこっちも読んでね > http://d.hatena.ne.jp/m_seki+b/