데이터 압축을 위한 Gorilla 알고리즘 적용 사례: 사내 솔루션 개발기 및 회고

데이터의 양이 기하급수적으로 많은 IT 환경에서, 효율적인 데이터 관리와 저장은 중요한 과제로 떠오르고 있다.

특히 대규모 시계열 데이터를 다루는 경우, 데이터의 저장 공간을 최적화하고 전송 속도를 향상시키는 것이 핵심 과제이다.

 

이번 포스팅에서는 사내 평가 데이터 테이블을 특정 인덱스로 조회한 뒤, 칼럼별로 정리된 리스트 데이터를 효율적으로 압축할 수 있는 솔루션을 개발한 경험을 공유하고자 하는 목적이 있다.

이 솔루션은 gorilla 알고리즘을 활용해 Time, Timestamp 데이터와 부동소수점 데이터를 효과적으로 압축하여, 데이터의 효율적인 관리와 조회 속도를 개선하는 것을 목표로 하고 있으며 평가 데이터 테이블을 특정 인덱스로 조회하여 List형태로 가공하고, 이를 특정 알고리즘을 사용하여 효율적으로 압축(+적재) 또는 (조회+)복원하는 솔루션이다.

 

Gorilla 알고리즘에 대한 설명은 이전 포스팅에 자세하게 작성해 두었다.(아래 링크)

https://wn1331.tistory.com/274

시계열 데이터의 압축 - Gorilla Algorithm(고릴라 알고리즘)

 

 

List 형태로 가공하는 이유는, 특정 평가와 사이클을 기준으로 압축해야 하기 때문이다. 충방전 IoT장비에서 나오는 시계열 데이터들은 여러 평가ID와 여러 사이클들이 혼합해서 나타나므로, 이에 대한 압축 기준이 명확히 존재해야 하기 때문에, List에 따로 담아 일괄 압축을 진행하는 방식으로 설계하였다.

 

복원 방법은 압축 로직에서 역산하면 되므로 굳이 포스팅에 첨부하지는 않겠다. 다만, 복원 시 문제점이 한개 있는데 바로 비트 끝처리 문제이다. 이 포스팅의 세번째 문단에서 그 부분에 대해 서술하겠다.

 

 

Gorilla - 시계열 압축

 

먼저 Gorilla 알고리즘의 시계열 압축 알고리즘 구현부는 아래와 같다.

 

    public static <T extends Date> byte[] compressTimeCore(List<T> items,
        ToLongFunction<T> timestampExtractor) {
        if (items == null || items.isEmpty()) {
            return new byte[0];
        }

        BitWriter writer = new BitWriter();

        long prevTimestamp = timestampExtractor.applyAsLong(items.get(0));
        writer.writeBits(prevTimestamp, 64);

        long prevDelta = 0;
        for (int i = 1; i < items.size(); i++) {
            long timestamp = timestampExtractor.applyAsLong(items.get(i));
            long delta = timestamp - prevTimestamp;
            long deltaOfDelta = delta - prevDelta;

            if (deltaOfDelta == 0) {
                writer.writeBits(DELTAD_1_MASK, 1);
            } else if (deltaOfDelta >= -63 && deltaOfDelta <= Long.SIZE) {
                writer.writeBits(DELTAD_7_MASK, 2);
                writer.writeBits(deltaOfDelta & 0x7F, 7);
            } else if (deltaOfDelta >= -255 && deltaOfDelta <= 256) {
                writer.writeBits(DELTAD_9_MASK, 3);
                writer.writeBits(deltaOfDelta & 0x1FF, 9);
            } else if (deltaOfDelta >= -2047 && deltaOfDelta <= 2048) {
                writer.writeBits(DELTAD_12_MASK, 4);
                writer.writeBits(deltaOfDelta & 0xFFF, 12);
            } else {
                writer.writeBits(DELTAD_32_MASK, 4);
                writer.writeBits(deltaOfDelta & 0xFFFFFFFFL, 32);
            }
            prevTimestamp = timestamp;
            prevDelta = delta;
        }
        return writer.getBytes();
    }

 

먼저, 첫 번째 파라미터의 리스트는 Date타입을 상속받는(Time,Timestamp) 타입의 리스트를 받는다.

