(논문) BtrBlocks - Efficient Columnar Compression for Data Lakes, SIGMOD 2023 (3. Scheme selection and compression)

본 글은 논문 BtrBlocks - Efficient Columnar Compression for Data Lakes (SIGMOD '23) 를 읽고 정리한 글입니다.

별도의 명시가 없는 한, 본 글의 모든 그림은 위 논문에서 가져왔습니다.

목차

• 1. Abstract, Intro
• 2. Background
• 3. Scheme selection and compression (현재 글)
• 4. Pseudodecimal encoding (BtrBlocks, SIGMOD 23)
• 5. Fast decompression
• 6. Evaluation
• 7. Related work and conclusion

3. Scheme Selection & Compression §

3.0. Overview §

Tip Section 3.0 Overview

• … 는 논문에는 없는 section 이고, 형식상 주인장이 끼워 넣은 것이다.

3.0.1 Scheme selection algorithms. §

• Data 에 맞는 compression scheme 을 고르는 알고리즘은 당연히 중요하다.
  • 각 compression scheme 은 대상으로 하는 자료형도 다르고, 어떤 data distribution 에 대해 효율적인지 등의 특성이 다르기 때문.
• 하지만 지금까지의 data format 들은 다소 정확하지 않은 방법으로 알고리즘을 선택해 왔다.
  • 가령 맨날 비교만 당하는 Parquet 의 경우에는, 문자열의 경우에는 무조건 Dictionary 을 사용하고 정수의 경우에는 무조건 Bit-packing 을 사용하는 등의 단순하고 static 한 방식을 사용했다.
    • 하지만 예상하듯이 이러한 방식은 데이터를 최대로 압축하지 못한다.
  • 다른 방식은 통계를 이용하는 것이다. 가령 Data Block 형식 의 경우에는 $min()$, $max()$, $unique()$ 정도의 통계 연산으로 세 알고리즘 (FOR, Dictionary, Single Value) 중 하나를 선택했다.
• 하지만 더 복잡한 encoding 방식까지 사용하기 위해서는, 더 범용적인 선택 알고리즘이 필요할 것이고, 이렇게 해야만 데이터를 더 꽉꽉 눌러담을 수 있을 것이다.

3.0.2. Challenges §

• 따라서 저자들은 올바른 scheme 을 선택하기 위한 방법으로 데이터에서 sample 을 추출하는 방식 (Sampling) 을 채택했다.
• 하지만 이 sample 을 추출하는 것은 생각보다 쉽지 않다; Compression scheme 과 관련된 데이터의 특성이 잘 드러나도록 sample 을 추출해야 하기 때문.
  • 가령 random 하게 값들을 추출하는 경우에는 연속된 값들이 추출되지 않아, RLE 를 사용할 수 있는지 없는지가 샘플을 통해서는 알 수 없다.
  • 또는 첫 $K$ 개의 값들을 샘플로 고르는 방식 또한 아주 편향된 샘플일 수 있기에 올바르지 않다.
• Scheme selection algorithm 을 개발하는 데에는 이 샘플 추출의 어려움 외에도 어떻게 Cascading 이 가능하게 할까 또한 난관이었다고 한다. 이것에 대해선 Section 3.2 에서 살펴보자.

3.0.3. Solution Overview §

• 기본적인 BtrBlock 의 sample-based selection 의 아이디어는 block 에 대해 sample 을 추출해 그것을 compression 하여 compression scheme 선택을 위한 힌트를 얻는 것이다.
• 다음과 같은 5단계를 반복적으로 수행하며 compression 을 진행한다고 한다.
  1. Block 에 대한 statistics 를 계산한다.
  2. 이 statistics 를 이용해, 몇가지 compression scheme 들을 걸러낸다.
  3. Sample 을 추출하고, 이 sample 에 대해 남은 compression scheme 을 적용해 compression ratio 을 확인한다.
  4. Sample 에 대해 compression ratio 가 가장 높은 놈을 이용해, 전체 block 에 대해 압축을 진행한다.
  5. 만일 압축의 결과가 cascading 이 가능하다면, (1) 으로 되돌아가 반복한다.

3.1. Estimating Compression Ratio with Samples §

3.1.1. Choosing samples. §

• 샘플을 추출하는 데에는 Spatial locality 와 “Unique 한 값들이 얼마나 포진해 있는지” 간에 trade-off 가 있다.
  • 즉, block 의 연속된 일부 구간을 추출한다면 이 “연속된 데이터의 특성” 을 더 잘 반영하는 반면, block 내에 흩뿌려져 있는 unique 한 값들은 추출될 가능성이 낮아진다.

Tip Spatial Locality 란?

• 논문에서 등장하는 Spatial Locality 는 cache replacement algorithm 에서의 그것과는 사뭇 다른 말이다.
• 여기서의 Spatial Locality 는 “연속된 데이터로 부터 알아낼 수 있는 특성” 정도로 이해하면 된다.
• 가령 위의 RLE 의 경우에는 어떤 값이 얼마나 연속적으로 등장하냐를 이용한 것이기 때문에, RLE 를 사용할 수 있는지 판단하기 위해서는 이 Spatial Locality 를 확인해야만 하는 것이다.

• 또한 그렇다고 샘플의 크기를 늘려버리게 되면, 샘플을 compression 하는 것에만 overhead 가 너무 커질 수도 있다.
• 따라서 BtrBlock 에서는 샘플의 크기를 작게 유지하면서 trade-off 를 절충하기 위해, “연속된 공간을 무작위로 추출하기” 의 방법을 사용한다.
• BtrBlock 에서 샘플을 추출하는 구체적인 방법은 다음과 같다:

• 일단 전체 block 을 몇개의 Partition 으로 나눈 후, 각 Partition 의 random offset 부터 일정 개수의 연속된 값들을 추출하고 합치는 식으로 샘플을 만든다.
  • 기본적으로는 6400 개의 entry 를 하나의 Partition 으로 묶어 총 10개의 Partition 을 만든다. (하나의 block 에는 64,000 개의 entry 가 들어가기 때문)
  • 그리고 각 Partition 에서는 64개의 연속된 entry 를 랜덤한 위치에서 추출한다.
  • 이렇게 해서 block 사이즈 대비 1/100 사이즈의 샘플이 완성된다.
• 이 방식이 진짜 좋을까? 이것에 관해서는 뒤의 evaluation 파트에서 설명될 것이다.

3.1.2. Estimating compression ratio. §

• 위에서 말한 것 처럼, 샘플을 추출하기 전에 우선 몇가지 통계를 내어 compression scheme 을 몇개 걸러낸다.
• 일단 여기서 구하는 통계는 대략 다음의 네가지 이다:
  1. 최소값
  2. 최대값
  3. Unique value 의 개수
  4. 평균 run length - 즉, 하나의 값이 연속적으로 등장하는 횟수의 평균
• 이 통계를 이용해 compression scheme 을 거르는 것은 그냥 heuristic 을 사용한다.
  • 가령, “평균 run length” 가 2 보다 작으면 RLE 는 후보에서 제외되고,
  • “Unique value 의 개수” 가 전체의 50% 을 넘으면 Frequency Encoding 이 제외된다.

3.1.3. Performance. §

• 이 방식이 효율적이려면 다음의 두 가지를 실제로 보여야 한다:
  1. 우선 이 방법이 lightweight 해야 한다.
  2. 또한 이 방법이 accurate 해야 한다 - 즉, 이 방법으로 예측한 compression scheme 이 실제로 다른 compression scheme 을 이용했을 때 보다 compression ratio 가 높아야 한다.
• Evaluation 결과, 전체 compression 과정 중 이 selection 과정은 1.2% 만의 비중을 차지했고, accuracy 도 높았다고 한다. 더 자세한 것은 뒤에서 확인하자.

3.2. Cascading §

3.2.1. Recursive application of schemes. §

• 한 scheme 을 적용하고 난 뒤에 어떤 scheme 을 적용할 수 있는가에 대한 decision tree 는 다음과 같다:

• 우선, 색깔이 중허다.
  • “녹색” 은 recursion step 을 뜻한다. 즉, output 으로 나온 leaf node 과 같은 자료형의 input (root node) 로 recursive 하게 처리될 수 있다는 것.
  • “파란색” 은 compression scheme 을 뜻한다. 이 scheme 을 고르는 것은 위에서 설명한 scheme selection 을 이용한다.
  • “회색” 은 recursion end 를 뜻한다. 이 node 에 대해서는 더 이상 recursion 이 불가능하다는 것.
• 그럼 recursion 진사 갈비를 무한으로 즐길 수 있느냐; 그렇지는 않다.
  • 최대 몇번까지 recursion 할지는 static configuration 으로 설정하게끔 되어 있고, 그 이후의 recursion 은 이루어지지 않는다.
  • 왜냐면 recursion 을 계속 하면 물론 ratio 는 높아지겠지만 compression 이 너무 오래걸리기 때문.
  • 기본값으로는 3번만 recursion 하도록 설정되어 있다.
• 각 recursion 을 거치면서 적용 순서 또한 저장을 해 decompression 에 사용될 수 있게끔 한다.

3.2.2. Cascading compression example. §

• 여기, 뭉게질 위기에 처한 실수 (double) 값이 있습니다.

[3.5, 3.5, 18, 18, 3.5, 3.5]

• 이때 scheme selection 에 의해 RLE 가 선택되었다고 가정해 보자.
• 그럼 다음과 같이 결과가 나올 것이다.
  • 첫번째 배열은 run value 이고, 두번째 배열은 run count 이다.

[3.5, 18, 3.5]
[2, 2, 2]

• 여기에 대해서는 또 scheme selection 를 돌려 value 에 대해서는 Dictionary 가 선택되고, count 에 대해서는 One Value 가 선택되었다고 해보자.
• 그럼 다음처럼 된다.
  • 첫번째는 dictionary index, 두번째는 dictionary, 세번째는 one value 이다.

[0, 1, 0]
[3.5, 18]
2

• 마지막 recursion 에서는 첫번째 배열에 FOR & Bit-packing 을 도입해서 첫번째 배열을 1bit 으로 표현하는 등의 작업을 거칠 수 있을 것이다.

3.2.3. Code example. §

• 위의 pseudocode 는 RLE 를 cascading 하는 예시이다.
• compress() 부터 따라가 보자.
  • 일단 res 는 결과를 저장하는 객체의 포인터이고, value 와 count 는 RLE 의 결과물이 저장되는 배열이다.
    • 여기서 value, count 는 알아서 적당히 RLE 로직을 통해 계산된다고 가정한다.
  • 그 다음에는 value 와 count 각각에 대해 pickScheme() 으로 scheme 을 정해서, 그것으로 전체 데이터를 재귀적으로 compress 하는것으로 마무리 된다.
• 이때, pickScheme 은 다음처럼 작동한다:
  • pool 은 가능한 전체 scheme 들이 담겨있는 곳이고, 여기를 iterate 하며 각각의 scheme 에 대해 estimateRatio() 로 compression ratio 를 계산한다.
  • 그리고 ratio 가 가장 큰 scheme 을 반환하게 된다.
• 마지막으로, 이 estimateRatio() 는 다음과 같다:
  • 일단 인자로 받은 stat 으로 해당 scheme 을 사용할 수 있는지 확인한다.
    • 위 코드에서는 RLE 이기 때문에 average run length 가 2 이상인지 확인하는 heuristic 으로 검사한다.
  • 위 확인작업이 끝나면, sample 에 대해 compression 하여 compression ratio 를 계산해 반환한다.

3.2.4. The encoding scheme pool. §

• Section 3.2.1 에 소개한 scheme pool 은 public BI dataset 을 이용해 선택되었다고 한다.
• 다음의 과정을 거쳐서 선택되었다:
  1. BI dataset 에서 compression ratio 가 (Bzip2 와 같은) 무거운 scheme ¹ 에 비해 더 안좋은 column 을 찾는다.
  2. 해당 column 의 데이터들의 특성을 분석한다.
  3. 해당 특성과 잘 맞는 compression scheme 을 도입하고
  4. Compression ratio 가 높지 않거나 decompression overhead 가 큰 scheme 은 제외한다.
• 위와 같은 과정을 통해 multi-level cascading 이 가능하고 확장성이 좋은 scheme pool 을 만들수 있었다고 한다.
• 이 pool 에 들어갈 scheme 을 고르는 것은 BtrBlock 성능 전체에 영향을 미치기에, 아주 중요하다.
  • 가령 scheme 을 pool 에 너무 많이 추가하면 sample evaluation 에 너무나 많은 시간이 소요되지만 compression ratio 는 늘어나는 장단점이 있고,
  • Compression ratio 가 높지만 decompression overhead 가 큰 scheme 의 경우에도 마찬가지의 장단점이 있기 때문.

Footnotes §

1. 여기 “무거운 (heavyweight)” 이 어떤 측면에서 말하는 것인지는 확실하지 않다. 만약 compression ratio 가 일반적으로 낮은 scheme 을 지칭하는 것이라면 일리가 있으나 decompression overhead 가 안좋은 것을 지칭하는 것이라면 decompression overhead 와 compression ratio 모두 좋은 scheme 을 새로 찾아야 하는 것인데, 쉽지는 않았을 듯. 근데 문맥상으로 보면 후자인 것 같다. ↩