1954

Thoughts, stories and ideas.

RedisのHyperLogLogの誤差について

HyperLogLogは集合のcardinalityを近似する確率的アルゴリズムです。

RedisにもPFxxxというcommandで実装されており、標準誤差は0.81%です。

The returned cardinality of the observed set is not exact, but approximated with a standard error of 0.81%.

redis.io

HyperLogLogは確率的アルゴリズムなので、精度は統計の手法で評価します。

HyperLogLogは期待値がcardinalityとなる確率変数で、標準偏差を真のcardinalityで割って得た相対誤差が0.81%であるということです。

ということは、誤差が0.81%を大きくはみ出すこともあるのでしょうか?

もちろんあります。

以下のデータをRedis 4.0.9にPFADDすると、真のcardinality 10000に対しPFCOUNTの値は1で、相対誤差-99.99%です。

gist.github.com

誤差が大きくなるような入力とは

HyperLogLogでは、ハッシュ関数(Redisの場合murmurhash2)を使ってランダムな試行をシミュレートします。

つまりハッシュ値が衝突するとき誤差が大きくなるのは自明ですが、一般にハッシュのpre imageを探すことは困難です。

いっぽう、HyperLogLogが保持するのはハッシュ値バケットの振り分けと、先頭で連続する0のbit数のみです。(くわしい話はぜひbuilderscon tokyo 2019で!)

つまり完全に衝突せずとも、同じバケットで同じ先頭の0 bit数のハッシュ値になる入力をさがせばよいことになります。

github.com

まとめ

builderscon tokyo 2019ではこういった誤差の話や動作原理も含め、HyperLogLogの色々な話をします。

builderscon.io

ビルコンにお越しの予定の方はぜひ聴きに来てみてください!

2018年の振り返り

登壇

LINE関連をメインに、いくつかのイベントで登壇の機会がありました。

仕事ではLINE Ads PlatformとりわけDMPの開発を担当していて、それについての発表が多かった。

LINE Ads Platformは8月に大幅刷新を行い、これからどんどんやっていくフェーズなので来年も楽しみです。

書いたもの

GoのGCについて調べた内容を、LINEの夏版Advent Calendar的なものに寄稿しました。

engineering.linecorp.com

ISUCON

メンバーは昨年に引き続き、前職の元同僚の方と組んだ「チーム人間性」で参戦しました。

昨年は予選で敗退してしまいましたが、今年は念願の本選出場を果たしました。

ocadaruma.hatenablog.com

とにかく運営の素晴らしさが際立っていました。

音楽

今年はセッションオフみたいなやつに行き始めてみました。

アイカツ、とかアニソンなんでも、とかテーマが決まっていて、やりたい曲に立候補し、当日スタジオで合わせるのが基本的な流れです。

イベントはおもにこのサイトやTwiplaで探しました。

バンオフ、やろう。 | バンオフまとめサイト「バンオフ.info」

参加したイベントリストは以下です。どの会もとにかく愛がすごかった。

来年

  • ベースをやっていく
    • トランペットよりもコンディションのコントロールがしやすくて精神的には楽。バテないし
    • 今までジャズのセッションはほとんどトランペットだったんですが、ベースでもぼちぼち参加したい
  • なんかすごいもの作る
    • めっちゃ面白い音ゲーを作る予定だったんですが作れなかったので
  • 引っ越す

複数サーバーでtail -fっぽく読むJavaライブラリtailer7

tailer7というJavaライブラリを公開しました。

github.com

これを使うと、たとえばcommons-io Tailerでログをtail -fしつつtailer7のLogSenderに投げれば、複数サーバーでLogTailerを立ち上げてstreamingでログを受け取れます。

イデアについてはこの記事にインスパイアされています。

lincolnloop.com

tailer7は以下のような用途を目的として作ったもので、厳密な順序保証とか信頼性とかそういった考慮はされていません。

  • Ansibleを実行するUIを開発していて、ansible logがリアルタイムに流れる画面を作りたい
    • リアルタイムに流れる画面を開き直したとき、新しく流れてくるログだけじゃなく、まずログの頭から読みたい
    • Ansibleを実行するサーバーはtailer7にログを投げ、画面を提供するサーバーはtailer7からログを読めば、スケールしやすくて便利!

ISUCON8本選に出場して5位だった

Webアプリケーションの高速化バトルISUCON8本選に「チーム人間性」で出場しました。

