Search

LINE株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。 LINEヤフー Tech Blog

Blog

This post is also available in the following languages. Korean, English


Redis Lua scriptingをatomicな処理とcache stampede対策に使った話

Kagaya Hokuto2017-12-17

2016年入社。LINE GAME プラットフォームのチームにおいてサーバサイドの開発に従事。

こんにちは。LINEでゲームプラットフォーム開発をしているKagayaです。この記事はLINE Advent Calendar 2017の18日目の記事になります。昨年新卒入社1年目で執筆した「マイクロサービスのためのプロジェクト生成ツールLazybonesを使ってみた」に引き続き、今年もAdvent Calendarの記事を書くことになりました。よろしくお願いします。

はじめに—RedisとLINE GAMEプラットフォーム

LINE GAMEプラットフォームでは、インメモリNoSQLデータベースであるRedisをメインデータベースの1つとして利用しています。キャッシュとしての利用が多く、例えば、LINEやFacebookなどのアカウントで認証を行っているユーザのソーシャルデータ（プロフィールや友だちリストなど）のキャッシュに利用しています。基本的にはRedis Clusterとして利用しており、開発環境では共通のクラスタを、本番環境ではゲームごとに独立のクラスタを組んで運用しています。

ちなみに、メインデータベースとしてRedisと併用しているのはHBaseです。多くのコンポーネントでは、Redisをキャッシュとして使う一方で、HBaseを永続化用ストレージとして利用しています。LINE GAMEプラットフォームでのHBaseのユースケースについては、今年のLINE DEVELPER DAYで「Data Processing behind LINE Game Platform」と題して発表していますので、ぜひご覧ください。

HBaseとRedisの2つのデータベースを併用するケースが非常に多いので、私たちのチームでは、アプリケーションからこれらを簡単に利用するためのクライアントライブラリAegisを内部で実装して利用しています。実際には、このライブラリは既製のJava向けクライアントをラップした上で、接続情報などのメタデータの管理を行う部分を追加した実装になっています。RedisのクライアントとしてはJedisを利用しています。

Redis cluster

すでに述べたように、私たちのチームでは基本的にRedis Clusterを組んで運用しています。Redis Clusterでは、データはHash slotと呼ばれる入れ物ひとつひとつに収納されます。スロットの数は固定で16384個です。そのスロットを各ノードに水平に分割することでクラスタリングを実現します。データをどのスロットに格納するかは、キーのCRC16値を計算してそれを16384で割った値を利用して決定します。

MGETやMSETなどの複数のキーを指定するコマンドは、それらのキーがすべて同一のスロットに属する場合は、クラスタ運用の場合もシングルノードの場合と同じように実行できます。

Lua scripting

Lua scriptingとは、Redisサーバに組み込まれたLua interpreter上で、EVALコマンド（またはEVALSHAコマンド）を利用して任意のコマンドを組み合わせた処理を行える機能のことで、Redis 2.6.0から利用できます。スクリプト内部で使えるように、いくつかのライブラリがあらかじめ組み込まれています。複数のコマンドをまとめられるだけでなく、スクリプトそのものが大きな1つのコマンドとして解釈されるので、スクリプトがatomicに処理されるのも大きなポイントです。型の変換やデバッグの方法など注意すべき点もいくつかあるので、詳しくは、公式ドキュメントのEVALコマンドのページをご参照ください。

JedisからLua scriptingを利用するコマンドのインタフェースは以下のようになっています。

Object eval(String script, List<String> keys, List<String> args);
// or..
Object eval(String script, int keyCount, String... params);

メソッド引数からも分かるように、EVALの引数にはkeyおよびargがあります。Luaのスクリプト内からはそれぞれKEYSおよびARGVという配列でアクセスできます。シングルノードで運用する場合には、ユーザから見てkeyとargに特に違いはなく、どちらに何を指定しても問題ありません。Redis Clusterとして利用している場合には、KEYSによってスクリプトを実行するノードを振り分けるので、キーはKEYSで指定する必要があります。

EVALSHAコマンドについて

スクリプトが長くなってくると、毎回EVALコマンドでスクリプト全体を送信するのはネットワーク帯域がもったいないと感じることがあると思います。RedisではSCRIPT LOADコマンドでスクリプトをサーバ側にキャッシュさせ、その返り値で受け取ったキーを使ってEVALSHAコマンドでスクリプトを実行できます。

ただし、私たちのチームはLua scriptingを利用してはいるものの、現在はEVALSHAコマンドを利用していません。というのも、ノード毎の管理・キーそのものの管理コストと、削減されるネットワーク帯域のメリットが釣り合わないと判断したためです。私たちのスクリプトは数コマンド数行程度の短いスクリプトであり、EVALSHAコマンドでキー（実際はその名のとおりSHA-1）を送信しても、ネットワーク帯域の削減割合は小さいです。また、Redis Clusterの場合、キーが格納されているノードでSCRIPT LOADコマンドを実行する必要があるので、クラスタ内のノードすべてにスクリプトをキャッシュさせなければなりません（ちなみに、シングルノードでは一度実行されたスクリプトは内部にキャッシュされるので、この点について気にする必要はありません）。もちろん、大きめのスクリプトを利用するユースケースでは、アプリケーション側であらかじめ各ノードにSCRIPT LOADコマンドを実行しておくのも良い方法だと思います。

