山梨県河口湖に開発合宿へ行ってきました！

<html><head></head><body>プレイドの @nashibao です。
弊社は大量のログデータを収集し、人軸で解析するサービスを展開しています。収集したデータの利用方法には様々な目的と様々な手法がありますが、そのうちの大きな一つに、中・大規模のデータに対して、アドホックなクエリをインタラクティブにかけアグリゲーション結果を得る というものがあります。
このようなアグリゲーションの問題において、<code>クエリの自由度</code> x <code>データ規模</code> x <code>レイテンシー</code>を共存するのはなかなか難しい問題になります。(1)
元ネタは結構有名かと思いますが、<code>Square</code> が開発している、<code>Crossfilter</code><a href="https://github.com/crossfilter/crossfilter" target="_blank" rel="noreferrer">GitHub - crossfilter/crossfilter: Fast n-dimensional filtering and grouping of records.</a>というものです。<code>Crossfilter</code>を内部に使ったビジュアライゼーションとして <a href="https://dc-js.github.io/dc.js/" target="_blank" rel="noreferrer">dc.js - Dimensional Charting Javascript Library</a> というものもありますが、こちらの方が有名かもしれません。
というわけで、このエントリは、bit matrixやbit twiddlingといったテクニックで効率的なフィルタリングとアグリゲーションを実現することで、数百万レコード程度であれば、数十msで結果を出すといった優れものについてのお話になります。(2)
（1 余談ですが、こんなエンジニアリングの課題と市場の要望の乖離があるフィールドはプロダクトアウトなビジネスを始める良い条件が揃っていると考えられるかもしれません。たぶん。）
（2 本来は数百万レコード程度であれば大規模とは言えないと思いますが、中・大規模と書いたのは、出来るだけ盛って描きたい、という気持ちがあったというのは前提ですが 前処理として1段aggregationしてからインタラクティブな環境に持ってくれば、それで十分という場合が意外と多いと思うからです）
<h1 id="ポイント">ポイント</h1>
jsでブラウザで動かしてここまでパフォーマンスが出るのは目からウロコ感があります。その肝は色々あると思いますが、僕個人としては次の3点が面白いところじゃないかと考えています。
<ol>
<li>問題を制限する（<code>filtering</code> x <code>reduceによるaggregation</code>に制限）</li>
<li>BitMatrixとBit演算による高速なフィルタリング</li>
<li>Sorted Arrayを使った効率的な差分更新</li>
</ol>
以下、この3点についてまとめてみます。
<h1 id="問題を制限する">問題を制限する</h1>
上に書いたように、<code>クエリの自由度</code> x <code>データ規模</code> x <code>レイテンシー</code>全てを同時に満たすのは難しい問題です。そのため、ここではクエリに対してある程度の制限をかけることで、データの圧縮と高速な取出しを可能にしています。
<ol>
<li>クエリ = フィルタリング x アグリゲーション のみ</li>
<li>アグリゲーションは<code>reduce</code>（データの追加/削除による値の変化が、追加/削除されるデータにのみ左右される）のみ</li>
</ol>
<code>SQL</code>のように何でもかんでもという感じで複雑な処理は書くことはできませんが、1. <code>WHERE</code>と<code>GROUP BY</code>、2. 集計関数としても<code>Max|Min|Sum|Count|Average</code>など<code>reduce</code>処理として書けるものだけ、これを一段階だけ、に制限しているイメージです。ある程度 <code>前処理すること</code>を前提とすれば、上記のような制限をかけても、大体のことはできそうなイメージはあるんじゃないでしょうか。
このような制限をかけることで、やりたいことは制限しすぎずに → 効率的なデータ表現を使って → 高速なアグリゲーションを、というシナリオです。
<h1 id="全体構造/概念">全体構造/概念</h1>
crossfilterの簡単なコードを下記に表します。コードを読めばなんとなくやろうとしていることはわかるかな、と思いますが、詳しくは <a href="https://github.com/square/crossfilter/wiki/API-Reference" target="_blank" rel="noreferrer">API Reference · square/crossfilter Wiki · GitHub</a> を参照してください。
<ol>
<li>dimension作成（フィルタリング/Aggregateする軸を決める）</li>
<li>group作成（グルーピング単位を決める）</li>
<li>reducer作成（aggregateの関数を設定）</li>
<li>最後にfiltering x aggregation</li>
</ol>
<pre><code class="hljs">data = [{fld1: 'type1', fld2: 10},...]
cf = crossfilter(data)

# create dimension
dim1 = cf.dimension (d) -&gt; return d.fld1
dim2 = cf.dimension (d) -&gt; return d.fld2

# create group
group = dim2.group (fld2) -&gt; return fld2 % 5

# creaate reducer
sumAdd = (p, v) -&gt; return p + v
sumReduce = (p, v) -&gt; return p - v
reducer = group.reduce sumAdd, sumRemove, 0

# filtering
dim1.filter('type1')

