Redis 비트맵

Redis 비트맵 (Bitmaps)

Redis의 데이터 타입을 이야기할 때 아주 자주 등장하는 게 비트맵이에요. 그런데 사실 비트맵은 독립된 데이터 타입이 아니라, String 타입을 '비트 벡터(bit vector)'처럼 다루는 비트 지향 연산들의 집합이라고 볼 수 있어요. 이 페이지에서는 비트맵이 뭔지, 언제 쓰면 좋은지, 그리고 어떤 명령들이 있는지를 옆에서 설명하듯 풀어드릴게요.

출처: Redis 공식 문서 — bitmaps

비트맵이란? (What are bitmaps)

비트맵은 실제 데이터 타입이 아니라, String 타입에 정의된 비트 지향 연산들의 집합이에요. String을 마치 비트 벡터처럼 취급하는 거죠. String은 바이너리 세이프(binary safe)한 블롭(blob)이고 최대 길이가 512MB이기 때문에, 최대 2^32개까지의 서로 다른 비트를 설정할 수 있어요.

하나 또는 여러 개의 String에 대해 비트 연산을 수행할 수 있어요. 비트맵의 대표적인 사용 사례로는 이런 것들이 있어요.

  • 집합의 멤버가 정수 0부터 N까지에 대응되는 경우, 효율적인 집합 표현
  • 객체 권한(permission) 표현 — 파일 시스템이 권한을 저장하는 것처럼, 각 비트가 하나의 특정 권한을 나타내는 방식

예시 (Example)

1000명의 자전거 선수가 경주를 하고 있는데, 자전거마다 0에서 999까지 번호가 붙은 센서가 있다고 가정해볼게요. 특정 센서가 지난 1시간 안에 트래킹 서버에 핑을 보냈는지(즉 라이더가 체크인했는지) 빠르게 확인하고 싶다고 해요.

이 상황을, 현재 시간(시간 단위)을 가리키는 키를 가진 비트맵으로 표현할 수 있어요.

  • 라이더 123이 2024년 1월 1일 00:00 시각에 서버에 핑을 보냈다고 해볼게요. 그러면 라이더 123이 그 시간에 핑을 보냈음을 확인할 수 있어요. 같은 시간에 라이더 456이 핑을 보냈는지도 확인할 수 있고요.

개별 비트 설정하고 조회하기 (SETBIT / GETBIT)

SETBIT와 GETBIT로 개별 비트를 설정하고 조회하며 이진 상태를 추적할 수 있어요.

> SETBIT pings:2024-01-01-00:00 123 1
(integer) 0
> GETBIT pings:2024-01-01-00:00 123
1
> GETBIT pings:2024-01-01-00:00 456
0

예를 들어 이 이진 상태를 추적해서 어떤 센서가 그 시간에 반응했는지 쉽게 알아낼 수 있죠.

비트 연산 (Bit Operations)

비트 연산은 크게 두 그룹으로 나뉘어요.

  1. 상수 시간(constant-time) 단일 비트 연산 — 비트를 1이나 0으로 설정하거나 그 값을 읽는 연산
  2. 비트 그룹 연산 — 예를 들어 특정 비트 범위에서 1로 설정된 비트의 개수를 세는 연산(population counting)

비트맵의 가장 큰 장점 중 하나는 정보를 저장할 때 극도의 공간 절약을 제공한다는 점이에요. 예를 들어 증가하는 사용자 ID로 서로 다른 사용자를 표현하는 시스템에서, 40억 명의 사용자에 대한 단일 비트 정보(예: 뉴스레터 수신 여부)를 단 512MB의 메모리만으로 저장할 수 있어요.

SETBIT 명령은 첫 번째 인자로 비트 번호를, 두 번째 인자로 설정할 값(1 또는 0)을 받아요. 명령은 주소가 가리키는 비트가 현재 String 길이를 벗어나면 String을 자동으로 확장해요.

GETBIT은 지정된 인덱스의 비트 값을 그대로 반환해요. 범위를 벗어난 비트(대상 키에 저장된 String 길이를 벗어난 비트를 주소로 지정하는 경우)는 항상 0으로 간주돼요.

