share facebook facebook facebook twitter twitter menu hatena pocket slack

2020.05.25 MON

BigQuery上で64ビット整数をビットスワップする話

丹野 航

WRITTEN BY 丹野 航

BigQuery上のユーザ定義関数で64ビット整数のビットスワップをした話です

タイトルからしてマニアックですが…。

なぜそんな事を…

BigQueryにビットスワップ(ビットの値が逆順)な64ビット整数が入ってしまって、
SQLとユーザ定義関数でもとに戻す処理を実装しました。

同じ状況の人必見です!(そんな人いるんだろうか?)

そもそもBigQueryとは

このQiitaを読んでもらうと凄さがわかると思いますが、
120億行の正規表現マッチ付き集計が5秒でできたり。
ペタバイトクラスのデータを投入してもビクともしなかったりする、
規格外のデータウエアハウスです。
まさに、今のビッグデータ分析のトレンドのサービスとも言えるかなと思います。
そして、自分の主な仕事はこのBigQueryをいかにうまく使うかだったりします。

「BigQueryは120億行を5秒でフルスキャン可能」は本当か?先日、kaheiさんがGoogle BigQuery(Googleクラウドの大規模クエリサービス)について、こんなエントリを書いていた。とにかくパフォーマン...

ビットスワップ

ビットスワップとはビットの順序を逆順にすることです
例えば2進数表現で
1100 0101
があった場合にビットスワップすると
1010 0011
になります。

並び順を逆にするためビット反転結果の
0011 1010
とは違います。

方針

方針としては4つ考えました。

  1. Cloud Dataflowを用いてJavaで反転する
  2. 対象テーブルをGCSへ出力しローカル上で反転し再度テーブルを作成する
  3. SQLと標準関数だけでなんとかする
  4. BigQueryのユーザ定義関数を用いてビット反転処理を書く

まず1についてですが、
この64ビット整数の反転がそもそもJavaのLongの関数を用いて行われていたため、
これを用いてもとに戻すのが一番バグもなく安定です。
ただ、その変換のためだけに非同期処理になるCloud Dataflowを用意するのは若干まどろっこしいかなと思いました。

2についてはJavaが動けばできるのでワンショットならいいですが定期的に必要になりそうなので流石に手動は辛そうです。
あと、レコード数が4000万行ほどあるのでなるべく外に出したくないです。

3については残念ながらBigQueryではビット演算系の関数が弱いためおそらく頑張ればできそうですが、
SQLを引き継いだときに保守性が悪そうです。

そこで、4番のユーザ定義関数をJavaScriptで書いてビットスワップする処理を実装しました。
BigQueryのユーザ定義関数は標準SQLの場合JavaScriptで書けます。
余談ですが、もしBigQuery内のJSONの値を加工する時に困っていたらユーザ定義関数で扱うのがおすすめです。

JavaScriptの64ビット整数

JavaScriptにおける数値型といえばNumberが思い浮かぶと思いますが、実は2018年ぐらいから一部ブラウザにてBigIntという数値型が実装されています。

BigInt は組み込みオブジェクトで、 Number プリミティブで表現できる最大の数、 253 - 1 よりも大きな数値を信頼できるものとして表現する方法を提供します。 BigInt は任意に巨大な整数に使用することができます。

使い方は数値の最後にnをつけるか、BigIntのコンストラクタに64ビット数値を表す文字列などを入れることで宣言できます。

// Number型で定義すると丸め誤差が発生する
12345678901234567890
// = 12345678901234567000

// BigInt型の整数として宣言
12345678901234567890n
// = 12345678901234567890n

BigInt("12345678901234567890")
// = 12345678901234567890n

// 引数をNumber型で渡してしまうと丸め誤差が発生してしまうので注意
BigInt(12345678901234567890)
// = 12345678901234567168n

油断してNumberにすると丸め誤差が発生してしまうので要注意です。
そして、実はまだBigInt型はドラフト段階のため一部の演算が実装されていません。

BigQueryのユーザ定義関数

ユーザ定義関数(UDF)は以下のように作成しました。

