論文 BTW'17, Survey and Comparison of Open Source Time Series Databases

  • [1]: B. Mitschang et al. 2017. Survey and Comparison of Open Source Time Series Databases. In BTW. slide

どんなものか

  • 全てのオープンソース時系列データベース(以下TSDB)の完全なリストと、人気のあるTSDBの機能リストを作成することが目的。
  • 機械的に検索した83個のTSDBのうち12個の主要なTSDBを比較する。

先行研究との差分はなにか

  • 先行研究では、機能比較よりは性能比較にフォーカスしている。
  • 先行研究では、すべてのユースケースを満たせない単一のデータベースはないということが示されている。
  • この研究では、上記のgapを埋める。*1

手法の要点はなにか

TSDBを以下の6つの基準グループ(合計27個の基準)で比較している。*2

  • 1: Distribution/Clusterability
    • 高可用性、スケーラビリティ、ロードバランシング機能で比較
  • 2: Functions
    • INS, UPD, READ, SCAN, AVG, SUM, CNT, DEL, MAX, and MIN の各functionで比較
  • 3: Tags, Continuous Calculation, Long-term Storage, and Matrix Time Series
  • 4: Granularity
    • データ粒度*3、ダウンサンプリング*4、最小粒度
  • 5: Interfaces and Extensibility
  • 6: Support and License

さらに、TSDBを4つのグループに分類している。

  • Group 1: TSDBs with a Requirement on other DBMS
  • Group 2: TSDBs with no Requirement on any DBMS
  • Group 3: RDBMS
  • Group 4: Proprietary

有効性をどのように示しているか

  • 12個のTSDBの選定基準は、Googleの検索ヒット数順。
    • https://www.google.com/webhp?gws_rd=cr,ssl&pws=0&hl=en&gl=us&filter=0&complete=0
  • 27個の基準を定性的に満たしているかいないかを表で示されている。

([1]のTab. 3: Comparison of Criteria Group 1: Distribution/Clusterability.より引用)

議論はあるか

  • Druidが多くの基準を満たすベストな選択肢。他のTSDBと比較して、5つのnode typeをもち、JavaScriptでself-writtenなaggregated functionをサポートする。次点で、InfuxDB, MonetDB, もしくは2つのRDBMS(MySQL, Postgres)。
  • 機能でTSDBを差別化できないが、性能で差別化できるかもしれない。
  • 次のステップは、repeatableでextensibleで任意のTSDB向けOSSベンチマーキングフレームワーク

興味深い関連論文はなにか

references.

  • [Ba16] Bader, A.: Comparison of Time Series Databases, Diploma Thesis, Institute of Parallel and Distributed Systems, University of Stuttgart, 2016. *5
  • [Wl12] Wlodarczyk, T.: Overview of Time Series Storage and Processing in a Cloud Environment. In: CloudCom. 2012.
  • [DMF12] Deri, L.; Mainardi, S.; Fusco, F.: tsdb: A Compressed Database for Time Series. In: Trafic Monitoring and Analysis. Springer, 2012.
  • [PFA09] Pungilă, C.; Fortiş, T.-F.; Aritoni, O.: Benchmarking Database Systems for the Requirements of Sensor Readings. IETE Technical Review 26/5, pp. 342Ű349, 2009.
  • [Th15] Thomsen, J. et al.: Darstellung des Konzeptes Ű DMA Decentralised Market Agent Ű zur Bewältigung zukünftiger Herausforderungen in Verteilnetzen. In: INFORMATIK 2015. Vol. P-246. LNI, 2015.

citations.

  • Jensen, Søren Kejser, et al. “Time Series Management Systems: A Survey.” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 11, 2017, pp. 2581–2600.

see also

*1:gapが何を指しているかわかりづらかった。

*2:この基準は、NEMAR プロジェクトのコンテクストからきているとのこと [Th15]

*3:粒度は解像度とも呼ばれる

*4:rollup aggregationと呼ぶこともある。

*5:学位論文のようなので、質の程度は不明

論文 Middleware'17, Data-Driven Serverless Functions for Object Storage

  • [1]: Josep Sampé, Marc Sánchez-Artigas, Pedro García-López, Gerard París. 2017. Data-Driven Serverless Functions for Object Storage. In Middleware.
  • [2]: Josep Sampé. zion. https://github.com/JosepSampe/zion

