THINKING MEGANE

Go Conference 2018 Autumnで発表してきた(3年ぶり3回目)

11/25にGo Conference 2018 Autumnというイベントでフィードバック制御によるGoroutine起動数の最適化を発表してきました.

Goでの開発時に常に悩んでいたGoroutine起動数に関してフィードバック制御という切り口でKaburayaアーキテクチャと題して解決策を検討したものです. 直前にWSA研向けに研究として再定義したことでGoroutineにこだわらない,より汎用的な問題に対するアプローチとして検討し直すことができ,まだ最適解は模索中ですが,面白いと思っていただける発表ができたのではと考えています.

歴史ある制御工学という分野の手法を用いることで蓄積されたノウハウを活用できると考えていましたが,発表後に早速有意義なアドバイスなど頂くことができ,今後の精度,速度向上並びに汎用化に向けて面白くなってきそうです.

ちなみに開発にあたってGoランタイムを調べていた時の資料も#goconハッシュタグで放流したところ,こちらも好評でしたので改めて置いておきます.

発表を終えて

GoConでの登壇は今回で3回目となりました.ここ数年,自分のキャリアや興味範囲が広がっていく中でも,Go言語はずっと相棒として付き合ってくれる言語でしたし,Go言語を中心に色々な付き合いができていると感じています. そしてその契機となったGoConと,これを継続して開催してくれている運営の方々に本当に感謝いたします.

主催するFukuoka.goでも微力ながらコミュニティの活発化に繋がるよう引き続き”楽しみながら“やっていきたいと思います.

次は海外カンファレンスで登壇するぞう.

Gopherくん

今回で登壇特典のGopherくん全色コンプリート!!

gophers

過去の発表

Kaburaya: CPU負荷に応じて継続的に上限値を最適化する動的セマフォ

このエントリは、第三回 Web System Architecture 研究会 (WSA研)の予稿です。

はじめに

マルチコア時代において,単一のマシンで処理性能を最大化するため処理の並行化が行われる. ノンブロッキングな処理方式の採用によってCPUを効率的に使用する場合には最適な並行数はCPUコア数と等しくなる. しかしノンブロッキングを実現するランタイム実装の限界から,もしくはノンブロッキングを採用していない場合のような,全体的もしくは部分的にブロッキングが発生する状況においては,最適な並行数の決定は依然として開発者の経験と地道なチューニングに依存している. このような最適な並行数を求める例としてnginx, unicornのworker_processes,Sidekiqのconcurrency,Goroutineの起動数などが挙げられる. これらは、実行される処理の負荷や特性がアプリケーションごとに異なるため実行される処理の特性とランタイムやスケジューリングの特性を考慮したチューニングが必要になる. このような複雑な系に対する普遍的なチューニング手法の発見は困難であることから,これらをブラックボックスとして扱い汎用的に調整できる手法が求められる.

三宅らは仮想サーバの予測的オートスケーリングにおいて,アプリケーションの処理内容ではなく運用経験から得られたサーバ単位のスループットを指標として,これを予測するモデルによってサーバ台数調整機能を実現した. また,「全自動パラメータチューニングさん」ではメトリクスを一点に絞りスループットが最大化する値を探索的に求める. これらの手法は指標を限定しても充分な成果が得られることを示した.一方でその求め方は予測的または探索的であり,Webサーバープロセスのように比較的長期稼働する場合に適用可能である. しかしながらCLIのような短期稼働かつ性能が求められるようなプロセスにおいては予測や探索は利用できない. これらの利用用途に対応するため,指標の限定に加え,反応的かつ誤差が少なく指標へ追従する手法が必要である.

本研究では,処理やランタイムの特性に依存せずに,マシンの負荷に応じて反応的かつ継続的に,並行数を最適化する手法を検討する. まず,最適な並行数を求めるために,最適化の手法としてフィードバック制御を用いる.指標にはノンブロッキングな処理方式がCPUを効率的に利用することに着目し,CPU使用率を採用する. 次に,並行数の制御にはセマフォを採用することで提案手法に汎用性を持たせる. 本報告では,ノンブロッキングな処理方式をランタイムとして採用するGo言語において,CPU負荷に応じて継続的に上限値を最適化する動的セマフォを実現するライブラリを開発し,これを評価する.

実装

フィードバック制御を用いてGoroutineの起動数を動的に調整する手法を実装するためには,ある時点で最適なGoroutineの起動数をフィードバック制御によって決定する仕組みと,その起動数を制約としてGoroutineの起動数を制御する仕組みが必要となる. このような並行処理の起動数を制御する仕組みには一般的にセマフォが利用される.Go言語ではセマフォとしてバッファ付きチャンネルを用いるのが定石となっている. そこで本研究では,最適なセマフォの値をフィードバック制御によって動的に変更可能な仕組みを構築した.なおこの実装はOSSのkaburayaとして公開している.