CREATE TEMPORARY FUNCTION
reverce_binaly(argStr STRING)
RETURNS STRING
LANGUAGE js AS """
    let argBin;
    let arg = BigInt(argStr);

    if(arg > 0n){
        argBin = arg.toString(2);
    }else{
        // 符号部を0に変更
        const argBinAbs = arg.toString(2).replace('-','0');

        // Bit反転処理 (64ビット整数に対して未実装のため文字列処理)
        const notArgBin = argBinAbs.replace(/0/g,'o').replace(/1/g,'0').replace(/o/g,'1');

        // 2の補数を求めるため加算
        const arg2c = BigInt(`0b${notArgBin}`) + 1n;

        argBin = arg2c.toString(2);
    }

    // 64ビットに桁揃え
    const padded = `0000000000000000000000000000000000000000000000000000000000000000${argBin}`.slice(-64);
    // ビットリバース
    const reversed = padded.split('').reverse().join('');
    // ビットとして解釈されるようにフォーマット
    const reversedBin = `0b${reversed}`;
    const result =  BigInt(reversedBin);

    // 数値のまま値を返すとBigInt表現のnがついてしまうので文字列化
    return result.toString();
""";

64ビット整数を文字列にキャストして渡し
文字列のまま順序を反転して64ビット整数として解釈する方針にしました。
ポイントは、以下の4つ。

  • 文字列として処理
  • 負の場合2の補数を算出
  • 返り値を文字列にする
  • 文字列のまま処理する

文字列として処理

まず、BigQueryの64ビット整数のINT64は
UDFにてサポートされていないため
JavaScriptに値を渡す場合は文字列か浮動小数点として扱うことになります
ですので、誤差の発生しない文字列型として処理する必要があります。
また、必要に応じて数値化する場合には必ずBigInt型として扱わなければ
浮動小数点のNumber型とされてしまうため、注意が必要です。

標準 SQL ユーザー定義関数 | BigQuery | Google Cloud

負の場合2の補数を算出

引数に負の値が来た場合は
2進数化したときに符号部がビット演算の邪魔になってしまうので、
除去して2の補数表現にしてから処理します。

返り値を文字列にする

そして、返り値としてBigIntを指定したいところですが、
JavaScriptのBigIntを戻した場合末尾にBigInt表現を表すnがついてしまうので
UDF内で文字列にキャストしています。

文字列のまま処理する

ビット演算を使ってうまく反転させたほうが計算コストが低そうな気はしました。
ただ、JavaScriptの64ビット整数のビット演算の符号付きビット反転などがまだ未実装のため

  • 32ビットごとに分割して処理を実装しないといけない
  • ビット演算でもそれほど簡潔にならない
  • 引数も返り値も文字列で扱う

などから、今回は文字列のままで処理しました。

paddingについて

paddingの部分はループ以下のように使ったほうが簡潔になりますが、
レスポンスが30秒ぐらい遅くなったのでスロット(BigQueryの処理単位)の負荷はあがるようですね。

//  配列に変換
let argBinArray = argBin.split('');

// 64ビットに桁揃え
while(argBinArray.length < 64){
    argBinArray = ['0'].concat(argBinArray);
}

// ビットリバース
const reversed = argBinArray.reverse().join('');

SQL側の処理

上記のUDFを宣言したSQLと共に次のように

CREATE TEMPORARY FUNCTION
reverce_binaly(argStr STRING)
RETURNS STRING
LANGUAGE js AS """
    let argBin;
    let arg = BigInt(argStr);

    // 省略
    
    return result.toString();
""";

select
  value,
  reverce_binaly(CAST(value AS STRING)) as reverced_value
from
  table

というように、SQLの関数と同様に呼び出すことが可能になります。

BigQueryのUDFのメリット

BigQueryのUDFを定義すると何が良いかというと
BigQueryの基盤を使ってすべてのレコードに対して処理を実行できるということです。
今回行った処理は約2,000万レコードあるテーブルに対して行いましたが、
結果は43.5秒後に返ってきました。
1秒あたり50万行以上の処理ができることになります。
このように変換処理などを大量のレコードに対して実行できる基盤としても
BigQueryはとても便利だと思います。

元記事はこちら

BigQuery上で64ビット整数をビットスワップする話

丹野 航

丹野 航

BigQueryを軸にクラウドのビッグデータ分析基盤作ってます。趣味はJavaScript。どこでも動いて便利。

cloudpack

cloudpackは、Amazon EC2やAmazon S3をはじめとするAWSの各種プロダクトを利用する際の、導入・設計から運用保守を含んだフルマネージドのサービスを提供し、バックアップや24時間365日の監視/障害対応、技術的な問い合わせに対するサポートなどを行っております。
AWS上のインフラ構築およびAWSを活用したシステム開発など、案件のご相談はcloudpack.jpよりご連絡ください。