カテゴリー別アーカイブ: 未分類

乱数の生成について

Pocket

こんにちは。データ解析部の西岡(敏)と申します。 広告配信の効果分析とアルゴリズム実装を担当しております。

今回は、システムで利用する乱数の生成について書きたいと思います。

乱数について

過去、コンピュータの無い時代には、サイコロを振ってその数字を記録したり、コインを投げてその裏表を調べたりすることで乱数を得ることができました。 ただし、こういった乱数は大量のデータを必要とする実験では不便であるため、現在はそのような実験を行う際にはコンピュータを利用して擬似的に乱数を生成しています。

こういった形でコンピュータを用いて生成する乱数のことを、前述のサイコロの乱数などとは区別し、算術乱数や擬似乱数と呼びます。

プログラムで使われる乱数

前述のように、疑似乱数はコンピュータから生成を行うため、乱数が本来持っているべき予測不可能性を持ちません。 ですが、出来る限りランダムであることが担保され、非常に長い周期を持てば、シミュレーションなどに利用するのに差し支えはないということになります。

疑似乱数は主にコンピュータ上で生成・使用され、そのために生成される乱数の質や周期の長さと同等に、コンピュータ上で生成される速度、プログラミングの簡素さ、使用する記憶領域の大きさが乱数生成器の評価のポイントとなっています。

以下では、システムで広く使われている代表的なアルゴリズムである、 線形合同法と、メルセンヌ・ツイスタの説明を行っていきます。

線形合同法

概要

1948年頃にレーマーが提案した方法で、今日でも広く使われている手法になります。 BASICやPascal, UNIXなどでこちらの方法が乱数生成に使われています。

基本的な算出方法は、 適当なX(0), 乗数a, 加数b, 法(modulus)Mを指定し、

X(n) = (a * X(n-1) + b) % M として、計算を行うものになります。

このとき、 bがMと互いに素 a-1がMを割り切るすべての素数の倍数 Mが4の倍数 であれば

a-1も4の倍数

という条件が、X(n)の周期が最大値Mとなる必要十分条件になります。

pythonによるプログラミング

実際にpythonで線形合同法を用いて乱数の生成を行ってみます。

線形合同法の問題点

上記のように、簡単に生成ができる一方で、この手法には 周期の限界が2^32にあること、下位ビットには周期的な偏りがあること(上記の例でも、下一桁が奇数→偶数の繰り返しになっている) などの問題点があります。 そのため、下位ビット部分を切り捨てて実装を行っている場合もあるそうです。

メルセンヌ・ツイスタ

概要

続いては、今日様々なシステムで利用されているメルセンヌ・ツイスタに関して説明を行います。 メルセンヌ・ツイスタはM系列を松本眞氏と西村拓士氏が発展させたものであり、疑似乱数生成器として現在最も高い評価を得ています。

メルセンヌ・ツイスタの説明

メルセンヌ・ツイスタの説明に当たって、まずM系列の説明を行います。

M系列

M系列とは、Xn = Xn-p + Xn-qで表現できる1ビットの数列になります。

例えば、 X0 = 1, X1 = 0, X2 = 0, p = 3, q = 1 としたとき、

X3 = X0 + X2 = 1 + 0 = 1
X4 = X1 + X3 = 0 + 1 = 1
X5 = X2 + X4 = 0 + 1 = 1
X6 = X3 + X5 = 1 + 1 = 0

という計算によって算出できます。

TGFSR

M系列を発展させたものに、 Twisted General Feedback Shift Register(TGFSR)があり、こちらは

Xn+p = Xn+q + Xn *A (p>q>0)

を用いて表現することができます。 ここで、Aはω✕ωの行列、Xはω次元の行ベクトルになります。 また、このときωは32, 64など、生成する乱数のビット数となります。

メルセンヌ・ツイスタ

さらにTGFSRを

Xn+p = Xn+q + Xn+1 *B + Xn *C (p>q>0)

として改良したものがメルセンヌ・ツイスタになります。

特に、こちらのこちらの最大周期が2^19937 – 1のときにMT19937と呼ばれ、 通常のメルセンヌ・ツイスタはこのMT19937を指します。

