Redis 비트맵

Redis 비트맵 (bitmaps)

비트맵은 사실 별도의 데이터 타입이 아니라, String 타입 위에서 동작하는 비트 기반 연산 모음이에요. String을 하나의 비트 벡터처럼 다룬다고 생각하면 돼요. 오늘은 비트맵이 뭔지, 언제 쓰면 좋은지, 비트 연산 명령어들은 어떻게 쓰는지 함께 살펴볼게요.

출처: Redis 공식 문서 — bitmaps

비트맵 소개 (Introduction)

비트맵은 실제 데이터 타입이 아니라, String 타입을 비트 벡터처럼 취급하는 비트 중심 연산들의 집합이에요. String은 이진 안전(binary safe)한 blob이고 최대 길이가 512 MB이기 때문에, 최대 2^32개의 서로 다른 비트를 표현할 수 있어요.

하나 이상의 String에 대해 비트 연산(bitwise operation)을 수행할 수 있어요. 비트맵의 대표적인 사용 사례 몇 가지를 볼게요:

  • 집합의 원소가 정수 0-N에 대응되는 경우, 집합을 효율적으로 표현할 때
  • 각 비트가 특정 권한을 나타내는 객체 권한(object permissions) 관리 — 파일 시스템이 권한을 저장하는 방식과 비슷하죠.

예시 (Example)

1000명의 사이클 선수가 경기 중이고, 자전거에는 0-999로 라벨이 붙은 센서가 있다고 상상해볼게요. 특정 센서가 지난 1시간 안에 추적 서버에 신호(ping)를 보냈는지 빠르게 확인하고 싶어요.

이 시나리오를 현재 시간을 키(key)로 하는 비트맵으로 표현할 수 있어요. 예를 들어 라이더 123이 2024년 1월 1일 00:00 시간대에 서버에 신호를 보냈다면, 이렇게 확인할 수 있어요:

> 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
  • SETBIT으로 라이더 123의 비트를 1로 설정했고,
  • GETBIT으로 라이더 123은 신호를 보냈는지(1), 라이더 456은 아직 신호를 안 보냈는지(0)를 바로 확인했어요.

관련 명령어

  • SETBIT — 비트 설정
  • GETBIT — 비트 값 조회

비트 연산 (Bit Operations)

비트 연산은 두 그룹으로 나눠져요:

  1. 상수 시간 단일 비트 연산 — 비트를 1 또는 0으로 설정하거나 값을 가져오는 연산
  2. 비트 그룹 연산 — 예를 들어 특정 범위에서 1로 설정된 비트의 수를 세는 연산(모집단 세기, population counting)

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

단일 비트 연산

  • SETBIT — 첫 번째 인자는 비트 번호, 두 번째 인자는 설정할 값(1 또는 0)이에요. 주소를 지정한 비트가 현재 String 길이를 벗어나면 명령어가 String을 자동으로 확장해요.
  • GETBIT — 지정한 인덱스의 비트 값을 반환해요. 범위를 벗어난 비트(대상 키에 저장된 String 길이를 초과하는 비트)는 항상 0으로 간주돼요.

비트 그룹 연산 (3가지 명령)

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

BITPOS와 BITCOUNT 둘 다 String의 전체 길이 대신 바이트 범위로 연산할 수 있어요.

예를 들어 웹사이트 사용자의 최장 연속 방문 일수(스트릭)를 알고 싶다고 해볼게요. 웹사이트 공개일을 0일차로 세고, 사용자가 방문할 때마다 SETBIT으로 비트를 1로 설정해요. 비트 인덱스는 현재 unix time에서 초기 오프셋을 빼고 하루의 초 수(보통 3600*24)로 나눠서 구해요.

이렇게 하면 사용자마다 매일의 방문 정보를 담은 작은 String이 생겨요. BITCOUNT로 특정 사용자가 방문한 총 일수를 쉽게 구할 수 있고, 몇 번의 BITPOS 호출 또는 클라이언트에서 비트맵을 직접 분석해서 최장 스트릭도 쉽게 계산할 수 있어요.

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

비트 단위 연산 (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

AND

대상 키의 비트를 모든 소스 키에서 1로 설정된 경우에만 1로 설정해요.

> BITOP AND R A B C
(integer) 1
> GET R
"\b"
# ASCII "\b" (backspace) = hex 0x08 = 0b00001000

OR

대상 키의 비트를 소스 키 중 적어도 하나에서 1로 설정된 경우 1로 설정해요.

> BITOP OR R A B C
(integer) 1
> GET R
"\xfd"
# Hex value: 0xfd = 0b11111101

XOR

두 개의 소스 키에 대해, 대상 키의 비트를 두 키에서 값이 서로 다른 경우 1로 설정해요. 세 개 이상의 소스 키에서는 처음 두 키를 XOR한 결과를 다음 키와 다시 XOR하는 식으로 이어져요.

> BITOP XOR R A B
(integer) 1
> GET R
"\xc1"
# Hex value: 0xc1 = 0b11000001

NOT

대상 키의 비트를 소스 키에서 1로 설정되지 않은 경우 1로 설정해요 (이것이 유일한 단항 연산자예요).

> BITOP NOT R A
(integer) 1
> GET R
"'"
# ASCII "'" (single quote) = hex 0x27 = 0b00100111

DIFF

대상 키의 비트를 첫 번째 소스 키에서는 1로 설정되어 있지만, 다른 소스 키 중 어디에도 설정되지 않은 경우 1로 설정해요.

> BITOP DIFF R A B C
(integer) 1
> GET R
"\x80"
# Hex value: 0x80 = 0b10000000

DIFF1

대상 키의 비트를 첫 번째 소스 키에서는 설정되지 않았지만, 다른 소스 키 중 적어도 하나에서는 1로 설정된 경우 1로 설정해요.

> BITOP DIFF1 R A B C
(integer) 1
> GET R
"%"
# ASCII "%" (percent) = hex 0x25 = 0b00100101

ANDOR

대상 키의 비트를 첫 번째 소스 키에서 1로 설정되어 있고, 또한 다른 소스 키 중 적어도 하나에서도 1로 설정된 경우 1로 설정해요.

> BITOP ANDOR R A B C
(integer) 1
> GET R
"X"
# ASCII "X" = hex 0x58 = 0b01011000

ONE

대상 키의 비트를 소스 키 중 정확히 하나에서만 1로 설정된 경우 1로 설정해요.

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

비트맵을 여러 키로 나누기 (Split bitmaps into multiple keys)

비트맵은 여러 키로 나누기가 매우 간단해요. 예를 들어 데이터셋을 샤딩하기 위해서나, 일반적으로 지나치게 큰 키를 피하는 게 좋기 때문이에요. 모든 비트를 하나의 키에 설정하는 대신 비트맵을 서로 다른 키로 나누는 간단한 전략은, 키당 M 비트를 저장하고 비트번호 / M으로 키 이름을, 비트번호 MOD M으로 키 안에서 주소를 지정할 N번째 비트를 구하는 거예요.

성능 (Performance)

  • SETBIT와 GETBIT는 O(1) 이에요.
  • BITOP는 O(n) 이에요. 여기서 n은 비교하는 가장 긴 String의 길이예요.

더 알아보기 (Learn more)