制御器

本研究では,ある時点で最適なGoroutineの起動数をフィードバック制御によって決定する仕組みを制御器と呼ぶ. 今回,制御器の設計についてはGoroutine起動数が制御可能な入力となる.これによって対象のスループットを最大化するのが目的である.しかしながら実行される処理の負荷や特性が異なっても共通に採用できる固定値のスループット値は事前に求めることはできないため別の指標を用いる必要がある. 本研究ではいくつかの制御器の評価を通して効果的な制御器を求める. 以降,Go言語ランタイムがI/Oブロッキングな処理についてもGoroutineの切り替えにより、その負荷をCPU側に移動させることから,CPU負荷が安定になることが一つの上限とみなせると仮定していくつかの制御器を設計する.

  1. 初期値からワーカー数を変えないFixController (比較用)
  2. CPU使用率100%を目標値とし,不足した場合は workerを1ずつ増加させる SimpleController
  3. CPU使用率100%を目標とし,目標との差分のK倍を加える PController(比例制御)
  4. 3.のCPU使用率の目標値を90%としたもの
  5. 直近3観測点の平均を目標値として3観測ごとにPControllerの目標値を変化させるDynamicController
  6. 一定期間のCPU使用率の標準偏差をとってそれが一定の値以下だったら安定したとみなして,workerを減らしていくStabilityController
  7. CPU使用率ではなくてCPU使用率の変化率を元に制御するRateController
  8. 5.のDynamicControllerを元に定期ではなく大きな変動ごとに目標値を見直す方式
  9. 8.のDynamicControllerを元に定常時の不要なworkerを削減する方式
  10. 9.のDynamicControllerを元に変動の精度と速度を向上させるために積分微分制御を導入する方式

セマフォ

本研究では,制御器によって決定された起動数を制約としてGoroutineの起動数を制御する仕組みをセマフォと呼ぶ. 今回のセマフォの要件としてはセマフォの上限値が動的に変更可能であること,そして通常のセマフォと同様にP操作において値が負になる場合に実行がブロックされる.またこれらの値の変更がアトミックに行われる必要がある.

これらはGo言語では二つのチャンネルを組み合わせることで実現可能である.すなわち,それぞれのチャンネルからの入力と出力でセマフォの値を更新し,必要に応じて内部でチャンネルへの操作の有効無効を切り替えることで結果的に利用者側に対するブロック処理を実現する.

評価

本研究では,設計した制御器の出力する起動数が最適であることを検証する.ここで最適であるとは,処理対象のタスク全体を,最低限の,のべ起動数で,最短の時間で処理できる起動数を指す. 評価には,汎用性と再現可能性を高めるため,以下の機能を持つシミュレーターを用いる.

  • シミュレータは実時間ではなく,単位時間をステップとみなす
  • JobはWorkloadを持ち,ステップごとのCPU利用率を定義する
  • Workloadが0のステップはブロッキング処理を表現する
  • シミュレータはステップごとに任意の数のジョブを投入する
  • シミュレータはステップごとに起動可能なワーカー数を制御器から取得する
  • ワーカーはシミュレータで利用可能なCPU利用率までジョブの該当ステップのWorkloadを消費する
  • 消費できなかったWorkloadは次回のステップに回される
  • Workloadが0のステップはCPU資源を消費しないため無条件にステップを進める

  • 現状はスイッチングコストがシミュレータに反映できていない.

JobにはCPUビジーとなる処理,多くのシステムコールが発生する処理,ネットワークのような長期間のブロッキングが発生する処理などを再現したものを投入する.

設計した制御器に対する主な評価結果は以下のとおり

シミュレーション1

初期値からワーカー数を変えないFixControllerによって固定値での最適なワーカー数を求めた.今回のシミュレーションではworker:7 ぐらいが最適と考えられる.

result

シミュレーション2

CPU使用率100%を目標値とし,不足した場合はworkerを1ずつ増加させるSimpleControllerでは,ジョブが多く投入される初期段階においてワーカー数の増加が追いつかないことからジョブ全体の処理がシミュレーション1と比較して長くなってしまっている.

result

シミュレーション4

CPU上限を目標値とした場合に制御器の出力が負にならないため,ワーカー数を削減することができない.そこでCPU使用率90%を目標とした.CPU上限に達した場合に不要なワーカー数を削減する一方で,目標値が固定のため,ジョブが完了し,CPU使用率が低下した場合にも反応してしまった.

result

シミュレーション5