그리고 두 번째 파라미터는 고차함수를 사용하여 Long타입의 데이터를 반환하는 함수(applyAsLong)를 받는다.

고차함수를 사용해서 위와같이 구현한 이유는, Time 타입의 데이터와 Timestamp타입의 데이터를 메서드 한개로 유연하게 사용가능하도록 하기 위해서이다. (개발하면서 처음 써보았다. 익숙해지면 좋을것 같다)

 

위 메서드를 사용하려면 아래처럼 코드를 작성하면 된다.

    public static byte[] compressTime(List<Time> times) {
        return compressTimeCore(times, Time::getTime);
    }
    
    public static byte[] compressTimestamp(List<Timestamp> timestamps) {
        return compressTimeCore(timestamps, Timestamp::getTime);
    }

자칫하면 싱크홀 안티패턴으로 사용되므로 실제 사용될 때는 compressTimeCore만 호출해주면 되겠다.

 

이렇게 받은 파라미터들로 압축을 수행하는데, 먼저 리스트가 빈값이라면 텅빈 바이트 배열을 리턴하고, 리스트의 첫 번째 값을 Long타입으로 가져온다. 가져온 첫 번째 값은 압축의 기준이 되는 첫번째 값이 된다.

이때부터 변화량으로 DeltaofDelta를 구해 그 값으로 분기처리가 되어 특정 컨트롤비트(MASK값에 정의)를 덧붙이고 압축을 수행하는 것이다.

 

주요 핵심 개념

1. Delta of Delta 기법

2. 분기처리에 의한 컨트롤비트 추가

3. 고차함수(함수가 파라미터에 들어감)

4. 비트연산

Gorilla -Value 압축

평가 데이터 중 가장 많은 부분을 차지하는 (64비트 배정밀도) 부동소수점 데이터를 압축하는데, 이에 대한 부분에서 설계에 문제점이 많았다. 

알고리즘별로 압축률과 속도 성능 테스트를 해보았을때, 자바 내장 압축 알고리즘 중 ZIP 알고리즘이 더 압축률 퍼포먼스가 좋게 나오는 것이 문제였다.

이에 대한 부분에서는, 속도 측면에서 갖고가는 이점이 매우 많을것으로 판단 되어 결국 Gorilla-value 알고리즘을 택한 것이다.

압축률은 ZIP에 비해 저조하지만 엄청난 속도 성능

 

 

Gorilla-value압축의 코드는 아래와 같다.

    public static byte[] compressDoubleValue(List<Double> values) {
        int storedLeadingZeros = Integer.MAX_VALUE;
        int storedTrailingZeros = 0;
        LongValuePredictor longValuePredictor = new LongValuePredictor();
        BitWriter writer = new BitWriter();
        long firstLongValue = doubleToLongBits(values.get(0));
        longValuePredictor.update(firstLongValue);
        writer.writeBits(firstLongValue, Long.SIZE);
        for (int i = 1; i < values.size(); i++) {
            long value = doubleToLongBits(values.get(i));
            long xor = longValuePredictor.predict() ^ value;
            longValuePredictor.update(value);
            if (xor == 0) {
                writer.writeZero();
            } else {
                int leadingZeros = Long.numberOfLeadingZeros(xor);
                int trailingZeros = Long.numberOfTrailingZeros(xor);
                writer.writeOne();
                if (leadingZeros >= storedLeadingZeros && trailingZeros >= storedTrailingZeros) {
                    writer.writeZero();
                    int significantBits = Long.SIZE - storedLeadingZeros - storedTrailingZeros;
                    xor >>>= storedTrailingZeros;
                    writer.writeBits(xor, significantBits);
                } else {
                    writer.writeOne();
                    int significantBits = Long.SIZE - leadingZeros - trailingZeros;
                    writer.writeBits(leadingZeros, 6);
                    writer.writeBits(significantBits - 1L, 6);
                    writer.writeBits(xor >>> trailingZeros, significantBits);
                    storedLeadingZeros = leadingZeros;
                    storedTrailingZeros = trailingZeros;
                }
            }
        }
        return writer.getBytes();
    }

 

먼저, storedLeadingZeros, storedTrailingZeros는 이전 값의 XOR결과의 선행, 후행0비트의 개수이다. 이걸 저장해야 비트 범위를 구해낼 수 있다. 

