Streams: a new general purpose data structure in Redis.

2017-10-02

스트림: Redis의 새로운 범용 자료구조

원문은 Salvatore Sanfilippo님이 2017-10-02에 게재했습니다. 이 블로그 구독하기

몇 달 전까지만 해도 스트림은 제게 메시징이라는 맥락에서 흥미롭고 비교적 단순한 개념 그 이상도 이하도 아니었습니다. Kafka가 이 개념을 대중화한 뒤, 저는 주로 Disque라는 메시지 큐에서의 활용 가능성을 살펴봤습니다. Disque는 이제 Redis 4.2 모듈로 전환될 예정인 메시지 큐입니다. 이후 저는 Disque가 본질적으로 AP 메시징, 즉 클라이언트의 큰 노력 없이도 내결함성과 전달 보장을 제공하는 데 초점이 맞춰져 있다는 점을 깨닫고, 스트림이라는 개념이 그 경우에는 그다지 잘 맞지 않는다고 판단했습니다.

하지만 동시에 Redis에는 기본으로 제공하는 자료구조에 대해 마음을 편하게 두지 못하게 하는 문제가 있었습니다. Redis 리스트, Sorted Set, 그리고 Pub/Sub 기능 사이에는 일종의 공백이 존재합니다. 이 도구들을 활용해 메시지나 이벤트의 연속을 모델링할 수는 있지만, 각각 다른 트레이드오프가 따릅니다. Sorted Set은 메모리를 많이 차지하고, 동일한 메시지가 반복해서 전달되는 상황을 자연스럽게 모델링할 수 없으며, 클라이언트가 새로운 메시지를 기다리며 블로킹할 수도 없습니다. Sorted Set은 순차적인 자료구조가 아니라 점수를 바꿔 요소를 이리저리 옮길 수 있는 집합이기 때문에, 시계열 같은 용도에는 잘 맞지 않는 것이 당연합니다. 리스트도 특정 사용 사례에서 비슷한 적용상의 제약을 만드는 다른 문제들을 안고 있습니다. 리스트 중간에 무엇이 있는지 탐색할 수 없는데, 그 경우 접근 시간이 선형이기 때문입니다. 게다가 팬아웃도 불가능하고, 리스트에 대한 블로킹 연산은 하나의 요소를 하나의 클라이언트에게만 전달합니다. 리스트에는 ‘이 요소부터 시작하는 것들을 달라’고 말할 수 있는 고정된 요소 식별자도 없었습니다. 일대다 워크로드에는 Pub/Sub이 있는데, 많은 경우 훌륭하지만 특정한 경우에는 fire-and-forget 방식을 원하지 않습니다. 히스토리를 유지하는 것이 중요한데, 이는 단순히 연결이 끊긴 뒤 메시지를 다시 가져오기 위해서만이 아니라, 시계열처럼 메시지 목록 자체를 범위 조회로 탐색하는 것이 매우 중요한 경우도 있기 때문입니다. ‘지난 10초 동안 내 온도 측정값은 어땠지?’ 같은 질문 말입니다.

위 문제들을 해결하기 위해 제가 시도한 방법은 Sorted Set과 리스트를 하나의 더 유연한 자료구조로 일반화하는 것이었지만, 설계 시도는 거의 항상 결과물이 기존 자료구조보다 훨씬 더 인위적으로 만들어지는 것으로 끝났습니다. Redis의 좋은 점 중 하나는 외부에 노출하는 자료구조가 ‘살바토레가 만든 이 API’라기보다 자연스러운 컴퓨터 과학 자료구조에 더 가깝다는 것입니다. 결국 저는 시도를 멈추고, ‘지금까지 제공할 수 있는 건 여기까지다. 나중에 Pub/Sub에 히스토리를 추가하거나 리스트 접근 패턴에 더 많은 유연성을 더할 수도 있겠지’라고 말했습니다. 하지만 컨퍼런스에서 사용자가 다가와 ‘Redis에서 시계열을 어떻게 모델링하면 좋을까요?’와 같은 질문을 할 때마다 얼굴이 창백해졌습니다.

기원

