とても昔の話なのだが

http://maedama.hatenablog.com/entry/2014/05/16/144315

で記載してる問題を解決するツールを作ってたのでこちらに。

partitionとしてはidでしつつ、運用としては日付でpartition落とすようなことをするつまり、1週間以上古いpartitionを落とすというような設定なのだけど、内部的にはidでpartitionされてる。運用としても楽になる

2015-04-14

忘備録: snowflake/shakeflakeについて

Twitterのsnowflakeについて

遅まきながらしったがこれは便利そうである。あとでちゃんと読む。

Unique identifierのgenerationは、

生成コスト+冗長性 <=> Idのdata size

のトレードオフなわけで

生成コスト+冗長性に倒したのが、UUIDであり(128bit)
Data sizeに倒したのが RDBSのシーケンステーブルだったり、Auto Incrementだったりする

これはその中間を目指してる模様。おおよそUUIDのように使用できて、UUIDと違ってMySQLのbigintに収まるとすると使いどころは多そう。

ちゃんとよんでないが、Generator(machineId)だけ中央集権的に管理をし、あとは生成器でネットワークを介さずにidをgenerateできるということっぽい。

しかし、machineIdの管理をどうしてるのかは少し気になるところ。異なるホストで使ったりすると時間のずれによる影響のコントロールが難しそうだったりするし、一方で使いまわししないとmachineIdが枯渇したりしそう。

一回破棄したmachineIdは一定時間使用不可能にして別のmachineでも使えるようにするなどすれば問題はでないだろうけど、多少の工夫は必要そうではある

2015-04-09

released reprow "reverse proxy for worker"

Release reprow which serves as reverse proxy for worker.

For english document, please see below. <a href="https://github.com/maedama/reprow">maedama/reprow</a>github.com

microservice/soa化が　ますます普及する中で Job Queue による非同期実装はとても一般的になりつつも、Job Queue Worker自体には

プログラミング言語 x Backend queue ごとに実装/プロトコルフレームワークが分かれている
通常のAPI Callなどは Push駆動、WorkerはPull駆動と、異なる方式でプロセス管理しないといけない

というところは個人的にあまりうれしくないなと感じていた部分です。それを解決するためのproductです(golangをまじめに使ってみたかったということもありますが)

Applicationはタスクの実行という本質的な処理に注力すればよく
BackendのQueueとのやりとりなどはmiddle wareに任せるべきで
そして、そのmiddlewareとの通信プロトコルは一般的なプロトコルを用いるべきである

と思っております。

Web ServerなどでReverse proxy と Applicationの間の通信プロトコルが Reverse proxyから Push駆動で Application Serverに HTTP でrequestするというのが必ずしも理想的な方法かという点に関しては議論があるところだと思いますが(Pull型のシステムと異なり比較的死亡しやすいWorkerの監視をかなり厳しく行わないといけないなど問題はあります)、一般のWeb Serverなどは現在の実情としてそのような作り方をしてますし、HTTP 自体は非常に一般的なプロトコルなのでそれほど筋は悪くないと思います。

今回つくったライブラリは WorkerもWeb Serverと同様の作り方で作れるようにしたものです。 nginxの代わりに、reprowで proxy serverをたてれば、BackendのJob Queueとのやりとりはreprowが責任をもち、Application Serverはreprowからよばれる HTTPのCallにたいして正しくresponseを返せばよくなります

 JobBackend                          reprow                         Application
                   <- pulls a job
                                                  -> HTTP Proxy
                                                  <- Returns response
                   <- abort or ends Job

sqsだろうが、q4mだろうが、別のbackendだろうが　、goで作ろうが、rubyで作ろうが reprowを立ち上げて、jobを実行するHTTP Serverをbackendに立てればWorkerがつくれるということです。

一応 Retry-After Headerとかにもsqsの場合は対応していたりします。

実際使ってみて不便な点も感じるかもしれませんが個人的には現在のように言語xBackendでworkerのframeworkかいてるよりは作りやすいのではないかと考えておる次第です。

2015-03-11

Microservice と Container技術と Entropty

Microserviceは最近様々な、企業で適用されている。

Microserviceは、いわばプログラム間の連携方法に制約をかして、プログラム全体のエントロピーをさげる行為である。

このようなパターンは数多く存在していた、例えば

Linux pipe
Plack/WSGI/Rack etc (Single interface for Server implementation and application behind)

共通していえるのは、適した抽象化をしながら自由度を下げて、制御しやすいシステムを実現するという事である。自由度がさがるので、パフォーマンスや表現力をある程度犠牲になるが、一方で制御しやすさをえるわけである。

このようなパターンはシステム以外でも例はある。例えば

DNA による生物情報の保存
機会学習による特徴量削減