LongValuePredictor는 다음 예상 값을 추정하고 추적하는 클래스인데, 단순하게 이전 값 자체를 저장해두었다고 생각하면 된다. 이걸 앞으로 예측기라고 부르겠다.

 

초기 값은 리스트의 첫 번째 부동소수점 실수값을 long값으로 변환하여 적재한다. 그리고 예측기의 값을 업데이트한다.

이렇게 초기값은 그대로 64비트로 bitWriter에 적재한다.

 

리스트의 두번째 값부터는 반복문으로 아래와 같이 수행한다.

1. 현재 값을 long으로 변환하고 예측기의 값과 XOR연산을 수행한다. (XOR연산하는 이유는 이전 포스팅을 참고)

2. 예측기를 현재 값으로 업데이트한다.

3. xor가 0이면, 현재 값이 예측기의 값과 같다는 뜻이므로 비트 '0'을 기록한다.

4. 그렇지 않으면 xor의 선행 0비트의 개수(leadingZeros)와 후행 0비트의 개수(trailingZeros)를 계산한다.

 

이후로, 비트의 범위에 따른 컨트롤비트를 붙여 비트에 쓰기작업을 수행한다.

 

주요 핵심 개념

1. XOR Based Delta Coding

2. Predictor pattern

3. 비트연산

 

 

비트 끝처리 문제?!

데이터를 압축한 결과 즉, 바이트 배열을 다시 복원할 때, 끝처리 문제가 나타나는 것을 발견했다. 

데이터를 압축했다 하면, 가장 마지막 바이트가 적재될 때 8바이트 단위로 끊어지지 않으면 8바이트로 만들기 위해 모든 비트를 뒤에서 0으로 채운다.

 

 

 

위 코드는 내가 작성한 BitWriter라는 비트연산(쓰기) 클래스이다.

이렇게 바이트를 만들어 바이트배열로 적재하기 때문에 끝처리이슈가 나타나는 현상이 생겼다.

    /**
     * 작성된 비트를 바이트 배열로 반환한다. 스트림에 남아 있는 비트가 있다면, 0으로 채워서 바이트 경계를 맞춘다.
     * <br>이 메서드에 관련하여 Gorilla 압축 사용 시 이슈가 있다(해결함). 자세한 내용은
     * {@link orgcdc.algorithm.gorilla.value.GorillaValueCompressor}에서 서술됨.
     *
     * @return 작성된 비트들의 바이트 배열
     */

    public byte[] getBytes() {
        while (readBitsCount != 0) {
            writeZero();
        }
        return out.toByteArray();
    }

 

위처럼 남은 비트들이 0으로 채워지면, Gorilla 알고리즘 특성상, 0이라는 데이터는 "이전값과 값이 일치하다" 라는 방식으로 복원 시 해석될 수 있다. 

 

예를 들면 Double의 리스트가 {0.1, 0.100001, 0.100002}라고 되어있다고 가정하자. 

압축했을 때의 마지막 바이트에서 비트들이 1, 0, 1로 끝났다고 생각해보자.

하나의 바이트를 만들기 위해서 1, 0, 1, 0, 0, 0, 0, 0로 바이트 배열이 완성되어 적재된다는 것이다.

그러면 이렇게 추가된 5개의 0비트들은 이전값과 같다고 코드에서 판단되어 복원 시 아래와 같은 결과값들이 나타나게 될 것이다.

 

    @Test
    @Order(7)
    @DisplayName("[테스트예제]")
    void testExample() {
        List<Double> originalList = Arrays.asList(0.1, 0.100001, 0.100002);

        // 연산 중 마지막 바이트의 비트들이 1,0,1로 끝나는 경우 마지막 바이트의 8비트는 1,0,1,0,0,0,0,0이 된다.
        byte[] compressed = compressDoubleValue(originalList);

        List<Double> decompressed = decompressDoubleValue(compressed);

        System.out.println(decompressed);

        // 출력 결과값은 [0.1, 0.100001, 0.100002, 0.100002, 0.100002, 0.100002, 0.100002, 0.100002] 가 된다.
    }

 

 

이에 대한 해결책으로는, 압축 시 DB에 저장될 때 압축한 row개수를 같이 저장하는 것이다. 

 