Redis 4.0에서 모듈이 도입된 뒤, 사용자들은 스스로 이 문제를 어떻게 해결할지 고민하기 시작했습니다. 그중 한 명인 Timothy Downs는 IRC를 통해 이렇게 메시지를 보내왔습니다.

<forkfork> 제가 만들려는 모듈은 트랜잭션 로그 스타일의 데이터 타입을 추가하는 겁니다 - 즉, 아주 많은 구독자가 Redis 메모리 증가 없이 Pub/Sub 같은 것을 할 수 있다는 의미죠
<forkfork> 구독자가 메시지 큐에서 자신의 위치를 유지하고, Redis가 각 컨슈머가 어디까지 읽었는지 관리하거나 구독자마다 메시지를 복제할 필요가 없는 방식입니다

이 아이디어가 제 상상력을 자극했습니다. 며칠 동안 곰곰이 생각해 보니, 바로 지금이 위의 모든 문제를 한 번에 해결할 수 있는 순간일지도 모른다는 생각이 들었습니다. 제가 필요했던 것은 ‘로그’라는 개념을 다시 상상하는 것이었습니다. 로그는 기본적인 프로그래밍 요소로, 누구나 익숙합니다. 그저 파일을 append 모드로 열어 어떤 형식으로든 데이터를 쓰는 것만큼 단순하기 때문입니다. 하지만 Redis의 자료구조는 추상적이어야 합니다. 자료구조들은 메모리에 있고, 우리가 RAM을 쓰는 이유는 게을러서가 아니라 몇 개의 포인터를 이용해 자료구조를 개념화하고 추상화함으로써 명백한 한계로부터 자유로워질 수 있게 만들기 때문입니다. 예를 들어 보통 로그에는 몇 가지 문제가 있습니다. 오프셋이 논리적이지 않고 실제 바이트 오프셋이라는 점입니다. 만약 우리가 항목이 삽입된 시간과 관련된 논리적 오프셋을 원한다면 어떨까요? 그러면 범위 조회를 공짜로 얻을 수 있습니다. 마찬가지로 로그는 가비지 컬렉션이 어려운 경우가 많습니다. append 전용 자료구조에서 오래된 요소를 어떻게 제거할 것인가? 우리의 이상적인 로그에서는 그냥 ‘최대 이만큼의 항목만 유지하고 싶다’고 말하면 오래된 것들이 사라지게 하면 됩니다. 그런 식입니다.

Timothy의 초기 아이디어에서 출발해 명세를 작성하려고 하는 동안, 저는 Redis Cluster의 일부 내부를 최적화하기 위해 사용하던 radix tree 구현을 작업하고 있었습니다. 이는 여전히 로그 범위 조회가 로그 시간에 가능하면서도 공간 효율성이 매우 높은 로그를 구현할 수 있는 기반을 제공했습니다. 동시에 저는 설계에 잘 어울릴 만한 다른 흥미로운 아이디어를 얻기 위해 Kafka Streams에 대해 읽기 시작했고, 그 결과 Kafka 컨슈머 그룹이라는 개념을 가져와 Redis와 인메모리 사용 사례에 맞게 다시 이상화했습니다. 하지만 명세는 수개월 동안 명세로만 남아 있다가, 어느 순간 이 새로운 Redis 기능에 대해 사람들과 이야기하며 모은 많은 힌트들을 반영하기 위해 거의 처음부터 다시 작성했습니다. 저는 Redis 스트림이 단순히 다른 종류의 이벤트나 메시징 애플리케이션뿐만 아니라 특히 시계열에 있어서도 아주 훌륭한 사용 사례가 되기를 바랐습니다.

코드를 작성해 보자

Redis Conf에서 돌아온 뒤 여름 동안 저는 ‘listpack’이라는 라이브러리를 구현하고 있었습니다. 이 라이브러리는 말하자면 ziplist.c의 후계자입니다. 즉, 단일 할당 안에 문자열 요소들의 리스트를 표현할 수 있는 자료구조입니다. 그저 매우 전문화된 직렬화 포맷일 뿐이며, 특이한 점은 오른쪽에서 왼쪽으로, 즉 역순으로도 파싱할 수 있다는 것입니다. 이는 모든 사용 사례에서 ziplist를 대체하기 위해 필요한 특성이었습니다.

