ikemonn's blog

技術ネタをちょこちょこと

A Top-Down Approach to Achieving Performance Predictability in Database Systems を読んだ

A Top-Down Approach to Achieving Performance Predictability in Database Systemsを読んだ時のメモ。

どんなもの?

  • DBのlatencyのバラ付きの主要な原因を特定するためにTprofiler(解析ツール)を作成しバラ付きを少なくした
    • MySQL, Postgres, VoltDBのバラ付きの原因を調べた
      • Tprofilerを使えば複雑なコードベースでも解析できる
      • 各DBでパフォーマンスとlatencyのばらつきが少なくなった

先行研究とくらべて何がすごい?

技術や手法の肝は?

  • Tprofiler
    • Dtrace等の既存のツールはトランザクションシステムのパフォーマンスのバラ付きの根本原因の特定には向いていない
      • 原因は子の関数よりも親の関数側にあることが多いが、原因を特定するための情報が少ない
  • Overview
    • Tprofilerはパフォーマンスのバラ付きが大きい関数をランキング形式で教えてくれる
    • 下記の2つがある
      • online trace collection
      • offline variance analysis
    • トランザクションの開始終了をコード側でAPIを叩いて指定する
  • Characterizing Execution Variance

    • トランザクション内での特定の関数のdulationを比較する
    • variance treeというlantecyのバラ付きの関係を表してたtreeを作る
      • 特定の関数のcall hierachyを表す f:id:ikemonn:20170730215151p:plain
  • Latency Variance in MySQL

    • os_event_wait()というlockに関する関数がlatencyのバラ付きの原因になっていた f:id:ikemonn:20170730215212p:plain
  • Latency Variance in Postgres

f:id:ikemonn:20170730215223p:plain

  • Variance-aware trancaction scheduling
    • Tprofilerによるとlocak wait timeがlantecyのバラ付きの原因
    • lock scheduling algorithmを変更する
    • Problem setting
      • 一般的なDBはconcurrency controlのための2-PLが原因でlatencyのバラ付きが起こる
      • 一般的なトランザクションスケジューリングはFCFS
        • 一番早いトランザクションがlockを獲得する
          • current queueに一番長くいるものからlockを獲得していく
          • これがlantecyの平均値を最小化しないだけでなく、latencyのバラ付きの原因になっている
      • トランザクションがどれくらいキューにいるかを考慮せずにtransaction scheduleをおこなう
        • トランザクションがキューにつまれたときに、そのageのみを考慮して、いつ終了するかやlockを開放するかについては知らない
  • Additional Strategies
    • LLU
      • MySQLはLRUの際に、LRU listの並び替えに時間がかかっていた
      • Lasy LRU Updateによってロックの時間を短くした
        • mutexをやめて、wait timeを管理することにした
    • Parallel Logging
      • Postgresはredo logをflushする処理に時間がかかっていたので、parallelに書き込むようにした

どうやって有効と検証した?

  • 下記を検証した
    • どれくらい効率的になったか
    • latencyやスループットの平均値を犠牲にして、latencyのバラ付きを無くすことに価値はあるのか
    • Tprofilerが既存のプロファイラに比べてどのくらい効率的で効果的に解析を行えるか
  • 結果
    • VATSはスループットを犠牲にすること無く、ばらつきを少なくし、更に速くなった
    • LLUはMySQLを下記のように改善
      • ばらつきは1.2倍改善
      • latencyは1.4倍改善
    • Parallel LoggingはPostgresを下記のように改善
      • ばらつきは1.3倍改善
      • latencyは1.8倍改善
    • TprofilerはDtraceにくらべて解析のオーバーヘッドが少なかった  

f:id:ikemonn:20170730215246p:plain

Dapper, a Large-Scale Distributed Systems Tracing Infrastructure を読んだ

Dapper, a Large-Scale Distributed Systems Tracing Infrastructureを読んだ時のメモ。

どんなもの?

  • 分散トレーシングシステム
    • 分散システムのtraceをする

f:id:ikemonn:20170730214056p:plain