論文のPDFは http://2017.middleware-conference.org/overview.html から手に入る。

どんなものか

  • オブジェクトストレージ向けのデータドリブンなサーバレスコンピューティングミドルウェアが提案されている。
  • データパイプライン上に、処理(computations)を注入することで、同期的なインタラクションを要求するユースケースに適している。例えば、動的コンテンツ生成やインタラクティブなクエリ、personalization、コンテンツの検証、アクセス制御など。

先行研究との差分はなにか

  • 従来のactive storage *1はデータ局所性を得るために、計算タスクをストレージノードに寄せている。そのため、ストレージノード数の分しかスケールアウトしない、計算リソースを共有するためリソース競合があるという課題がある。
  • 従来の非同期なイベントドリブンなサーバレスモデル*2とは異なり、オブジェクトストアに対するデータの読み書きを同期的にインターセプトできる。これをデータドリブンと呼んでいる。
    • AWS API Gatewayは余分なオーバヘッドともうひとつのAPIが増える
    • Amazon Lambda@EdgeはCloudFrontに対するリクエスト/レスポンスをインターセプトできるが、コンピューティングの制約が厳しい。ヘッダやメタデータの改ざん用にデザインされている。

手法の要点はなにか

[1]Figure 1より引用

  • Figure 1のようにstorage nodeとgateway nodeの間にcomputing nodeを配置し、レイテンシを削減する

有効性をどのように示しているか

実装

[1] Figure 2より引用

  • OpenStack Swift上にserverless frameworkのプロトタイプが実装されている。プロキシ側でリクエストをインターセプトするSwift Middlewareが唯一の変更点。[2]がおそらく公開されている実装。
  • computationレイヤは、Figure 2のように、Dockerコンテナで実装されている。

評価

  • 理想的な条件で、Swiftがstorage nodeでリソース競合することを確認
  • DockerとJavaのランタイムの起動時間が、0.85sec - 0.95secでAWS Lambdaの5倍速いことを確認
  • 10kBのオブジェクトに対して5,000 GETリクエストしたとき、Zion(提案手法)のオーバヘッドは9ms。ただし、Swiftへの内部ホップが5msなので実質+4ms。
  • アクセス制御、イメージリサイズ、署名検証、圧縮のそれぞれのfunctionについて、レスポンスタイムとスケーラビリティを評価し、レスポンスタイムについてはTPSを上げつづけてCPU 100%になるとレスポンスタイムが悪化することを確認し、スケーラビリティについてはstorage nodeを増やしてもTPSが向上せず、computingレイヤのワーカーを増やすとTPSがおおざっぱには線形増加することが示されている

議論はあるか

  • Amazon Athena、Redshift Spectrum、Facebook Prestoとの関連があり、Prestoのパイプライン実行により不必要なI/Oとレイテンシオーバヘッドを避けるところは、提案手法のモデルに似ているが、これらのシステムは汎用のfunctionを提供するわけではなく、インタラクティブなクエリ実行にフォーカスしている点が異なる。

興味深い関連論文はなにか

  • Scott Hendrickson, Stephen Sturdevant, Tyler Harter, Venkateshwaran Venkataramani, Andrea C Arpaci-Dusseau, and Remzi H Arpaci-Dusseau. 2016. Serverless computation with OpenLambda. In HotCloud.
  • Krste Asanovic and D Patterson. 2014. Firebox: A hardware building block or 2020 warehouse-scale computers. In FAST.
  • Peter X Gao, Akshay Narayan, Sagar Karandikar, Joao Carreira, Sangjin Han, Rachit Agarwal, Sylvia Ratnasamy, and Scott Shenker. 2016. Network requirements or resource disaggregation. In OSDI. 249-264.

*1:OpenStack Swiftなど

*2:AWS Lambdaなど

ウェブシステム内の待ち行列をMackerelで可視化してみる

この記事は、Mackerel Advent Calendar 2017の19日目の記事です。 前日は fullsat_ さんによる Lambdaを使ってMackerelのアラートをRedmineのチケットにする でした。

ウェブシステムの障害発生時に、どのコンポーネントの処理が滞っているかをざっくり知りたいことがあります。 そこで、ウェブシステムは待ち行列の集合体であることに着目し、各コンポーネント状態を把握するダッシュボードを最近作成しています。