그리하여, 복원 메서드를 수행했을 때 파라미터에 해당 데이터의 원본 row 개수만큼 복원을 수행하면 해결된다.

   /**
     * <p>이 메서드는 Gorilla 알고리즘을 사용하여 압축된 64비트 부동소수점(Double) 데이터를 복원한다. 압축된 데이터는
     * XOR 연산을 통해 이전 값과의 차이점만을 저장하기 때문에, 복원 과정에서 이 XOR 값을 기반으로 원래의 값을 계산한다. 이 과정은 비트 단위로 매우 정밀하게
     * 진행되며, 각 단계에서 저장된 비트 정보를 정확하게 해석해야 한다. 복원된 데이터는 원래의 정수 리스트로 변환되어 반환된다.</p>
     *
     * <p>복원 과정에서 각 데이터의 선행0비트(leading zeros)와 후행0비트(trailing zeros)를 관리하여 효율적인
     * 복원이 가능하도록 한다. 압축된 데이터는 row 개수를 기반으로 처리되며, 데이터가 8비트로 나누어지지 않는 경우 마지막에 추가된 비트들이 잘못된 복원 결과를 초래하지
     * 않도록 주의해야 한다.</p>
     *
     * @param compressedData 압축된 데이터를 담은 바이트 배열
     * @param size           복원할 데이터의 크기 (행 개수)
     * @return 복원된 Double 값의 리스트
     * @throws IOException 데이터 복원 중 발생할 수 있는 입출력 예외
     */
    public static List<Double> decompressDoubleValue(byte[] compressedData, long size)
        throws IOException {
        int storedLeadingZeros = Integer.MAX_VALUE;
        int storedTrailingZeros = 0;
        LongValuePredictor longValuePredictor = new LongValuePredictor();
        BitReader reader = new BitReader(compressedData);
        List<Double> values = new ArrayList<>();
        // 첫 번째 값 그대로 Double로 복원
        long firstLongValue = reader.readBits(Long.SIZE);
        longValuePredictor.update(firstLongValue);
        values.add(longBitsToDouble(firstLongValue));
        int count = 1;
        while (reader.hasNext() && count++ < size) {
        // 두 번째 값부터 Gorilla 복원
        // ... 복원 코드 ...
        //
        }
        return values;
    }

위 부분에서 size(원본의 row개수) 만큼 복원을 수행하기 때문에 정상적으로 원본 값이 나타나는 것을 볼 수 있다.

 

이 문제를 해결함과 동시에, 그러면 페이스북에서도 이 문제가 나타났을텐데 어떻게 해결했을까? 라는 궁금증이 생기게 되었다.

여러 레퍼런스를 찾아보던 도중, 그 궁금증을 해결할 수 있었다. 

 

페이스북의 고릴라 알고리즘은 오로지 "실시간 적재되는 시계열 데이터의 압축"에 사용되기 때문에, 비트의 끝을 알고있을 필요가 없다는 것이다. 실시간으로 계속 압축을 수행하는데, 인메모리 데이터에서 실제 db로 압축되는 순간은 특정 엔드포인트에 의해 그만큼의 값을 적재하는 방식이라서 비트 끝처리 문제가 나타나지 않게 되는 것이다.. (데이터 스트림의 끝이 없음)

 

그에 비해 이번에 개발한 사내 압축 솔루션은 "이미 적재된 데이터를 조회하고 컬럼별로 가공(리스트화) 하고 압축-적재" 하는 점에서 차이가 있다. 이 말뜻은 시작과 끝이 명확하게 정해져 있는 데이터를 압축하고 적재해야 하기 때문에 비트의 끝을 알려주는 플래그가 존재해야 한다는 것이다.

 

 

 

성능 테스트

Gorilla 압축 알고리즘 외에도 RLE, RLE-Delta 알고리즘을 추가로 구현하여 평가데이터에 적합한(타이트한) 압축 모듈을 구현했는데, 이에 대한 성능 테스트를 가장 일반적인 ZIP알고리즘과 비교하여 테스트를 해 보았다.

 

테스트하기 이전, ZIP알고리즘을 조사해 보았는데 너무 종류가 많아서 평가데이터에 가장 적합한 라이브러리를 찾아보았는데 그것들 중 3개(ZIP4j, GZIP, ZIP)만 추려서 어떤 압축 라이브러리가 가장 효율이 좋은지를 테스트해보았다.

 

 