これらも同じような考え方に基づいている。表現力を犠牲にはなるが、結果として制御しやすい構造を得る訳である。 DNAは生物の情報としては不完全である。それをコピーしたから全く同じ人間がそだつわけではない。

ただ次元を落とす事によって、コピーのしやすさや、進化のしやすさ、保存のしやすさといった制御のしやすさの恩恵を得ているのである。

Microserviceはプログラム内の連携を限定されたendpointによるHTTP callのみに制限する等してプログラム全体のエントロピーをさげている。このようにすることで、我々はたくさんの恩恵を得ている訳である。

一方で、インフラ面からみるとエントロピーは増加してしまう。

モノシリックなApplicationのインフラのパラメーターは少なくすむ。新規の構築もないし、プロセス数や、サーバー数くらいをコントロールしていればおおまかなニーズは足りる。急激な負荷がきたらサーバーをふやすというシンプルさである程度の問題は解決できる。しかしMicroserviceになると、インフラの自由度(エントロピー)は格段にあがってしまう。

パラメーターの数は単純にServiceの数倍される。それだけのリリース行為があるし、しかも各パラメーターは相互に依存してしまうので、事態はもっと深刻になる。

例えば、リソースを使い切ろうと思ったら CPUボトルネックのapplicationとMemoryボトルネックのapplicationを同じサーバーにいれたいとか、相互に依存度の高いApplicationは同じサーバーにあった方がいいとかそういうった事情によりインフラの自由度は格段にあがるのだ。

このような状況に対応するのはコンテナ技術である。つまり、人手でインフラをサーバー単位で管理するのを辞めてしまい、Application単位(コンテナ)で管理する事とし、各コンテナの依存関係や、実際のサーバーのリソース調整はすべてオーケストレーションツールに任せる(このコンテナ同士はちかくにあるといいな。ちらちら。みたいな)。

もちろんそれをする上で Heroku - 12 Factor App - モダンなサービス運営に必要な12のインフラ的要素 - Qiita

のようなApplication側の制約は発生するがエントロピーがどんどん高くなってカオス化していくインフラを社内独自のシステムをメンテしながら管理するよりは格段に幸せだし、そのようなシンプルさが実現できれば自然とクラウドを使ったサービスのScaleoutとかも可能である。

コンテナ技術を本番で使うという行為はMicroserviceを実現する上では必須な要件となってくると思う。

それをしない限りインフラのエントロピーがどんどん増加し、管理コストが増加し人々は疲弊してしまう。というわけで今年はコンテナとそのオーケストレーション周りの動向をおいつつプロダクトを作りたいと思う昨今である。

なむ

2015-03-11

jbuilder_deferred_render作ってみました

Rails等でAPIを書いてると、いくつか問題にぶちあたります。

n+1問題がその一つなんですけど、Railsではこれをcontroller側で解決しろと話をしてます。

元々はWebページを作るフレームワークなので、そもそもAPIを作るのはどうなのみたいな話はありますが、まぁ色々総合的に別にRailsでもいいんじゃないかなと思ってるので、それはいいんですがn+1問題は結構めんどいです。

Webページの場合はViewの階層構造とかって比較的シンプルなので、includeを都度かいていくのは問題ないと思いますが、RESTFul APIをかいてると、client friendlyでつくる複雑なjsonつくっちゃいがちです。

i.e

 {
    "id": 1,
    "kind": "activity",
    "actor": {
      "kind": "user",
      "id": 1, 
      "displayName": "ほげほげ"
    },
    "verb": "like",
    "target": {
      "id": 3,
      "kind": "Page",
      "owner": {
        "id": 4,
        "kind": "user",
        "displayName": "げほげほ"
      }
    }
 }

階層構造が深くなると、includeしていく方法は結構つらくなりがちです。そもそも、

リソースをどのようにRenderingするかはViewが知っている(Pageのownerをrenderingするかしないかとか)
Viewが、モデルの様々な属性にアクセスするのは論理的には間違ってない
だけど、モデルの属性のbackendの特性として、一つ一つアクセスするのは現実的に遅い。
Viewは深さ優先renderingをするので、モデルの属性に一つ一つアクセスする => パフォーマンス劣化

みたいな流れで、そもそも Controllerがviewがどういうrenderingをするかに応じて includeするのはちょっとつらいだろうなと、そこでgemかきました。まだ完全にアルファ qualityですがすでに本番で限定的に稼働しています。

maedama/jbuilder_deferred_render · GitHub

こんな感じで、jbuilderのviewをかくと

@users = User.take(10)
@jbuilder = Jbuilder.new do |json|
json.array! @users do |user|
  json.name user.name
  json.when(
    user.deferred_load.books
  ).then do |books|
    json.books books, :title
  end
