はじめに
こんにちは、AudienceOne開発部です。AudienceOne開発部ではいわゆるビッグデータと呼ばれる大量のデータをアドホックあるいは定常的に日々ETLだの集合演算だのをする一方で、様々な大規模データ処理ソリューションを継続的に検証しております。
本記事は、その中でもユーザが保持している属性値に対する集合演算に特化した処理の高速化検討のために、Amazon ElastiCache上のRedisを用いた集計処理パフォーマンスを確認し、結果をまとめたものです。
Redis
Redisという名前はREmote DIrectory Serverの大文字部分を拾ったもので、最大の特徴は全てのデータをメモリ上に展開し処理するという点で、当然高速なのだけどその代わりデータを載せれば載せるだけそれなりのメモリを食いまくる、といった動きとなります。このため、「どのようなデータをどれくらい乗せたらどの程度データを消費するか?」をHadoopベースのソリューション等よりもシビアに見る必要がありそうです。
詳細仕様などは下記のわかりやすい記事とオフィシャルなサイトをご覧いただくとして、
メモリに全部乗せるんであればMySQLのMemoryストレージエンジンでもいいじゃないか、という気もしますが、以前HadoopでのHiveとMySQL Memoryを比較した際に意外と前者のほうが早い結果に終わったということもあり(定量的ではないですが…)あまり早い印象は無いです。というわけで話を進めます。
Redis vs Memcached
Redis同様にAmazon ElastiCacheで利用可能なmemcachedについては、こちらのベンチマーク結果ではRedisより高速であるとの結果がでていますが、今回は「集合演算を実施すること」が主題ですので、keyとvalueが一対一対応に限定され後述するRedisのリスト相当の処理しかできないmemcachedについては、今回は検証対象とはしません。
Amazon ElasticChase
自前でRedisサーバを立てても良いのですが、細かいチューニングを避けるため、メモリ内キャッシュ提供サービスとしてmemcachedあるいはredisが利用できる、Amazon AWSサービスの一部であるAmazon ElastiCacheを使うことにしました。Elasticacheサービスの詳細については公式ページを参照ください。他AWSサービスと同様、コンソール経由で新規インスタンスを作成、立ち上げを実施することになります。
環境
以下が今回検証する環境となります。
- Redis クライアント:m1.large
- Amazon Linux AMI release 2012.03
- redis-cli 2.8.6
- Python等のスクリプトは利用せずにredis-cliのコマンドでデータを投入します
- Redis サーバ
- Cache Node Type: cache.r3.xlarge
- Engine: redis
- Number of Cache Nodes: 1
- Engine Version: 2.8.6
- クライアントとサーバは同一リージョン
対象データ・処理方法
Redisで利用できる型情報の詳細についてはこちらを参照ください。
User IDおよびUserが持っている情報(User Preference)およびそれらの関連が、データ・エンティティです。この前提で、対象データ構造を検討します。集合演算に適しているSetsを利用した場合、データ構造としては以下のようになります。
Key:User_Preference_1 -> Value:{ User_01, User_12, User_03, ... } Key:User_Preference_2 -> Value:{ User_03, User_55, User_19, ... } Key:User_Preference_3 -> Value:{ User_06, User_02, User_01, ... }
Bit Arraysを利用することでUserに対してUser_PreferenceをValueとして列挙し、効率的な格納ができるかもと考えたのですが、その場合は
Key:User01 -> Value:01010000001010111.... Key:User02 -> Value:01010000001010111.... Key:User03 -> Value:01010000001010111....
のような構造が想定されます。しかしUser Preference 1を1ビット目、User Preference 2を2ビット目、のように利用した場合、Redisのコマンドでは「2ビット目が1のKey(=User)を全て拾う」といった処理はできないようです。
また、下記のようなUser_PreferenceをキーにしてUserをValueとする構造も考えられます。
Key:User_Preference1 -> Value:01010000001010111.... Key:User_Preference2 -> Value:01010000001010111.... Key:User_Preference3 -> Value:01010000001010111....
このパターンはUserが単なるincrementされる数値表現であれば有用そうですが、擬似乱数などによりUser IDが自動生成されるケースにおいてはbit位置とUser IDとのマップ情報を保つ必要があり、仕組みが煩雑になりそうです。
以上の検討から、今回の検証は、最初に説明しました、Setsを利用した構造を採用することとします。
この前提で、更新方法やデータ量などは、極力単純に、以下のようにします。
- User Preferenceは各々16バイト固定の文字列で表現される
- User_NN はユーザIDに相当し、64バイト固定の文字列で表現される
- User Preferenceは10個あり、それぞれのPreferenceには10,000,000のユニークなユーザIDが存在する
- データのアドホックな更新はなく、データの一括削除およびバルクでのインポートしか実施しない
- つまり同時接続数は1となる
- テキストから10,000,000ユーザ x 10属性の 100,000,000回のSADD命令を一括で実施する
- 処理結果はクライアント・ローカルのEBSボリューム:Amazon EBS General Purpose (SSD) volumes に出力する
測定内容
- データのバルク・インポート時間、bytes-in量
- SINTER(A∩B; A and B)実行時間 … A=B ⇒ SCARD(A∩B)=SCARD(A)、A≠B ⇒ SCARD(A∩B)=0
- SUNION (A∪B; A or B)実行時間 … A=B ⇒ SCARD(A∪B)=SCARD(A)、A≠B ⇒ SCARD(A∪B)=2*SCARD(A)
- SDIFF (A-B; A and not B)実行時間 … A=B ⇒ SCARD(A-B)=0、A≠B ⇒ SCARD(A-B)=SCARD(A)
- 各コマンドを実行した際のファイルへの書き出しにかかった時間
- FLUSHDB(データの一括削除)時間
- 1を実行した際のメモリ消費量推移
- 全体的なCPUリソース消費量推移
※SCARD = 集合内の要素数
SINTER, SUNION, SDIFF, FLUSHDBについてはredis-cliの実行完了後に表示される実処理時間(sec)を利用する。データのバルク・インポート時間についてはtimeコマンドで実行開始から終了までの実時間を利用する。
実行方法
1. データをバルクインポート
$ head -1 data SADD User_Preference_1 000000b8Q0702Q478eQ0f03Q087f808eQ0e0000000b8Q0702Q478eQ0f03Q087f $ cat data | time redis-cli -h NNNN.cache.amazonaws.com -p 6379 --pipe & All data transferred. Waiting for the last reply... Last reply received from server. errors: 0, replies: 100000000 9.28user 23.82system 9:52.67elapsed 5%CPU (0avgtext+0avgdata 5936maxresident)k 0inputs+0outputs (0major+452minor)pagefaults 0swaps
2. SINTER(A∩B; A and B)実行
$ echo "sinter USER_PREFERENCE1 USER_PREFERENCE3" | redis-cli -h NNNN.cache.amazonaws.com -p 6379 > result $ tail -1 result (6.13s)
3. SUNION (A∪B; A or B) 実行
$ echo "sunion USER_PREFERENCE1 USER_PREFERENCE3" | time redis-cli -h NNNN.cache.amazonaws.com -p 6379 > result $ tail -1 result (406.03s)
4. SDIFF (A-B; A and not B) 実行
$ echo "sdiff USER_PREFERENCE1 USER_PREFERENCE3" | time redis-cli -h NNNN.cache.amazonaws.com -p 6379 > result $ tail -1 result (114.26s)
5. データの一括削除
$ echo "flusbdb" | redis-cli -h NNNN.cache.amazonaws.com -p 6379
測定結果
1,5については1回のみ実施、2〜4については各ケース毎に連続11回試行、1回目は捨てて平均値μ±標準偏差σを求めた。
- データのバルク・インポート時間・bytes-in量
- 592 [sec]
- 下記グラフのよう、ピーク時で 16,856,514.84 (Bytes/Second) が発生
- SINTER(A∩B; A and B)実行時間
- A=Bのケース :102.45±0.54 [sec]
- A≠Bのケース :4.85±0.45 [sec]
- SUNION (A∪B; A or B)実行時間
- A=Bのケース :122.33±2.15 [sec]
- A≠Bのケース :408.03±3.44 [sec]
- SDIFF (A-B; A and not B)実行時間 [各ケース10回試行]
- A=Bのケース :2.31±0.07 [sec]
- A≠Bのケース :116.84±0.49 [sec]
- データの一括削除時間
- 130.09 [sec]
- 1を実行した際のメモリ消費量推移
- おおよそ、28 GiB から13 GiBまで空きメモリリソース(Freeable Memory)が減少、約15 GiBが消費された。
- 全体的なCPUリソース消費量推移
- bulk import時最大25%、集合演算時最大10%〜15%程度。
考察
- key値 16B -> 64B x 20,000,000 ≒ 1.2GiB なので 10 keys で 12 GiB とすると、全体消費量は15GiBであるから、データ管理用領域に約 3 GiBを消費していると見なせそう。
- cache.r3.xlargeは28.4GiBのメモリが利用可能なので、( 28.4[GiB]/ 12 [GiB] ) x 100,000,000 [records] = 189,333,333 [records] 程度が収まる計算。
- 100,000,000レコードのロードにかかる時間は約592秒であり、概算で 100,000,000 [records] / 600 [sec]とすると166666.6667[record/sec] ≒ 150,000[record/sec] = 9,000,000[record/min] = 540,000,000[record/h]程度。
- Redisへのbytes-inが 16,856,514.84 [B/sec] = 16.07 [MiB/sec]、命令1行(SADD KEY VALUE)は87Bなので、単純にデータ量を命令で割ると193,753[record/sec]程度になり、150,000[record/sec]との差分があるが、この程度は通信時のヘッダ等のオーバーヘッドと見なせそう。
- SUNION, SDIFF, SINTER時の最悪値の条件としてはA=B、A≠B、A≠B時とみなせそうだが、今少しデータ種別を増やした検討が必要そう(例えばA∩BがちょうどSCARD(A)/2に等しくなるケースは処理時間がA=B時とA≠Bの間くらいに収まるのか、など)
まとめ
1000万レコード同士のロードしてのUNION処理が ロード3分弱、処理7分弱と10分程度で結果が得られるのはかなり高速な処理である、と言えるのではないかと思います。
今回はUser Preferenceをキーとした形のデータ構造で検証をしましたが、このデータの持ち方ですとUser Preferenceが増えるとデータ量が爆発するため、Preferenceを多数持つような形式においては現実的ではありません。よって、前述のようなBit Arraysの利用検討・検証を今後の課題とします。