radix tree와 listpack을 섞으면 공간 효율적이면서 동시에 인덱싱된, 즉 ID와 시간으로 랜덤 액세스가 가능한 로그를 쉽게 만들 수 있습니다. 이것이 준비되자 저는 스트림 자료구조를 구현하는 코드를 작성하기 시작했습니다. 아직 구현을 마무리하는 중이지만, 지금 시점에서 GitHub의 Redis ‘streams’ 브랜치에는 가지고 놀고 즐길 만한 충분한 기능이 들어 있습니다. API가 100% 최종이라고 주장하지는 않지만 두 가지 흥미로운 사실이 있습니다. 하나는 이 시점에서 컨슈머 그룹과 스트림을 조작하는 몇 가지 덜 중요한 명령어들만 빠져 있을 뿐, 큰 기능들은 이미 모두 구현되어 있다는 점입니다. 두 번째는 모든 것이 안정적으로 보이면 약 두 달 안에 스트림 관련 작업 전체를 4.0 브랜치로 백포트하기로 결정했다는 점입니다. 즉, Redis 사용자들은 스트림을 사용하기 위해 Redis 4.2까지 기다릴 필요가 없으며, 가능한 한 빨리 프로덕션에서 사용할 수 있게 된다는 뜻입니다. 이는 새로운 자료구조이기 때문에 거의 모든 코드 변경이 새로운 코드 안에 자체적으로 포함되어 있어 가능합니다. 예외는 블로킹 리스트 연산뿐인데, 스트림과 리스트의 블로킹 연산이 같은 코드를 공유하도록 코드가 리팩터링되었고, 이를 통해 Redis 내부가 크게 단순화되었습니다.

튜토리얼: Redis Streams에 오신 것을 환영합니다

어떤 면에서 스트림은 Redis 리스트의 슈퍼차지 버전이라고 생각할 수 있습니다. 스트림의 요소는 단순한 문자열 하나가 아니라 필드와 값으로 구성된 객체에 가깝습니다. 범위 조회가 가능하고 빠릅니다. 스트림의 각 항목은 논리적 오프셋인 ID를 갖습니다. 서로 다른 클라이언트들은 지정된 ID보다 큰 ID를 가진 요소들을 블로킹 방식으로 기다릴 수 있습니다. Redis 스트림의 핵심 명령어는 XADD입니다. 그렇다, 모든 Redis 스트림 명령어는 ‘X’로 시작합니다.

> XADD mystream * sensor-id 1234 temperature 10.5
1506871964177.0

XADD 명령어는 지정된 스트림 ‘mystream’에 지정된 항목을 새로운 요소로 추가합니다. 위 예제에서 항목은 sensor-id와 temperature라는 두 개의 필드를 갖지만, 같은 스트림 안의 각 항목은 서로 다른 필드를 가질 수도 있습니다. 같은 필드 이름을 사용하면 단순히 메모리 사용량이 더 좋아질 뿐입니다. 흥미로운 점은 필드 순서가 유지된다는 것이 보장된다는 점이기도 합니다. XADD는 방금 삽입된 항목의 ID를 반환하는데, 이는 세 번째 인자에 별표(*)를 넣어 ID를 자동 생성하도록 요청했기 때문입니다. 이는 거의 항상 원하는 방식이지만, 예를 들어 명령어를 슬레이브나 AOF 파일로 복제하기 위해 특정 ID를 강제로 지정하는 것도 가능합니다.

ID는 두 부분으로 구성됩니다. 밀리초 단위 시간과 시퀀스 번호입니다. 1506871964177은 밀리초 시간으로, 밀리초 해상도를 가진 Unix 시간일 뿐입니다. 점 뒤의 숫자 0은 시퀀스 번호로, 같은 밀리초 안에 추가된 항목들을 구분하기 위해 사용됩니다. 두 숫자 모두 64비트 unsigned 정수입니다. 즉, 심지어 같은 밀리초 안이라도 스트림에 원하는 만큼 항목을 추가할 수 있습니다. ID의 밀리초 부분은 ID를 생성하는 Redis 서버의 현재 로컬 시간과 스트림 안의 마지막 항목 중 더 큰 값을 사용해 얻습니다. 따라서 예를 들어 컴퓨터 시계가 뒤로 점프하더라도 ID는 계속 증가합니다. 어떤 면에서는 스트림 항목 ID를 전체 128비트 숫자로 생각할 수도 있습니다. 하지만 ID가 추가된 인스턴스의 로컬 시간과 상관관계가 있다는 사실은 밀리초 정밀도의 범위 조회를 공짜로 얻을 수 있다는 것을 의미합니다.

