Diff as a Service
差分を扱うのが得意なサーバーサイドフレームワークを作りました。
https://github.com/rikuTanide/isyumi_deltist
概要
僕はFirestoreにViewを作る！
問題意識
Firestoreはどこまで正規化するべきか問題があります。
バックエンドを書いている時の僕はできるだけ正規化したい派です。
しかし、クライアントを書いている時の僕はそのまま表示できる形式で渡してほしい派です。
また、僕は「非正規形のデータを直接いじるプログラムを書くと絶対間違える」という硬い信念を持っています。
なので、非正規形データは正規形データから純粋関数で展開するべきだと思います。
解決策案
単純な解決策
正規化したデータと非正規化したデータを別々にFirestoreに保存する。正規形データが変更されたら非正規形データをまるごと更新する
豪快にやっちゃいます。
データ量が少ないなら一番簡単な方法です。
しかし、データ量が増えてきたら無理です。read/writeの遅延や課金が大きくなります。
現実的な解決策
正規化したデータと非正規化したデータを別々にFirestoreに持つ。正規形データが変更されたら非正規形データを更新する 。ただし、どの正規形データへの更新がどの非正規データに伝播するか細かくプログラミングする
今の所の最善策だと思います。
このやり方には２つの欠点があります。
一つはテーブルとビューの依存関係を洗い出すのがめんどくさいことです。どのテーブルへの変更がどのビューのどの行に影響するかを確実に洗い出すのは難しいことです。
もう一つは、最適化をしたいならコードを沢山書かないといけないことです。例えば商品ごとの売上なら、売上が発生するごとに売上一覧を集計して出すより、前回の計算結果に今回の売上を加算したほうが速いです。
このような最適化の余地はたくさんありますがめんどくさいです。
夢想的な解決策
全部オンメモリでビューを計算する
まず、全てのテーブルを元に全てのビューをつくる関数を一つ用意します。
メモリに現在のテーブルを載せておき、どこかに変更が発生したらその関数を実行します。
そして前回作ったビューと今回のビューの差分をチェックしてFirestoreを更新しに行けばいいかと思います。
この方法の最大の欠点はメモリ使用量です。
EC2でも、2~4GBよりたくさんのメモリを使えるインスタンスは高いです。
最終解決策 イシュミ・デルティスト
そこで僕は、フレームワークを作りました。
プログラマはこの２つをします。
フレームワークはこれをします。
- 起動時
- JSONなどでエクスポート出来る形式でビューを実体化する
- テーブルの変更イベント受信時
- ビューを差分更新する
- どんな差分が発生したのかを出力する
テーブルとビューのデータはディスクに保存してあるのでメモリをほとんど使いません。
また、どのビューのどの行がどのテーブルのどの行に依存しているかについて細かい依存グラフを作成しているので、最短距離で差分更新できます。
あとは、このフレームワークが返してきたDIFF情報をそのままFirestore APIに書き込めばOKです。
Viewができた！
使い方
デルティストは単純なステートマシンです。
ReduxのReducerに似ています。
Tableへの書き込みイベントを引数にビューの差分が帰ってくる関数です。
返ってくるのは新しいビューではないです。
その中で変更があった行だけが返ってきます。
疑似コードですがこんな感じに動きます。
売上一覧テーブルに鉛筆の売上を挿入したら「月ごとの売上合計ビュー」と「商品ごとの売上ビュー」が１行ずつ変更された
void main() {
var db = new Database();
var diff = db.insert("Sales", {productID: 'pencil', date: '2019-09-01' });
print(diff);
}
出力
[
{
viewName: 'SalesParMonth' ,
data: {year: 2019, month: 8, sum: 1000},
},
{
viewName: 'SalesParProducts',
data: {productID: 'pencil', productName: '鉛筆', sum: 500 }
}
]
Firestoreで使うことを想定していますが、入出力は単純な構造体なので何にでも使えます。
ブラウザからWebSocketで直接つなぐこともできますし、MySQLにMaterialized Viewを作る用途で使うこともできます。
ディスクを使うのでLambdaやGAEなどで使うことはできません。
EC2インスタンスが一つ必要です。
ロードバランスやSPOF回避の仕組みは何も考えていません。
実装方法
デルティストはビューを作る途中の仮想テーブルも全てビューとみなし実体化してディスクに保存しています。
デルティストでは３個以上のテーブルやビューをJOINする方法はありません。JOINは２個に限ります。
３個以上のテーブルやビューをJOINしたければパラマス式トーナメントにします。
そしてそれぞれを実体化します。
例えば４個のテーブルをJOINしてビューを作るなら、合わせて３つビューが実体化されることになります。
下の図の場合、本当にほしいビューがView3ならこうなります。
Table1 -┐
|-View1┐
Table2 -┘ |-View2-┐
Table3 --------┘ |-View3-
Table4 ----------------┘
テーブルが更新されると、ビューに行変更イベントを通知します。
受け取るのはテーブルに直接依存しているビューだけです。
変更イベントを受け取ったビューは、そのイベントを元に自分を変更しないといけないかどうかを判断します。
もし変更があった場合は自身を書き換えてから行変更イベントを作成しディスパッチします。
それを再帰的に行うと全てのビューが更新されます。
この時の重要なのが、最小コストでビューを更新出来るようにすることです。
例えば、TweetsテーブルとUsersテーブルをJOINしてTimelineビューを作るとします。Tweetsテーブルに一行挿入されたらUsersテーブルからそのTweetのuserIDと一致するUsersテーブルの行だけを取得してJOINしてTimelineビューに挿入します。
逆にUsersテーブルから行が削除されたらTimelineビューの中でuserIDが一致するツイートだけを削除します。
実体化したビューはRocksDBというデータベースで保存します。
RocksDBはKVSです。
TableとViewのPrimary Key == KVSのKeyです。
DBサーバーではなくCのライブラリとして使えるので運用が楽です。
デルティストは1万行の中の1行を書き換えるような処理が多いので、RocksDBのLSM-Treeというアルゴリズムと相性がいい（らしい）です。詳しくは知りません。
大変だった点
始めてDartのC++インテロップを書きました。大変でした。
どういう文法だったらプログラマにわかりやすくて間違えにくいか一生懸命考えました。
データを設定する時に文字リテラルでテーブル名やカラム名を指定するようなことはしたくなかったです。
// 嫌な例
row.set("Tweets" , "UserID", 10);
これは誤字脱字が発生します。
このように書きたいです。
row.set(tweets.userID, 10);
この時型を間違ったらコンパイルエラーにしたいです。
row.set(tweets.userID, "10"); // 第二引数がintじゃないのでエラー
Dartの型システムの強さに救われました。
ビュー更新の実行計画
アルゴぢからが足りないため、大変苦労しました。
やることは各演算のオペランドが増えたときと減った時にそれぞれ前回の結果からどう変わるかを１個ずつプログラミングすることです。
例えばMax関数なら
- Insert
- 入って来た数が既存のMaxより大きい -> Maxを更新
- 入って来た数が既存のMaxより小さい -> 無視
- Delete
- 消した数が既存のMaxと等しい -> 二番目をMaxに昇格
- 消した数が既存のMaxより小さい -> 無視
みたいなコードをいっぱい書きます。
インデックス
RocksDBはRDBのようなインデックスの機能がありません。
その代わりPrefix Seekという機能があります。キーのビット列が前方一致する行を全て列挙してくれます。
つまり主キー以外の属性で行を取得したいなら、その属性をキー、テーブルの主キーをバリューにしたKVSを別に作っておく必要があります。
例えば、Timelineビューの主キーはtweetIDだったとします。
ユーザー名が変更された時にTimelineビューを更新するにはuserIDをキー、tweetIDをバリューにしたKVSが必要です。
どんなインデックスが必要なのか全て洗い出すのが大変でした。
進捗
今のところ完成している機能は
- INNER JOIN
- UNION
- SELECT
- Optional型
- Float型
- 負の数
開発中・調整中なのが
- GROUP BY
- MAX
- MIN
- COUNT
- AVERAGE
- ARRAY
- OUTER JOINとLEFT JOIN
- RANK
- WHERE
- UPDATEの高速化（Insert/Deleteに比べてUpdateは最適化可能性が多すぎるのでだいぶサボってる）
- 生成列
- 初期データ
構想中なのが
- Infinite ScrollのためのSelect機能
- 休眠ユーザーを識別して計算量をサボる機能
です。
引き続きがんばります。