先行研究とくらべて何がすごい?

  • 設計上の目標
    • オーバーヘッドが少ない
      • サービスのパフォーマンスに影響を与えないように
    • アプリケーションレベルでの透過性
    • 大規模システムにもubiqitousデプロイ出来る
  • 要件
    • ubiqitous deploy
      • システムの一部がモニタリングされていないだけで大きな影響を受ける
    • continuous monitoring
      • 不測の事態や記録しておくべき挙動は、再現できない/難しいのでずっとモニタリングしておく必要がある

技術や手法の肝は?

  • Distributed Tracing in Dapper

    • trace tree
      • node
        • span
          • unit of work
          • RPCの開始/終了のタイミングをencodeしたデータ
          • human-readableな名前がつけられている
          • span間での関係性の再構築のため、span idやparent idなどを含む
          • 特定のtraceに関連するspanには共通のtrace idが振られている
      • edge
        • spanと親spanの関係を表す

    f:id:ikemonn:20170730214204p:plainf:id:ikemonn:20170730214210p:plain

  • Instrumentation points

    • 共通ライブラリを使うことで簡単にアプリケーションに組み込める
    • Annotations
      • シンプルなAPIを用いて、タイムスタンプを含むannotationを定義できるようにした
      • key-value型もサポート

      f:id:ikemonn:20170730214252p:plain

    • Trace collection
      • ログキングと集計のパイプライン
        • 1 span dataがローカルのログファイルに書き込まれる
        • 2 Dapper daemonによって全ての本番ホストからデータが収集される
        • 3 Dapper BigTableに保存される
          • rowがtrace id, columunがspan idに対応 f:id:ikemonn:20170730214412p:plain
  • Managing Tracing Overhead

    • traceのオーバーヘッドは主にspanとアノテーションの作成/削除にある
      • Root spanは平均204 nanosec
      • Non root spanは176 nanosec
        • 違いはglobalでユニークなtrace idを割り当てる部分
    • local diskへの書き込みは最も遅いが、まとめて書き込むのと非同期に書き込むのでオーバーヘッドはそれほどない
    • Dapper daemonは1コアあたりCPU 0.3%以上は使わない、メモリのfootprintも小さい
  • General-Purpose Dapper Tools

どうやって有効と検証した?

  • Using Dapper during development
    • Google Adwordsで利用した
    • Dapperを用いることでパフォーマンスが向上した
    • performance
      • request latencyをトラックできたので、ピンポイントに最適化できた
      • 他の人が書いたサブシステムが発行している、不要なrequestの特定もできた
    • correctness
      • Ads Reviewサービスでは2種類のDBがいる
        • read-only replica(inexpensive access)
        • read-write master(expensive access)
      • Dapperのお陰でmasterにアクセスする必要のないクエリがあることがわかった
    • understanding
      • Ads Reviewのクエリは様々なシステムに対して発行される
      • totalのクエリコストをみて、それらのシステムの依存性のredesignを行えた
    • testing
      • システムが正しい挙動をしているかや、パフォーマンスを確認できるようになった

議論はある?

  • 緊急時にshared stroage serviceでは役に立たない
    • すぐにログやメトリックがみたいが、すぐに見れない
      • shared stroage serviceではアグリゲートされた情報が必要であり、すぐに見れない(約10分以内でみれる)
  • Tracing batch workloads
    • Dapperはオンラインサービスを対象に作られたが、MapReduceのようなオフラインサービスのパフォーマンス向上にも使いたい
  • Finding a root cause

    • 処理のある部分が速いか遅いかは分かるが、根本原因を特定するのに十分な情報は得られない
  • Logging kernel-level information

    • kernel-visible event に関する詳細な情報をとりたい
      • user levelにいながらkernelの情報をとるのは一般的な方法では難しいのでsnapshot等を使う

次に読むべき論文は?

Web Search for a Planet: The Google Cluster Architecture.

In Search of an Understandable Consensus Algorithm(Extended Version) を読んだ

