Atomic 처리와 cache stampede 대책을 위해 Redis Lua script를 활용한 이야기

안녕하세요? LINE에서 게임 플랫폼 개발을 맡고 있는 Kagaya입니다. 신입 사원 1년차였던 2016년에 마이크로 서비스용 프로젝트 생성 도구 Lazybones를 사용해 보니(일본어 글)를 포스팅한 데 이어 한번 더 기고하게 되었습니다. 반갑습니다.

Redis와 LINE GAME Platform

LINE GAME Platform은 주 데이터베이스의 하나로 인메모리(in-memory) NoSQL 데이터베이스인 Redis를 사용하고 있으며, 이를 주로 캐시로 이용합니다. 이를테면 LINE이나 Facebook 등의 계정으로 인증하는 사용자의 소셜 데이터(프로필이나 친구 목록) 캐시로 이용합니다. 기본적으로는 Redis Cluster 형태로 이용하고 있으며, 개발 환경에서는 공통 클러스터를, 서비스 환경에서는 게임별로 독립 클러스터를 구성해 운영하고 있습니다.

참고로 Redis와 함께 HBase도 주 데이터베이스로 사용하고 있습니다. 많은 컴포넌트에서 Redis는 캐시로 HBase는 영속화용 스토리지로 사용하고 있습니다. LINE GAME 플랫폼의 HBase 유스케이스에 대해서는 2017년 LINE DEVELOPER DAY에 Data Processing behind LINE Game Platform이라는 제목으로 발표한 바 있으니 관심 있는 분은 확인해 보시기 바랍니다.

HBase와 Redis 이 두 가지 데이터베이스를 자주 같이 사용하곤 하는데 이를 애플리케이션이 손쉽게 이용할 수 있도록 저희 팀은 내부용으로 클라이언트 라이브러리 Aegis를 구현하였습니다. 이 라이브러리는 기성 Java용 클라이언트를 래핑한 것으로, 접속 정보 등 메타 데이터를 관리하는 부분이 추가되었습니다. Redis 클라이언트로는 Jedis를 사용하고 있습니다.

Redis Cluster

앞에도 언급했지만, 저희 팀은 기본적으로 Redis Cluster를 구성해 운영하고 있습니다. Redis Cluster에서는 데이터가 해시 슬롯(hash slot)이라 불리는 칸에 한 단위씩 보관됩니다. 슬롯의 개수는 16,384개로 고정되어 있으며 슬롯은 각 노드에 수평하게 분할해서 클러스터링합니다. 데이터를 어느 슬롯에 저장할지는 키의 CRC16 값을 계산한 뒤 이를 슬롯의 개수, 즉 16,384로 나눈 값을 가지고 결정합니다. 클러스터 형태에서 MGET이나 MSET처럼 키를 여러 개 지정하는 명령어를 사용하려면 지정하는 키가 모두 같은 슬롯에 속한다는 조건이 만족되어야만 싱글 노드일 때와 마찬가지로 클러스터를 운영할 수 있습니다.

Lua scripting

Lua scripting이란 Redis 서버에 내장된 Lua 인터프리터에서 EVAL 명령어(또는 EVALSHA 명령어)를 이용하여 임의의 명령어를 조합한 처리를 수행하는 기능으로, Redis 2.6.0부터 사용할 수 있습니다. Lua script 내에서 사용할 수 있도록 몇몇 라이브러리가 Redis에 탑재된 Lua 언어 프로세서에 이미 내장되어 있습니다. 여러 가지 명령어를 조합할 수 있을 뿐 아니라, 스크립트 자체가 하나의 큰 명령어로 해석되기 때문에 스크립트가 atomic하게 처리된다는 점도 커다란 특징입니다. 타입 변환이나 디버그 방법 등 주의할 점도 몇 가지 있는데요, 자세한 내용은 공식 문서의 EVAL 명령어 페이지를 참고하시기 바랍니다.