짐작할 수 있듯이, 두 항목을 아주 빠르게 추가하면 시퀀스 번호만 증가하게 됩니다. ‘빠른 삽입’을 MULTI/EXEC 블록으로 간단히 시뮬레이션할 수 있습니다.

> MULTI
OK
> XADD mystream * foo 10
QUEUED
> XADD mystream * bar 20
QUEUED
> EXEC
1) 1506872463535.0
2) 1506872463535.1

위 예제는 또한 사전에 어떤 스키마를 지정할 필요 없이 서로 다른 항목에 대해 서로 다른 필드를 어떻게 사용할 수 있는지도 보여줍니다. 하지만 실제로 일어나는 일은 각 블록(보통 50~150개 정도의 메시지를 담는다)의 첫 번째 메시지마다가 레퍼런스로 사용되고, 같은 필드를 가진 이후의 항목들은 ‘이 블록의 첫 번째 항목과 필드가 동일하다’는 플래그 하나로 압축된다는 것입니다. 따라서 연속된 메시지에 같은 필드를 사용하면, 시간이 지나 필드 집합이 서서히 바뀌더라도 실제로 많은 메모리를 절약할 수 있습니다.

스트림에서 데이터를 가져오는 방법은 두 가지가 있습니다. XRANGE 명령어로 구현된 범위 조회와 XREAD 명령어로 구현된 스트리밍입니다. XRANGE는 start부터 stop까지의 항목 범위를 양쪽 끝을 포함해 가져옵니다. 예를 들어 ID를 알고 있다면 단일 항목을 이렇게 가져올 수 있습니다.

> XRANGE mystream 1506871964177.0 1506871964177.0
1) 1) 1506871964177.0
   2) 1) "sensor-id"
      2) "1234"
      3) "temperature"
      4) "10.5"

하지만 최소 및 최대 ID를 나타내기 위해 특별한 시작 기호 ‘-’와 특별한 종료 기호 ‘+’를 사용할 수도 있습니다. 반환되는 항목 수를 제한하기 위해 COUNT 옵션을 사용하는 것도 가능합니다. 좀 더 복잡한 XRANGE 예제는 다음과 같습니다.

> XRANGE mystream - + COUNT 2
1) 1) 1506871964177.0
   2) 1) "sensor-id"
      2) "1234"
      3) "temperature"
      4) "10.5"
2) 1) 1506872463535.0
   2) 1) "foo"
      2) "10"

여기서는 ID 범위의 관점에서 생각하고 있지만, ID의 ‘시퀀스’ 부분을 생략할 수 있기 때문에 XRANGE를 사용해 특정 시간 범위에 있는 요소들의 범위를 가져올 수도 있습니다. 따라서 밀리초 단위의 시간만 지정하면 됩니다. 다음은 ‘Unix 시간 1506872463부터 시작하는 10개의 항목을 달라’는 의미입니다.

127.0.0.1:6379> XRANGE mystream 1506872463000 + COUNT 10
1) 1) 1506872463535.0
   2) 1) "foo"
      2) "10"
2) 1) 1506872463535.1
   2) 1) "bar"
      2) "20"

XRANGE에 대해 마지막으로 주목할 중요한 점은, 응답으로 ID를 받고 바로 다음 ID는 ID의 시퀀스 부분을 증가시키는 것만으로 쉽게 얻을 수 있기 때문에, XRANGE를 사용해 전체 스트림을 호출마다 지정된 수의 요소씩 점진적으로 순회할 수 있다는 점입니다. Redis의 *SCAN 계열 명령어가 애초에 순회를 위해 설계되지 않았음에도 Redis 자료구조를 순회할 수 있게 한 뒤, 저는 같은 실수를 반복하지 않으려 했습니다.