[In Search of an Understandable Consensus Algorithm(Extended Version)(https://raft.github.io/raft.pdf)を読んだ時のメモ。

どんなもの?

  • わかりやすさを重視して開発された合意アルゴリズム
    • Paxosよりもわかりやすいが、Paxosよりも効率的

先行研究とくらべて何がすごい?

  • Paxosに比べてわかりやすい
    • 何故動くのかまでを開発者が理解しやすい
  • 3つの特徴
    • Strong leader
      • 他の同意アルゴリズムよりも、リーダの権限が強い
        • 例えばlogのreplicationはリーダーからスレーブへの一方向
      • RPCの呼び出しはリーダのみが行う
    • Leader election
      • リーダの選出のためにrandomized timerを用いる
        • どの同意アルゴリズムにも必要になってくる、ハートビートのメカニズムを簡単にした
    • Membership change
      • joint consensusという手法でmembershipの変更を行う
        • membershipの変更中に新旧の設定がoverlapする
        • membershipの変更中もクラスタは稼働し続ける

技術や手法の肝は?

  • Replicated state machines
  • 処理の流れ

    • 1: サーバ上のConsensus Moduleがclientからコマンドを受け取る
    • 2: ログにコマンドを追加、他のサーバのConsensus Moduleをやりとりをして、コマンドを同じ順になるようにする
    • 3: replicateを行い、完了すると、serverのstatemachineがログの順にコマンドを実行していく
    • 4: outputがclientに送られる f:id:ikemonn:20170727211344p:plain
  • What’s wrong with Paxos?

    • 2つの問題
      • 理解するのが難しすぎる
      • 実際に実装するとなると理論と現実とのギャップがある
  • Designing for understandability

    • 直感的に理解しやすいことを目標にした
      • 開発者が拡張しやすい
      • 問題を分割してわかりやすくした
      • Paxosに比べて状態の数を減らした
  • The Raft consensus algorithm

    • リーダを選び、リーダにreplicated logを管理する権限を与える
    • リーダはclientからログを受けとって、他のサーバにreplicateする
    • 各サーバに対して、statemachineにログを適用するのに良いタイミングを通知する
    • consensus problemを3つの独立した問題に分割した
      • Leader election
        • 新しいリーダは既存のリーダが死ぬと選ばれる
      • Log replication
        • リーダがclientからログを受け取ってから、クラスタに流す
      • Safety
        • Figure 3
  • Raft basics
    • Raft cluster

      • 5台のサーバで構成される(2台死んでもOK)
      • それぞれのサーバは以下のいずれかのstateを持つ
        • Leader
          • clientからのrequestを受ける
        • follower
          • 自身でrequestは受けずに、leaderかcandidateからのrequestに対して、responseを送る
        • candidate
          • 新しいリーダの選出時に使われる

      f:id:ikemonn:20170727211454p:plain

    • Term

      • 特定のleaderが活動していた論理時間
      • termにはシーケンシャルなIDが振られる
      • 各termはリーダの選出から始まる
      • leaderが死んだらcandidateが次のtermを開始する
      • 各サーバはcurrent termの情報を持ち、stale requestをrejectしたりするのに使う

      f:id:ikemonn:20170727211513p:plain

    • Leader election

      • ハートビートをリーダの選出を開始するトリガーにする
      • followerが一定期間leaderからハートビートを受け取っていない場合(election timeout)にcandidateとなり選出が始まる
        • 自分のcurrent term numberを増やして、RequestVoteRPCを発行する
    • candidateは下記の3つのうちの1つが起こるまで続ける
      • electionに勝つ
        • 同タームで過半数のサーバから投票されるとリーダになる
      • 他のサーバがリーダになる
      • 誰も選出されない状態で一定期間が経つ
        • ランダムなelection timeoutを用いるのでリーダーがずっと選ばれないことはめったにおこらない
  • Log replication

    • リーダは受け取ったコマンドを新しいentryとしてログに追加していく
    • entryがreplicateされたら、そのentryを自身のstate machineに適用し、clientに結果を返す
      • replicateの途中でfollowerがcrashしても、全てのfollwerにreplicateされるまでおくり続ける
    • leaderは過半数のfollowerからresponseがあったら、それらのstate machineにログを適用させる(commit)
  • Cluster membership changes

    • 新旧のconfigが混ざった状態を間に挟むことで、無停止でconfigの変更を行えるようにした
    • 流れ
      • 古いconfigのリーダが新旧のconfigが混ざった状態に遷移するように指示
      • 新旧混ざった状態がcommitされると、joint consensusに移行
      • 新しい状態がcommitされると古い状態のプロセスは消える f:id:ikemonn:20170727211618p:plain

どうやって有効と検証した?

  • RaftとPaxosのクイズの正答率を比較したところ、どちらを先に勉強してもRaftの方が得点が良かった

f:id:ikemonn:20170727213721p:plain

  • RaftとPaxosを実装する/説明するのにどちらが簡単かを聞いたところRaftの方が簡単という答えが多かった

f:id:ikemonn:20170727213731p:plain

  • timeoutの時間をランダムに変化させた時のリーダ選出にかかった時間

    • 150ms-151msだとsplit voteが起きて10秒くらいかかるが、5ms長くすると中央値が287msになった
    • 150ms-200msくらいが良い
  • timeoutの時間をもっと減らしてみた

    • 12-24msだと平均35msだったが、Raftの要件に合わない
      • 他のサーバが新たな投票を開始する前に、リーダがハートビートをbroadcastをできない
      • 150ms-300msくらいが良い

f:id:ikemonn:20170727213753p:plain

議論はある?

  • Raftのパフォーマンスは他の同意アルゴリズムと同じくらい
    • 他のアルゴリズムに当てはまる最適化の手法はRaftにも使える
      • batchingやpipeline requestなど

次に読むべき論文は?

ZooKeeper: Wait-free coordination for Internet-scale systems

Paxos Made Live - An Engineering Perspective を読んだ

Paxos Made Live - An Engineering Perspectiveを読んだ時のメモ。

どんなもの?

  • Paxosを実際のプロダクト(Chubby)で使用するために行った挑戦とその際に選択したアルゴリズムについて
    • Paxosは論文には1ページの擬似コードで説明されているが、実プロダクトで使うには数千行かかった(C++)
    • 論文では書かれていた耐障害性アルゴリズムは慎重に選択された一部の障害にしか耐えられなかった
      • 実世界ではアルゴリズム自体のエラーやオペレーターのエラー等が起こる

先行研究とくらべて何がすごい?

  • Paxosを実装し、Chubbyに組み込んだこと
    • 実プロダクトで使う際に、論文の内容だけでは足りなかったので下記を実装した
      • Handling disk corruption
      • Master leases
      • Epoch numbers
      • Group membership
      • Snapshots
      • Data transaction

技術や手法の肝は?

f:id:ikemonn:20170721152452p:plain

  • Architecture outline
    • Fault-tolerant replicated Log
      • 全てのレプリカは同一順序のエントリーをローカルログに持っている
    • Fault-tolerant DB
      • 下記から成る
        • local snapshot
        • DBの操作に関するreploy-log
      • Chubbyが自分の状態を保存するのにも使う
  • Paxos Basics

    • 3つのフェーズがある
        1. coordinatorとなるreplicaを選択する
        1. coordinatorは値を選択し、acceptメッセージで全てのreplicaにbroadcastする
        1. replicaの過半数がcoordinatorをacknowledgeしたら同意に至る
        2. coordinatorはreplicaに知らせるためにcommitメッセージをbroadcastする
        3. 一度過半数のreplicaがack messageを受け取って、ackしたら同意が成立する
          • たとえすべての少数派のreplicaがfailしても、少なくとも1つのreplicaには同意された値が届いている
    • 現実ではcoordinatorもfailするかもしれない
      • Paxosではcoordinatorは一度に1つとは言っていない
        • 複数のreplicaがcoordinatorとなるようにした
        • 複数のcoordinatorがそれぞれ別の値を選ぶかもしれない
      • Paxosは2つの追加のメカニズムを導入することで1つの値で同意に到れるようにした
          - 1. succesive coordinatorの順番を決める
              - 前回と今回のcoordinatorを区別する
                  - propose/promise messageで番号を送っているのでそれで区別
          - 2. 値を選択する時に、coordinatorが取れる選択肢を制限する
              - promise messageに直近acceptした値を入れて返す
        
  • Algorithmic challenges

    • Handling disk corruption
      • メディアの障害やオペレーターエラーによってdiskが破損する可能性がある
        • diskが壊れて永続的な状態を失うと、過去に他のreplicaが行ったpromiseを再実行する可能性がある
      • diskの破損の2パターン
        • ファイルの内容の変更された - チェックサムをいれる
        • ファイルにアクセスできなくなった
          • 空のdiskを持つ新しいreplicaと区別がつかない
          • 新しいreplica起動時にGFSにマーカーを残すことで検出する
            • replicaが空のdiskから再開されると検出される
      • 破損したdiskを持つreplicaの再構築
        • non-votingメンバーとしてPaxosに参加する
          • 最新の状態に追いつくためにcatch-up メカニズムを使用するが、promise/acknowlegement メッセージには反応しない
          • replicaが再構築されたと観測されるまでこの状態
        • まだこれは実装されていない
    • Master leases

      • 基本的なPaxosアルゴリズムを使ってreplicated data構造を実装する場合に古いデータを読み込む可能性がある
        • 他のレプリカが別のマスターを選択肢、古いマスターに通知すること無くデータ構造が変わった場合
      • master leaseを実装してこの問題を回避する
        • masterにleaseがある限り、他のレプリカがPaxosに値を正常に送信できないことが保証される
        • leaseを持つmasterがlocal dataに構造に最新の情報を持ち、localでの読み取り操作を行うことが出来る
          • leaseの期限切れになるまでに、マスターが更新しようとするので一度に数日間くらいleaseを持つ
      • まだ実装されていない
    • Epoch numbers

      • master replicaがrequestを受けてから、DBを更新するまでにマスターステータスを失う可能性がある
        • Chubbyは管理権が失われたり、再獲得されるとrequestの受付を中止する必要がある
      • グローバルエポックnumberを導入した
        • 2つのrepuestの間に連続してそのレプリカがmasterだったら、同じ値を受け取る
        • DBのエントリとして保存され、DBの操作はエポック番号の値を条件とする
    • Group membership
      • 現実のシステムでは一連のreplicaの変更を処理する必要がある
        • group membership
      • 文献には書かれていないし、アルゴリズムの正当性も証明されてない
      • 実システムでは必要なので実装した
    • Snapshots
      • 同意アルゴリズムを使っていくと、replicatited logが増えていく
      • ログが増えていくと2つの問題が起こる
        • disk spaceを無限に使う
        • 無限の復旧時間がかかる
      • snapshotをとるようにする
        • Paxosフレームワーク自体はデータ構造については、何も知らされていないためアプリケーション側がsnapshotを作成する
        • アプリケーションが任意のタイミングでshapshotをとり、Paxosに通知するとそれ以前のログを削除するようにした
    • Database transactions
      • ChubbyでのDB要件はkey-valueのペアを保存できて、一般的なDB操作(insert, delete, lookup, an atomic compare and swap)ができることだった
      • DB全体のsnapshotをとるのとsnapshotに適用したDB操作のログ(Paxos)に使えるように設計した
      • 定期的にDBの状態をsnapshotにとり、それに応じてログを削除する

どうやって有効と検証した?

f:id:ikemonn:20170721152511p:plain

  • 元々使われていた3DBと、自分たちで実装したDBを使用したChubbyのパフォーマンスを測定して比較した
    • 全体的にPaxosを利用した方がパフォーマンスが良い
  • replicated log sizeが100MBを超えるとsnapshotをとるように設定されており、そこでdiskに書き込むのでパフォーマンスが一時的に低下した
    • この部分の最適化の余地があるが、3DBよりはパフォーマンスが出ているので手を付けなかった

議論はある?

  • まだまだ最適化の余地がある
    • snapshot等
  • Paxosアルゴリズムの説明と実システムでのニーズには大きなギャップがある
  • The fault-tolerance computing communityはアルゴリズムの実装を容易にするツールを開発していない
  • The fault-tolerance computing communityは耐障害性システムを構築するために重要な要素であるテストに十分な注意を払っていない

次に読むべき論文は?

In Search of an Understandable Consensus Algorithm(Extended Version)

Paxos Made Simple 読んだ

Paxos Made Simpleを読んだ時のメモ。

どんなもの?

  • Paxos
    • 分散合意アルゴリズム
      • 複数のプロセスが値を提案した時に、どのように1つの値を選ぶかについて

技術や手法の肝は?

  • The Problem

    • safety requirements

      • 提案された値のみが選ばれる
      • 1つの値のみが選ばれる
      • 値が選ばれた後でしたか、その値は使えない
    • roles

      • proposer
      • acceptor
      • learner
    • 1つのprocessが複数のroleを担っても良い

    • 分散システムの問題点
      • Agentは任意の速度で処理を行う
      • 処理が止まって、失敗するかもしれないし再起動するかもしれない
      • メッセージは到達するまで任意の時間がかかる
      • メッセージは重複するかもしれないし、失われるかもしれない
      • メッセージは壊れた状態では届かない
  • Chosing a Value

    • 1つの値を選ぶのに一番簡単な方法はacceptorを1つにすること
      • SPOFになるのでダメ
    • acceptorを複数にし、proposerが複数のacceptorに提案を送る
      • 過半数のacceptorがacceptした値が選ばれるとする
    • P1. acceptorは最初に受け取った提案をacceptしなければならない
      • 同時に異なるproposerからいくつかの値がproposeされて、acceptorがそれぞれ別の値をacceptしていると、どの値も過半数にならない時がある
      • acceptorは1つ以上の提案をacceptできるようにする
        • 提案にユニークなIDをつけるようにする
          • 提案 = (ID, 値)
        • 過半数のacceptorに1つの値がacceptされた時に、値が選ばれたとする
      • 複数の提案を選べるようになると、値がどんどん上書きされていってしまう
    • P2. 値vの提案が選ばれたら、それより大きいIDのproposalの値はvでなければならない
      • 提案が選択されたあとの上書きを防げる
      • 提案は少なくとも1つのacceptorにacceptされる必要がある
    • P2a. 値vの提案が選ばられたら、全てのacceptorによってacceptされたものより大きなIDの提案は値vを持たねばならない
      • これだと、P1が満たせない(acceptorは最初に受け取った提案をacceptせねばならない)
      • 新しいacceptorが異なる値の提案をしたときに、P1を満たすためにはその提案をacceptせねばならない(P2aに違反)
    • P2b. 値vの提案が選ばれたら、それより大きなIDを持つ提案は全て値vを持つ
    • P2c. ID:n, 値:vの提案が発行されたら、下記のようなacceptor群Sが存在しなければならない
      • a) ID:nより小さな提案をacceptしているacceptorはSにはいない
      • b) ID:nより小さい全ての提案の中で最も大きいnumberの提案の値がv
    • ID:n より小さい提案を全部無視して欲しい
    • prepare request
      • ID:n より小さい提案をacceptしないことを約束する
    • accept request
      • 提案を受け入れた
    • P1a. AcceptorはID:nより大きなIDのprepare requestにresponseしていない場合、ID:nの提案をacceptできる
  • Paxos
    • Phase 1
      • ProposerがID:nの提案を選び、prepare reqをacceptorの過半数に送る
      • もしID:nがPromise済みのIDよりも大きければacceptし、違ったら現在acceptしている提案を返す
    • Phase 2
      • ProposerがAcceptorの大半からprepare reqを受け取ったら、それぞれのacceptorに accept reqを送る(ID:n, value:v)
      • acceptorがID:nのaccept reqを受け取る
        • nがPromiseした提案のID以上ならaccept
  • Learning a Chosen Value
    • 提案が選ばれたことを確認するにはLearnerを使う
    • 過半数のacceptorに提案がacceptされたことをlearnerに確認させる
    • Distinguished learnerにacceptorが提案がacceptされたことを報告する
      • Distinguished learnerが他のlearnerに通知する