Jedis에서 Lua scripting를 이용하는 명령어의 인터페이스는 다음과 같습니다.

Object eval(String script, List keys, List args);

// 혹은
Object eval(String script, int keyCount, String... params);

메서드 인자를 보면 알 수 있듯, EVAL의 인자로는 keysargs가 있습니다. Lua script 내에서는 각각 KEYS배열 및 ARGV 배열로 인수 값에 접근할 수 있습니다. 만약 Redis를 싱글 노드로 운영한다면 사용자 입장에서는 KEYSARGV인자에 딱히 차이가 없으므로 어느 인자에 어떤 값을 넣어도 상관없습니다. 다만, 싱글 노드가 아닌 Redis Cluster를 이용한다면 KEYS 값에 따라 스크립트 실행 노드가 할당되므로 키는 KEYS 인자에 지정해야 합니다.

EVALSHA 명령어

스크립트가 길어지면 스크립트 전체를 매번 EVAL 명령어로 전송하기에는 네트워크 대역이 아깝다는 생각이 들 텐데요, Redis에서는 SCRIPT LOAD 명령어로 스크립트를 서버 측에 캐싱한 다음, 캐싱 반환 값으로 받은 키를 이용하여 EVALSHA 명령어로 스크립트를 실행할 수 있습니다. 다만, 저희 팀은 Lua script를 사용하긴 하지만 EVALSHA 명령어는 현재 사용하지 않고 있습니다. 왜냐하면 노드 관리와 키 관리에 소요되는 비용과 네트워크 대역 절감 효과를 비교해보니 EVALSHA 명령어를 사용하더라도 장점이 그다지 크지 않다고 판단했기 때문입니다. 저희 스크립트는 명령어 몇 개, 몇 줄 정도로 짧은 편이라, 키(실제 값: SHA-1)를 EVALSHA 명령어로 전송해도 네트워크 대역의 절감 효과는 크지 않습니다. 또한 Redis Cluster에서 SCRIPT LOAD 명령어를 실행하려면 키가 저장되어 있는 노드에서 해야 하기 때문에 스크립트를 클러스터 내의 모든 노드에 캐싱해야 합니다. (참고로, 싱글 노드에서는 한 번 실행된 스크립트는 내부에 캐싱되므로 이 부분은 신경쓰지 않아도 됩니다.) 물론 긴 스크립트를 사용하는 유스 케이스라면 애플리케이션 측에서 미리 각 노드에 SCRIPT LOAD 명령어를 실행해두면 좋겠지요.

해시 태그

이쯤에서 이것이 벌써 궁금한 분도 계실 겁니다. 키(key)가 여러 개 지정되었을 경우, 스크립트는 어디에서 실행될까요? 앞서 말씀드린 명령어와 마찬가지로, 스크립트가 인자 값으로 서로 다른 해시 슬롯에 보관된 복수의 키를 받으면 스크립트는 실행할 수 없습니다. 이 문제를 해결하기 위해 Redis는 해시 태그(hash tag)라 불리는 방법을 제공합니다. 키의 일부를 중괄호({})로 감싸면 해당 부분이 일종의 태그처럼 인식되며 같은 태그를 갖는 키는 반드시 같은 슬롯에 포함됩니다. 가령 다음 키들은 모두 하나의 슬롯에 포함됩니다.

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

따라서 키를 여러 개 받는 스크립트를 실행하고자 한다면 해시 태그를 사용하면 됩니다.

여기서부터는 LINE GAME Platform을 개발하면서 실제로 Lua script를 활용한 사례를 소개하겠습니다.

Redis에서 Lua script를 활용한 사례 1: Atomic한 처리

앞서 살짝 언급한 소셜 그래프의 친구 데이터는 Redis에서 관리하고 있습니다. 중간중간 애플리케이션 서버에서 Kafka로 시그널이 전송되며, 이를 처리하는 작업 프로세스가 데이터를 연산해서 Redis에 저장합니다. 다음은 친구 목록을 작성하는 명령어 예제입니다.1

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