最終スコアは13,914で5位という結果に終わりましたが、素晴らしい運営と問題で、大変楽しいコンテストでした。

使用言語はGoでした。

やったこと

3人チームで参加し、自分はデプロイなどの足回りやインフラ周りを主に担当しました。

ここでは自分のやったことにフォーカスして書きますが、他にもクエリのキャッシュやmysqlのindex最適化など色々入ってます。

非docker化

今回与えられたマシンは4台で、ベンチマーク対象として指定できるのは1台でした。

初期状態では全てのマシンが同じ中身で、1台の中にnginx, mysql, アプリが全てdocker-composeで上がっていました。

後々辛くなりそうな気がしたので、dockerを剥がして以下のような構成にしました。

  • app server1
  • app server2
  • app server3 兼 nginx (エントリポイント)
  • db server (mysql8)

また、各サーバーのプロビジョニングはansibleで行いました。

ログのバッファリング

今回のアプリケーションには、外部のログ分析APIに一部の操作のログを送信するという仕様がありました。

ただしログ分析APIにはrate limitが設けられていて、rate limitを超えて送信した分はログが欠損し、ベンチマーク後のvalidationを通過できずfailするようになっています。

初期状態では1件ごとにログを送信しているため、スコアが伸びてくるとrate limitに引っかかってベンチマークがfailしてしまいます。

お誂え向きに、ログ分析APIにはバルクでログを受け付けるAPIが用意されていたので、goroutineとchannelを使ってログを一定数バッファリングしてバルクで送信するようにしました。

他の言語を使っていて、バッファリングをいい感じに書くのに苦労したチームもいたようです。

share有効化

今回は「仮想椅子取引所ISUCOINが世界的SNS"いすばた"と提携開始!」というシチュエーションで、いすばたでシェアされるとバイラル的にユーザーが増え、スコアが伸びるようになっています。

ただし、すごい勢いでユーザーが増える(ような挙動をベンチマーカーがする)ことによりrequest timeoutが頻発して、規定のエラー数を超えてfailしてしまうため、初期状態ではシェア機能がOFFになっています。

これを、10%のリクエストでのみシェア機能を有効にするようにしました。(単純にシェア機能を有効にするだけだと、エラー数超過でfailしてしまった。)

シェア機能を有効にするリクエストを絞るという発想にいたったのが17:30ごろだったのでだいぶ苦し紛れでしたが、これによりスコアがだいぶ伸びました。

まとめ

スコアの遷移はこんな感じでした。(予選もそうでしたが、ポータルサイトかっこよかった)

f:id:ocadaruma:20181021003417p:plain

うまく分担して進められた気はするものの、それでも時間が足りないと感じるほどボリュームのある問題でした。

あらためて、素晴らしい運営をしてくださったみなさん、ほんとうにありがとうございました!!

redshift-fake-driverでAmazon Redshiftをモックする

Amazon Redshiftは便利でコスパのよいDWHですが、時間に対する従量課金なので、ちょっとした動作確認のために立ち上げっぱなしにしとくのが気がひける場合もあります。

もしJVMプロジェクトを開発しているなら、redshift-fake-driverを使うことでRedshiftを代替できます。 github.com

What is redshift-fake-driver

Redshift固有のSQL syntaxを無視したり同等のものに置き換えてPostgresqlまたはH2にプロキシする、JDBCドライバーです。

UNLOAD, COPYのようなコマンドもサポートしています。

その場合、Java system propertyでS3エンドポイントを渡すことで、fake-s3のようなS3互換のモックを使うことも可能です。

Usage

では、fake-s3とPostgresqlを使って、使い方を見ていきます。

言語はScalaで、実行はAmmonite REPLで行います。

0. Postgresqlのセットアップ

$ createuser sample_user
$ createdb -O sample_user sample_database

1. fake-s3のセットアップ

$ gem install fakes3
$ fakes3 -r ./fakes3_root -p 9444

2. 依存の追加

redshift-fake-driverは、artfifactにAWS SDKPostgresql driverを含まないため、それらの依存を追加する必要があります。

以降、Ammonite REPLは立ち上げっぱなしと仮定します。

$ amm
scala> import $ivy.`com.amazonaws:aws-java-sdk-s3:1.11.43`
scala> import $ivy.`org.postgresql:postgresql:9.4.1211`