次に読むべき論文は?

Kafka: a Distributed Messaging System for Log Processing を読んだ

Kafka: a Distributed Messaging System for Log Processingを読んだ時のメモ。

どんなもの?

  • LinkedInによって開発された分散メッセージングシステム
    • 大容量のログを高スループットで配信、低レイテンシで収集することを目的としている

先行研究とくらべて何がすごい?

  • ログの処理の焦点を絞って開発されたので低レイテンシで高スループット
    • 従来のメッセージングシステムに備わっていた、不要な機能を削ぎ落としている
      • delivary guaranteeや順番の担保等
        • ログなので多少欠けていても問題ない
      • 従来のメッセージングシステムはスループットにforcusしてなかった
        • バッチ処理でやればいいと考えていた
        • ビジネス的にはリアルタイムでログを処理したい場面も増えた
  • スケールアウトしやすい

技術や手法の肝は?

f:id:ikemonn:20170712230147p:plain

  • Kafka Architecture and Design Principles
    • producer
      • topic(メッセージのfeedのようなもの)にメッセージを送る
    • broker
      • topicに送られてきたメッセージを保存する
    • consumer

      • 1つ以上のtopicをsubscribeできて、pullすることでbrokerからデータを取得する
    • 負荷を分散するためtopicは複数のbrokerに分散されている

    • producerとconsumerは同時にmessageをpublish/subscribeできる

