GoSuda

Mapa de bits animado

By snowmerak
views ...

비트맵이란?

여기서 비트맵은 인덱스의 한 종류입니다. 그래픽스 생각하고 들어오셨다면 뒤로가기 누르시면 됩니다.

기본 개념

비트맵은 데이터베이스의 인덱싱 기술의 한 형태입니다. 특정 칼럼의 값을 비트 배열이나 벡터의 한 원소나 형태로 표현하여, 각 비트가 해당 칼럼의 특정 값이 존재하는지 여부를 나타냅니다. 그래서 가장 기본적인 형태는 각 row에 대해 비트 인덱스를 할당하고 존재 여부를 0과 1로 표현하는 것입니다.

예를 들어, 성별 칼럼이 있는 테이블이 있다고 가정해봅시다. 이 테이블에 5개의 row가 있고, 성별 칼럼의 값이 다음과 같다고 합시다:

  1. 남성
  2. 여성
  3. 남성
  4. 여성
  5. 기타

이 경우, 성별 칼럼에 대한 비트맵 인덱스는 다음과 같이 표현될 수 있습니다:

  • 남성: 10100
  • 여성: 01010
  • 기타: 00001

그래서 진짜 어디다가 쓰냐면

그래서 단순히 저걸 나타내기 위한 것이 아니라고 다들 생각할 것입니다. 비트맵 인덱스를 제대로 사용해보기 위해 다음 경우를 고려해봅시다.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

이 테이블에 1,000,000개의 row가 있다고 가정해봅시다. 그리고 다음과 같은 쿼리를 실행한다고 합시다.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

이 쿼리는 active와 sex 칼럼이 모두 TRUE인 row를 찾습니다. 그러면 가장 빠르게 두 칼럼이 TRUE인 조건을 성립하는 row를 찾는 방법으로 bit and 연산을 활용할 수 있을 것입니다.

  • active 칼럼에 대한 비트맵 인덱스가 1100110011... (1,000,000개 비트 배열)이 미리 인덱싱 되어 있고,
  • sex 칼럼에 대한 비트맵 인덱스가 1010101010... (1,000,000개 비트 배열)이 미리 인덱싱 되어 있다고 합시다.

그러면 두 비트맵 인덱스에 대해 bit and 연산을 수행하여, 두 칼럼이 모두 TRUE인 row를 빠르게 찾을 수 있습니다. 단순 비트 연산이기 때문에 다른 인덱스 스캔보다 훨씬 빠르게 결과를 얻을 수 있을 것입니다.

트레이드 오프

비트맵 인덱스는 매우 효율적일 수 있지만, 몇 가지 트레이드 오프가 있습니다. 다른 단점이 많지만 지금은 하나만 짚고 넘어가겠습니다.

바로 비트맵 인덱스는 낮은 카디널리티(즉, 칼럼에 가능한 값의 수가 적은 경우)에 더 적합합니다. 높은 카디널리티의 칼럼에 비트맵 인덱스를 사용하면 비트맵이 매우 커질 수 있습니다.

높은 카디널리티의 칼럼에 비트맵 인덱스를 사용하면, 각 고유 값에 대해 별도의 비트맵을 생성해야 하므로, 저장 공간이 많이 필요할 수 있습니다. 예를 들어, 만약 칼럼에 1,000,000개의 고유 값이 있다면, 1,000,000개의 비트맵을 생성해야 하므로, 이는 매우 비효율적일 수 있습니다.

그래서 우리는

높은 카디널리티에서 오는 비트맵을 대체하여 Roaring Bitmap이라는 것을 사용할 수 있습니다. Roaring Bitmap은 여러가지 특성이 있지만, 가장 큰 기반 철학과 특성은 데이터의 밀도에 따라 가장 적합한 저장 방식을 동적으로 선택하여 압축률과 연산 속도 모두 극대화하는 것입니다.

Roaring Bitmap의 기본 개념

2단계 인덱싱

Roaring Bitmap은 정수 하나를 저장하기 위해 먼저 다음 2단계를 거칩니다. 말이 2단계 인덱싱이지, 그냥 2차원 배열이라고 생각하시면 됩니다.

  • 상위 16비트 추출: 정수의 상위 16비트를 추출하여, 이를 인덱스로 사용합니다. 총 65536만큼의 길이를 가진 2차원 배열 중 바깥 배열의 인덱스가 되는 것입니다. 이 배열은 후술할 컨테이너의 주소를 저장합니다.
  • 하위 16비트 추출: 정수의 하위 16비트를 추출하여, 이를 컨테이너 내에서의 위치로 사용합니다.

컨테이너

이 컨테이너는 방금 비유했던 대로 2차원 배열 중 안쪽 배열에 해당합니다. 하지만 상위 16비트의 그것과는 다르게, 이 컨테이너는 내부 데이터가 얼마나 있냐에 따라 내부 구조가 달라집니다. Roaring Bitmap은 다음 3가지 컨테이너를 지원합니다.

  • Array Container: 이 컨테이너는 내부에 저장된 데이터가 적을 때 사용됩니다. 구체적으로, 4096개 이하의 원소를 저장할 때 사용됩니다. 이 컨테iner는 단순히 정렬된 정수 배열로 구현되어 있습니다. 이진 탐색 하여 원소를 찾을 수 있습니다.
  • Bitmap Container: 이 컨테이너는 내부에 저장된 데이터가 많을 때 사용됩니다. 구체적으로, 4096개 초과의 원소를 저장할 때 사용됩니다. 이 컨테이너는 65536비트(8192바이트)의 비트맵으로 구현되어 있습니다. 각 비트는 해당 위치의 정수가 존재하는지 여부를 나타냅니다.
  • Run Container: 이 컨테이너는 연속된 정수 범위를 저장할 때 사용됩니다. 예를 들어, 1, 2, 3, 4, 5와 같은 연속된 정수들을 저장할 때 효율적입니다. 이 컨테이너는 (시작 값, 길이) 쌍의 리스트로 구현되어 있습니다. 만약 다 있으면? 그냥 처음부터 끝까지 다 있다는 뜻이니, (0, 65536) 하나만 저장하면 됩니다.