目標値が固定であることからジョブ完了後にワーカー数を増加し続けてしまう問題に対応するためCPU使用率の目標値自体を変動させることとする. 本シミュレーションでは,CPU使用率が均衡する時点をワーカー数の上限であると仮定し,直近3観測点の平均を目標値として3観測ごとに制御器の目標値を変化させるDynamicControllerを実装評価した.

result

シミュレーション9

CPU使用率やジョブ実行状況にできるだけ速く追従するため,一定間隔ごとに目標値を見直すのではなく,CPU使用率の変動があった時点で目標値を変更する. 大きな増減を契機に調整していく仕組みになったことで,CPU安定時に積極的にワーカーを削減することができるようになった

以下では目標値の変動を赤でプロットしている.

result

シミュレーション11

頻繁に変更される目標値に高速かつ誤差が少なく適応していくため古典的制御手法であるPID制御を導入した. 調整の結果,本シミュレーションではPID制御のゲインとしてKp: 0.1, Ki: 0.5, Kd: 0.5が有効であった.

result

result

その他のシミュレーション

検討段階の各シミュレーション結果についてはこちら以降のコメント欄を参照のこと. 制御器の実装の番号とシミュレーション番号が同じにしている.

また,実環境で同様のジョブを用いた評価結果について今回は間に合わず未評価である.

まとめ

本研究では,処理やランタイムの特性に依存せずに,マシンの負荷に応じて反応的かつ継続的に,並行数を最適化する手法として,CPU負荷に応じて継続的に上限値を最適化する動的セマフォを提案した. また,シミュレーション環境においてではあるが,ノンブロッキングな処理方式を前提とする場合に有効なCPU使用率の目標値を負荷情報に応じて変動させる制御器として設計することができた. 本方式はCPU使用率とセマフォというランタイムや実装に依存しない方式を採用しているため,並行数を求めなければならない様々な場面に適用可能であると考える. 今後の課題として,実環境での評価としてGo言語のGoroutineの起動数に対する評価が必要である. また,制御器のパラメタ設計も課題として挙げられるが,フィードバック制御という歴史ある分野の蓄積を有効的に活用することで解決したい.

発表スライド

発表を終えて

第三回のWSA研も様々な観点からの提案と活発な議論が交わされる有意義な場であったと思う. 特にrrreeeyyyさんのA survey of anomaly detection methodologies for web systemは業務で得た知識をサーベイ論文と組み合わせて再体系化していく非常に興味深い試みで,サービス運用者が参考にしていくべき取り組みだと思えた. 自分自身の研究発表では,個人的な開発時の課題であるGoroutine起動数のチューニングという課題から,研究を意識して問いを抽象化することで,実装に囚われない多角的な解決策を講じることができた点が良かったと思う.質疑では本手法が活きる場面を整理できていなかったことに気づけたことでもう一段先に進めた. 自身のアイディアや実装など狭い範囲から視点を広げるのは難しいことではあるが,こうして研究会を契機に継続的に訓練していくことで少しづつでも前に進んでいると思えるのはとても嬉しい.

理性の人

思えばこの一年半は自分の感情に振り回された期間だった. エンジニアとして新しい道が見えながらも,そこに近づけない不甲斐なさと焦り. 自己肯定感が著しく下がったために価値基準がだんだんと外部へ移り,余計に道を見失う. 局所的には努力しているけれども,不安解消や短期的な承認に囚われて殻にこもりがちになる. 愚痴や相談で一時的に心は軽くなれどもいつのまにか焦りが高まる.

いい加減,自分との向き合い方について考えなければならない時期だと思った.


幸いにもここ最近,何人かの自分の尊敬する人とまとまった時間話す機会があり,自分との考え方の違いなどを意識して比較してみた. 元から,皆一様に論理的で理路整然と自他の意見の要点や本質を掴んだ議論ができる能力の面で見習いたいと感じていたのだが, 最も自分と違っていたのは,客観性をもって自分がなすべきことを検討し続け,そこに向けて邁進している点だと思えた.

すなわち,彼らは理性的であった. 理性とは,手元の辞書によると「感情に動かされたりしないで,論理的に考えをまとめたり物事を判断したりする頭の働き」とある.

自分も感情に振り回されないようになれば,先に進めるのかと思いつつも,思考から感情を分離することはとても難しいことではないかと思えた. なぜなら自分は極度の負けず嫌いである.自分にも他人にも負けたくないというのが心根にある.勝っていたり承認されている状態というのは素直に嬉しいし,この動機付けが今まで自分を成長させてきたとさえ思っている. しかしながら,この主観的で感情的な動機は上手くいくうちは良いが,失敗すると簡単に歪んでしまうというのもまた事実である. 誰かに勝つため,負けないため,舐められないため,価値を認めてもらうため.往往にしてなすべきことではないものを目指し始める.さらには引け目があるから,それらを貫き通すことも難しくなる.