f:id:ikemonn:20170712230205p:plain

  • Efficiency on a Single Partition
    • Simple storage
      • topicのそれぞれの部分はlogical logに対応している
      • 物理的なログは一定サイズのsegment fileとして、保存されている
      • producerがメッセージをpartitionにpublishすると、brokerはログの最後にメッセージを追加していく
      • パフォーマンス向上のために、ある程度メッセージが溜まってからdiskにflushする
      • メッセージはflushされてから、consumerにconsumeされる
      • 従来のメッセージングシステムと異なり、メッセージにはIDは振られていない
        • それぞれのメッセージはlog内のoffsetで位置を決められている
      • consumerは特定のpartitionから順番にメッセージをconsumeする
        • consumerからのpull requestにはメッセージのoffsetとfetchするbyte数が含まれている
      • brokerはin-memoryに各segment fileの初期位置を示したoffset listを持っている
    • Efficient transfer
      • Kafka Layerにはcacheを持たず、file systemのpage cacheを利用している
        • GCのoverheadが小さい
    • Stateless broker
      • brokerは各consumerがどれくらいメッセージをconsumeしたかについての情報は管理しない
        • consumer自身がその情報を持っている
        • brokerが管理すると複雑になってしまうのと、overheadが生まれるから
      • brokerはどこまでデータが読まれたかがわからないので、一定時間が経ったデータを消していく
        • アプリケーションのバグがあっても一定期間内であれば、再度同じ情報をconsumeできる
  • DistributedCoordination
    • consumer group
      • 1つ以上のconsumerから成るグループ
      • そのグループに対して一つずつメッセージが配信される
      • グループはそれぞれ独立していて、他のグループと協働しない
    • 工夫点
      • topic内のpartitionを並列化の最小単位とした
        • どんな時も1つのpartitionの全てのメッセージはそれぞれのグループの1つのconsumerからのみconsumeされる
          • どのconsumerにどのメッセージを送ったかという情報やlockのことを考えずにすむのでoverheadが少ない
      • central master modelは避けた
        • ZooKeeperを用いて、master無しでconsumer達が協調して動くようにした
    • Delivery Guarantees
      • at-least-once delivery
        • consumerがcrashしてももう一度同じメッセージを読みにいける
        • 正確に一度だけ送ろうとすると2PC等を使わねばならず、非効率
      • single partitionからは順番にデータが送られるが、partition間での順序は保証しない

