わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

即興で,実現方法を提案する

1. 小ゼミにて

「発表スライドの中で出た『アクセス履歴の管理にKVSが使われる』について,そのためのKeyとValueの設定方法を,考えてみましたんで,ホワイトボードに書きますね.実際にこういう方法がとられているかは分らないし,僕が2,3分で考えたことなので,新規性もないと思われます.
「対象としては,mixiなんかの足あと管理とします.利用者は,最近の10件だとか30件だとか,いつ誰からのアクセスがあるかを見ることができて,サーバ側ではそのためのデータを管理することにします.
「それで,KeyとValueですが,まずKeyには,『誰に』のユーザID,それと番号とします.Valueは,『誰から』のユーザIDと『いつ』の情報です.それぞれ,Key,Valueとして適切なビット列またはバイト列になるよう,何らかのコーディングをするものとします.
「最大の疑問は,Keyの中に入れた番号ですね.これは,最近の10件だとかいうのと別の,通し番号になります.この値については,もう一つ別のデータ構造を定義し,アクセス方法を決めてから,振り返ることにします.
「もう一つのデータ構造も,KeyとValueのペアで表現します.こちらのKeyは,『誰に』のユーザIDで,Valueは,番号です.先ほどの通し番号を踏まえるなら,『通し番号の最大値』と言ってもいいでしょう.
「さて,あらかじめ値が格納されている状態で,『誰に』のユーザID…Uと書くことにしましょう…これを与え,最近の10件の『誰から』『いつ』の情報を求めるには,まず,2番目のKey Valueストア*1を使って,Uに結びつけられた番号を取り出します.この値をNと書くことにします.
「次に,先に定義したKey Valueストアで,UとNのペアをKeyとして,Valueを取り出します.これが『最も新しい,Uへのアクセス』となります.次に,UとN-1のペアをKeyとして,Valueを取り出せば,『その次に新しい,Uへのアクセス』です.そんな感じで10回繰り返せば,ほしい足あと情報になります.DBMSへの1回のクエリよりも,KVSのそれが数十倍速ければ,十分に元が取れます.
「足あとの登録については,『誰に』のU,『誰から』のV,『いつ』のTを既知として,次の手順を踏みます.まず,足あと履歴参照と同じように,Uから,Nを取得します.次に,KeyとしてUとN+1,ValueとしてVとTを,それぞれ適切にエンコーディングし,KeyとValueのペアとして登録します.最後に,2番目のKey Valueストアに対して,Uに結びつける値をN+1に更新します.
「というのがナイーブな方法ですが,Nがいくらでも大きくなるのが,気になります.結局これでは通し番号です.このやり方で,すべての足あとを記録しておくというのは,Key Valueストアにけっこうな負担がかかります.
「ですが,番号に上限値を設けておいて…例えば255までとしますか…取得したNがその上限値であれば,N+1の代わりに0にしてしまえばいいのです.足あと検索の際にも,0の一つ前は,-1ではなく上限値とします.このような,循環型の番号表現を利用して,古い履歴情報は上書きされるようにすれば,ユーザあたりの最新足あとのレコード数,そして全体としても必要な,Key Valueストアのデータサイズを,一定数に保つことができるのです.

小ゼミの後で考えたこと

「しまった,Valueの長さに制限がないなら,Keyを『誰に』のユーザID,Valueにそのユーザへの足あとリスト(『誰から』『いつ』のリスト)にするほうが単純じゃないか!!

2. 家族旅行の前に

大阪駅まで行かなあかんやんか」
  「せやな」
貴志川線阪和線の時刻,これで行こうと思うんやけど」
  「うん,それでええんやないかな.ただ…」
「おかしい?」
  「いや,和歌山駅紀州路快速に座りたいよな」
「せやね.座られへんかな」
  「たぶん…いったん改札を出て,大阪までの切符を買って,改札を通って,ホームに行ったら,すでに列車は入っていると思うねんな」
「それに乗ったらええんやろ?」
  「いやいや,すでに他の人が,ボックス席のところに座ってる可能性があるんや」
「土曜日の朝やし,始発なんやし,いけるんちゃうかな」
  「いやあ,休日のこの時間は,不安やね.1分でも早く,乗り込みたいなあ」
「何かいい方法ある?」
  「方法としては…最も単純なのは,俺以外は先にそのホームに行って,俺だけ改札を出て切符を人数分,買うことかな」
「そんなんでいけるの?」
  「違法ではないはず.まあ,大阪駅を出るときには,入札の記録がないから,有人の改札を通らなあかんけどな」
「ほんなら,あたしらどこに乗ったらええんかな?」
  「そらまあ座れるところに.んでケータイで,何号車に乗ったと電話してくれれば」
「なるほど」
  「ちなみに,娘が駅の中を歩きたいともし言うんなら,逆転の発想もあるぞ」
「どんなん?」
  「俺だけが先に,荷物を持って列車に乗り,他のみんなが改札を出て切符を買うっちゅうこと」
「あなた,切符は?」
  「ICOCAのカードがあるからな.貴志川線の改札を出てすぐの機械でピッとすれば,(駅の)改札に出んでもJRに乗れるんや」
「ふーん,そんな方法もあるんや」

結局どうした?

自分のみICOCAを使い,他の同行者は,貴志川線和歌山駅の改札でもらった切符を持って,すぐに紀州路快速に乗り込み,列車の中で,車掌さんから大阪までの切符を買いました.
無事に座れました.始発でボックス席は埋まってしまい,1席でほんの少し空きがありましたが,その空きも,紀伊駅を出たときにはなくなっていました.

*1:Key Value Storeの総称をKVSと書き,データをアクセスする対象をKey Valueストアと表記しています.個人的な語感による書き分けです.「データベース」についても,ときには総称,ときにはアクセス対象(アクセス時に指定する名前)の意味で使われ,混乱することがあるのですが.