위 테스트 케이스 중 특히 평가데이터에 가장 적합하게 사용될 케이스들은 List<Double>(증가값) 과 List<Integer>(고정값, 증가값)이다. 

 

물론 세 가지 라이브러리 모두 Deflate(Lempel-Ziv + Huffman coding) 알고리즘을 사용해서 크게 성능차이가 나지는 않았지만 어떤 것들은 압축파일에 암호를 건다거나, 추가 보안관련 기능을 넣는다거나, 파일 분할압축을 제공한다거나 같은 기능들이 있는데, 이런 잡다한 기능들로 인해 라이브러리가 무거운것도 있을 것 같아 가장 빠른 속도이면서 자바의 기본 내장 라이브러리인 java.util.zip을 사용하기로 했다.

 

평가 데이터의 특성상 반복되는 정수값, 순차적으로 1씩 증가되는 정수값, 미묘한 차이로 증가하는 부동소수점 데이터들이 많고, 언제 적재되었는지 또는 경과시간이 어떻게 되는지에 대한 Date타입의 데이터가 많은 관계로 아래와 같은 알고리즘들을 구현한 것이다.

1. RLE (반복되는 정수 데이터)

2. RLE-Delta (순차적으로 증가하는 정수 데이터)

3. Gorilla-TS (시계열 또는 시간타입 데이터)

4. Gorilla-Value (부동소수점(double) 데이터)

 

RLE과 RLE-Delta 알고리즘을 구현한 부분도 ZIP알고리즘에 비해 엄청 좋은(속도는 10배이상 , 압축률은 44->99% 차이) 성능을 보여주지만 이에 대한 부분은 레퍼런스가 매우 많으므로 본 포스팅에서는 올리지 않았다.

 

구현을 완료하고 ZIP 알고리즘(deflate)과 성능비교를 해보았을때 준수한 성능을 보여주는 것을 확인했다.

 

실제 적재된 평가데이터를 csv파일(100만 건의 데이터)로 뽑고, 각 알고리즘의 벤치마킹에 대한 출력은 아래와 같다.

 

시계열 데이터(100만건)에 대한 gorilla-TS vs ZIP 알고리즘

 

부동소수점 데이터(100만건)에 대한 gorilla-value vs ZIP 알고리즘

 

Gorilla-TS는 압축률, 속도 측면에서 엄청 좋은 성능을 보여준다. 

Gorilla-Value는 압축률은 ZIP에 비해 낮은 편이지만, 엄청난 속도 차이를 보여주었다.

 

정리 표

 

사내 압축 솔루션 개발 회고

입사하고 처음으로 혼자 설계/기획하고 해외 논문을 분석한 후, 직접 알고리즘을 구현해보면서 압축 모듈을 완성해보았다. 

처음 기획은 회사의 높은 분(상무) 님께서 도와주셨는데 고릴라 알고리즘의 이해와 OS지식, 비트연산의 지식에 많은 도움이 되어주셨다.

 

설계 도중 한 가지 문제점이 있었다면, 사내 충방전기의 데이터가 실시간으로 적재되지 않는다는 점이었다. 사실 Gorilla 알고리즘은 실시간으로 적재되는 시계열 데이터에 가장 효율이 좋은 알고리즘이다. (압축률을 일정 포기하면서 엄청난 속도를 자랑하는..)

사내 충방전 데이터 적재 시스템은 특정 chunk 또는 시간 단위로 한 뭉터기(?) 씩 db에 적재되는 방식이다.

(왜 이런 충방전기를 쓰는건지는 모르겠다. 실시간으로 데이터 적재해주는 충방전기를 인터배터리 행사에서 본것 같은데.. 뭔가 이유가 있겠지..)

이렇게 적재된 데이터를 조회해서 압축하고 다시 적재하는 방식으로 운영하고 싶다 하셔서 해당 사내 압축 솔루션 개발을 내가 맡게 된 것이다.

이에 대한 추가적인 문제점으로 여러 오픈소스에서 Gorilla알고리즘은 압축/적재 프로세스가 데이터베이스 계층에서 수행된다.

데이터베이스 계층에서 수행되는 고릴라 알고리즘은 조회 속도를 엄청나게 줄이면서, 특정 압축 테이블에 대해 모든 칼럼에 조회조건을 걸 수 있다.