ただ,このようなことを悶々と考えるうち,自分の中で感情的である状態と理性的である状態というのを区別し現状を俯瞰できるようになってきた. ここで,理性的な人は,感情を抑え込むのではなく,感情とうまく付き合い,感情に動かされないための方法論をそれぞれ持っているのではないかと考えた. 自分の場合,承認欲求は強く自己と結びついてしまっていてこれを無視することはできない.であれば二つの状態があることを認識し,これを行き来するための方法論を見つけることで理性的に振る舞えるようになるのではないか.

理性の人でありたい.

  • 理性の人は,感情を抑え込むのではなく感情に動かされないための方法論を持つ.
  • 理性の人は,論理的になすべきことを定める.
  • 理性の人は,なすべきことを解決するため,己を高める.
  • 理性の人は,なすべきことを解決するため,周りと協力する.

何も感情を無くそうというのではない.自分の性質のため視野が狭くなりがちなことを認めて,目的を客観的に定めたのち,楽しい手段を見つけたい.行動方針における優先順位を明確にしただけである. 結果的に相対的な価値観の世界からも脱却し,より大きなことを成せるのではないかと思う. もちろん,理性の人になるためには多くの努力が必要であり,今後も継続して努力していく.技術力も思考力に対してもやるべきことはたくさんある.ただ,局所的であろうが今までの努力も無駄ではない.うまく活かして一気に花開きたい.

First Half of 2018

上期も昨年度から引き続き研究開発に従事した.これまでやってきたいくつかの研究が繋がり始めて”なめらかなマッチング”というおぼろげながら大きな研究テーマが見えてきたように思う. 推薦システムに代表されるような要望と提案のマッチングをなめらかにするためには,マッチング観点からの研究と,それをサービスとして的確かつ即時に提供できるような実装や導入の観点からの両方が必要であり,マッチングを支える仕組み全体に対する研究を進めていきたいと考えるようになった.

また,上期はこのテーマに基づく各研究内容を実装するにあたって技術的な深堀りを進めることができたこと,継続してアウトプットを続けることができたのも良かった. マッチング観点からは消費者行動や情報探索プロセスも考慮しながら検討している.実装面からは,近似近傍探索を高速かつ高精度に提供するためにSannyやSmux,go-avxなどこれまでよりレイヤを掘り下げながら目的を達成するための最適な実装を検討することができるようになった. アウトプットについても,これらの内容を元に継続的にブログや登壇を行った. 技術的な必要性などをきちんと記述することで反響が大きくなるものもあり論理的な思考やそれを用いて人に伝えることの重要性も感じた.

それでも,特に論文のような専門的なアウトプット過程において,力不足は常に感じていた. 論文執筆において,初稿はなんとか書き上げられるようになったものの,共著者や査読からの指摘点を踏まえてより良いものにするための議論が上手くできず,徐々にこれがストレスとなってしまっていった. 技術的な背景による新規性についてはサーベイの積み重ねで少しづつでも回答できるが,研究として新規性や有用性を謳う部分,これらを論述する部分の議論において,そもそも前提となる能力が足りないようにも思えた. 論文執筆を続けていく中でこれらの能力が上がるようコツがつかめてくるのかもしれないが,自分としては一旦この足りない能力についてきちんと向き合った上で,今後の研究開発へ取り組んでいきたいと思っている. そのため下期はこれまでの研究開発成果を導入・課題発見の部分に力を注ぎながら,論文執筆に向けたスキルを高めていきたい.

実績

以下,上期実績を列挙する.

論文

3本,ジャーナルについては事前査読制度への投稿のみで終わったこともあり,上述した対策を進めた上で再度挑戦したい.

発表

技術イベントでの発表の他,研究会での発表,大学での登壇など計6回.

OSS

なめらかなマッチングの実装面の観点から高速かつ高精度,かつ拡張性も備えた近似近傍探索の実装とそれらの要素技術の検討を行っていった. Smuxやgo-avxなどこれまで扱ってこなかったレイヤで課題に対処できるようになってきたと思う.

  • Sanny: Scalable Approximate Nearest Neighbors in Golang optimized for embedding vectors.
  • go-avx: AVX(Advanced Vector Extensions) binding for golang.
  • Smux: smux is a socket multiplexer written in Golang. It provides fast communication by efficiently a single connection.
  • SmartSifter: SmartSifter (On-line outlier detection) by Golang.
  • Guardian: Monitor file changes and execute custom commands for each event.
  • Gannoy(NGT ver.): Approximate nearest neighbor search server and dynamic index written in Golang.

