発明のための再発明

内部動作のような、プログラムを書くときの参考になることを書きます

巨大企業のサーバー構成や内部ツールを覗く

はじめに

この記事は設計・アーキテクチャ Advent Calendar 2018の1日目の記事です。

大きなサービスを支えるのは一筋縄では行かず、考えることは多くあります。しかし、ありがたいことに巨大な企業の中にも自社のサーバー構成やそれを支えるツールを公開している企業があります。
この記事では、彼らの叡智に触れるため、有名企業の事例を取り上げ要約をします。
各事例には元記事へのリンクを書いているので、興味があればリンク先も覗いてみてください。

※新しいものばかりではないので、古くなっていたり既に別の方法に移行している可能性があることに注意してください。


LINE: 25k/secのスパイクをさばくアーキテクチャ

元記事: 25K request/secをさばいた「LINEのお年玉」のアーキテクチャの裏側

最初に紹介するのは、LINEが2018年に実施した、「LINEのお年玉」というイベントをさばいたアーキテクチャです。
この記事では、アーキテクチャの他にイベントで発生した問題についても書かれています。

Kafkaを軸とした多段構成

f:id:mrasu:20181130233406p:plain

「LINEのお年玉」では、即時に反映する必要が有る処理を前段で受けつつ、非同期でも問題ない処理をKafka(Streams)に流す構成を取ったそうです。
「LINEのお年玉」はスパイクが見込まれるイベントであることから、キューを挟むことによって、前段の負荷を減らして遅延処理できるように注意した構成ですね。
また、キューとは別にバッチ処理も行ったようです。
仕様技術はKafka, Prometheus, Fluentdです。

WeChat: アクションに応じた負荷制御システム DAGOR

元記事: Overload Control for Scaling WeChat Microservices

次は、中国でLINEのようなサービスを展開するWeChatです。
WeChat内で実装されている負荷制御に関する論文の内容が興味深かったので紹介します。
※ 元記事を読んだのではなく、The morning paperにあったまとめを読んだだけなので、原文とは異なった解釈をしているかもしれません。

負荷が高くなった場合は、優先度の低い行動に対する応答を止める

LINEと同じく、WeChatでも正月(春節旧正月)のアクセスは平常時を大きく超えるらしく、DAGORという負荷制御システムを実装して負荷に対応しているそうです。
DAGORは事前に各サービスの優先度を設定し、負荷の高まりを検知した時に

  • 処理可能な基準を変更することで、特定の優先度以上のサービスへの処理は止める
  • 大きなボトルネックが特定の優先度上にある場合、ユーザー単位に優先度を割り当てることによって処理を止めるユーザーを選択する

という動作をします。
下の図の矢印部分に制御が入るイメージです。

f:id:mrasu:20181130233835p:plain

これによって、「支払い処理は動作するが、動画のアップロードは出来ない」という制御を自動化で出来ると共に、サービス間連携の流れを把握せずにDAGORの運用することが可能になります。
ちなみに、ユーザー単位に優先度を設定することに関して、セッション単位に優先度を割り当てても良さそうな気がします。しかし、セッションを使用すると、ユーザーが「エラーが出たら再ログインし続ければ治る」ということに気がつき、再ログインを繰り返してしまうそうです。結果UXの低下につながるので、セッション単位での優先度割当は使わないそうです。

Salesforce: マルチテナントを支えるDB運用

元動画: Salesforce Multi Tenant Architecture: How We Do the Magic We Do
別スライド: SlidShare

次は、マルチテナントの運用で有名なSalesforceです。
SaaS企業ではほぼ必須になるマルチテナントですが、Salesforceは奇抜なデータ構造を持っています。
この発表では、彼らの「データとメタデータを分けたテーブル設計」とそれに伴う処理方法や、彼らの持つスケーラビリティ性を説明しています。

DataTables vs MetadataTables vs SpecializedPivotTables

f:id:mrasu:20181130234451p:plain

通常のテーブル設計では、テーブルは「事前に決めた対象分野のデータ」を入れるためにあると考えますが、Salesforceではあらゆるデータを放り込む「Data Table」と、そのテーブルの行と列の「意味」を保持する「Metadata Table」に分かれています。
さらに、インデックスや制約を保持する「SpecializedPivotalTable」なども存在します。

つまり、DataTableの各列に意味はなく、列名もテナントのidなどを除いて、Value1,Value2,Value3...となっています。Value1が何を表すかはMetadataTableを参照することで確認できる様になっています。
この構成により、どんなデータにも対応可能になり、柔軟性を発揮しているそうです。