end

こんな感じでqueryされます。

SELECT * FROM users ORDER BY id DESC LIMIT 10;
SELECT * FROM books where user_id in (?, ?, ?, ?, ?, ?, ?, ?, ?)

user.deferred_load.books

の部分は、任意の q-deferの promiseを入れられるんですが、必要なタイミングでまとめてとるための実装は deferred_loaderというgemで実装したので、特に何もせずとも使用できます。

https://github.com/maedama/deferred_loader jclem/q-defer · GitHub

深さ優先探索を前提としたjbuilderの上に無理矢理のっけてるのでちょっとつらいんですけど利用側からするともうincludeとかかかなくていいので個人的な需要は満たしています。階層構造の深いJSONを返すAPIの実装をしてる人はご検討いただければ

2015-02-02

released gem token_pagination. No more LIMIT 100000000 , 100 queries

token_pagination というgemをリリースしました。rubyは経験が浅くはじめてのgemです。

maedama/token_pagination · GitHub

Railsには、offset/limit のqueryを前提としたgemはすばらしいものがありますが、offset/limit は RDBSのB-Tree Indexだとパフォーマンスに難がありますし、Twitterみたいな更新性が非常に高いリソースがあると、 2ページ目にさきほどまで1ページ目に含まれていたものが含まれてしまうといったUI/UX上の問題もあります。

最近Railsでapiをかく機会があったので、こういった問題を脱するgemをかきました。詳細はrepositoryのREADMEにあります。

直した方がいい点などありましたらぜひ教えてください。

かしこ

2014-12-25

When to use distributed database system?

背景

DDBSについてあまりきちんと知らなかったので、各DDBSがどのような経緯でうまれているのか、その前提条件をしらべるために以下の記事を読んだのでそれについて。

http://cs-www.cs.yale.edu/homes/dna/papers/abadi-pacelc.pdf http://www.cs.berkeley.edu/~rxin/db-papers/CAP.pdf

下記は文献から得た知識を自分の意見も交えてまとめたものです。以下メモみたいなものなので、間違いもあるかもしれませんし、きちんとcitationできてないですがご了承ください。

CAP定理

RDBSやDDBSの文脈でよく登場するのがCAP定理です。まず、CAP 定理自体は Node partition が発生したタイミングで ACID を実装するデータベースがとりうる選択を示しています。以下の三つ

(Perfect) Consistency
(Perfect) Availability
(Perfect) Partition tolerance

CAP定理について、よく勘違いされがちがな点がここにあります。一つ目があくまで Node partition が発生した際の挙動に関する言及であるという事(そうでない場合はConsistency + Availabityを両立することは可能)。二点目が全ての要素についている Perfect です。

CAP定理自体は数学的にも証明されてますが、データを分散してもってる Nodeが完全に分断された状態で、それぞれにConflictするデータ更新Requestを送った際の挙動をどう扱いうるのかというのが本質的な問題状況です。

それぞれの更新処理がConflictしており、かつお互いに通信ができない状態で Partition tolerance (システムとして稼働することろ) を実現すると、

ACIDを満たす Consisitency を犠牲にして、双方の要求をうけつけて、Partition 復活時に何らかの復旧処理をする(Last writeが勝つとか)
Availability を犠牲にして、一方ないしは双方の要求を棄却する

のいずれかの二択しかとれないという事を示しています。

例えば私が所属している会社では MySQL + MHA でハッピーライフをおくってます(AWSのRDS+自動Fail overもだいたい同じような構成だと思います)が MHA時には瞬間的に更新処理ができなくなるので、AvailabilityはCAP的な意味では犠牲になっています。でも実運用としてそれでほとんど困ってません。

それは以下のような理由からです。

Node partition がMySQLが利用される環境だとかなりのレアケースであることが多い
Availabilityは完璧ではないがかなり高いので、実運用として困るレベルにない

ちなみに、Partitionが頻繁に発生するような環境で動くデータベースももちろん存在します。google spread sheetとかgitとかその良い例です。gitは Availabilityを重視していて、offlineだろうが、localのデータベースにいくらでもcommitできます。が復旧して、masterにmergeしようとすると場合によってはconflictしたりして、merge不可能な状況が発生します。

Why not RDBS?

僕RDBS大好きです。でも、RDBSに適さない要件がいくつか発生したからDDBSが生まれたはずでそれは何なのか？

多分、多くはCAPではないでしょう。CAP的な意味では実運用上はほとんど困らない事が多いと思います(もちろん、要件にもよりますが)。ではなにか？