具体的な計算方法としては、 init_genrand関数とgenrand_int関数を準備し、 init_genrand関数を実行した後に、生成する乱数分genrand_int関数を実行するという流れになります。 それぞれの関数は以下の形式となります。

  • init_genrand 関数
    • 0 番地に種を代入する。
    • i 番地の値を得るために、i-1 番地の値を使用する。シフト、EXOR、乗算、加算の順に演算を行う。
    • 623 番地まで計算を繰り返し、値を代入する。
  • genrand_int 関数 a. (624n+1)回目の場合(n=0,1,2,…)
    • 0 番地から 227 番地まで AND、OR、EXOR 演算を行う。
    • 228 番地から 623 番地まで、別の数値を使って AND、OR、EXOR 演算を行う。
    • 再び別の数値を使って、AND、OR、EXOR 演算を行い、y に代入する。 b. 毎回共通の部分
    • y にシフト、AND、EXOR 演算を行い、生成された乱数を返す。

pythonによるプログラミング

実際にpythonで線形合同法を用いて乱数の生成を行ってみます。

以上のような形で、乱数の生成を行うことができました。 このメルセンヌ・ツイスタに関しては、線形合同法であったような、 周期が短かったり、値によっては下一桁が偶数, 奇数と交互に出現するといった問題点が発生せず、 非常に優れた擬似乱数生成器として、様々なプログラミング言語に幅広く利用されています。

まとめ

このように乱数と言っても複数の種類があり、それぞれの乱数には特徴があります。 現在は、高い精度の検証をする場合などは、線形合同法で作成されたよりもメルセンヌ・ツイスタの方が良いと言われています。 もし何かしらの実験を行っているときなどに、こういった乱数に着目すると、意外な解決策が見いだせるかもしれません。

参考

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/ichimura-sho-koen.pdf http://www.soi.wide.ad.jp/class/20010000/slides/03/sfc2002.pdf http://random.ism.ac.jp/info01/random_number_generation/node6.html http://www.utp.or.jp/book/b300859.html http://www001.upp.so-net.ne.jp/isaku/rand.html https://narusejun.com/archives/5/

Amazon Elasticsearch ServiceでKibanaを利用する

Pocket

みなさんこんにちは。配信/インフラチームの佐々木と申します。adstirの配信サーバの開発とインフラを担当しております。

今回はAmazon Elasticsearch ServiceとKibanaを利用したデータの可視化について書きたいと思います。

ElasticsearchとKibanaについて

両方とも有名なミドルウェアなので詳細な説明は省きますが、端的に言うとElasticsearchは全文検索エンジンでKibanaがそれを可視化するためのWEB-GUI(中身はNode.js)になります。

ポイントとしてはElasticsearchもKibanaもオープンソースで公開されているのですが、両方ともAWSのマネージドサービスとしても提供されているため、構築と運用の負担が非常に軽いという点があります。(もちろんEC2を利用する事もできますし、AWS以外の環境でも利用は可能です。) 開発元が同一なため親和性が高く、今後はバージョンも統一されていくようです(現在は5.x) Kibanaは以前のバージョンではダッシュボードは黒をベースとしたUIでしたが、このバージョンは非常にカラフルなデザインになっております。

ちなみに余談ですが正しくは”ElasticSearch”ではなく”Elasticsearch”となります。ですがちょっと長いのでこのブログではESと略させていただきます。

データのフロー

ESはWEB-APIとして動作するのですが、Fluentdでプラグインが用意されているためそれを利用するケースが多いです。 直接POSTしても良いのですが、Fluentdを利用した方が簡単かつフレキシブルに使えます。流れとしては

Fluentd -> ES -> Kibana

となりますが、データをS3に保存する場合は以下のような流れが良さそうです。

Fluentd -> S3 -> Lambda -> ES -> Kibana

今回は前者の手順を記載いたします。

構築手順

1. AmazonESとKibanaのセットアップ

セットアップ自体は非常に簡単で、ものの数分で終わります。(作成の待ち時間がそれなりにありますが)AWSさまさまと言ったところです。

ESのダッシュボードでCreate a new domainをクリックします。 スクリーンショット 2017-06-15 18.36.03

Domain名とバージョンを指定しNextをクリックします。 スクリーンショット 2017-06-15 18.36.59

インスタンス数やスペックなどを指定しNextをクリックします。 スクリーンショット 2017-06-15 18.37.52

最後にアクセスポリシーを設定し、Confirm and createをクリックします。 スクリーンショット 2017-06-15 18.39.40

10分程度待てば作成が完了します。同時にKibanaも使える状態になっています。 スクリーンショット 2017-06-15 18.40.28

2. Fluentd設定

下準備としてはFluentdとfluent-plugin-aws-elasticsearch-serviceをインストールしている必要があります。送信先にESのURLを指定します。

3. ES設定