コミュニティ活動

福岡のGo言語コミュニティ主催として継続的なイベント開催を進めた. 研究開発とはまた別の技術の付き合い方ができる活動であり,大切な活動となっている. また,分散アプリケーションも興味があるため仮想通貨コミュニティの地方開催もお手伝いさせていただいた.

ブログ

実装紹介を主に7本.もう少し気軽に考えをまとめてアウトプットするようにしたい.

読書

半期で購入した本と読み直した本を重ねてみた.物理本が54冊.電子書籍を含めるともう少しなりそう. ベイズは相変わらず分からない. これだけ学んだのだという自信が半分,本当に自分の知識として議論へ活かせるようにせねばなという反省が半分.

books

まとめ

上期はとにかく濃くて長い半年だった. 論文執筆など自分が上手くできないことに対してストレスと感情の起伏が大きくなってしまって相変わらず未熟だなあと反省しきりであったが,こうして客観的に実績としてまとめてみると進んでいるところももちろんあって,適切に都度自分を認めてあげなくてはなあと思えたのはよかった.

もちろん力不足で悔しい思いをしているのは事実であるので,下期は研究開発への付き合い方も見直しながら,まわりも見る余裕を持って,どんどん影響を与えていけるよう成長できればなあと思う.

Sanny: 大規模ECサイトのための精度と速度を両立した分散可能な近似近傍探索エンジン

このエントリは、第二回 Web System Architecture 研究会 (WSA研)の予稿です。

はじめに

ECサイトの商品種類増大に伴う情報過多問題を解決するため,利用者の要求を満たす商品を自動的に提案する機能がECサイトにとっての関心事となる.商品の提案は任意の観点での商品同士の類似性を根拠とすることから,商品の特性を数値化し,任意の距離空間で近傍に位置する要素を求めることで,機械的に扱えるようにする.この数値化された商品特性を特徴量と呼ぶ. 深層ニューラルネットワークの発展によって,これまで適切な特徴量を導くことが難しかった画像やテキストに対しても,人の感性に近い,特性をよく表現する高精度な特徴量を得られるようになったことからECサイトの商品提案機能に利用され始めている. これらの深層ニューラルネットワークから得られる特徴量は,数百から数千次元の高次元ベクトルとして表現される. また,大規模なECサイトでは提案対象となる商品数も多いため,この特徴量の集合も数十から数百万を超える大規模なものとなる. このような大規模かつ高次元ベクトル集合に対する類似度の比較において,正確ではあるが,データ数と次元数に比例して計算量が増加する線形探索は現実的ではない.そこで,事前に近傍候補となる集団を求めておくことで,少数の近傍候補から計算量を抑えて近傍点を得る空間分割や局所性鋭敏型ハッシュといった手法が用いられる. しかしながら,高次元ベクトル集合においては正確な近傍を求めるための計算量が線形探索と同程度となると考えられており,精度を犠牲にして近似解を用いることで計算量の増加に対処する近似近傍探索が採用されているが,商品を自動的に提案する機能は、提案内容の的確さと充分な応答速度が求められることから,大規模かつ高次元ベクトル集合に対して精度と速度を両立する近似近傍探索の手法が必要となる.

大規模かつ高次元ベクトル集合に対する近似近傍探索では,データ数と次元数に依存して計算量が増加するため,これらを分割して処理することが効果的である. ベクトル集合を行列と見なし,行方向での分割,つまりデータ数によって分割する手法は一般に採用されるが,依然として次元数に依存した計算量の課題は残る. そこで,列方向での分割が必要となる. 直積量子化は,高次元ベクトル集合を任意の次元数の低次元ベクトル集合に等分し,各低次元ベクトル集合に対する近傍探索結果を集約する. しかしながら,集約処理はデータ数に依存するという課題がある.

そこで,本報告では,大規模ECサイトで商品を提案することを想定して,精度と速度を両立した分散可能な近似近傍探索エンジンSannyを提案する. Sannyは,商品特性をよく表現しており高精度に類似度が比較可能な高次元かつ密なベクトルの集合において,検索質問データ(クエリ)に対する高次元ベクトル集合の近傍探索結果の上位集合が,クエリと高次元ベクトル集合を任意の次元数で等分した部分ベクトル単位で近傍探索した結果の上位集合と類似しやすいことに着目して,提案すべき商品の近傍探索を部分ベクトル単位での探索に分解することで分散処理可能にし,その探索結果の和集合である近傍候補から再度近傍探索を行うことにより,全体として高速に近似近傍探索を行える.

提案手法

事前準備