XREAD로 스트리밍하기: 새로운 데이터를 기다리며 블로킹하기

XRANGE는 ID나 시간으로 범위를 가져오거나 ID로 단일 요소를 가져오고 싶을 때 완벽합니다. 하지만 서로 다른 클라이언트들이 데이터가 도착하는 대로 스트림을 소비해야 하는 경우에는 이것만으로는 충분하지 않으며 일종의 폴링이 필요하게 됩니다(가끔씩 연결해 데이터를 가져오는 *특정* 애플리케이션에는 괜찮은 방법일 수도 있습니다).

XREAD 명령어는 스트림에서 가져온 마지막 항목의 ID를 지정하는 것만으로 여러 스트림에서 동시에 읽을 수 있도록 설계되었습니다. 게다가 데이터가 없을 경우 블로킹을 요청해 데이터가 도착하면 깨어나도록 할 수 있습니다. 블로킹 리스트 연산과 유사하지만, 여기서는 스트림에서 데이터가 소비되지 않으며 여러 클라이언트가 동시에 같은 데이터에 접근할 수 있습니다.

다음은 정석적인 XREAD 호출 예제입니다.

> XREAD BLOCK 5000 STREAMS mystream otherstream $ $

이는 ‘mystream’과 ‘otherstream’에서 데이터를 가져오라는 의미입니다. 사용 가능한 데이터가 없으면 타임아웃 5000밀리초 동안 클라이언트를 블로킹합니다. STREAMS 옵션 뒤에는 구독하려는 키와 우리가 가진 마지막 ID를 지정합니다. 하지만 특별한 ID인 ‘$’는 ‘지금 스트림에 있는 모든 요소를 이미 가지고 있다고 가정하고, 다음에 도착하는 요소부터 달라’는 의미입니다.

다른 클라이언트에서 다음 명령어를 보내면,

> XADD otherstream * message "Hi There"

XREAD 쪽에서는 다음과 같은 일이 일어납니다.

1) 1) "otherstream"
   2) 1) 1) 1506935385635.0
         2) 1) "message"
            2) "Hi There"

데이터를 받은 키와 함께 수신된 데이터를 얻게 됩니다. 다음 호출에서는 아마도 마지막으로 받은 메시지의 ID를 사용할 것입니다.

> XREAD BLOCK 5000 STREAMS mystream otherstream $ 1506935385635.0

이런 식으로 계속됩니다. 하지만 이 사용 패턴에서는 클라이언트가 (메시지 처리에 시간이 걸리거나 다른 이유로) 아주 긴 지연 후에 다시 연결될 수도 있다는 점에 유의해야 합니다. 그런 경우 그동안 많은 메시지가 쌓여 있을 수 있으므로, XREAD와 함께 항상 COUNT 옵션을 사용해 클라이언트가 메시지에 압도되지 않고 서버도 단일 클라이언트에 너무 많은 메시지를 서비스하느라 시간을 낭비하지 않도록 하는 것이 현명합니다.

Capped 스트림

지금까지는 좋습니다… 하지만 스트림은 어느 시점에서는 오래된 메시지를 제거해야 합니다. 다행히 이는 XADD 명령어의 MAXLEN 옵션으로 가능합니다.

> XADD mystream MAXLEN 1000000 * field1 value1 field2 value2

이는 기본적으로 스트림이 새로운 요소를 추가한 뒤 100만 개 이상의 메시지를 가지고 있는 것으로 확인되면, 길이가 다시 100만 개가 되도록 오래된 메시지를 제거하라는 의미입니다. 리스트에서 RPUSH + LTRIM을 사용하는 것과 같지만, 이번에는 이를 위한 내장 메커니즘이 있습니다. 하지만 위 방식은 새로운 메시지를 추가할 때마다 스트림의 반대쪽에서 메시지를 제거하는 데 필요한 작업 비용도 함께 부담해야 한다는 점에 유의해야 합니다. 이는 어느 정도 CPU를 소모하므로, MAXLEN의 개수 앞에 ‘~’ 기호를 사용해 *정확히* 100만 개의 메시지를 요구하는 것이 아니라 몇 개 더 많아도 크게 문제되지 않는다는 것을 지정할 수 있습니다.

