プレイドの @nashibao です。

弊社は大量のログデータを収集し、人軸で解析するサービスを展開しています。収集したデータの利用方法には様々な目的と様々な手法がありますが、そのうちの大きな一つに、中・大規模のデータに対して、アドホックなクエリをインタラクティブにかけアグリゲーション結果を得る というものがあります。

このようなアグリゲーションの問題において、クエリの自由度 x データ規模 x レイテンシーを共存するのはなかなか難しい問題になります。(1)

元ネタは結構有名かと思いますが、Square が開発している、CrossfilterGitHub - crossfilter/crossfilter: Fast n-dimensional filtering and grouping of records.というものです。Crossfilterを内部に使ったビジュアライゼーションとして dc.js - Dimensional Charting Javascript Library というものもありますが、こちらの方が有名かもしれません。

というわけで、このエントリは、bit matrixやbit twiddlingといったテクニックで効率的なフィルタリングとアグリゲーションを実現することで、数百万レコード程度であれば、数十msで結果を出すといった優れものについてのお話になります。(2)

（1 余談ですが、こんなエンジニアリングの課題と市場の要望の乖離があるフィールドはプロダクトアウトなビジネスを始める良い条件が揃っていると考えられるかもしれません。たぶん。）

（2 本来は数百万レコード程度であれば大規模とは言えないと思いますが、中・大規模と書いたのは、出来るだけ盛って描きたい、という気持ちがあったというのは前提ですが 前処理として1段aggregationしてからインタラクティブな環境に持ってくれば、それで十分という場合が意外と多いと思うからです）

ポイント

jsでブラウザで動かしてここまでパフォーマンスが出るのは目からウロコ感があります。その肝は色々あると思いますが、僕個人としては次の3点が面白いところじゃないかと考えています。

1. 問題を制限する（filtering x reduceによるaggregationに制限）
2. BitMatrixとBit演算による高速なフィルタリング
3. Sorted Arrayを使った効率的な差分更新

以下、この3点についてまとめてみます。

問題を制限する

上に書いたように、クエリの自由度 x データ規模 x レイテンシー全てを同時に満たすのは難しい問題です。そのため、ここではクエリに対してある程度の制限をかけることで、データの圧縮と高速な取出しを可能にしています。

1. クエリ = フィルタリング x アグリゲーション のみ
2. アグリゲーションはreduce（データの追加/削除による値の変化が、追加/削除されるデータにのみ左右される）のみ

SQLのように何でもかんでもという感じで複雑な処理は書くことはできませんが、1. WHEREとGROUP BY、2. 集計関数としてもMax|Min|Sum|Count|Averageなどreduce処理として書けるものだけ、これを一段階だけ、に制限しているイメージです。ある程度 前処理することを前提とすれば、上記のような制限をかけても、大体のことはできそうなイメージはあるんじゃないでしょうか。

このような制限をかけることで、やりたいことは制限しすぎずに → 効率的なデータ表現を使って → 高速なアグリゲーションを、というシナリオです。

全体構造/概念

crossfilterの簡単なコードを下記に表します。コードを読めばなんとなくやろうとしていることはわかるかな、と思いますが、詳しくは API Reference · square/crossfilter Wiki · GitHub を参照してください。

1. dimension作成（フィルタリング/Aggregateする軸を決める）
2. group作成（グルーピング単位を決める）
3. reducer作成（aggregateの関数を設定）
4. 最後にfiltering x aggregation

これらの概念は内部的には

1. filters:データ数 x フィルタ数のBitMatrix
2. dimension: sort済みArray x lower/upper bounds

で表現されています。

BitMatrixによるフィルタリング

さて一つ目のテクニックはBitMatrixによるフィルタリング行列の実装です。 N（データ数）x D（Dimension数）のBitMatrixは、JavascriptだとUint8ArrayなどのTypedArrayで表現されます。例えば、30行のデータ x 8Dimension の場合、new Uint8Array(30)（30 x 8 = 240 bit) が実態になり、一つのデータがUint一つで表されます。もしDimension数が8に満たない場合は、使わない部分はできますがUint8Arrayで、16までであればUint16Arrayで、32までならUint32Arrayで表現する、といった具合です。（それ以上であればTypedArrayを並べて表現します、が、パフォーマンスは落ちるはずです。）

また、一つのbitは

• 0: フィルタリングされてない状態
• 1: フィルタリングされている状態

を表します。下図の例で言えば、データ(1)がフィルタ(2)で弾かれた場合、XOR演算で0^32=32になり、さらにフィルタ(5)で弾かれると32^4=36になります。そして、0と比較すればデータ(1)が弾かれているかどうかチェックすることができます。

このようにO(N)なメモリスペースを比較的高速な演算のみで利用することでfilteringを実現しています。

Sorted Arrayを使った差分更新

二つ目の面白ポイントはaggregationの差分更新の部分です。

上のコードに書いたように、reducerは常にreduceAdd, reduceRemoveの両方を定義する必要があり差分更新を効率的に対応します。それに加えて、dimensionは、値をソートした配列 x 元データのindex配列 x 現在のlower/upper bound を持ち、BitMatrixも差分更新することができます（旧lower/upper boundと新lower/upper boundの差分indexだけXORで更新する）。

ちょっと端折って書いていますが、下記に例を書きました。sortされた配列からbinary searchでboundsを更新し、次に上記で説明したBitMatrixを更新し、更新のあったデータ行のみreducerを差分更新する、といった具合です。

ちなみに、上記のトリックはequalやrangeでのフィルタリングの話ですが、crossfilterは関数を定義したフィルタリングもかけることができます。

その場合は上記のトリックは効かないため、若干パフォーマンスが落ちると考えられます。そのため、できればdimensionの時点で前処理をしておいて、filterはequalやrangeでかける方がパフォーマンスが良いと考えられます。

感想

さて、とりあえず3つほどCrossfilterのキモっぽいポイントを紹介しましたが、実際のパフォーマンスのインパクトの割にはなんだか地味だな、、と書いていて思ったのと、自分には絵を書いているうちに力尽きる傾向があることに気がつきました。Crossfilter自体には他にもbit演算を駆使した高速化（ Bit Twiddling Hacks）が散らばっていて ぶっちゃけかなり読みづらい 結構面白いので興味があったらコードリーディングしてみると良いかもしれません。

また、filter|reducer共に並列化可能な形式であったり、tree上のcacheを使えばaggregationをさらに高速化できそうな所、サーバーとしての利用など、随所にupdateできそうな部分があります。ここら辺も詳しい人|知らないけど議論してみたい人など募集しています。是非とも気軽に五反田まで遊びに来てください。やけに安いけれど美味しくない焼肉屋とか奢ります！

ウェブ接客プラットフォーム「KARTE」を運営するプレイドでは、 KARTEを支える技術に興味を持つエンジニア（インターンも！）を募集しています。 詳しくはプレイドの採用ページか、Wantedlyをご覧ください。