待ち行列については、自分もそれほど詳しいわけではありませんが、をみるとざっと把握できます。 簡単な例として、安定した系であれば、リトルの法則により、平均待ち行列数Lは、平均到着率λと平均待ち時間Wの積に等しいことがわかっています。 リトルの法則とキャパシティプランニング - ゆううきメモ

これらのパラメータをウェブシステムに置き換えると以下のような見慣れた要素になります。

  • 平均待ち行列数 => ワーカースレッド数など
  • 平均到着率 => 単位時間あたりのリクエスト/クエリ数など
  • 平均待ち時間 => レスポンスタイムなど

これらの2つのうちが判明していれば、残りの1つも推定できます。

MySQLの場合

mackerel-plugin-mysqlで取得できるメトリックのうち、平均待ち行列数がmysql.threads.Threads_Running、平均到着率が分間クエリ数mysql.cmd.Com_select *1となり、平均待ち時間、つまり平均クエリ実行時間を以下の式グラフで可視化できます。

alias(scale(divide(max(role('ServiceA:db-master','custom.mysql.threads.Threads_running')),max(role('ServiceB:db-master','custom.mysql.cmd.Com_select'))), 60000), '推定平均クエリ実行時間 ms')

法則というと大仰ですが、実際は時間/クエリ/スレッドを計算しているだけです。 MySQLの場合、クエリ実行時間を取得する一般的な手法がない気がしているため、平均値だけ知るには良い方法となります。 しかし、ネットワークI/O時間を含まないため、ネットワークごしのクライアントからみた実行時間ではないことに注意します。

Webアプリケーションサーバの場合

Webサーバの待ち行列の状態を知るには、mackerel-plugin-accesslogが便利です。 特に、Webアプリケーションサーバがアクティブワーカー数などのメトリックを直接提供していないケースでは、nginxを同居させてアクセスログを集計しておき、分間リクエスト数と平均レスポンスタイムのグラフから、Webアプリケーションサーバのアクティブワーカー数のグラフを出力できます。

このように、各ロールについて、式グラフと、基となる2つのメトリックのグラフをダッシュボードに並べ、ざっくりどのコンポーネントの調子が悪いかを知る手段として活用しています。

*1:簡単のため、SELECTクエリが支配的であるとする

詳解システムパフォーマンス 8章ファイルシステム メモ

今回も章末の練習問題をみながら、みんなで議論をしていた。

アプリケーションの I/O パフォーマンスを解析するときには、ファイルシステムのパフォーマ ンスの方がディスクパフォーマンスよりも大きな問題になる。ファイルシステムは、アプリケー ションがディスクレベル(またはリモートシステムレベル)のレイテンシの影響を被らないように するために、キャッシング、バッファリング、非同期 I/O を使っている。それにもかかわらず、 パフォーマンス分析やツールセットは、伝統的にディスクパフォーマンスに重点を置いてきた。

Brendan Gregg,西脇靖紘,長尾高弘「詳解システム・パフォーマンス」, オライリージャパン p.337

この章では、アプリケーションからディスクまでのスタックのうち、ファイルシステムの層でなにが起きているかを大まかなモデルにしたがって説明してくれている。この章まで読むと、例えば read(2) vs mmap(2) の迷信 に書かれた内容がだいたい理解できるようになる。

議論していた内容は、主に以下のような内容。

メモ

チューニングの節で、前回の 詳解システムパフォーマンス 7章「メモリ」メモ - ゆううきメモ でも書いたposix_fadvise(2)の話があり、以下のようにcatコマンドをstraceすると、catのファイルアクセスパターンはシーケンシャルであることから、POSIX_FADV_SEQUENTIALにより先読みページ数をデフォルトの2倍にすることで最適化されているといった話をした。

