All Articles

データ指向アプリケーションデザインメモ

このページについて

データ指向アプリケーションデザイン読書の記録をつらつらと書いておく

2章

  • NoSQL

    • ドキュメントデータベース
    • ドキュメント間の関係を意識しなくてよいときに向いている
    • その逆の場合はRDB使う
    • グラフデータベース

    • 潜在的にあらゆるもの同士に関係が存在するものに向いている

      • ソーシャルグラフ
      • 路線図
    • SQLでも再帰共通テーブル式使えばいけるっぽい

3章

  • ストレージエンジン

    • log-structured ストレージエンジン
    • Bツリー ストレージエンジン
    • red-black ツリー
    • AVL ツリー

SSTable: Sorted String Table ストレージのセグメントを表すkey - value のkeyを辞書順で保持しておく仕組み 一定のセグメントでソートしながらkey-valueを分散させ、コンパクションとマージによって
メモリを効率的に使えるようになる。また、探索も効率的に行える(ディスク領域とI/O削減)。

ブルームフィルタとは @Todo

SSTableのマージとコンパクションの戦略には以下2点が提案されている 各DBごとのとっている戦略と組み合わせがこちら

サイズ 階層
cassandra ○ ○
HBase ○
RocksDB ○
LevelDB ○

サイズは新しくて小さいsstableを大きいものに随時マージしていく レベルはキーの範囲を小さなsstable分割し古いデータを分割されたレベルへ移行する

  • Bツリー

    • データベースはページあるいはブロックという単位(4KB)に分割されている
    • キーを探すときには根の上から下に探索を進めていくような感じ
    • 最終的に到達するキーに対する値を示す場所はリーフノードと呼ばれる

    • WAL Write Ahead Log を実装することでクラッシュにも強い仕組みになっている

      • Bツリーへのすべての変更をツリーを操作する前に書き込んでおく

    • Bツリーは木のバランスを維持するために、参照先を分割して新しくNodeを増やしたりする

      • この操作によって探索時にO(logn)が実現されているっぽい。すごい。 一般にLSMツリーのほうが書き込みが早く、Bツリーのほうが読み取りは早い LSMツリーはSSTableやデータ構造を調べないといけない。Bツリーは書き込みの際に木のバランスを考えないといけない 列ストレージ RedShiftとか
  • メリット

  • マテリアライズドビュー

    • クエリ結果のキャッシュ(COUNT, SUM...)

4章

RPC系の仕組みついて。どうやってクライアント <-> サーバが整合性のあるスキーマをやりとりするか。 フィールドに対するキーを連番で管理するなど、バイナリサイズを減らしながら制約を与えている この辺はもう少し自分で触ってみないとなぁ。grpcとかちょっと触っただけだし。。 Thriftとか初めて聞いたAvroはどこか使ってる会社あんのかなぁ。コミュニティでも見ないし。 分散アクターフレームワークAkkaやメッセージング提供のKafkaなどの思想は理解しときたいなぁ こういうことやれるやつでしょ?くらいには。 アクターは子スレッドを発行しつつ、協調や仕事させつつ、振る舞いはいくつか限定するなどの仕組みを提案しているっぽい 分散データ

5章

  • レプリケーションの目的

    • 可用性を高める(マシンを別の地域においてリスク回避)
    • レイテンシを下げる(マシンをユーザの近くにおいて、ラストワンマイルの時間を短縮)
    • スループットを高める(読み取りクエリを処理するマシン数をスケールアウトさせる)

  • レプリケーションアルゴリズム

    • シングルリーダー
    • マルチリーダー
    • リーダーレス

マスタースレーブレプリケーション レプリカ(データベースのコピーを保存する各ノード)の1つはリーダーになる
クライアントはリーダーにデータを送る
リーダーはデータをローカルストレージに書き込み、変更データをレプリケーションログとしてすべてのフォロワー(リーダー以外のノードでリーダーと同じデータを保持する役目を担う)に送信する
データを受け取ったらリーダーと同じようにデータを自身のローカルストレージに書き込む クライアントが 読み取り を行いたい場合は、どのノードにリクエストを投げてもよい
RDB系やMongoなどのNoSQL系、KafkaやRabbitMQなどもこの仕組を採用している