> XADD mystream MAXLEN ~ 1000000 * foo bar

이렇게 하면 XADD는 전체 노드를 제거할 수 있을 때만 메시지를 제거합니다. 이를 통해 capped 스트림을 유지하는 비용이 일반 XADD와 비교해 거의 무료에 가깝게 됩니다.

컨슈머 그룹 (작업 중)

이것은 아직 Redis에 구현되지 않았지만 작업 중인 기능 중 첫 번째입니다. 또한 비록 여기서는 꽤 다른 방식으로 구현되었지만 Kafka에서 가장 명확하게 영감을 받은 아이디어이기도 합니다. 요점은 XREAD를 사용할 때 클라이언트가 ‘GROUP <name>’ 옵션도 추가할 수 있다는 것입니다. 그러면 같은 그룹에 속한 모든 클라이언트는 자동으로 *서로 다른* 메시지를 받게 됩니다. 물론 같은 스트림을 읽는 여러 그룹이 있을 수도 있는데, 그런 경우 모든 그룹은 스트림에 도착하는 동일한 메시지의 중복본을 받게 되지만, 각 그룹 내에서는 메시지가 반복되지 않습니다.

그룹에 대한 확장으로, 그룹을 지정할 때 ‘RETRY <milliseconds>’ 옵션을 지정할 수 있게 될 예정입니다. 이 경우 XACK로 처리가 확인되지 않은 메시지는 지정된 밀리초 후에 다시 전달됩니다. 이는 클라이언트가 메시지를 처리됨으로 표시할 별도의 수단이 없을 경우 메시지 전달에 어느 정도의 best-effort 신뢰성을 제공합니다. 이 부분 역시 작업 중입니다.

메모리 사용량과 저장/로딩 시간

Redis 스트림을 모델링하는 데 사용된 설계 덕분에 메모리 사용량은 현저히 낮습니다. 필드와 값의 수와 길이에 따라 다르지만, 단순한 메시지 기준으로 100MB당 수백만 개의 메시지를 저장할 수 있습니다. 게다가 포맷은 매우 최소한의 직렬화만 필요하도록 고안되었습니다. radix tree 노드로 저장되는 listpack 블록은 디스크와 메모리에서 동일한 표현을 가지므로 저장과 읽기가 매우 간단합니다. 예를 들어 Redis는 RDB 파일에서 500만 개 항목을 0.3초 만에 읽을 수 있습니다. 이는 스트림의 복제와 영속화를 매우 효율적으로 만듭니다.

중간의 항목 삭제도 허용할 계획입니다. 이는 부분적으로만 구현되어 있지만, 전략은 항목 플래그에서 항목을 삭제된 것으로 표시하고, 항목과 삭제된 항목 사이의 특정 비율에 도달하면 가비지를 수집하기 위해 블록을 다시 쓰고, 필요한 경우 단편화를 피하기 위해 인접한 다른 블록과 합치는 것입니다.

결론과 출시 예정

Redis 스트림은 연말 이전에 Redis 안정 버전의 4.0 시리즈에 포함될 예정입니다. 저는 이 범용 자료구조가 Redis가 커버하기 어려웠던 많은 사용 사례를 메우는 데 큰 패치가 될 것이라고 생각합니다. 즉, 기존 자료구조를 창의적으로 남용해 특정 문제를 해결해야 했던 경우를 말합니다. 매우 중요한 사용 사례 중 하나는 시계열이지만, TREAD를 통한 다른 사용 사례를 위한 메시지 스트리밍 또한 fire-and-forget보다 더 높은 신뢰성이 필요한 Pub/Sub 애플리케이션을 대체하는 용도로든, 완전히 새로운 사용 사례를 위한 용도로든 매우 흥미로울 것이라는 느낌이 듭니다. 지금 당장 여러분의 문제 맥락에서 새로운 기능을 평가해 보고 싶다면, GitHub에서 ‘streams’ 브랜치를 가져와 가지고 놀아보세요. 어쨌든 버그 리포트는 언제나 환영입니다 :-)

동영상을 좋아한다면, 스트림을 실시간으로 보여주는 세션은 여기에서 볼 수 있습니다: https://www.youtube.com/watch?v=ELDzy9lCFHQ