Dropbox: 全文検索エンジン Nautilus

元記事: Architecture of Nautilus, the new Dropbox search engine

次は、Dropboxが内部で使用している全文検索エンジンNautilus」についてです。
Dropboxともなるとデータは地理的に分散されています。加えてユーザー毎にシャーディングするわけに行かないせいで、検索が大変そうです。

Indexing vs Serving

Nautilusは「Indexing」と「Serving」の2役に分かれて動作しています

f:id:mrasu:20181130234625p:plain

Indexingは、保存しているドキュメントからメタデータを生成して検索出来るようにすることが仕事です。
メタデータは、「ドキュメントから直接取り出したもの」と、「そこから更に加工されたもの(加工するものをannotatorという)」で構成されています。
さらにメタデータ作成とは別に、転置インデックス作成のためのoffline buildが別のタイミングで実行されます。
メタデータ作成とインデックス作成が分離しているので、新規annotatorに対するカナリアリリースや既存ドキュメントへの反映が、特別な処理をすることなく実現できています。

ServingではOctopusというシステムを中心に、

  • Nautilus上での検索
  • 外部サービス(Dropbox paperなど)への検索依頼
  • 結果のランク付け
  • アクセスコントロール

が実行されます。
このように、IndexingとServingの2役に分割されていることで、両者が独立して動けるようになっています。

Netflix: コンテナマネジメントシステム Titus

元記事: Titus: Introducing Containers to the Netflix Cloud

最後はNetflixが内部で使用しているコンテナマネジメントツール「Titus」です。
NetflixAWSを使用していることから、Kubernetesとは違い、AWSの各種サービスと連携する事を前提としています。

既存システムを考慮したコンテナ移行

Netflixがコンテナへ移行する際には、既存インフラとの連携や「小さく変える」というのが重視されたようで、Titusでは以下を考慮して作られたそうです。

  • 変更無しで、既存のアプリケーションがコンテナ上で動く
  • コンテナに乗せたアプリケーションが簡単に他のアプリケーションやAWSサービスに繋げられる
  • バッチやジョブが同じリソースプール上で動く
  • 効率的で信頼性がある

Titusは、EC2インスタンス内で動いている「Titus Agent」と、インスタンスにコンテナを配置する「Titus Master」、外からリクエストを受け付ける「Titus API」で構成されています。

f:id:mrasu:20181130234707p:plain

ミドルウェアでは、ZookeeperがMasterのリーダー選出を、Cassandraが永続化を担当しています。

AWS連携

TitusはAWSのサービス(S3やSQS)を使うため、各コンテナのIAMを管理したいところですが、IAMはインスタンス単位で制御されています。
そのため、TitusAgentがプロキシとなり、各コンテナに必要な情報のみをコンテナに渡しています。
またコンテナのIPについて、各コンテナは同一VPC内の固有IPを割り当てられます。それによって、ポート管理やゲートウェイ管理、セキュリティグループ管理が簡単になっています。

他にも、ワークロードの違うアプリケーションを両立させる管理方法や、既存のデプロイツール(Spinnaker)への連携、CloudWatchに連動した独自オートスケール管理といった興味深いトピックが以下の記事で公開されています


まとめ

以上、巨大企業のサーバー構成や内部ツールに関する記事を紹介しました。
今回の記事のように、このブログではプログラムを作る時の参考になることを書き続けるつもりです。
もし興味があれば、twitterやブログのフォローしていただけると嬉しいです。

「F1 Query: Declarative Querying at Scale」 - Google内部のクエリ実行プラットフォームF1の動き

はじめに

以前Dynamoの論文を読んだので、ついでにGoogleのF1についての論文読んだ。
Dynamoは古かったが、こちらは2018年発表と新しい。
以下のリンクから手に入る。
https://ai.google/research/pubs/pub47224

F1はSpannerと一緒の文脈に居ることが多くSpannerをいじるためのものだと考えていたが、GoogleSpreadSheetなど複数ソースをまたいで動作するらしい。
論文の内容は全体を通して興味深い内容だった。
この論文では、

  • どのようにソースをまたいだ動きを実現したか
  • OLTP・OLAP・ETLという、別特性の動きをどのように一体化したか

を書いている。

以下、特に興味を引いた1章から4章の内容である。


F1の目的

F1は、社内で必要な機能である以下の3種全てを提供することを目的としている。

  1. 少ないレコードを対象としたOLTP
  2. low-latencyなOLAP
  3. データの変換やロードを行うETL