提案手法ではまず,商品特性をよく表現しており高精度に類似度が比較可能な高次元かつ密なベクトルの集合を対象とする. このような集合として,学習済み深層畳み込みニューラルネットワークを特徴抽出器として利用して画像から得られる特徴量集合や,テキストを分散表現へ変換するWord2vecのネットワークから得られる特徴量集合がある. 筆者らはこれらの集合において,検索質問データ(クエリ)に対する高次元ベクトル集合の近傍探索結果の上位集合が,クエリと高次元ベクトル集合を任意の次元数で等分した部分ベクトル単位で近傍探索した結果の上位集合と類似しやすい特性があることを見出した. この,高次元ベクトルで表現される特徴量のうち,部分が類似しているものは全体としても類似する可能性が高いという特性を利用することで,高次元ベクトル集合を列方向に分割した結果の集約のデータ数依存の課題を解決する.

ここでは,対象となるベクトル集合を$Y \subset \mathbb{R}^D$と置き,これを重複しない$D^*=D/m$次元の部分ベクトル$S_j(1 \leq j \leq m)$に分割する.

近傍探索

Yに対する近傍探索は次のように行う. クエリベクトル$q \in \mathbb{R}^D$を$p_j (1 \leq j \leq m)$に分割し,対応する添え字$j$の部分ベクトル集合$s_j$に対して上位$n$件を得る近傍探索を行う.

\begin{align} NN(p_j) = \argmin_{s \in S_j} d(p_j,s) \end{align}

$NN(p_j)$の結果を$n$個の識別子からなる集合$N_j$とし,全ての$N_j$の和集合を$N$としてこれを近傍候補とする.なお,距離関数には現時点でユークリッド距離を想定しているが,すべての部分ベクトルで統一されていれば近傍探索の手法自体は問わない.

最後に近傍候補$N$に対応する元のベクトル集合 $YN \subset \mathbb{R}^D$ に対して正確な類似度を比較するためにクエリベクトル$q$との線形探索を行う.$|YN|$は最大$n*m$であることから線形探索のコストは非常に小さいが,距離関数にユークリッド距離を用いる場合,以下で求まる近似的な線形探索を用いることで一層の高速化が見込める.

\begin{align} argmin_a (a - b)^2 = argmin_a a^2 - 2ab + b^2 = argmin_a a^2 - 2ab \end{align}

システム構成

提案手法では,探索対象となる高次元ベクトル集合を任意の次元数で等分した部分ベクトルに分割する.これらの部分ベクトルに対する近傍探索は互いに独立していることから並列に処理することができるため,データ数や次元数に応じた分散構成を取ることができる. 分散構成では,部分ベクトルの近傍探索結果$N_j$がネットワーク上でやり取りされるが,前述のように最小限のデータ量のみが通信されることからネットワーク通信における影響を抑えることができる.なお,大規模なECサイトにおいては大量のクエリが想定されることから,HTTP/2のバイナリフレームレイヤーのように通信の多重化を行うことで影響を抑える手法も合わせて導入する.

また,分散構成では,データを重複して保持することで,可用性も高めることができる.

評価

速度と精度による性能評価

以下に,2048次元,40,000件程度の高次元ベクトル集合に対して提案手法と従来手法の精度と速度のバランスを比較した予備実験の結果を示す.横軸は再現率であり,各手法の提示した予測近傍集合と正しい近傍集合との重複率である.縦軸は検索にかかった秒数の逆数を取ったもので,上にあるほど高速である. 従来手法として,線形探索(brute_force),近似線形探索(brute_force_blas),近似近傍探索(annoy)と比較した.提案手法は,近傍候補から正確な近傍を求めるために用いた手法ごとに評価を行なっている.

sanny

結果から,近傍候補からの探索に近似線形探索を用いた場合の提案手法が従来の近似近傍探索手法より精度並びに速度でも有効であることを示している.

発表スライド

発表を終えて

大規模なデータセットでの評価,事前分類による推薦との差など研究報告としてはまだ新規性や有用性の面で示しきれていない箇所もあったが,そこも含めて議論ができてよかったと思う.特にGPU環境での評価や,データ数や次元数への依存が少ないと思われるLSHなどの手法への適用など具体的に差を示すべき箇所が浮かんできたのが収穫である.サーベイ並びに評価を進めたい.

WSA研は,事業で研究的なアプローチをどう活かすかを普段から考えて実際に成果を出している人々が集まっている.研究成果とサーベイを携えて次はどう論述するかについて吸収し,次回は誰かに影響を与えられるようになれたら良いなと思う.

Go言語でTCPやソケット通信を多重化,高速化するsmux(ソケットマルチプレクサ)をつくった