위 코드는 캐시를 지우고 Redis의 list 타입에 친구 목록을 추가한 다음, TTL 키를 설정합니다. 보신 바와 같죠. 어느 날, 몇몇 사용자의 친구 목록에 친구가 중복되어 있음이 밝혀졌습니다. 친구가 딱 두 배로 늘어나 있었기 때문에 RPUSH 명령어가 두 번 호출된 것이 아닌가 의심스러웠지요. 조사해 보니 문제가 발생한 사용자의 친구 목록 작성 요청이 정확히 동시에 서버에 두 건 전송된 것이 확인되었습니다. 저희가 이용 중인 Kafka 0.9.x대에는 ‘At least once’ 정책이 적용되어 한 개의 메시지가 두 번 전달될 수 있습니다. 또한 애초에 저희 플랫폼 안에 메시지 생성 트리거가 여럿 존재하다보니 이미 메시지가 중복으로 발송될 가능성이 높은 상태였습니다. 즉, 다음 예제와 같은 시퀀스가 얼마든지 발생할 수 있는 것이지요. 따라서 주어진 명령어들을 atomic하게 처리할 필요가 있었습니다.

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

Redis에서 서버로 여러 건의 처리 요청을 한꺼번에 보내는 방법은 다음과 같이 몇 가지 있습니다.

  • MSETMGET처럼 복수의 키를 조작하는 명령어를 사용한다.
  • Pipeline을 사용한다.
  • Transaction(MULTIEXEC 명령어)을 사용한다.
  • Lua script를 사용한다.

여러 개의 명령어를 통합하려면 첫 번째 방법을 제외한 나머지 세 가지 선택지 중에 고를 수 있는데, 이 중 pipeline 사용은 다른 선택지와 개념이 조금 다릅니다. 왜냐하면 pipeline을 이용하는 것은 어디까지나 대역폭 활용을 최적화하기 위함이기 때문입니다. Pipeline을 이용하면 서버 내부의 일련의 처리에서 atomicity는 보장되지 않습니다. 즉 여러 개의 명령어를 atomic하게 처리하려면 트랜잭션을 이용하거나 Lua script를 이용하는 방법 밖에 없습니다.

싱글 노드가 아닌 Redis Cluster를 사용하는 환경이라고 가정하고 클라이언트 관점에서 생각해 볼까요? Transaction(MULTIEXEC 명령어)을 사용한다고 합시다. 예를 들어 MULTI 명령어를 실행할 때, 변경하려는 키(key)가 어느 노드에 있는지 Redis 클라이언트는 판단할 수 없습니다.2 미리 transaction에 포함된 키를 Redis 클라이언트에 전달해서 노드를 연산해두면 판단이 가능할 수도 있겠지만, 리샤딩의 영향까지 고려하면 노드를 미리 연산하는 것은 구현하기가 어렵고 실제로 Jedis에는 이 구현체가 없습니다. 하지만 Lua script를 이용하면 앞서 설명한 것과 같이 명령어를 실행할 때 키를 명시적으로 부여받으므로 서버 측에서 노드 연산을 타겟 서버로 리다이렉션할 수 있습니다. 이에 저희는 Lua script를 택하기로 했습니다.

다음 코드는 Redis에서 명령어를 atomic하게 처리하는 예제입니다.

String script = "redis.call('del', KEYS[1]);" +
"redis.call('rpush', KEYS[1], unpack(ARGV, 2));" +
"redis.call('expire', KEYS[1], ARGV[1]);";
List 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);

eval() 함수로 전달하는 파라미터인 params의 첫 번째 값을 TTL 값으로 활용하고, 두 번째 파라미터 이후를 RPUSH 명령어의 인자로 이용합니다. 참고로 공식 문서에는 다음과 같이 적혀 있습니다. 앞으로는 클러스터가 보급되어 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 website