3. バケット作成

scala> import com.amazonaws.auth.BasicAWSCredentials
scala> import com.amazonaws.services.s3.{S3ClientOptions, AmazonS3Client}
scala> val options = S3ClientOptions.builder().setPathStyleAccess(true).build()
scala> val s3Client = new AmazonS3Client(new BasicAWSCredentials("DUMMY", "DUMMY"))
scala> s3Client.setEndpoint("http://localhost:9444/")
scala> s3Client.setS3ClientOptions(options)
scala> s3Client.createBucket("bar")

4. redshift-fake-driverのインストール

scala> import $ivy.`jp.ne.opt::redshift-fake-driver:1.0.7`

Scala以外のJVM言語の場合、artifact名はredshift-fake-driver_2.11などとすればよいです。

また今回fake-s3を使うため、Java system propertyを以下のように設定します。

scala> sys.props.put("fake.awsS3Endpoint", "http://localhost:9444/")
scala> sys.props.put("fake.awsS3Scheme", "s3://")

5. CREATE TABLE

Redshift固有の情報を含んだDDLでテーブルを作成します。

redshift-fake-driverを使うときは、JDBC接続文字列をjdbc:postgresqlredshiftで始めます。

scala> import java.util.Properties
scala> import java.sql._
scala> val url = "jdbc:postgresqlredshift://localhost:5432/sample_database"
scala> val prop = new Properties()
scala> prop.setProperty("driver", "jp.ne.opt.redshiftfake.postgres.FakePostgresqlDriver")
scala> prop.setProperty("user", "sample_user")
scala> Class.forName("jp.ne.opt.redshiftfake.postgres.FakePostgresqlDriver")
scala> val conn = DriverManager.getConnection(url, prop)
scala> val stmt = conn.createStatement()
scala> stmt.execute("""
               |CREATE TABLE foo_bar(a int ENCODE ZSTD, b varchar(255))
               |DISTSTYLE ALL
               |DISTKEY(a)
               |INTERLEAVED SORTKEY(a, b);
               |""".stripMargin)

ちゃんとテーブルが出来ています。

$ psql -U sample_user -d sample_database
sample_database=> \d foo_bar
           Table "public.foo_bar"
 Column |          Type          | Modifiers
--------+------------------------+-----------
 a      | integer                |
 b      | character varying(255) |

6. UNLOAD

まずデータを入れます。

$ psql -U sample_user -d sample_database
sample_database=> INSERT INTO foo_bar (a, b) VALUES (1, 'one');
sample_database=> INSERT INTO foo_bar (a, b) VALUES (2, 'two');

UNLOADを打って、fake-s3のデータを確認します。

scala> stmt.execute("""UNLOAD ('select * from foo_bar') to 's3://bar/result'
         |CREDENTIALS 'aws_access_key_id=DUMMY;aws_secret_access_key=DUMMY'
         |ADDQUOTES""".stripMargin)

ちゃんとデータが出来ていることがわかります。

f:id:ocadaruma:20180428190123p:plain

Redis cluster + lettuceでmget/msetすると複数リクエスト飛ぶ

Redis clusterに対してmget/msetしたとき、slotが異なるものが混在しているとCROSSSLOT errorが返ります。

したがってhash tagを用いてslotを指定するか、まとめたい単位でhash型のvalueに突っ込むなどのkey設計にする必要があります。

Redis Cluster Specification – Redis

いっぽう、lettuce(async対応のJava Redis client)では、mset/mget中にslotの異なるkeyが混在している場合、エラーを返すのではなく「slotごとにリクエストを投げる」実装になっています。(2018/4/4時点)

github.com

なので、key設計ミスっててもちょっと動かす分には問題なくて、負荷をかけた時にめっちゃリクエストが飛んでパフォーマンス出なくてミスに気づく、みたいなことになりえます。(それでハマった)

goofysを使ってS3以外のストレージをfstabでマウントする

goofysはAmazon S3またはAPI互換なストレージをfile systemとしてマウントできるツールです。

github.com

起動時に自動的にマウントするにはREADMEにあるように/etc/fstabへ追記すればよいですが、S3以外のストレージを使う場合は、以下のようにendpointを指定すればOKです。

goofys#your-bucket   /path/to/mountpoint        fuse     _netdev,allow_other,--file-mode=0666,--endpoint=https://some-s3-compatible-storage.com    0       0