문제
수억개 이상의 row와 수천개의 dimension이 있다고 가정.
주어진 조건을 만족하는 (rule-match) 가장 빠른 자료구조는 어떤게 있을까?
Bitset
BitSet은 Bit들로 이루어진 vector로, boolean 배열처럼 이용할 수 있다. boolean 배열에 비해 갖는 이점은 boolean 값은 1byte를 잡아먹지만 bit는 말그대로 1bit다. 한 값당 7bit씩 아낄 수 있다.
10개의 row가 있다고 가정
G:Male 1010000010
Age:15-19 0110000000위와 같은 Bitset으로 0번, 2번, 8번 row가 남성인 데이터를 표현할 수 있다. (Bitmap Index)
Set & Get
import java.util.BitSet;
public class Test {
public static void main(String[] args) {
BitSet b = new BitSet();
b.set(10);
b.set(100);
System.out.println(b.get(10)); // true
System.out.println(b.get(100)); // true
System.out.println(b.get(0)); // false
}
}10번째, 100번째 인덱스 값의 bit를 true로 설정하고, get을 이용해 그 값들을 가져온 것. 추가적으로 boolean값을 주면 false로도 설정이 가능하다.
Flip
import java.util.BitSet;
public class Test {
public static void main(String[] args) {
BitSet b = new BitSet();
b.set(2);
System.out.println(b.get(2)); // true
b.flip(2);
System.out.println(b.get(2)); // false }
}flip. 말그대로 뒤집기
RoaringBitmap
RoaringBitmap은 압축된 bitset이다. Bitset을 활용할 수 있는 상황이라면 압축으로 이점을 얻을 수 있도록 RoaringBitmap을 사용하는 것이 효과적이다.
- RAM과 디스크에서 더 적은 공간을 사용한다.
- 이는 곧 memory locality와 cache efficiency를 통해 빠른 연산을 가능하게 한다.
Apache Spark, Apache Hive, Lucene, Druid 등 많은 곳에서 bitmap index를 구현하기 위해 사용하고 있다.
압축 메커니즘: Prefix Compression
Tree 최상위에 있는 배열에 각 value의 상위 16비트가 저장되어 있을 것이고 하위 16비트는 동일한 상위 16비트에 해당하는 range의 모든 값을 저장하는 container에 저장되어 있다. ( ex) 11, 12, 13, 14, 15 → RunConatiner 11, 4)
각 16 bit range가 다양한 density와 clustering characteristic를 가질 수 있다는 인식하에, 8KB 미만의 세 종류 container가 있다.
- Sparse:
ArrayContainer- 16bit 값 + 16bit cardinality의 정렬된 array. 4096보다 작은 element 수 대상. ⇒ 배열
- Dense:
BitmapContainer-Bitset처럼long[], 값마다 1bit + 16bit cardinality. 4096보다 큰 element 수 대상. ⇒ Bitmap
- Really dense, or clustered:
RunContainer- 16비트 값의 정렬된 배열. 각 짝수 값은 세트 비트 실행의 시작이고 각 홀수 값은 실행 길이. 공간을 절약할 때마다 변환된다. ⇒ RLE를 생각하면 된다
70,000에서 130,000 사이의 integer 집합이 있다고 가정해보자. 이를 BitSet에 저장하면 offset 기반이므로 0~70000까지 값이 모두 0임에도 저장해야한다. 이는 이 집합을 저장하기 위해 최대 16KB가 필요함을 의미하는데, RoaringBitmap에선 트리의 최상위 레벨에 있는 배열의 상위 16비트에 대한 값 1을 저장하고 데이터에 따라 컨테이너 하나와 추가로 일부 개체 참조에 대한 오버헤드 정도를 저장하면 된다.
- 겨우 2개의 값만 있다면,
ArrayContainer. cardinality를 위해 4 바이트, 값을 위해 4 바이트, 그리고 상위 비트와 object reference를 위해 위해 최상위에 2바이트가 필요
- 5000개의 값이 범위내에 골고루 퍼져 있다면,
BitmapContainerCardinality를 위해 4 바이트, long 배열을 위해 8KB, 그리고 상위 level과 object reference를 위해 2바이트가 필요
- 2개의 연속된 값의 배열이 있다면,
RunContainer. 연속된 값 배열의 갯수 위해 4 바이트, 연속된 값 배열을 저장하기 위해 8 바이트, 그리고 상위 level과 object reference를 위해 2바이트.
위 모든 케이스에서 Bitset보다 이기지만 꼭 모든 data set에서 그렇지만은 않다는 걸 명심하자.
ex) 모든 홀수를 저장한다고 하면, 각 16 bit range에서 2의 15승 개의 값을 저장해야하고, RLE는 도움이 되지 않으니까 8KB의 BitmapContainer가 필요해지는데, higher bits와 cardinality, object reference가 필요하므로 더 큰 공간이 필요해진다.
참고
Uploaded by Notion2Tistory v1.1.0