Hash tags

読者の方の中にはすでに疑問・ツッコミをお持ちの方もいらっしゃると思いますが、keyが複数指定された場合、スクリプトはどこで実行されるのでしょうか？すでに述べたコマンドの場合と同様に、異なるHash slotに収納された複数のキーを引数に取るスクリプトは実行できません。この問題の解決策として、RedisではHash tagsと呼ばれる仕組みが準備されています。キーの一部を{}で囲うことにより、その部分が一種のタグのように判断され、同じタグをもつキーは同じスロットに含まれることが保証されます。例えば、以下のキーはすべて同じスロットに含まれます。

{LINEGAME}:user
{LINEGAME}:friends
{LINEGAME}:blacklist

複数のキーを受け取るスクリプトを実行したい場合は、この仕組みを使うことで対策できます。

RedisでのLua scripting活用例1：Atomicな処理

ここからは、LINE GAMEプラットフォームの開発での、Lua scriptingの実際の利用例を紹介します。

先程例を挙げたソーシャルグラフの友だちデータはRedisで管理しています。いくつかのタイミングでアプリケーションサーバからKafkaにシグナルが送られ、それを処理するワーカープロセスがデータを計算してRedisに格納しています。例えば、友だちリストを作成するコマンドは以下のようなイメージです[1]。

DEL friends:user1 
RPUSH friends:user1 user2 user3 user4 ...
EXPIRE friends:user1 YYYYY

元々のキャッシュを消して、Redisのリスト型に友だちリストを追加して、TTLを設定します。見たとおりですね。ある日、何人かのユーザの友だちリストにメンバーが重複しているケースが見つかりました。ちょうど数が2倍になっていたので、RPUSHコマンドが2回呼ばれている可能性が疑われました。調査の結果、問題が発生していたユーザの友だちリスト作成リクエストが、全く同時に2件サーバに届いていたことがわかりました。私たちが利用しているKafka 0.9系ではAt least onceポリシーが採用されているために、1つのメッセージが2度配送される可能性がありますし、先程述べたように、そもそも私たちのプラットフォームの中で、メッセージがプロデュースされるトリガは複数あるので、それだけでも十分重複してしまう可能性があります。そのため、以下のシーケンスが発生する可能性は十分にあるということですね。

DEL (by message A)
↓
DEL (by message B)
↓
RPUSH (by message A)
↓
RPUSH (by message B)

よって、これらのコマンドをatomicに処理する必要があるということになりました。

Redisで複数の処理を一気にサーバに送る方法はいくつかあります。

  • MSETやMGETのような複数のキーを操作するコマンドを使う。
  • pipelineを使う。
  • transaction（MULTIおよびEXECコマンド）を使う。
  • Lua scriptingを使う。

複数のコマンドをまとめる処理となると、1つ目を除いた3個の選択肢がありますが、その中でもpipelineは少し毛色が違って、あくまで帯域幅の側面から最適化するための機能です。そのため、サーバ内部での一連の処理のatomicityは保証されません。よって、複数のコマンドをatomicに処理するには、transactionかLua scriptingしか方法がありません。さて、Redis Clusterを利用している場合のクライアントの視点から考えてみると、MULTIおよびEXECコマンドを利用する際、MULTIコマンドの実行時には変更を行おうとしているキーがどのノードにあるかを判断できません[2]。あらかじめtransactionに含まれるキーを渡してノードを計算しておけば良いかもしれませんが、リシャーディングの影響まで考えると実装が難しく、実際にJedisにはその実装はありません。Lua scriptingの場合、前述のとおりコマンドの実行時に明示的にキーを与えられるので、サーバ側でリダイレクトできます。よって、私たちはLua scriptingを採用することに決めました。

コードのイメージは以下になります。

String script = "redis.call('del', KEYS[1]);" +
                "redis.call('rpush', KEYS[1], unpack(ARGV, 2));" + 
                "redis.call('expire', KEYS[1], ARGV[1]);";
List<String> params = new ArrayList<>();
params.add(String.valueOf(TTL)); // "TTL" is a predefined constant for TTL.
params.addAll(getFriends()); // getFriends() returns users' ID list.
jedisCluster.eval(script, ImmutableList.of(key), params);

argのうち、1つ目の引数をTTLに、2つ目以降をRPUSHコマンドの引数として利用しています。

ちなみに、公式ドキュメントには以下の記述があり、clusterが普及していくであろう今後はtransactionは廃止の方向に向かうかもしれません。

[..] However it is not impossible that in a non immediate future we'll see that the whole user base is just using scripts. If this happens we may deprecate and finally remove transactions.

RedisでのLua scripting活用例2：Cache stampede対策

