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のばらつきが少なくなった
- MySQL, Postgres, VoltDBのバラ付きの原因を調べた
先行研究とくらべて何がすごい?
- DBの平均的なパフォーマンス向上については今まで研究されてきた
- Tprofiler
技術や手法の肝は?
- Tprofiler
- Dtrace等の既存のツールはトランザクションシステムのパフォーマンスのバラ付きの根本原因の特定には向いていない
- 原因は子の関数よりも親の関数側にあることが多いが、原因を特定するための情報が少ない
- Dtrace等の既存のツールはトランザクションシステムのパフォーマンスのバラ付きの根本原因の特定には向いていない
- Overview
Characterizing Execution Variance
Latency Variance in MySQL
- os_event_wait()というlockに関する関数がlatencyのバラ付きの原因になっていた
Latency Variance in Postgres
- 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のバラ付きの原因になっている
- 一番早いトランザクションがlockを獲得する
- トランザクションがどれくらいキューにいるかを考慮せずにtransaction scheduleをおこなう
- トランザクションがキューにつまれたときに、そのageのみを考慮して、いつ終了するかやlockを開放するかについては知らない
- Additional Strategies
どうやって有効と検証した?
- 下記を検証した
- どれくらい効率的になったか
- latencyやスループットの平均値を犠牲にして、latencyのバラ付きを無くすことに価値はあるのか
- Tprofilerが既存のプロファイラに比べてどのくらい効率的で効果的に解析を行えるか
- 結果
Dapper, a Large-Scale Distributed Systems Tracing Infrastructure を読んだ
Dapper, a Large-Scale Distributed Systems Tracing Infrastructureを読んだ時のメモ。
どんなもの?
- 分散トレーシングシステム
- 分散システムのtraceをする
先行研究とくらべて何がすごい?
- 設計上の目標
- 要件
- ubiqitous deploy
- システムの一部がモニタリングされていないだけで大きな影響を受ける
- continuous monitoring
- 不測の事態や記録しておくべき挙動は、再現できない/難しいのでずっとモニタリングしておく必要がある
- ubiqitous deploy
技術や手法の肝は?
Distributed Tracing in Dapper
- trace tree
- node
- span
- unit of work
- RPCの開始/終了のタイミングをencodeしたデータ
- human-readableな名前がつけられている
- span間での関係性の再構築のため、span idやparent idなどを含む
- 特定のtraceに関連するspanには共通のtrace idが振られている
- span
- edge
- spanと親spanの関係を表す
- node
- trace tree
Instrumentation points
Managing Tracing Overhead
General-Purpose Dapper Tools
どうやって有効と検証した?
- Using Dapper during development
議論はある?
- 緊急時に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等を使う
- kernel-visible event に関する詳細な情報をとりたい
次に読むべき論文は?
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つの特徴
技術や手法の肝は?
- Replicated state machines
処理の流れ
- 1: サーバ上のConsensus Moduleがclientからコマンドを受け取る
- 2: ログにコマンドを追加、他のサーバのConsensus Moduleをやりとりをして、コマンドを同じ順になるようにする
- 3: replicateを行い、完了すると、serverのstatemachineがログの順にコマンドを実行していく
- 4: outputがclientに送られる
What’s wrong with Paxos?
- 2つの問題
- 理解するのが難しすぎる
- 実際に実装するとなると理論と現実とのギャップがある
- 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
- Leader election
- Raft basics
Raft cluster
- 5台のサーバで構成される(2台死んでもOK)
- それぞれのサーバは以下のいずれかのstateを持つ
- Leader
- clientからのrequestを受ける
- follower
- 自身でrequestは受けずに、leaderかcandidateからのrequestに対して、responseを送る
- candidate
- 新しいリーダの選出時に使われる
- Leader
Term
- 特定のleaderが活動していた論理時間
- termにはシーケンシャルなIDが振られる
- 各termはリーダの選出から始まる
- leaderが死んだらcandidateが次のtermを開始する
- 各サーバはcurrent termの情報を持ち、stale requestをrejectしたりするのに使う
Leader election
- ハートビートをリーダの選出を開始するトリガーにする
- followerが一定期間leaderからハートビートを受け取っていない場合(election timeout)にcandidateとなり選出が始まる
- 自分のcurrent term numberを増やして、RequestVoteRPCを発行する
- candidateは下記の3つのうちの1つが起こるまで続ける
- electionに勝つ
- 同タームで過半数のサーバから投票されるとリーダになる
- 他のサーバがリーダになる
- 誰も選出されない状態で一定期間が経つ
- ランダムなelection timeoutを用いるのでリーダーがずっと選ばれないことはめったにおこらない
- electionに勝つ
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されると古い状態のプロセスは消える
どうやって有効と検証した?
- RaftとPaxosのクイズの正答率を比較したところ、どちらを先に勉強してもRaftの方が得点が良かった
- RaftとPaxosを実装する/説明するのにどちらが簡単かを聞いたところRaftの方が簡単という答えが多かった
timeoutの時間をランダムに変化させた時のリーダ選出にかかった時間
- 150ms-151msだとsplit voteが起きて10秒くらいかかるが、5ms長くすると中央値が287msになった
- 150ms-200msくらいが良い
timeoutの時間をもっと減らしてみた
- 12-24msだと平均35msだったが、Raftの要件に合わない
- 他のサーバが新たな投票を開始する前に、リーダがハートビートをbroadcastをできない
- 150ms-300msくらいが良い
- 12-24msだと平均35msだったが、Raftの要件に合わない
議論はある?
次に読むべき論文は?
ZooKeeper: Wait-free coordination for Internet-scale systems
Paxos Made Live - An Engineering Perspective を読んだ
Paxos Made Live - An Engineering Perspectiveを読んだ時のメモ。
どんなもの?
- Paxosを実際のプロダクト(Chubby)で使用するために行った挑戦とその際に選択したアルゴリズムについて
先行研究とくらべて何がすごい?
- Paxosを実装し、Chubbyに組み込んだこと
- 実プロダクトで使う際に、論文の内容だけでは足りなかったので下記を実装した
- Handling disk corruption
- Master leases
- Epoch numbers
- Group membership
- Snapshots
- Data transaction
- 実プロダクトで使う際に、論文の内容だけでは足りなかったので下記を実装した
技術や手法の肝は?
- Background
- Architecture outline
- Fault-tolerant replicated Log
- 全てのレプリカは同一順序のエントリーをローカルログに持っている
- Fault-tolerant DB
- 下記から成る
- local snapshot
- DBの操作に関するreploy-log
- Chubbyが自分の状態を保存するのにも使う
- 下記から成る
- Fault-tolerant replicated Log
Paxos Basics
- 3つのフェーズがある
- 現実ではcoordinatorもfailするかもしれない
- Paxosではcoordinatorは一度に1つとは言っていない
- 複数のreplicaがcoordinatorとなるようにした
- 複数のcoordinatorがそれぞれ別の値を選ぶかもしれない
- Paxosは2つの追加のメカニズムを導入することで1つの値で同意に到れるようにした
- 1. succesive coordinatorの順番を決める - 前回と今回のcoordinatorを区別する - propose/promise messageで番号を送っているのでそれで区別 - 2. 値を選択する時に、coordinatorが取れる選択肢を制限する - promise messageに直近acceptした値を入れて返す
- Paxosではcoordinatorは一度に1つとは言っていない
Algorithmic challenges
- Handling disk corruption
- メディアの障害やオペレーターエラーによってdiskが破損する可能性がある
- diskが壊れて永続的な状態を失うと、過去に他のreplicaが行ったpromiseを再実行する可能性がある
- Paxosアルゴリズムの主要な仮定に違反する
- diskが壊れて永続的な状態を失うと、過去に他のreplicaが行ったpromiseを再実行する可能性がある
- diskの破損の2パターン
- ファイルの内容の変更された - チェックサムをいれる
- ファイルにアクセスできなくなった
- 空のdiskを持つ新しいreplicaと区別がつかない
- 新しいreplica起動時にGFSにマーカーを残すことで検出する
- replicaが空のdiskから再開されると検出される
- 破損したdiskを持つreplicaの再構築
- non-votingメンバーとしてPaxosに参加する
- 最新の状態に追いつくためにcatch-up メカニズムを使用するが、promise/acknowlegement メッセージには反応しない
- replicaが再構築されたと観測されるまでこの状態
- まだこれは実装されていない
- non-votingメンバーとしてPaxosに参加する
- メディアの障害やオペレーターエラーによってdiskが破損する可能性がある
Master leases
- 基本的なPaxosアルゴリズムを使ってreplicated data構造を実装する場合に古いデータを読み込む可能性がある
- 他のレプリカが別のマスターを選択肢、古いマスターに通知すること無くデータ構造が変わった場合
- master leaseを実装してこの問題を回避する
- masterにleaseがある限り、他のレプリカがPaxosに値を正常に送信できないことが保証される
- leaseを持つmasterがlocal dataに構造に最新の情報を持ち、localでの読み取り操作を行うことが出来る
- leaseの期限切れになるまでに、マスターが更新しようとするので一度に数日間くらいleaseを持つ
- まだ実装されていない
- 基本的なPaxosアルゴリズムを使ってreplicated data構造を実装する場合に古いデータを読み込む可能性がある
Epoch numbers
- master replicaがrequestを受けてから、DBを更新するまでにマスターステータスを失う可能性がある
- Chubbyは管理権が失われたり、再獲得されるとrequestの受付を中止する必要がある
- グローバルエポックnumberを導入した
- 2つのrepuestの間に連続してそのレプリカがmasterだったら、同じ値を受け取る
- DBのエントリとして保存され、DBの操作はエポック番号の値を条件とする
- master replicaがrequestを受けてから、DBを更新するまでにマスターステータスを失う可能性がある
- Group membership
- 現実のシステムでは一連のreplicaの変更を処理する必要がある
- group membership
- 文献には書かれていないし、アルゴリズムの正当性も証明されてない
- 実システムでは必要なので実装した
- 現実のシステムでは一連のreplicaの変更を処理する必要がある
- Snapshots
- Database transactions
- ChubbyでのDB要件はkey-valueのペアを保存できて、一般的なDB操作(insert, delete, lookup, an atomic compare and swap)ができることだった
- DB全体のsnapshotをとるのとsnapshotに適用したDB操作のログ(Paxos)に使えるように設計した
- 定期的にDBの状態をsnapshotにとり、それに応じてログを削除する
- Handling disk corruption
どうやって有効と検証した?
- 元々使われていた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しなければならない
- 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できる
- 1つの値を選ぶのに一番簡単な方法はacceptorを1つにすること
- 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
- Phase 1
- 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によって開発された分散メッセージングシステム
- 大容量のログを高スループットで配信、低レイテンシで収集することを目的としている
先行研究とくらべて何がすごい?
- ログの処理の焦点を絞って開発されたので低レイテンシで高スループット
- スケールアウトしやすい
技術や手法の肝は?
- Kafka Architecture and Design Principles
- producer
- topic(メッセージのfeedのようなもの)にメッセージを送る
- broker
- topicに送られてきたメッセージを保存する
consumer
- 1つ以上のtopicをsubscribeできて、pullすることでbrokerからデータを取得する
負荷を分散するためtopicは複数のbrokerに分散されている
- producerとconsumerは同時にmessageをpublish/subscribeできる
- producer
- 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が小さい
- Kafka Layerにはcacheを持たず、file systemのpage cacheを利用している
- Stateless broker
- brokerは各consumerがどれくらいメッセージをconsumeしたかについての情報は管理しない
- consumer自身がその情報を持っている
- brokerが管理すると複雑になってしまうのと、overheadが生まれるから
- brokerはどこまでデータが読まれたかがわからないので、一定時間が経ったデータを消していく
- アプリケーションのバグがあっても一定期間内であれば、再度同じ情報をconsumeできる
- brokerは各consumerがどれくらいメッセージをconsumeしたかについての情報は管理しない
- Simple storage
- DistributedCoordination
- consumer group
- 1つ以上のconsumerから成るグループ
- そのグループに対して一つずつメッセージが配信される
- グループはそれぞれ独立していて、他のグループと協働しない
- 工夫点
- topic内のpartitionを並列化の最小単位とした
- どんな時も1つのpartitionの全てのメッセージはそれぞれのグループの1つのconsumerからのみconsumeされる
- どのconsumerにどのメッセージを送ったかという情報やlockのことを考えずにすむのでoverheadが少ない
- どんな時も1つのpartitionの全てのメッセージはそれぞれのグループの1つのconsumerからのみconsumeされる
- central master modelは避けた
- ZooKeeperを用いて、master無しでconsumer達が協調して動くようにした
- topic内のpartitionを並列化の最小単位とした
- Delivery Guarantees
- at-least-once delivery
- consumerがcrashしてももう一度同じメッセージを読みにいける
- 正確に一度だけ送ろうとすると2PC等を使わねばならず、非効率
- single partitionからは順番にデータが送られるが、partition間での順序は保証しない
- at-least-once delivery
- consumer group
どうやって有効と検証した?
- LinkedInで半年間使った
Producer Performance
- 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を読んだ時のメモ。
どんなもの?
- 擬似ランダムデータ分散アルゴリズム
先行研究とくらべて何がすごい?
- 先行研究
- CRUSH
技術や手法の肝は?
- ClusterMap
Collisions, Failure, and Overload
Bucket Types
どうやって有効と検証した?
- storage deviceを追加・削除した後のデータの再配置の効率性 - 1が最適な状態 - 総合的にみるとstraw bucketのパフォーマンスが良い
- アイテムを追加した後のデータの再配置の効率性
- 1が最適な状態
- strawとlist headのパフォーマンスが良い
- listのtailは悪い
- treeはbucket sizeの対数値によって変化する
- 階層サイズの計算時間の違い - CRUSHは対数的にスケールする
- レプリカを個々のCRUSH bucketとbucketサイズにマッピングするLow-level speed
- uniformは一定の時間
- treeは対数的な時間
- listとstrawは線形の時間
議論はある?
- 一般的にはdevice failedは一時的なものなので、階層構造に残しているが、本当に故障していたりするとパフォーマンスが劣化する
次に読むべき論文は?
Evaluation of distributed recovery in large-scale storage systems.