|| [y_uuki@yuuki~]$ sudo strace cat /var/log/messages 2>&1 | grep -5 fadvise brk(0) = 0xc14000 brk(0xc35000) = 0xc35000 fstat(1, {st_mode=S_IFIFO|0600, st_size=0, ...}) = 0 open("/var/log/messages", O_RDONLY) = 3 fstat(3, {st_mode=S_IFREG|0640, st_size=10088, ...}) = 0 fadvise64(3, 0, 0, POSIX_FADV_SEQUENTIAL) = 0 mmap(NULL, 139264, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fc24d24b000 read(3, "Oct 29 06:25:11 yuuki rsysl"..., 131072) = 10088 ||<

詳解 システム・パフォーマンス

詳解 システム・パフォーマンス

詳解システムパフォーマンス 7章「メモリ」メモ

しばらく輪読を休んでたけど、再開した。第7章「メモリ」。 章末の練習問題を見ながら、みんなで議論していた。

  • メモリのページとはなにか
    • OSとCPUがメモリを管理する単位
  • 仮想メモリとは何か
    • 無限のメモリの抽象
    • メインメモリとスワップ領域を抽象化している
    • 他に抽象化している組み合わせはあるか? 分散OSの分野で、分散システム上の各ノードのメモリを一つの仮想メモリとして扱うみたいな研究はあるかも?
  • Linuxの用語では、ページングとスワッピングの違いは何か
  • スワップバイススワップファイルの違い?
    • mkswapでスワップ領域をブロックデバイスかファイルか選べる
    • ファイルのほうがダンプしやすそう。オーバヘッドも大きそう。
  • スワップ領域のサイズはいくつに設定する?
    • Chapter 7. Swap Space
    • 定期的にメモリをダンプして再開
    • live migration プロセスの状態を保存して移動 コンテナだとこういうの CRIU
  • デマンドページングの目的は何か
    • 仮想 => 物理のマッピング作成の遅延評価
    • これがないとCoWができない
  • メモリの使用率と飽和を説明しなさい
    • 使用率: ファイルシステムキャッシュは再利用できる
    • 飽和: 図7-6 メモリの解放 で上から順に戦略が使われる
    • リーピングとか実践で使ったことない
  • MMUとTLBの目的は何か
    • MMU: 仮想アドレスから物理アドレスへの変換
    • L1だけ仮想アドレス参照なのはなぜか?
      • L2以降はあとでつけたしたから?
      • L1には命令キャッシュが入ってるから?
      • 単に仮想アドレスで参照すれば速いため?
    • TLBは仮想アドレスから物理アドレスへの変換のキャッシュ
    • スレッドあたりのエントリ数が決められている => HyperThreading コンテキストスイッチ発生してもキャッシュが消えないメリットある?
  • ページアウトデーモンの役割は何か
    • ページキャッシュの掃除 フリーリストにいれる。kswapd
    • フリーリストはどこ?=> カーネル内。 図7-13
  • OOMキラーの役割は何か
  • 無名ページングとはなにか。ファイルシステムページングよりもこの種のページングを分析するほうが重要なのはなぜか
    • プロセスのプライベートデータのページング。ヒープ領域やスタック領域など。
    • ファイルシステムキャッシュはOSが追い出せる。プロセスのプライベートデータを解放できるのはアプリケーションのみ。
  • フリーメモリが不足したときに、メモリを広げるためにカーネルが取る手段を説明しなさい
    • ページキャッシュ追い出し => スワッピング => リーピング => OOMキラー
    • MyISAMは全部ページキャッシュ バッファプールとかない
    • 最近のLucenemmapでインデックスファイルをのせる。昔はJVMヒープ
  • スラブベースのアロケーションのパフォーマンス上の利点

最後に、Mackerelにおける時系列データベースの性能改善 / Performance Improvement of TSDB in Mackerel // Speaker Deck でのディスクスラッシング問題について話をした。 激しい random writeにより、ページイン数が爆発し、メモリを飽和させるので、ページアウト数もまた爆発する。ページキャッシュがなくなるため、read時にキャッシュミスし、read I/Oが増加する現象。 posxix_fadvise(2)のPOSIX_FADV_RANDOMにより、write時のページインの先読みを切ることができる。これにより、ページイン数を減らすことができる。 posxix_fadvise(2)のパッチをあてた前後で、/proc/meminfoのActive(file)とInactive(file)に変化があった。バッチ前は、Inactiveが多く、パッチ後はActiveが増えた。ActiveとInactiveの定義は以下の通り。

Active: Memory that has been used more recently and usually not reclaimed unless absolutely necessary. Inactive: Memory which has been less recently used. It is more eligible to be reclaimed for other purposes

https://www.kernel.org/doc/Documentation/filesystems/proc.txt

詳解 システム・パフォーマンス

詳解 システム・パフォーマンス