# get result
console.log reducer.top(3)
</code></pre>
これらの概念は内部的には
<ol>
<li>filters:データ数 x フィルタ数のBitMatrix</li>
<li>dimension: sort済みArray x lower/upper bounds</li>
</ol>
で表現されています。
<h1 id="BitMatrixによるフィルタリング">BitMatrixによるフィルタリング</h1>
さて一つ目のテクニックはBitMatrixによるフィルタリング行列の実装です。 
<code>N</code>（データ数）x <code>D</code>（Dimension数）のBitMatrixは、Javascriptだと<code>Uint8Array</code>などの<code>TypedArray</code>で表現されます。例えば、<code>30</code>行のデータ x <code>8</code>Dimension の場合、<code>new Uint8Array(30)</code>（30 x 8 = 240 bit) が実態になり、一つのデータが<code>Uint</code>一つで表されます。もしDimension数が8に満たない場合は、使わない部分はできますが<code>Uint8Array</code>で、16までであれば<code>Uint16Array</code>で、32までなら<code>Uint32Array</code>で表現する、といった具合です。（それ以上であれば<code>TypedArray</code>を並べて表現します、が、パフォーマンスは落ちるはずです。）
また、一つのbitは
<ul>
<li><code>0</code>: フィルタリング<code>されてない</code>状態</li>
<li><code>1</code>: フィルタリング<code>されている</code>状態</li>
</ul>
を表します。下図の例で言えば、データ(1)がフィルタ(2)で弾かれた場合、XOR演算で<code>0^32=32</code>になり、さらにフィルタ(5)で弾かれると<code>32^4=36</code>になります。そして、<code>0</code>と比較すればデータ(1)が弾かれているかどうかチェックすることができます。
<img src="https://ik.imagekit.io/newt/tr:w-1000,h-1000,c-at_max/61b151f921640c0018173598/b86087dc-7aad-4b91-988b-af38c925e7e8/58e9dcea6ec63b0bbac5853c.png" alt="58e9dcea6ec63b0bbac5853c.png">
このように<code>O(N)</code>なメモリスペースを比較的高速な演算のみで利用することでfilteringを実現しています。
<h1 id="Sorted Arrayを使った差分更新">Sorted Arrayを使った差分更新</h1>
二つ目の面白ポイントはaggregationの差分更新の部分です。
上のコードに書いたように、reducerは常に<code>reduceAdd</code>, <code>reduceRemove</code>の両方を定義する必要があり差分更新を効率的に対応します。それに加えて、dimensionは、値をソートした配列 x 元データのindex配列 x 現在のlower/upper bound を持ち、BitMatrixも差分更新することができます（旧lower/upper boundと新lower/upper boundの差分indexだけXORで更新する）。
ちょっと端折って書いていますが、下記に例を書きました。sortされた配列からbinary searchでboundsを更新し、次に上記で説明したBitMatrixを更新し、更新のあったデータ行のみreducerを差分更新する、といった具合です。
<img src="https://ik.imagekit.io/newt/tr:w-1000,h-1000,c-at_max/61b151f921640c0018173598/5e3a0d79-b8ff-40b1-828c-9325f21b2bff/58e9dcee6ec63b0bbac5853d.png" alt="58e9dcee6ec63b0bbac5853d.png">
ちなみに、上記のトリックはequalやrangeでのフィルタリングの話ですが、<code>crossfilter</code>は<a href="https://github.com/square/crossfilter/wiki/API-Reference#dimension_filterFunction" target="_blank" rel="noreferrer">関数を定義したフィルタリング</a>もかけることができます。
<pre><code class="hljs">dim.filter([100, 200]) # range
dim.filter(120) # equal
dim.filter((d) -&gt; return d % 2) # function
</code></pre>
その場合は上記のトリックは効かないため、若干パフォーマンスが落ちると考えられます。そのため、できれば<code>dimension</code>の時点で前処理をしておいて、<code>filter</code>はequalやrangeでかける方がパフォーマンスが良いと考えられます。
<h1 id="感想">感想</h1>
さて、とりあえず3つほど<code>Crossfilter</code>のキモっぽいポイントを紹介しましたが、実際のパフォーマンスのインパクトの割にはなんだか地味だな、、と書いていて思ったのと、自分には絵を書いているうちに力尽きる傾向があることに気がつきました。<code>Crossfilter</code>自体には他にもbit演算を駆使した高速化（ <a href="https://graphics.stanford.edu/~seander/bithacks.html" target="_blank" rel="noreferrer">Bit Twiddling Hacks</a>）が散らばっていて <s>ぶっちゃけかなり読みづらい</s> 結構面白いので興味があったらコードリーディングしてみると良いかもしれません。
また、filter|reducer共に並列化可能な形式であったり、tree上のcacheを使えばaggregationをさらに高速化できそうな所、サーバーとしての利用など、随所にupdateできそうな部分があります。ここら辺も詳しい人|知らないけど議論してみたい人など募集しています。是非とも気軽に五反田まで遊びに来てください。やけに安いけれど美味しくない焼肉屋とか奢ります！
ウェブ接客プラットフォーム「KARTE」を運営するプレイドでは、 KARTEを支える技術に興味を持つエンジニア（インターンも！）を募集しています。 
詳しくは<a href="https://plaid.co.jp/recruit.html" target="_blank" rel="noreferrer">プレイドの採用ページ</a>か、<a href="https://www.wantedly.com/companies/plaid/projects" target="_blank" rel="noreferrer">Wantedly</a>をご覧ください。
</body></html>

このエントリは、bit matrixやbit twiddlingといったテクニックで効率的なフィルタリングとアグリゲーションを実現することで、数百万レコード程度であ

Bit Matrixを使って超高速にアグリゲーションする