もともと、RBDSの多くは ConsistencyとLatencyを重視したシステムでした。それにMHAのような技法が加わり、ほとんどのユーザーケースにおいては十二分なシステム要件だったと思います。特に ACIDを満たす Consistency は非常に魅力的でそれに恩恵をえているシステムはとても多いです。

でも、ある日 RBDS では満たせないけど、満たしたくてたまらない要求が生まれます。

Scalability
Cross region write latency

まず、Scalbilityについてはいわずもがな多くのRDBSは中央集権的にデータを管理する設計で動いてました。これは ACIDで定義されるConsistency を担保する要求を満たす上での自然な設計です。

同等のレベルの事をやろうとすると何らかの投票システムのようなものをつかって全員で Transacitonについて合意をとるようなプロセスが要求されるはずです。

この方法は、Write(+ それに付随するデータ量)に関して Scalabilityを担保するのが困難で、Application側でのShardingをしないとScaleしない仕組みになり、LINEやFacebookのような大規模なサービスの登場と主に、既存のRDBSをこえるScalabilityが要求されるケースが多くなりました。

次に重要なのが Cross region Latencyです。MySQLのように中央集権的なRDBSはデータの更新処理や、最新のデータを読み取る処理がある特定のNodeに要求されなければならないという制約が有り、これがGlobalでサービスを展開する上での一つの大きな制約となったでしょう。Readはreplicationの遅延をある程度許容しつつ、Web server等の近くにデータベースをおけばいいですが、更新のRequestが特定の拠点のマスターのサーバーにむかなければいけないというのは相当つらいです。

地球の反対側にサーバーがあるとすると光の早さでデータが1往復したとしても 130msecくらいかかります。これが理論上の最速の値で、Protocolをどれだけ簡素にしようが、回線をどれだけ高速にしようがこれを上回る実測値はだせません。実際はこれより数段遅くなるはずなので、TCPでconnectionはるためにround tripを繰り返すとかなるとちょっと恐ろしい思いです。

このような事情から、特定のマスターサーバーでデータを管理するのではなく分散システムとしてデータを管理する需要が高まったと想像されます。

Latency Consistency Trade off

さて、上記の点で面白い点が、DDBSにすると、RDBSが抱えていたScalabilityの問題は解決されますが、結局 ACID の consistencyを満たそうとすると、本質的に Cross region write latencyの問題は DDBSにしても問題が解決されません。

距離が離れてるNodeをもつDDBSで Latency (write) を低くするという事はmaster のReplicaを多くのNodeでもつという事と本質的には同じです。

Round tripの時間がボトルネックになる以上、近くにデータがないと Low latency でデータ更新は実現できません。

( 近くにデータをおく手法としてapplication側の性質やhuerisistics を利用する事で高速にする事はできるでしょう。例えば、Masterデータのshardingのlogicに頻繁に更新される場所を考慮すれば良いわけですから。それは Application側で担保してもいいし、場合によってはデータベース側でそういった仕様をもつというのも面白いかもしれません。更新 Requestのipの分布等を考慮して、masterデータの置き場所を動的にかえていくとか )

しかし、コピー = consistentencyの低下です。

ACIDが定義するようなレベルでのConsistencyを得るためには、中央集権的なシステムまたは何らかの投票システムを利用して、データの更新処理に合意をとる必要が有ります。一方で World wideなサービスでは合意する上での通信がボトルネックになるわけですから、ここに DDBSのジレンマがあります。

実際、DDBSの多くは ACID を緩和したconsistencyのレベルの BASE を実装しています。BASEはtransaction完了時に、データが更新されて未来永劫変わらないという事を担保しなくてよいので、近くのNodeに対して更新Requestを送った場合、そのNodeが投票をせずして transactionの結果について自ら判断できます。

もちろん BASE になることにより、システムの実装は難しくなる部分はあります。例えば

Atomicな処理を DDBSがサポートしてくれない
Commit成功しても、場合によっては rollback相当の事が行われる

もちろんこのへんは使ってるデータベースに依存しますし、transactionを発行するタイミングでユーザー側がconsistencyのレベルをcontrollする事もできるでしょう。でも、一般的にはこのへんが RDBS にたいするデメリットになるはずです。

なので、RDBSを離れるべきかどうかは

Scalabilityに問題が有る？
World wideに展開するサービスで low write latencyを実現したい

あたりがキーになると想像します。前者は Aurora DBがMySQLの５倍速いとうたってますし、SNSでSOA化されたサービスであれば相当大規模にならないと問題にはならないかもしれません。一方で、後者はどちらかというと ACID にまつわる問題なので解決が大変そうです。

maedamaのブログ

アプリケーションエンジニアです。最近は主に設計を担当しています。

mysql 自動partition更新ツールを作ってた。続.) Why I want to stop using range partition with timestamp column