Redis에서 Lua script 활용하기 사례 2: Cache stampede 대책

애플리케이션단에서 데이터의 캐시를 만드는 방법은 여러 가지입니다. 일례로 사용자의 요청에 따라 캐시가 있으면 캐시를 이용하고, 캐시가 없으면 마스터 데이터를 참조하여 요청에 대한 응답을 반환하면서 동시에 캐시를 생성하는 방식을 생각해 봅시다. 동시 요청 수가 아주 많은 상황에서 캐시가 다 소진되면 마스터 데이터측의 I/O와 애플리케이션 측의 캐시 재연산용 CPU 리소스, 양쪽 모두에 갑자기 큰 부하가 걸릴 수 있습니다. 이를 막기 위한 방법이 몇 가지 알려져 있는데요3, Probablistic Early Recomputation(PER)도 그중 하나입니다. 이 방법을 Redis Cluster에서 구현한 사례를 살펴볼까 합니다.

PER는 원래 VLDB라는 국제 학술대회에서 발표된 방법인데, 인터넷에 관련 논문이 공개되어 있습니다. 쉽게 말해서 이 방식은 캐시 엔트리의 유효 기간이 만료되기 전에 요청이 마치 ‘자원봉사자’ 같은 역할을 해서 일정 확률로 캐시를 재연산하는 방식입니다. 비슷한 방식 중에 서로 다른 TTL을 갖는 동일 내용의 캐시를 준비하는 패턴도 있는데, PER는 용량을 1 엔트리만큼 절감할 수 있다는 장점이 있습니다. PER 알고리즘의 슈도코드(pseudocode)는 다음과 같습니다.

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의 Hash 타입에 데이터와 연산 시간을 저장하는 방법도 생각해 볼 수 있습니다. 이 방법을 사용한다면 HMSET 명령어와 HMGET 명령어를 사용하게 되겠지요.

LINE DEVELOPER DAY 2017에서 소개했던 새로운 LINE GAME Platform에서도 PER를 사용했습니다. PER를 성능 테스트에 도입한 결과, 캐시 소진 시 응답 시간이 약 세 배 개선되는 것을 확인할 수 있었습니다. (물론 응답 시간은 애플리케이션 작업 처리 부하 혹은 주 데이터베이스에서 불러오는 데이터의 크기 등에 따라 달라집니다.) 본 포스팅은 Redis Lua script를 어떻게 활용할 것인지에 주안점을 두고 있으므로 성능이 얼마나 좋아지는지에 대해서는 다음 기회에 설명해 드릴까 합니다.

글을 맺으며

이번 포스팅에서는 LINE GAME Platform을 개발하는 저희 팀의 실제 사례를 통해 Redis Cluster에서 어떻게 Lua script를 활용했는지 소개했습니다. Redis의 Lua script는 그 자체만으로도 의외로 다양한 활용이 가능한 기능입니다. 기타 기능 및 자세한 내용에 대해서는 Redis 공식 문서소스 코드를 참고하시기 바랍니다.

1: ‘친구 목록’이라고 하면 사용자가 직접 추가/변경/삭제하는 것처럼 들리겠지만, 이 글에서의 ‘친구 목록’은 LINE이나 Facebook 등 인증 서비스가 제공하는 API를 통해 얻은 목록 그 자체입니다. 따라서 저희 쪽에서는 diff를 연산하지 않는 한 Redis의 SET 타입으로 중복을 막는 대책은 세우기 어렵습니다.2: 일단 키를 포함하는 Hash 슬롯을 직접 구한 다음, CLUSTER NODES 명령어로 어느 노드가 어느 슬롯에 포함되는지 연산할 수는 있습니다.

3: 그 밖의 방법들과 각각의 장단점에 대해서는 RedisConf 2017에서 발표한 Preventing Cache Stampede with Redis and XFetch 세션에 잘 정리되어 있으니 참고해 보세요.

Related Post