비트 그룹에 대해 동작하는 명령은 세 가지가 있어요.

  1. BITOP — 서로 다른 String들 사이에서 비트 연산을 수행해요. 제공되는 연산자는 AND, OR, XOR, NOT, DIFF, DIFF1, ANDOR, ONE이에요.
  2. BITCOUNT — population counting을 수행해서 1로 설정된 비트의 개수를 보고해요.
  3. BITPOS — 지정된 값(0 또는 1)을 가진 첫 번째 비트를 찾아요.

BITPOS와 BITCOUNT는 모두 String 전체 길이 대신 바이트 범위에 대해 동작할 수 있어요. 이를 이용해 비트맵에 설정된 비트 수를 쉽게 확인할 수 있죠.

비트 수 세기 (BITCOUNT)

집합 크기(population count)가 필요할 때 BITCOUNT로 비트맵에서 1로 설정된 비트 수를 셀 수 있어요.

> BITCOUNT pings:2024-01-01-00:00
(integer) 1

예를 들어 웹사이트 사용자들의 일일 방문 최장 연속 기록(스트릭)을 알고 싶다고 해볼게요. 웹사이트를 공개한 날을 0으로 시작해서 날짜를 세고, 사용자가 웹사이트를 방문할 때마다 SETBIT로 비트를 설정해요. 비트 인덱스로는 현재 유닉스 시간을 가져와 초기 오프셋을 빼고, 하루의 초 수(보통 3600*24)로 나누면 돼요.

이렇게 하면 사용자마다 매일의 방문 정보를 담은 작은 String이 생겨요. BITCOUNT로 특정 사용자가 웹사이트를 방문한 날 수를 쉽게 구할 수 있고, BITPOS를 몇 번 호출하거나 비트맵을 클라이언트 쪽에서 가져와 분석하면 최장 연속 기록도 쉽게 계산할 수 있어요.

비트 연산 (Bitwise operations)

BITOP 명령은 두 개 이상의 소스 키에 대해 비트 연산을 수행하고, 그 결과를 대상 키(destination key)에 저장해요.

아래 예시들은 세 개의 키를 사용해 사용 가능한 연산을 보여줘요. A(비트 패턴 11011000), B(00011001), 그리고 C(01101100)를 사용해요.

비트를 왼쪽부터 0으로 시작해 번호를 매기면, 다음 SETBIT 명령들이 이 비트맵들을 만들어요.

> SETBIT A 0 1
(integer) 0
> SETBIT A 1 1
(integer) 0
> SETBIT A 3 1
(integer) 0
> SETBIT A 4 1
(integer) 0
> GET A
"\xd8"
# Hex value: 0xd8 = 0b11011000
> SETBIT B 3 1
(integer) 0
> SETBIT B 4 1
(integer) 0
> SETBIT B 7 1
(integer) 0
> GET B
"\x19"
# Hex value: 0x19 = 0b00011001
> SETBIT C 1 1
(integer) 0
> SETBIT C 2 1
(integer) 0
> SETBIT C 4 1
(integer) 0
> SETBIT C 5 1
(integer) 0
> GET C
"l"
# ASCII "l" = hex 0x6c = 0b01101100

비트 연산을 위한 준비로, SETBIT로 여러 개의 비트맵을 만들고 각 비트 패턴을 확인했어요.

ONE

ONE 연산은 정확히 하나의 소스 키에서만 1로 설정된 비트를 대상 키에 1로 설정해요.

> BITOP ONE R A B C
(integer) 1
> GET R
"\xa5"
# Hex value: 0xa5 = 0b10100101

ONE은 배타적 멤버십(exclusive membership)이 필요할 때, 정확히 하나의 비트맵에만 설정된 비트를 찾을 때 유용해요.

비트맵을 여러 키로 분할하기 (Split bitmaps into multiple keys)

비트맵은 여러 키로 분할하기가 아주 쉬워요. 예를 들어 데이터셋을 샤딩해야 하거나, 일반적으로 거대한 키를 다루는 것을 피하는 게 더 좋을 때 유용하죠. 모든 비트를 하나의 키에 설정하는 대신 비트맵을 여러 키에 나눠 저장하는 단순한 전략은, 키당 M개의 비트를 저장하고 bit-number/M으로 키 이름을 얻고, 키 안에서 주소를 지정할 N번째 비트는 bit-number MOD M으로 구하는 거예요.

성능 (Performance)

  • SETBIT와 GETBIT는 O(1)이에요.
  • BITOP는 O(n)인데, 여기서 n은 비교에 포함된 가장 긴 String의 길이를 뜻해요.

더 알아보기 (Learn more)