アプリケーションレベルでデータのキャッシュを作る方法はいくつかありますよね。ユーザのリクエストに応じて、キャッシュがあったらそれを見て、なかったらマスタデータを参照して返すと同時にキャッシュを生成する、という仕組みを採用している場合を考えてみます。同時リクエスト数がかなり多い場合は、キャッシュが切れた瞬間に、マスタデータ側のI/Oとアプリケーション側のキャッシュ再計算のためのCPUリソースのどちらについても、負荷がスパイクしてしまう可能性があります。これを防ぐための手法はいくつか知られています[3]が、その1つにProbablistic Early Recomputation（PER）があります。このセクションでは、この手法をRedis Cluster上で実装したケースについて書きたいと思います。

PERは元々VLDBという国際会議で発表された手法で、論文もインターネット上で読むことができます。簡単に言えば、キャッシュエントリの有効期限が切れる前に、「ボランティア」とでも呼ぶべきリクエストがある確率でキャッシュを再計算する手法です。類似の手法として、2つの異なるTTLを持つ同一内容のキャッシュを用意するパターンもありますが、PERには容量を1エントリ分に削減できるメリットがあります。アルゴリズムの擬似コードを以下に示します。

def get(key, ttl, recomputer) {
    beta = 1.0 # typically
    data, remained_ttl, computation_time = read_from_cache(key)
    time = now()
    if (!data or time - delta * beta * log(random(0, 1)) >= time + remained_ttl) {
        start = now()
        data = recomputer.recompute(key)
        end = now()
        computation_time = end - start
        write_to_cache(key, data, computation_time, ttl)
    }
    return data;
}

確率分布に何故この分布が採用されているか、betaをどのように決めるべきか、などは非常に興味深いトピックですが、このブログの趣旨からは外れますのでオリジナルの論文をご覧ください。

さて、上記の擬似コードをJava + Jedisで書き直すと、以下のようになるでしょう。

private static final int TTL = 60;
private static final String SET_SCRIPT = "redis.call('mset', KEYS[1], ARGV[1], KEYS[2], ARGV[2]);" + 
                                         "redis.call('expire', KEYS[1], ARGV[3]);" +
                                         "redis.call('expire', KEYS[2], ARGV[3])";
private static final String GET_SCRIPT = "return {redis.call('mget', KEYS[1], KEYS[2])," +
                                         "redis.call('ttl', KEYS[1])}";
 
public String get(String key, Function<String, String> recomputer) {
    List<Object> ret = (List<Object>) jedisCluster.eval(GET_SCRIPT, 2, key, getDeltaKey(key));
    List<String> valueList = (List<String>) ret.get(0);
    String data = valueList.get(0);
    String deltaStr = valueList.get(1);
    if (data == null || 
        - Long.valueOf(deltaStr) * beta * Math.log(random.nextDouble()) >= (long) ret.get(1)) {
        long start = System.currentTimeMillis();
        data = recomputer.apply(key);
        long computationTime = (System.currentTimeMillis() - start) * 1000; 
        jedisCluster.eval(SET_SCRIPT, 2, key, getDeltaKey(key), data, computationTime, ttl);
   }
   return data;
}

public String getDeltaKey(key) {
    // return key for storing delta, that is, computation time.
}

読み取りの際は、MGETコマンドで実際のデータと計算時間のそれぞれのエントリを取得し、データの残りTTLをTTLコマンドで取得します。書き込みのときは、MSETコマンドとEXPIREコマンドでデータと計算時間を収納します。ちなみに、この他にもRedisのハッシュ型にデータと計算時間を収納する方法も考えられます。その場合はHMSETコマンドとHMGETコマンドを利用することになるでしょう。

Developer Day 2017で発表した新しいLINE GAMEプラットフォームでも、PERを利用しています。性能テストでは、PERの導入でキャッシュが切れた時のレスポンスタイムが3倍ほど改善しました（もちろん、レスポンスタイムはアプリケーション側での処理の重さや、メインのデータベースから取得するデータの大きさなどに依存しますが）。今回の記事はRedis Lua scriptingの使い道の解説が主眼なので、どれだけパフォーマンスが改善するかは、今後機会があればご紹介したいと思います。

おわりに

本記事では、LINE GAMEのプラットフォームを開発する私たちのチームでの実例を交えながら、Redis ClusterにおけるLua scriptingの使い所を紹介しました。RedisのLua scriptingはそれ単体で見ても意外と奥が深い機能です。その他の機能や詳細については、公式ドキュメントやソースコードをご覧ください。

明日の記事は米原さんによる「V8のHidden Classの話」です！お楽しみに。

  1. 「友達リスト」というと、ユーザが直接追加・変更・削除をするように聞こえますが、この場合の「友達リスト」についてはLINEやFacebookなどのAPIを通じて得られたリストそのものを格納しています。そのため我々の視点では差分を計算しない限りRedisのSET型を使って重複を防ぐなどの対策は難しくなっています。 ↩

  2. 一応、キーを含むHash slotを手計算で求めた上で、CLUSTER NODESコマンドでどのノードがどのスロットに含まれるかを計算することは可能です。 ↩

  3. その他の手法とその長所短所については、RedisConf 2017で発表された「Preventing Cache Stampede with Redis and XFetch」によくまとまっています。 ↩