どうやって有効と検証した?

  • LinkedInで半年間使った
  • KafkaとApache ActiveMQの比較をした f:id:ikemonn:20170712230224p:plain

  • Producer Performance

    • producerはbrokerからのackを待たないので速い
    • 効率的なメッセージフォーマットなので速い
      • メッセージのoverheadは9bytes(ActiveMQは144bytes)
    • ActiveMQはメッセージのメタデータを管理するindexへのアクセスに時間がかかる

f:id:ikemonn:20170712230235p:plain

  • Consumer Performance
    • 効率的なメッセージフォーマットなので速い
    • 全てのメッセージの配信状況を管理しないので速い
      • 中には送られていないメッセージもある
    • sendFile APIが転送のoverheadを少なくした

議論はある?

  • 複数のbroker間でのメッセージレプリケーションをbuilt-inの機能として入れる
  • 幾つかのストリーム処理を組み込む
    • window countingとか
  • producerはbrokerのackを待たないので、全てのメッセージが送られていることを保証できない

次に読むべき論文は?

ZooKeeper: Wait-free coordination for Internet-scale systems

CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data を読んだ

CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Dataを読んだ時のメモ。

どんなもの?

  • 擬似ランダムデータ分散アルゴリズム
    • データの名前に対して偏りが無いようにデータノードを割り当てる
    • central allocatorがいなくても新しいデータの保存先を計算できるアルゴリズム
    • マッピングの計算はO(log n)で終わり、何千台ものデバイスがあっても数ミリ秒で計算できる