이러한 방식은 Roaring Bitmap이 매우 효율적으로 메모리를 사용하고, 다양한 데이터 밀도에 대해 최적의 성능을 제공할 수 있게 합니다.

Roaring Bitmap의 기능

기본 기능

Roaring Bitmap은 다음과 같은 기본 기능을 제공합니다.

  • 삽입: 새로운 정수를 비트맵에 추가합니다. 이 과정에서 적절한 컨테이너를 선택하거나, 필요에 따라 컨테이너를 변환할 수 있습니다.
  • 삭제: 기존 정수를 비트맵에서 제거합니다. 이 과정에서도 컨테이너의 상태에 따라 적절한 처리가 이루어집니다.
  • 검색: 특정 정수가 비트맵에 존재하는지 여부를 확인합니다. 이 과정은 매우 빠르게 수행됩니다.

집합 연산

Roaring Bitmap은 또한 다음과 같은 집합 연산을 지원합니다.

  • 합집합 (Union): 두 비트맵의 모든 원소를 포함하는 새로운 비트맵을 생성합니다.
  • 교집합 (Intersection): 두 비트맵에 모두 존재하는 원소만을 포함하는 새로운 비트맵을 생성합니다.
  • 대칭 차집합 (Symmetric Difference): 두 비트맵 중 하나에만 존재하는 원소를 포함하는 새로운 비트맵을 생성합니다.

이러한 연산들은 비트맵의 컨테이너 유형에 따라 최적화되어 매우 빠르게 수행됩니다.

Go 언어에서

Go 언어에서는 github.com/RoaringBitmap/roaring 패키지를 사용하여 Roaring Bitmap을 쉽게 활용할 수 있습니다. 이 패키지는 Roaring Bitmap의 모든 기능을 제공하며, Go 언어의 특성에 맞게 최적화되어 있습니다.

설치

1go get github.com/RoaringBitmap/roaring/v2

사용 예시

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Inicializa con 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializa con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Añade 5
14	b2.Add(10) // Añade 10
15
16	b2.Remove(12) // Elimina 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Las operaciones de Bitmap modifican el original, así que se usa un clon
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

위 예시 코드에서 나오지 않은 주요 기능들로

  • Contains(x uint32) bool: Verifica si un valor específico existe en el Bitmap.
  • GetCardinality() uint64: Retorna el número de elementos contenidos en el Bitmap.
  • Rank(x uint32) uint64: Retorna el número de elementos menores o iguales a un valor específico.
  • ToBytes() ([]byte, error): Serializa el Bitmap a un slice de bytes.
  • FromBytes(data []byte) error: Restaura el Bitmap desde un slice de bytes.
  • Clone() *Bitmap: Crea un clon del Bitmap.
  • Clear(): Inicializa el Bitmap.
  • NextValue(x uint32) int64: Retorna el siguiente elemento mayor o igual a x.
  • PreviousValue(x uint32) int64: Retorna el elemento anterior menor o igual a x.
  • Maximum() uint32: Retorna el elemento más grande en el Bitmap.
  • Minimum() uint32: Retorna el elemento más pequeño en el Bitmap.

이런 기능들이 있습니다. 자세한 내용은 공식 문서를 참고하세요.

참고로 roaring 패키지는 내부에 uint32 뿐만 아니라 uint64를 지원하는 패키지를 포함하고 있습니다. 거의 동일한 인터페이스를 제공함으로 바로 교체하여 사용할 수 있습니다.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Inicializa con 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializa con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Añade 5
14	b2.Add(10) // Añade 10
15
16	b2.Remove(12) // Elimina 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Las operaciones de Bitmap modifican el original, así que se usa un clon
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

마치며

Roaring Bitmap은 높은 카디널리티의 정수 집합을 효율적으로 저장하고 조작할 수 있는 강력한 도구입니다. Go 언어에서 github.com/RoaringBitmap/roaring 패키지를 사용하면, Roaring Bitmap의 모든 기능을 쉽게 활용할 수 있습니다. 이 패키지는 다양한 컨테이너 유형과 최적화된 연산을 통해, 메모리 사용량과 성능을 극대화합니다. 데이터베이스 인덱싱, 로그 분석, 통계 계산 등 다양한 분야에서 Roaring Bitmap을 활용하여 효율적인 데이터 처리를 구현할 수 있습니다.

Roaring Bitmap은 특히 대규모 데이터셋에서 높은 성능을 발휘하며, 다양한 응용 프로그램에서 유용하게 사용될 수 있습니다. Go 언어의 간결하고 효율적인 문법과 결합하여, Roaring Bitmap은 개발자들에게 강력한 도구를 제공합니다. 앞으로도 Roaring Bitmap의 발전과 함께, 더 많은 기능과 최적화가 이루어질 것으로 기대됩니다.

전 이걸 왜 했냐구요? 시계열 데이터베이스에서 각 태그 별 인덱싱과 빠른 합집합 연산을 위해서요.