또한 아래와 같이 4,294,967개의 Data 객체가 137,438,944Byte를 점유하고 있는 것을 확인할 수 있었다.
Data 객체는 int형 필드 2개(4byte * 2 = 8byte)와 long형 필드 1개(8byte)에 부가적인 크기를 합쳐 32byte로 구성되고, 객체의 수가 4,294,957개이기 때문에 137,438,944byte(약 134MB)가 되는 것이다.
Bitmap Index로 접근하기
Index
위의 for loop를 통한 접근에서 사용한 Data 객체 리스트를 표로 표현해보면 아래와 같을 것이다.
위와 같은 구성에서 “Country Code가 2인 Row의 ID 값은 무엇인가?”라는 질문을 했을 때, 우리는 모든 Row를 순회하여 찾을 수 밖에 없다. 저장 시 데이터의 묶음인 Row 기준으로 저장했었기 때문이다.
발상을 바꾸어 “어떤 값을 가지는 데이터는 몇 번째 데이터이다”라는 방식으로 저장해보면 어떨까?
CountryCode 값에 따라 어떤 Row에 속해있는지를 저장해놓았다. “Country Code가 2인 Row ID의 값은 무엇인가?”라는 질문에 O(1)만에 응답할 수 있다.
이렇게 특정 컬럼의 값을 기준으로 자신이 속한 데이터의 위치를 저장해놓고 조회할 수 있도록 하는 방식을 인덱스(Index)라고 한다.
AND, OR 등의 연산
Index를 이용하여 특정 조건을 만족하는 데이터는 빠르게 찾을 수 있었다. 만일 조건이 1개가 아닌 여러개일 경우(AND, OR 등) 어떻게 처리해야 효율적으로 처리할 수 있을까?
가장 쉽게 생각할 수 있는 자료구조는 Set 일 것이다. AND 연산의 경우 두 Set의 교집합을 찾으면 되고, OR 연산의 경우 두 Set의 합집합을 찾으면 된다.
보다 쉽고 빠르게 처리하기 위해서는 비트 연산을 사용하면 된다. 위에서 A Set과 B Set의 데이터는 각각 \[1, 2, 3\]과 \[2, 3, 4\] 였다. 이를 4bit로 표현해보면 다음과 같다.
A Set: \[1, 1, 1, 0\]
B Set: \[0, 1, 1, 1\]
이를 다시 int 형 데이터의 하위 4bit로 표현해보면 각각 14와 7을 가지게 될 것이고, 이 숫자에 대해 AND와 OR 연산을 수행한 뒤의 하위 4bit가 결과로 표현될 것이다.
위의 Set을 통한 연산의 경우 54000 nano seconds가 소요되었지만, 아래 Bit 연산을 이용하면 570 nano seconds 밖에 소요되지 않았다.(결과를 Set에 넣는 것 제외)
그래서 Bitmap Index란?
Bitmap Index는 Bit를 통해 Index를 구성하는 방법으로 데이터를 빠르게 필터링하고, AND, OR 등의 비트 연산도 빠르게 수행할 수 있도록 한다.
위에서 Country Code를 기준으로 Index를 표현했던 그림을 Bitmap Index로 표현하면 아래와 같다.
Country Code 컬럼에 등장하는 모든 유일 값 별로 BitSet을 가지고 있고, 이 BitSet의 길이는 Row 수와 동일하다. Row 수가 200개이고 유일한 Country Code의 갯수가 10개인 경우 각 BitSet의 길이는 10이고, Country Code가 가진 모든 BitSet의 크기는 10 * 200 = 2000bit가 될 것이다. 8bit = 1byte이기 때문에 Country Code에 관련된 데이터를 표현하는데 250byte 밖에 사용하지 않는다.
Bitmap Index로 구현한 Filter
Java에는 BitSet이라는 자료구조가 존재한다. 이는 Bit로 구성된 Vector를 표현하는 자료구조이다. 이를 통해 Filter를 구현해보았다.
성능 측정
시간복잡도는 ForFilter와 동일하게 데이터의 입력은 O(1), 조회는 O(N)를 가질 것이다. 성능 테스트는 FilterTest의 IFilter 객체 초기화를 BitmapFilter로 바꾸어 수행하였다.
두 메서드에 대해 아래와 같은 결과를 얻어낼 수 있었다.
filterByCountryCode: 70 millisecond
filterByCountryAndCityOrCityCode: 140 millisecond
또한 아래와 같이 26개의 BitSet 객체가 754Byte를 점유하고 있는 것을 확인할 수 있었다.
다만 BitSet 내부적으로 long 타입의 배열로 Bit Word들을 유지하고 있기 때문에 각 BitSet 별로 1,048,600byte를 사용하고 있었기 때문에, 총 26개의 BitSet이 20,972,000byte의 공간을 점유하고 있는 것을 확인하였다.
정리
데이터의 필터와 AND, OR 등의 연산에 최적화 되어 있는 Bitmap Index에 대해서 살펴보았다.
Druid에서도 OnHeap 공간을 사용하는 Realtime Task에서는 BitSet 클래스를 Wrapping 하여 org.apache.druid.collections.bitmap.WrappedBitSetBitmap이라는 것을 구현해 사용하고 있다.
다만 더 많은 최적화(저장 공간 최적화, Off-Heap을 사용한 Bitmap 연산)를 수행하기 위해 Historical Node에서는 Off Heap 기반의 Concise Bitmap이나 Roaring Bitmap을 사용하고 있다.