サーバ間で分散処理を行う際の相互通信におけるボトルネックを解消するため,smux(Socket multiplexer)を開発している.

サーバ間の相互通信におけるボトルネックとその解決策

一対のサーバ間で多数のリクエストとレスポンスが送受信され,信頼性の高い通信としてTCPを利用する場合,コネクション確立のオーバーヘッドを排除するために接続の再利用が行われる.しかしながら,クライアントは送信に対する受信を待つ必要があるため,レスポンスまでに幾許かの処理時間を要する状況では送信のキューがたまってしまう.そこで複数の接続を利用することでこれを解消する方法が取られるが,追加の接続はリソース使用に関するオーバーヘッドを発生させてしまう.なにより各接続におけるレスポンス待ち時間は依然として解決しておらず,接続の利用面から見て非効率である.そこで,単一の接続において,仮想的に並行送受信を行う方法が提案されている.これは,HTTP/2におけるバイナリフレーミングレイヤの役割であり,コネクション内にストリームと呼ばれる仮想的なチャンネルを設けて双方向の通信を並行して行う.下位レイヤの制約であるリクエスト送信後のブロッキングは,リクエストやレスポンスをフレームと呼ばれる単位に分割することで影響を抑えている.

このように多数のリクエストとレスポンスが送受信され,レスポンスまでに幾許かの処理時間を要する状況においては,HTTP/2は非常に魅力的であり,はじめに採用を検討すべき価値がある.一方で,HTTP/2を利用する場合,HTTPプロトコルに依存した一定のオーバーヘッドは発生する.もちろんHTTP/2にはバイナリ化やヘッダ圧縮などの多数の対策が組み込まれているため,自身の適用課題において十分な性能が見込めるならば問題ないが,より最適化したパフォーマンスが必要な状況では,これらのオーバーヘッドの除去も検討の余地がある.

smux(Socket multiplexer)

smux(Socket multiplexer)はこのような状況において,非常にシンプルなバイナリフレーミングレイヤの振る舞いをアプリケーションに提供する.すなわち,単一コネクションの仮想多重化である.アプリケーションは独自の(そしておそらく簡潔な)プロトコルに則ってストリーム経由でデータを送受信する.複数コネクションのハンドリングが不要になり,複数のリクエストを並行して発行することができるため,アプリケーション実装は簡潔に,通信は高速になることが見込める.

smuxはGo言語で実装されており,アプリケーションがGo言語であれば,以下のように利用することができる.

// smux server
server := smux.Server{
	Network: "tcp", // or "unix"
	Address: "localhost:3000", // or "sockfile"
        Handler: smux.HandlerFunc(func(w io.Writer, r io.Reader) {
                io.Copy(ioutil.Discard, r)
		fmt.Fprint(w, "Hello, smux client!")
        }),
}

server.ListenAndServe()
// smux client
client := smux.Client{
	Network: "tcp", // or "unix"
	Address: "localhost:3000", // or "sockfile"
}

body, _ := client.Post([]byte("Hello, smux server!"))
fmt.Printf("%s\n", body) // "Hello, smux client!"

内部的には,streamはReadやWriteのメソッドを持っているため,より最適化したい場合はこれらを自身で利用することもできる. また,あくまでソケットインターフェースを経由したやり取りであり,smuxのプロトコルに従えば他の言語での実装も可能である.

パフォーマンス

以下は,smuxとHTTP/1.1,HTTP/2を対象としたベンチマークである.それぞれ多重度として,コネクション数やストリーム数を増加させながら,一定数のリクエストを捌くまでの時間を計測した.リクエストとレスポンスの内容,サーバサイドでの処理は各手法で統一している.また,サーバーサイドでの処理の代替に数十msのsleepを入れている.

benchmark

今回の条件では多重度を上げた場合に,手法によっては性能が頭打ちになる中で,smuxが特に高い多重度において性能を十分に発揮できた.今回のベンチマークはサーバーとクライアントが同一の環境であり,各手法に適したチューニングや適用時の条件によっても変動はあると考えられるため,利用においては条件に合わせたパフォーマンス計測を行うことが望ましい.ベンチマークのコードはここにおいている.

まとめ

サーバ間通信のボトルネックを解決するため,HTTP/2のバイナリフレーミングレイヤを参考に,プロトコルのボトルネックを排除するシンプルなコネクションの仮想多重化を行うsmuxを開発した.手元でのベンチマークでは,できるだけ多くのリクエストを並列に処理したいような状況で効果がありそうであることが確認できた.まだまだ安定性の面などで不安もあるが,引き続き本番運用に向けて開発を継続していきたい.


2018/05/04追記