個々の機能について見れば既に実現されているものであるが、F1の新規性はDBMSやDremel(Google製のanalytical queryに特化したクエリエンジン)の機能を如何に(現代的なアーキテクチャ上で)統合したかにある。
また、初期段階ではSpannerとMesaのみをサポートしていたが、現在ではGoogleSpreadsheetやBigtableといった別のフォーマットにも対応している。

つまり、F1に対する要求は以下である

  1. Data Fragmentation
    Googleにはデータ管理のための方法が(SpannerやBigtableなど)数多く有るので、それらを横断して処理したい
  2. Datacenter Architecture
    F1は個別のマシンやクラスタではなく、データセンターに対して実行するものとして作られている。
  3. Scalability
    サイズ、速度、信頼性、コストなどの要求水準がユースケースによりバラバラであるが、各種に対応する
  4. Extensibility
    クエリとして書きづらい処理が必要になることがあるので、ユーザー定義関数のような拡張性を備える

F1の動き

具体的なF1の動きは、以下の図で表される。
「F1 Server」、「F1 Master」、「F1 Worker」が主な登場人物である。

f:id:mrasu:20181028215037j:plain

つまり、F1 Serverがクライアントからリクエストを受け付けたのち、

  • クエリが小さいなら、その場で実行
  • クエリが大きければ、workerに実行させるようスケジューリングする
  • 更に大きければ、MapReduceを使う

と、処理方法が3種類有る。
F1 Masterは、各データセンター内のF1のサーバー達を監視する。
ちなみに、F1 ServerとF1 Workerはデータを持たないので、台数を増やせばスケールする。

具体的なクエリ実行の流れは以下の様になる

  1. ClientからServerへリクエス
    F1 ClientがF1 ServerにSQLを送る。
    リクエストを受け取ったデータセンターよりも(対象データを保管している場所が近くて)ふさわしいデータセンターが有る場合は、それをクライアントに通知する。
    別のデータセンターを指定された場合は、クライアントはそのデータセンターに向けて再度SQLを送る。
  2. 実行プランの作成
    受け取ったSQLを物理的、論理的最適化を考慮した実行プランを生成する。(クエリ最適化の詳細はブログに書かないので本文を参照)
    クライアントはSQLを送るときにInteractiveかBatchのいずれかのMODEを指定し、オプティマイザはMODEによってどのように実行するか変化させる
  3. クエリ実行
    • Interactive 実行
      クライアントのリクエストに対して同期的に返答するモード
      クエリオプティマイザはヒューリスティックに、その場で実行する(centralized)かworkerを使用してクエリを分散させる(distributed)かを選択する
    • Batch 実行
      大量のデータ処理を行い長時間の実行が必要になる場合に使用するモードで、実行計画はF1 Server以外に保存される。
      また、MapReduceフレームワークを使用して非同期に分散される
  4. データアクセス
    F1 Serverはデータセンター毎に割り当てられているが、各F1 Serverは別データセンターのデータにもアクセス可能。
    前述のように、対象データはSpannerでも、CSVや圧縮データ(Capacitorとか)でも良い。
    対象データがconsistent readやrepeatable readをサポートしていれば、それをサポートする。
    データソースが多岐に渡るため、joinなどを行うために必要なメタデータをglobal catalog serviceという場所に置いている。
    また、クエリ発行時にDEFINE TABLEを通してメタデータを定義することも可能。
  5. Data Sinks への格納
    クライアントが要求した場合、実行結果をData Sinkへ格納することができる。
    Data Sinkには、データソースに応じて色々な形式でデータが保管される。
    必要であれば、出力先を変えたり、session-local な一時データとして保存することも可能
  6. クライアントへ返答

ちなみに、クエリはSQL2011標準に従い、拡張としてArrayなどをサポートしている。(つまり、joinや集計、window関数が使える)

閑話休題

長くなってきたので小休止。
ここからが、論文のテーマである「どのようにクエリを実行するか」の詳細が始まるので、一旦整理する。

F1に送られてきたSQLはF1 Server内で実行計画へと変形される。
実行計画の作成時において、複数の選択肢の中から実行方法が選択される。
実行方法が変わるとF1の動作は大きく変化し、この変化こそがOLAP,OLTP,ETLの全種サポートを可能にした根本である。