先行研究とくらべて何がすごい?

  • 先行研究
  • CRUSH
    • リソースに余裕がある部分に動的にデータを分散していく
    • ストレージデバイスの追加・削除時には効率的にデータを再配置する
    • データの位置を擬似ランダムマッピング関数で計算することで、データの保存位置に関するメタデータの必要性を減らした

技術や手法の肝は?

  • ClusterMap
    • データノードのリストのこと
    • bucketとdeviceで構成される
      • 双方、数値IDと重みを持っている
    • bucket
      • 木構造のnode
      • 任意の数のdeviceとbucketで構成される
    • device
    • 階層構造になっており、root -> row -> cabinet -> diskのように構成されている

f:id:ikemonn:20170710233357p:plain

  • Collisions, Failure, and Overload

    • バイスが高負荷だったり、障害があったりすると、階層構造に残したままフラグが立てられる
      • 高負荷だったり障害は一時的なものが多く、不要なデータの移動を避けるため
      • placementアルゴリズムによって、再分散される
  • Bucket Types

    • 下記の4つがあり、データ移動の際にそれぞれ異なった選択アルゴリズムが適用される
      • uniform bucket
        • 従来のhashアルゴリズムと同じで、全ての要素に重みが与えられる
      • list bucket
        • 要素がlinkリストのような構造をしており、要素に任意の重みをつけられる
      • tree bucket
        • 素数が少ない時は効率的に処理ができるlinkリストのような構造
      • straw bucket
        • ハッシュ関数を横ではなく縦に適用するようなイメージ
        • 重みが最大になるアイテムに、より多くのアイテムがひも付きやすくなる
          • deviceの追加・削除時のデータの移動を効率化する

f:id:ikemonn:20170710233310p:plain

どうやって有効と検証した?

f:id:ikemonn:20170710233433p:plain - storage deviceを追加・削除した後のデータの再配置の効率性 - 1が最適な状態 - 総合的にみるとstraw bucketのパフォーマンスが良い

f:id:ikemonn:20170710233447p:plain

  • アイテムを追加した後のデータの再配置の効率性
    • 1が最適な状態
    • strawとlist headのパフォーマンスが良い
    • listのtailは悪い
    • treeはbucket sizeの対数値によって変化する

f:id:ikemonn:20170710233516p:plain - 階層サイズの計算時間の違い - CRUSHは対数的にスケールする

f:id:ikemonn:20170710233530p:plain

  • レプリカを個々のCRUSH bucketとbucketサイズにマッピングするLow-level speed
    • uniformは一定の時間
    • treeは対数的な時間
    • listとstrawは線形の時間

議論はある?

  • 一般的にはdevice failedは一時的なものなので、階層構造に残しているが、本当に故障していたりするとパフォーマンスが劣化する

次に読むべき論文は?

Evaluation of distributed recovery in large-scale storage systems.