Redis의 Bitmap
Redis의 Bitmap
Bitmap
Bitmap이란 기존의 String 자료구조를 비트 단위로 다루는 방식을 말한다.
String은 binary-safe하다. 텍스트, 이미지 파일 등 전부 바이트의 나열로 저장한다. 예를 들어 Redis에 SET key 'A'를 수행하면, 메모리에는 0100 0001이 저장된다. ‘A’의 아스키 코드값이 65이기 때문이다. Bitmap의 명령을 사용하면 8개의 비트 중 하나를 지정하여 수정할 수 있게 된다.
Bitmap은 오직 0과 1만 저장 가능한 거대한 비트 배열이라고 생각하면 된다. offset은 Bitmap(비트 배열)의 인덱스로, 주로 사용자 ID와 같은 정수형 식별자를 사용한다. value는 해당 offset의 상태를 말한다.
Bitmap의 가장 큰 장점은 메모리 효율적이라는 것이다.
천만 명의 사용자의 방문 여부를 관리하는 상황을 가정해보자. 사용자의 상태를 Java의 HashMap또는 Redis의 Set을 사용한다면, 사용자 한 명를 저장하는 데 대략 4 ~ 8 바이트가 필요하게 되며, 추가로 포인터와 같은 오버헤드가 발생한다. 사용자 당 4바이트로 잡아도 대략 40MB가 필요하다.
그러나 Bitmap을 사용하면 사용자 당 1비트만 필요하므로 대략 1.2MB만 있어도 충분하다.
String의 최대 크기는 512MB이다. 이를 비트로 환산하면 약 42억 비트가 나오게 되는데, 이는 곧 Bitmap이 커버할 수 있는 ID의 수이다.
내부 구조 및 동작 원리
Bitmap이라는 별도의 구조체가 존재하는 것이 아니라, String에 비트 단위 연산 기능을 제공하는 것이다. 내부적으로 Redis의 문자열 구조체인 SDS(Simple Dynamic String을 사용한다.
SDS는 데이터의 길이를 별도로 저장한다. 0과 1로 이루어진 데이터를 저장하기 좋은 구조이다.
또한 SDS는 가변 길이 배열처럼 동작한다. 필요 시 배열의 크기를 확장하며 비어있는 비트는 0으로 채운다.
Redis는 어떻게 사용자가 요청한 offset을 찾을까? Bitmap은 Big Endian 방식으로, 왼쪽에서 오른쪽으로 비트 번호를 매긴다. Byte 0은 offset 0부터 7비트, Byte 1은 offset 8부터 15, .. 이런 방식이다.
또한 바이트 내부에서도 MSB가 가장 작은 offset이다. 10000000에서 0번 비트의 값이 1인 것이다.
명령어
SETBIT
SETBIT key offset value
SETBIT은 offset의 비트를 value(0 또는 1)로 설정하는 명령이다. key는 데이터를 저장할 키이다. 리턴값은 해당 비트의 변경 전 원래 비트 값이다.
offset을 8로 나눈 몫이 바이트가 되며, offset을 8로 나눈 나머지가 비트가 된다.
위치를 찾았으니 접근해야 한다. 배열 특성 상 데이터들이 메모리 상에 연속적으로 붙어 있으므로, 시작 주소에 바이트 크기를 더함으로써 접근할 수 있다. 바이트 크기는 중요하지 않다. 똑같이 한 번의 메모리 접근이다.
이후 바이트를 CPU로 가져온 후, OR 또는 AND 비트 연산을 통해 비트를 수정한다.
이 모든 과정은 $O(1)$에 수행 가능하다.
GETBIT
GETBIT key offset
GETBIT은 offset의 비트 값이 0인지 1인지 조회하는 명령이다.
key가 존재하지 않거나 offset이 현재 문자열의 길이보다 긴 경우 0을 리턴한다.
SETBIT와 같은 메커니즘으로 비트 값을 조회하며, $O(1)$이다.
단일 비트 값이 궁금한 경우 GETBIT를 사용하는 것이 좋다. GET을 통해 애플리케이션 레벨에서 비트 연산을 수행하는 경우 큰 크기의 Bitmap을 가져와야 하고, 메모리에 로드하고 비트를 찾는 과정에서 네트워크, 메모리, CPU 낭비가 발생한다.
BITCOUNT
BITCOUNT key [start end [BYTE | BIT]]
BITCOUNT 명령은 값이 1로 설정된 비트의 총 개수를 세는 명령이다.
start와 end는 개수를 셀 범위이며, BYTE와 BIT는 그 범위를 바이트 단위로 할지, 비트 단위로 할지 결정하는 옵션이다. 기본 단위는 바이트이다. 음수 인덱스가 가능하다.
Redis 7.0부터 비트 단위가 추가되었다.
시간복잡도는 $O(N)$이나, 비트를 하나씩 세는 방식이 아니기 때문에 실제로는 더 빠른 속도를 가진다.
1바이트(8비트)는 0부터 255까지 표현 가능하며, 경우의 수가 256개이다. 따라서 미리 룩업 테이블을 만들어 256개의 수에 대해 1의 개수를 기록한다(e.g. table[255] = 8). 단순 메모리 참조로 개수를 셀 수 있는 것이다.
또한 하나의 레지스터 안에서 병렬 처리하여 1의 개수를 구한다. 이 방식을 SWAR(SIMD within a Register)라고 한다. 분할 정복의 원리를 사용한다.
CPU의 64비트 레지스터를 8개의 8비트의 묶음이라고 간주한 후, 미리 정의된 마스킹된 숫자를 사용하여 인접한 비트끼리 2비트, 4비트, 8비트 단위로 점진적으로 합친다. 이후 최종 곱셈으로 각 바이트에 흩어진 1의 개수들을 상위 비트로 모으며, 몇 개의 비트 연산으로 64비트 안의 1의 개수를 구할 수 있다.
최신 CPU의 경우 비트를 세기 위핸 명령인 POPCNT가 존재한다. POPCNT는 SWAR같은 알고리즘을 수행하는 것이 아니라 CPU에서 1의 개수를 세는 명령만 내린다. CPU는 내부 게이트 회로를 통해 1 클럭 사이클만에 64비트 정수의 비트 수를 세어 전달한다. 이 방법이 물리적으로 가장 빠른 방법이다.
따라서 Redis는 먼저 현재 CPU가 POPCNT를 지원하는지 확인하고, 지원하면 POPCNT 방식을 사용한다. 데이터를 64비트 단위로 한 번에 로드하기 위해 메모리 주소가 8의 배수가 될 때까지 앞부분의 바이트는 룩업 테이블로 처리한다. 이후 정렬이 되었디면 8바이트 단위로 읽어 POPCNT 명령 또는 SWAR 알고리즘을 수행한다. 반복 횟수가 바이트 기준 기존의 $1/8$ 수준으로 줄어든다. 이후 남은 뒷부분 바이트들은 다시 룩업 테이블로 처리한다.
BITPOS
BITPOS key bit [start [end [BYTE | BIT]]]
BITPOS는 특정 비트 값이 처음으로 등장하는 offset을 찾는 명령이다. bit는 찾으려는 비트 값, start와 end는 검색할 범위, BYTE 또는 BIT는 범위의 단위이다.
찾으려는 비트가 1이냐 0이냐에 따라 동작이 다르다.
1을 찾을 때, 찾았다면 해당 비트의 offset, 찾지 못했다면 -1을 리턴한다.
0을 찾을 때 찾았다면 해당 비트의 offset, 찾지 못했다면 현재 문자열 길이의 바로 다음 비트 offset을 리턴한다. Bitmap은 끝없이 0으로 채워져 있다고 가정하기 때문에 모든 비트가 1이라도 그 문자열이 끝나는 지점 바로 다음은 0으로 간주한다. 만약 범위를 지정하여 0을 찾는 경우는 찾지 못했다면 -1을 리턴한다.
시간복잡도는 $O(N)$이나, BITCOUNT와 마찬가지로 비트를 하나씩 확인하지 않는다. 만약 1을 찾는 경우 0x00인 바이트, 0을 찾는 경우 0xFF인 바이트는 통째로 건너뛴다.
또한 CPU가 한 번에 8바이트씩 비교하며 빠르게 찾는다. CPU 입장에서는 1비트를 읽나, 8바이트를 읽나 비용은 동일하다. 메모리와 CPU를 연결하는 데이터 버스는 64비트이므로, 한 번 메모리에 접근하는 김에 64비트를 가져오는 것이 이득이다.
Redis는 1인 비트를 찾을 때 64개의 비트를 하나씩 확인하는 것이 아니라 하나의 거대한 정수로 보고 판단한다. 메모리에서 8바이트 데이터를 한 번에 가져온 후, 0과 같은지 비교한다. 만약 같다면 1이 하나도 없다는 의미이므로 다음 8바이트 데이터를 가져오고, 그렇지 않다면 값이 1인 비트가 적어도 하나 존재한다는 의미이므로 64비트 내부를 살펴본다.
0을 찾는 경우는 반대로 동작한다. 8바이트 데이터가 1과 같은지를 살펴본다.
BITOP
BITOP operation destkey key [key ...]
BITOP 은 Bitmap key를 대상으로 비트 논리 연산을 수행하고 그 결과를 새로운 destkey에 저장하는 명령이다.
operation은 AND, OR, XOR, NOT과 같은 연산자이다.
리턴값은 destkey에 저장된 문자열의 총 길이이다. 가장 긴 입력 문자열의 길이와 같다.
만약 key마다 문자열의 길이가 다르면 어떻게 처리할까? 입력된 key들 중 가장 긴 문자열의 길이에 맞춰 계산한다. 길이가 짧은 key들은 부족한 뒷부분을 모두 0으로 채운 것으로 간주하고 연산한다.
시간복잡도는 $O(N)$으로, $N$은 가장 긴 문자열의 길이이다. 길이가 긴 key들을 연산하면 결과를 저장할 메모리 공간을 확보해야 하고, 각 key들을 CPU에 가져오고, 연산하는 과정에서 많은 메모리 사용이 발생하기 때문에 주의해야 한다.
BITFIELD
BITFIELD key [GET type offset] [SET type offset value] [INCRBY type offset increment] [OVERFLOW strategy]
BITFIELD 는 문자열을 사용자가 정의한 크기의 정수 배열로 다루도록 하는 명령이다.
SET 명령은 8바이트 정수를 저장할 수 있는데, 작은 수를 저장하는 경우 메모리 낭비가 발생한다. SETBIT는 1비트만 저장하므로 숫자를 표현하기엔 너무 작다. BITFIELD는 메모리를 필요한 비트 수만큼 잘라서 사용할 수 있다.
type은 데이터 타입과 비트 크기, value는 저장할 값, increment는 더할 값이다.
type으로 비트를 몇 개 묶을 것인지, 부호를 고려할 것인지를 결정한다. i는 signed integer, u는 unsigned integer이다. 묶을 비트 수는 부호 기호 옆에 위치한다. 예를 들어 i8은 8비트 signed integer, u4는 4비트 unsigned integer를 의미한다.
offset 지정 방식은 두 가지가 있다. 비트 단위 offset을 직접 지정하거나 #을 붙여 몇 번째 정수인지를 지정할 수 있다.
일반적인 offset으로 비트 위치를 지정할 수 있고, 배열 인덱스를 사용할 수도 있다. 배열 인덱스를 사용하는 경우 앞에 # 기호를 붙인다. 예를 들어 u8 8은 8번 비트부터 8개를 의미하며, u8 #1는 1번째 8비트 정수를 의미한다.
가능한 하위 명령으로는 SET, GET, INCRBY가 있다.
SET은 특정 위치에 값을 덮어쓴 후 기존 값을 리턴한다.
GET은 특정 위치의 값을 읽어온다.
INCRBY는 값을 증가시키거나 감소시킨다.
C언어 등에서는 수가 변수 표현 범위를 넘어서면 의도치 않은 값으로 변하지만, BIRFIELD는 오버플로우가 발생했을 때 어떻게 처리할지 정할 수 있다.
가능한 옵션은 WRAP, SAT, FAIL이 있다.
WRAP은 기본값으로, 범위를 넘어가면 한 바퀴 돈다. 즉, 일반적인 정수 오버플로우가 발생했을 때 설정되는 값과 동일하다.
SAT은 범위를 넘어가는 경우 최댓값/최솟값에서 멈춘다.
FAIL은 오버플로우가 발생하면 연산을 수행하지 않고 nil을 리턴한다.
시간복잡도는 $O(N)$으로, $N$은 하위 명령의 수이다. 작은 숫자들을 저장하는 경우 JSON 또는 Hash보다 훨씬 적은 메모리를 사용한다.
주의사항
Bitmap은 논리적으로는 비트의 집합이지만 물리적으로는 연속된 바이트 배열이다. 배열 특성 상 중간을 비워두고 양끝만 저장할 수 없다.
예를 들어 ID가 0, 100000000인 사용자의 기록만 저장하는 경우, 두 명의 정보를 저장하기 위해 1억 개의 공간을 물리적으로 확보해야 한다. 나머지 비트들은 전부 0으로 채워진다. 불필요한 공간이 발생할 수 있다.
이는 Roaring Bitmap 등을 통해 해결할 수 있다. 0이 반복되는 구간을 저장하지 않는 방식이다. 또는 거대한 Bitmap 하나를 쓰는 대신 작은 BItmap 여러 개로 쪼개서 관리하기도 한다.
Bitmap에서 offset은 0 이상의 정수여야 하는데, ID가 UUID나 이메일같은 형식이라면 이러한 문자열을 배열의 offset으로 사용할 수 없다. 이 경우 ID를 정수로 매핑하는 과정이 필요하다. 정확도가 중요하지 않다면 해시 함수를 사용하기도 한다(단, 충돌이 발생할 수 있다).