しかし、リーダーに対し、複数のフォロワーへのデータ送信が同期的に行われるとクライアントへのレスポンスが滞ってしまう
そのため、同期するフォロワーと非同期で通信するフォロワーをわけてレイテンシを下げることを一般的には行う。ただ、この場合はリーダーとの一貫性がとれないことがある。

チェーンレプリケーション -> microsoft azure storage @Todo

フェイルオーバー 端的に言うと、リーダーが何らかの原因で仕事ができなくなり、フォロワーからリーダーを選出する状況のこと
リーダーが復旧したときに自身がリーダーとして再び動き始めていないか(スプリットブレイン)確認したり、データの整合性を確認したり、割と確認事項の多い障害である

postgresのレプリケーションで注意する点 ログとして書き込むデータがストレージエンジンに依存するのでリーダーとフォロワーのバージョン違いによってデータが同期できないことがあり得る。レプリケーションプロトコルで許されていないことが多い様子

モノトニックな読み取り リーダと同期するフォロワーA, フォロワーB があり、同期速度がフォロワーAのほうが早くフォロワーBまでデータが到達するのが遅かったとする。 そのとき、クライアントがフォロワーAからデータを取得し、再度データをフォロワーBに問い合わせると 一度取得できていたデータが見れなくなることがある
モノトニックな読み取りはこの種の異常が生じないことを保証する
各クライアントが常に同じレプリカからデータを引くようにすればこれは実現できる

一貫性のあるプレフィックス読み取り

  1. クライアントAが書き込み
  2. クライアントBが書き込み

そのときにフォロワーAに到達するデータが 2 だったとすると
第三者からは、2 -> 1 の順番でデータが見えてしまうかもしれない
実際には、orderがかかってるのが普通なのでありえないと思うが。。 一貫性のあるプレフィックス読み取りは、ある順序で一連の書き込みが行われたとき
データを引く側には必ずその順序でデータを返すことを保証している

マルチリーダーレプリケーション

CouchDBなどが強いらしい。@Todo クライアントはローカルに保存して、同期をよしなに非同期でやってくれる?

書き込みの衝突をどう解決するか -> なるべく衝突を回避する
例えば、ある項目のリクエストは同じDBにかならず送るようにするなど また、マルチリーダのとれるDBでは衝突が起こったときに実行するスクリプトを登録できるものもある
書き込みにバージョンのメタをつけたりもする(CouchDB)

リーダーレスレプリケーション dynamoDBが再び火をつけた クライアントから受け取ったデータをノード分並列に書き込み 読み取り時は、並列にリクエストし、バージョンの新しいものを返す -> それぞれのノードで古いデータ/新しいデータが混在しているかもしれないので ここと本書に書かれてたクオラムについて学ぶことでようやくdynamoDBがなんたるものかわかってきた
それまでは単に料金体系複雑なNoSQLという認識でしかなかったので。。 ただ、書き込み遅延が致命的だとデータの整合性がとれなくなりしんどくなってくる
そこら辺をしっかりやらないといけない要件の場合はおとなしくRDBを使うべき

ちなみに、Cassandraは書き込みにタイムスタンプを与えて一番大きい書き込みが勝つように設計されている

@Todo Riakのデータ構造詳細 CRDT 並行書き込みの解決の仕方、マージ方法、削除。並行する値は sibling と呼ばれる

レプリカ複数の場合はどうする? -> バージョンベクトルの仕組みがレプリカの状態を相互に解決する現時点のベストらしい @Todo 調べる 似た言葉としてベクトルクロックがある Riak ではドット付きバージョンベクトルを使っている @Todo

6章

ページ分ける

Published 1 Sep 2019

Software engineer at Tokyo. smith-30 on Twitter