実行方法は下のように分類できる

  1. Interactive モード
    同期実行するモードで、少量のデータをさばく場合に使用される。
    クライアントがInteractiveモードを選択した場合、オプティマイザはクエリを基に2つの実行方法をのいずれかを選択する
    1. Centralized execution
      1スレッドで完結し、クライアントからのリクエストを受けたF1 Serverがその場で実行する
    2. Distributed execution
      Workerを通して、複数のサーバーにクエリを実行させる。
      F1 Serverは各Workerのコーディネーターとして機能する
  2. Batchモード
    非同期実行するモード
    大量のデータを扱う場合に使用される。
    長時間実行されることを想定したフォールトトレラントアーキテクチャを持っている。

以下は、各動作内容を詳細化しているので、この分類を頭に置いた上で、各論を見ていく。

Interactive + Centralizedの動き

1スレッドで完結するモード。
SQLを基にした実行計画の内容を、単一スレッド上で各演算が実行される
論文では、ScanとJoin、Sortの動きを紹介している。

f:id:mrasu:20181028215055j:plain

  1. Scan
    データソースに応じて動きが異なる。
    フルスキャンしか出来ないものもあれば、key-based index lookupをサポートしているものもある。
    他にも、Array型を利用する挙動やProtocolBuffersを利用した挙動もある。
  2. Join
    nested loop join, hash join, merge joinなどが使える。array joinという、array型用のjoinも有る
    また、Spannerが持つストリーム用のmerge joinも使える
  3. その他
    Projection, Aggregation, Sort, Union, Window Function, Limit, Offsetなどがある。

Interactive + Distributed の動き

Workerを使用して、並列実行するモード。
実行計画は処理の一部を表したFragmentに分けられ、FragmentはDAGになる。

f:id:mrasu:20181028215109j:plain

特徴は

  • Fragmentは各ノードに割り当てられ、マルチスレッドで動き、場合によっては複数Workerを使って一つのクエリを処理することも有る。
  • 各演算には(joinや集計のために必要な列のような)必要条件があり、必要条件に入力互換性がある場合は両演算は1つのFragmentにまとめられ、違う場合はオプティマイザが変換用の演算を間に挿入する。
  • 各Fragmentに割り当てられるノード数は、子Fragmentが必要としたノード数の大きい方の値を取る。
  • Fragment内の各ノードでは、各行の計算が終わったら、結果をどのノードに送るかを計算するpartitioningという作業が存在する。
  • partitioning中には転送データを削減する処理も入っていて、例えばCOUNTを取る場合には各ノードの中でCOUNTを取り、その結果を親Fragmentに送ることで転送量を減らす。

Batch モード

Googleでは大規模データのために、MapReduceやFlumeJavaを使ってきたが、メンテナンス性や再利用性から、宣言的なSQLを使えるようにした。
クエリの最適化や実行プランの生成時はInteractiveと同じ処理を実行している。

Batchモードには以下の特徴がある。

  • F1 Serverがクエリを管理するのではなく、中央集権で動いている。
  • 途中処理を保存することでF1 ServerやWorkerが止まった場合も継続可能
  • Fragmentの実行タイミングはバラバラである (InteractiveではRPCにより同期している)
    フォールトトレラントMapReduceを使用していて、実行結果はColossusに保存され共有される。
    パイプライン処理ではないので、MapReduce処理における依存関係がなければ複数のFragmentに対するMapReduceが同時に動くことが出来る
  • BatchモードではMapReduce間で多大なデータ移動が発生するので、Hash joinではなく、Index nested-loop join(lookup join)にしてIOを下げることがある
  • クライアントとの接続が切れても続行可能

Batchの流れは下の図のようになっている

f:id:mrasu:20181028215119j:plain

  1. F1 Serverがクライアントからリクエストを受け付ける
  2. 実行計画をSpannerで作成された、QueryRegistryに登録する。
    QueryRegistryは実行計画だけでなく、Batch関連のメタデータを保存している。
  3. 登録されたクエリはQueryDistributerが負荷やデータソースを考慮して、各データセンターに分配する。
  4. QuerySchedulerがクエリを発見したら、実行すべきタスクの依存グラフを作成する
    各データセンターでは、QuerySchedulerが定期的にクエリを監視している
  5. データセンターに余裕ができ次第、QueryExecuterにタスクを実行させる
  6. QueryExecuterがMapReduceを使用してタスクを行う

当然、これらの機能は耐障害性を持っていて、たとえデータセンターが死んでも別のデータセンターにクエリが再配布される。


終わりに

以上が、「F1 Query: Declarative Querying at Scale」の内容である。
この論文には、他にも最適化やUDFなどによるクエリ拡張、パフォーマンスの話が載っているが、長くなるのでここまでにする。