하지만 사내 솔루션은 압축하지 않은 특정 컬럼을 기준으로 조회하여 어플리케이션 계층에서 압축/복원을 수행한다.

이는 I/O속도는 엄청나게 줄이겠지만, 어플리케이션 계층의 메모리에 부하가 많이 가고 수행시간이 많이 늘어난다는 것이다.

 

하지만 스토리지 용량의 대폭 감축에 있어서, 결과적으로는 성능 좋은 압축 모듈이 되었다고 생각한다.

(전체적인 수행시간 성능도 45.62%로 상당히 개선되었다.)

 

 

모듈을 주입한 샘플 프로젝트(뷰 허접함 주의) 

모듈개발을 완성해 나가면서, "이 모듈을 그래서 어떻게 쓰는거지?" 라는 생각이 들어 모듈을 주입한 샘플 프로젝트를 스프링 부트와 타임리프를 활용해서 SSR로 간단하게 구현해서 실행해봤다. (프론트는 정말 어렵다..)

 

사용하는 곳에서 모듈에서 정의한 Compress 클래스를 빈으로 등록해주는 과정이 있어야 하고, 압축된 데이터를 저장할 테이블(메타데이터 테이블이라 칭함) 은 application.properties에 정의했다. (모듈 측에서 이 부분도 직접 구현해야 했음..)

 

 

 

 

그리고, 이 모듈을 사용하는 직원들 입장에서 전체적으로 어떤 함수와 메서드, 클래스가 있고 어떻게 사용하는지, 어떻게 동작하는지에 대한 설명을 Javadoc으로 작성하였다. (다른 오픈소스 라이브러리들도 다 작성되어 있길래 꽤 시간을 들여 만들었다)

 

 

docs.zip

0.34MB

 

 

 

 

이번 사내 평가데이터 압축 솔루션은 나에게 있어서 꽤 많은 것을 경험하게 한 프로젝트였다. 먼저 비트단위로 연산은 학부생 시절 이론적으로만 접해본 것이 전부였는데, 실제 솔루션에 이를 적용해본 것은 이번이 처음이었다. 비트 단위의 최적화와 압축 알고리즘 구현 과정에서, 단순한 이론적 지식을 실제로 활용하는게 얼마나 값진 경험인지 깨달을 수 있었다. 

 

가장 어려웠던 부분은 예상 외의 문제들이 끊임없이 발생하는 상황에서, 그 문제의 원인을 분석하고 해결하는 과정이었는데, 예를 들어 비트 끝처리 문제의 경우 처음에는 데이터가 잘못 복원되는 이유를 쉽게 파악하지 못했다. 하지만 문제의 근본 원인을 파악하기 위해 디버깅으로 압축과 복원 과정을 한단계씩 체크하고, 여러 테스트 케이스를 만들어 시뮬레이션해보는 과정을 거치며 문제를 해결할 수 있었다. 

이러한 과정에서 데이터의 시작과 끝이 명확하게 정의되지 않는 페이스북의 고릴라 알고리즘과 달리, 사내 평가 데이터의 특성에 맞춘 커스터마이징이 필요하다는 점을 깨달았다. 

 

또한 Maven Local 및 Private Repository에도 배포하여 gradle에 주입해 직접 이 모듈을 import하여 사용해보았는데, 이는 실제 업무에서 유용하게 쓰일 수 있는 경험을 쌓을 수 있었다. (javadoc 작성하는 데에 시간투자가 많이 되어 퇴근시간이 많이 늦춰졌었다.. ㅠ)

 

결국, 이번 프로젝트를 통해 얻은 가장 큰 교훈은 새로운 기술과 도구에 대한 두려움을 극복하고, 이를 활용해 실제 업무에 접목시키는 과정에서의 성장이 아닐까 싶다. 비트 연산을 통해 알고리즘을 구현하는 과정뿐만 아니라, 이를 실제 환경에서 모듈화하고 배포하며 활용하는 전반적인 과정과 팀 내에서 내가 개발한 모듈이 실제로 사용되고 개선되는 과정은 나에게 커다란 성취감을 안겨주었다. 앞으로도 이런 경험을 바탕으로 더 많은 기술과 지식을 습득하고 실무에 적용해 나가고 싶은 바램이 있다.