簡単な使い方をするのであれば設定は特に必要ありません。データがインサートされればそのまま使えるようになります。

4.Kibana設定

まずIndexの設定をする必要があります。ManagementでIndex Patternsをクリックします。 スクリーンショット 2017-06-20 12.40.21

Add Newをクリックします。 スクリーンショット 2017-06-20 12.41.07

作成したインデックスのパターンを入力し、Createをクリックします。 スクリーンショット 2017-06-21 11.58.45

登録したインデックスのデータは、Discoverから確認できます。この例ではscore_Xというランダム数値のデータを使用しています。 スクリーンショット 2017-06-21 11.56.59

次にインデックスからグラフを作成します。今回は折れ線グラフを作成しますので、VisualizeでLine chartを選択します。 スクリーンショット-2017-06-22-12.01.21

対象のインデックスを選択します。 スクリーンショット 2017-06-21 12.01.46

Y-Axisに対象のデータを登録し、X-AxisでDate Histogramを選択すれば時系列の折れ線グラフが出来ます。設定したらSaveをクリックします。 スクリーンショット 2017-06-21 12.23.32

あとはDashboardで作成したグラフを貼り付けます。KibanaはDashboardが自由にカスタマイズ出来、例えばWEBサーバのレイテンシを確認しながら生のログを見るといった使い方が出来ます。 スクリーンショット 2017-06-21 12.44.18

以上が構築手順になります。

最後に

弊社ではアドテクエンジニアを募集しております。広告技術に興味がある方・経験がある方のご応募をお待ちしております。また広告以外の部署やエンジニア以外の職種でも募集しておりますので、興味がある方はぜひご応募くだされば幸いです。

弊社コーポレートサイト
http://united.jp/recruit/information/

Wantedly
https://www.wantedly.com/companies/united/projects/

Redisにおけるデータの大量挿入手法

Pocket

こんにちは。Bypass開発チームの川住と申します。
今回はRedisにおけるデータの大量挿入手法について紹介します。

Redisとは?

まず、Redisについて少し紹介します。
Redisとは、メモリ上に Key-Value Store(KVS)を構築できるソフトウェアです(http://redis.io/)。
同系統のソフトウェアにはmemcached (http://memcached.org/) などがあります。
memcachedと比較すると、

  • シングルスレッドでクエリを処理する
  • データを永続化できる
  • ハッシュやリストなど、様々なデータ型を利用できる

といった特徴があります。

これらのソフトウェアを用いると、
メモリ上にデータを保持しており、かつ処理がシンプルであるため、
高速にデータの取得(格納)可能なKVSを構築できます。

データの大量挿入

本題に移ります。
Redisのデータの格納はとても高速ですが、シングルスレッドでクエリを処理するため、
データ数に比例して処理に時間がかかってしまいます。

そこで、大量のデータを挿入する時には、
「1件あたりのデータの挿入にかかる時間」をできるだけ短くする必要があります。

弊社では、Perlスクリプトでデータを加工し、Redisに大量のデータを格納しています。
この時、PerlのRedisモジュールを用いて1件ずつデータを格納してしまうと、

  • Redisとのデータの送受信で発生するRTT (Round-Trip Time)
  • Redisからのレスポンスをパースし、Perlのデータ型に加工する時間

が問題になります。そこで、

  • 複数のコマンドの一括送信
  • Redisからのレスポンスの破棄
    • socketやnc (netcat) でコマンドを送信し、レスポンスを/dev/null等に捨てる

を行い、処理時間を削減します。

処理時間の計測

下記の手法で10万件のデータの格納にかかった時間をそれぞれ計測しました。

  • PerlのRedisモジュールを使う(手法1)

  • socketを用いてデータを流し込む(手法2)

  • ncを用いてデータを流し込む(手法3)

計測結果

同端末で各手法5回ずつ試行し、その平均を処理時間としました。

手法 処理時間 (sec) ロス率
手法1 (module) 59.710145 0%
手法2 (socket) 2.978576 0%
手法3 (netcat) 2.626164 18%

複数のデータの格納コマンドを一括で送信し、
レスポンスのパースを行わないことによって処理時間を大幅に削減できます。
socketを用いる場合は送信(受信)バッファの管理を行わないと、
バッファ溢れによってデータロスが発生してしまいます。

まとめ

今回はRedisにおけるデータの大量insert手法を紹介しました。
目的に合わせて最適な手法を選択することでより効率的にデータを処理できるようになります。
(参考URL: http://redis.io/topics/mass-insert