この論文は詳細に書かれていて興味深い工夫もあり面白かった。
BigQueryがGoogleSpreadSheetに対応したというのも、同じような仕組みなんだろうなと想像が膨らむ内容でもあった。

yarnを使ってimportが解決されるまでを追う

yarn add から webpackがimportを解決するまでを追う

Javascriptでは、Yarnとwebpackを使うのが主流なので、それらがどのような動きをしているかを追った。

事前準備

動きを追うために以下を用意した

  1. コード
  2. Verdaccio

コード

コードの配置は以下

.  
├── build  
│   └── bundle.js  
├── node_modules  
│   ├── my-isarray  
│   ├── webpack -> ../../../.config/yarn/link/webpack  
│   ├── webpack-cli  
├── package.json  
├── src  
│   └── app.js  
├── webpack.config.js  
└── yarn.lock  

各ファイルの中身は、

  • my-isarray
console.log("test-isarray");  

export default function(obj) {  
    console.log("my-isarray is called");  
    return Array.isArray(obj);  
}  
  • src/app.js
import a from "my-isarray";  

(function() {  
    console.log("src************");  
})()  

a();  
  • webpack.config.js
module.exports = {  
  mode: "none",  
  entry: "./src/app.js",  
  output: {  
    filename: "bundle.js",  
    path: __dirname + "/build"  
  }  
}  

Verdaccio

プライベートnpm のレポジトリ用にVerdaccioを使った。
dockerが用意されているので、configを弄った後に自作のpackageを登録すれば完了する

Yarnとwebpackのコミットハッシュ

調査に使用したコードのハッシュ値は以下である

Yarn: c58bd58e029ab5a69d75742c6ae82aa96cef0140 (v1.11.0-0)
webpack: 5ade57451073ef0993379d2cc6b80d616e86ef5d (v4.19.0)

動きを追う

大まかな流れは画像の様になる

f:id:mrasu:20180923170303j:plain

yarn add

最初に、yarn addをしてnode_modulesに展開されるまでを追う

  1. npmからメタデータを取得する
    npmのAPIを使用して、hash値やバージョンなどの最新情報を取得する。
  2. npmから~/.cache/yarn/v2に保存
    メタデータと以前にダウンロードしたものが違うものであればtarballをダウンロードして、展開する。
    この時、直接 node_modules にダウンロードするのではなく、~/.cache/yarn/v2のような共通ディレクトリにダウンロードすることで、別プロジェクトが使うときにも使いまわせるようになっている。
  3. 対象のnode_modulesディレクトリへコピー
    ~/.cache/yarn/v2に保存したパッケージ内容を対象ディレクトリにコピーする。

webpackを使って対象パッケージを使用する

次に、webpackが"ビルド"として行っている「ファイルの結合」の流れを追う

  1. Parserを通して各ファイルの依存関係を発見する
    Acornを使用してパースしている。
    Acornの結果を基に、webpack内にあるParser.jsがフックポイントを作って回る。
    このフックポイントの一つがimportを通ったときに発火するようになっているので、発火した場所を見ることで各ファイルが依存したパッケージを知ることが出来る。
  2. Resolverが名前解決する
    enhanced-resolveという、デフォルトのResolverがwebpackから切り出されている。
    これを利用することで、各ファイルが依存しているパッケージをnode_modulesから選び出している。
  3. webpackに登録されたLoader,Pluginsを実行し、各ファイル・全体を変更する
  4. 結果を基にファイルをつなぎ合わせる

以上

以上で、yarnがパッケージをダウンロードしてwebpackがファイルに結合するまでの流れが追えた。

読んでいて思ったこと

Yarn

yarnでは、jestとflowを使用していて、「やはり、Facebook製」といった感じを出している。
やることを絞っているためか、コードは結構シンプルで読みやすい。
上に書いた事以外にも、ネストや重複した依存関係の解決があるのでそこはまた読んでみたい所

webpack

webpackはプラグインの仕組みを使っていて、他の人が勝手にプラグインを書いて好きに公開できるようになっている。
この仕組みはwebpackを下支えしている良い仕組みだと思う。
ただし、コードを見ると、制御できている人が居るのか疑問なレベルの複雑さを持っている。
読み慣れていないせいかもしれないが、コールバック地獄がかなり読みづらかった。
また、hooksという各PluginやLoaderに対するフックポイントをまとめた変数があるのだが、フックポイントが多すぎてどこがいつ影響するのかわかりづらい。
あと、デフォルトのプラグインがまとめてlib直下に送られているのは流石にどうかと思う・・・