コメントにて先行実装として,hashicorp/yamuxxtaci/smuxを教えていただいたので,ベンチマークを再実行した.xtaci/smuxはSimple Stream Multiplexingらしいので,ここではssmuxと呼称する.

benchmark_2

yamuxに対しては同等以上と言えるが,ssmuxが優秀であるという結果になった.両者とも,ストリームにおけるリクエストに対してレスポンスが発生する場合では,リクエスト側の終了を検知するためにクローズ処理が利用できないため,別途自前でデータサイズを送信する必要があるなど使い勝手に関しては多少の難もありつつも,実装や性能については参考になる部分が多い.まだ改善の余地が残っていること,着眼点自体は良さそうであるという点は喜びたい.並列時の性能に効果があると考えられるフロー制御周りを中心に実装参考しながらパフォーマンスなど改めて見直していく.

Go言語でオンライン外れ値検出エンジンSmartSifterを実装した

推薦システムにおける被推薦者の文脈把握に向けて確率的な手法での行動分析を検討している.そこで,データマイニングによる異常検知で紹介されていたオンライン外れ値検出エンジンであるSmartSifterの理解を深めるため実装してみた.

SmartSifter

On-line Unsupervised Outlier Detection Using Finite Mixtures with Discounting Learning Algorithms. This method is proposed by Yamanishi, K., Takeuchi, J., Williams, G. et al. (2004)

refs: http://cs.fit.edu/~pkc/id/related/yamanishi-kdd00.pdf

SmartSifterはデータの発生分布が時間とともに非定常に変化していくことを考慮した外れ値検出の手法である.離散値と連続値のベクトルを入力とし,離散値はヒストグラム型の確率密度関数で,連続値は混合ガウスモデルで表し,これをデータから推定する.実際にはオンライン対応のために忘却型学習アルゴリズムとしてそれぞれ拡張されたSDLEとSDEMと呼ばれるアルゴリズムが利用される.また,パラメトリックなモデルを用いるSDEMアルゴリズムはノンパラメトリックなSPDUアルゴリズムと交換することが可能である.外れ値のスコアリングには対数損失またはヘリンジャースコアを利用することができる.詳細は上記論文を参照されたい.

外れ値検出

Old Faithful Geyser Dataとして公開されている間欠泉に関するデータを用いてオンライン外れ値検出を試みる.

smartsifter

x軸がeruptionsで,y軸がwaiting.各軸は標準化N(0,1)で標準化済みとする.このデータを順番に入力し,各入力でオンライン学習されたSmartSifterの外れ値スコアを全エリアで確認した.スコアが高い(=外れ値の確率が高い)ほど黄色に近付く.

入力が進むごとにデータの分布に大まかに沿うようにスコアリングされていることが確認できる.

離散値を含んだ外れ値検出

SmartSifterは離散値ベクトルを排反な集合に分類したセルごとに混合ガウスモデルを学習する.標準化後の間欠泉のデータからxが正か負,yが正か負かの4象限をセルとしてオンライン外れ値検出を試みる.

smartsifter_2

各セルごとにスコアが異なることが見て取れる.実運用ではsource-IPaddressなど,各セルごとに連続値側の振る舞いが異なることが想定されるようなものが与えられるだろう.

実装

実装は論文に準じているが,$\overline{\mu}_i^{(t)}$と$\overline{\Lambda}_i^{(t)}$については論文中に初期値が与えられていなかったので,それぞれ$\mu_i^{(t)}$と$\Lambda_i^{(t)}$から求めた.また,$\Lambda_i^{(0)}$は単位行列とした.

現状,Golangからは以下のように利用することができる.

r := 0.1 // Discounting parameter.
alpha := 1.5 // Hyper parameter for continuous variables.
beta := 1.0 // Hyper parameter for categorical variables.
cellNum := 0 // Only continuous variables.
mixtureNum := 2 // Number of mixtures for GMM.
dim := 2 // Number of dimentions for GMM.

ss := smartsifter.NewSmartSifter(r, alpha, beta, cellNum, mixtureNum, dim)
logLoss := ss.Input(nil, []float64{0.1, 0.2}, true)
fmt.Println("Score using logLoss: %f\n", logLoss)

まとめ

こういった確率モデルに従うようなアルゴリズムの勉強のため,今回はSmartSifterを実装した.実運用ではハイパーパラメータの調整が必要になってくると思われるが,今回のような単純なデータであれば想定した結果を得られることがわかった.

現状,ヘリンジャースコアやノンパラメトリックなアルゴリズム(SPDU)は実装していない.また,CLIも用意していないので今後必要になれば順次実装していく.

また,今後は独立モデルとしての外れ値検出だけでなく時系列モデルや行動モデルを仮定していく異常検出も試していきたい.

Archives