회사에서 제공하는 웹 서비스는 B to B 모델이면서, 엄청나게 많은 데이터를 다룬다. (유저 데이터는 아니고 장비 데이터임)
이 웹 서비스의 초기 개발이 마치면서 나에게 기술과제가 하나 주어졌는데 그건 바로 데이터의 압축이다.
본 포스팅은 해당 압축에 대해 자료조사 했던 내용들과, 논문에 대해 해석한 내용을 바탕으로 작성한 것이다.
1. 압축???
데이터 압축은 저장 공간을 절약하고 전송 속도를 높이기 위해 데이터를 효율적으로 변환하는 기술이다.
흔히 우리가 사용하는 알집이나, 반디집 같은 프로그램을 사용하여 특정 Encoding 알고리즘들로 원본 파일에 비해 더 작은 파일로 압축할 수 있다.
기존에 알고있는 압축파일(.7z, .zip..) 말고도 이미지(jpeg)나 동영상(mp4, avi..)도 압축 파일이다.
Encoding, Compress 다 같은 말이고 소위 동영상 플레이어에서 CODEC이 ENCODE/DECODE를 말하는 것이다.
2. 압축 알고리즘
압축 알고리즘에는 두 가지의 유형이 있다. 바로 손실 압축과 비손실 압축이다.
2.1. 손실 압축
손실 압축은 원본 데이터에서 일부 정보를 제거하여 데이터의 크기를 줄이는 방식이다. 특징으로는 압축된 데이터를 복원할 때 원본 데이터와 정확히 일치하지 않을 수 있다는 것이다.이미지나 오디오, 동영상 파일에 사용되는 압축이다.
- JPEG : 이미지 파일을 압축할 때 널리 사용되는 알고리즘. 인간의 시각적 특성을 이용하여 불필요한 데이터를 제거한다.
- MP3 : 오디오 파일을 압축할 때 사용되며, 인간의 청각적 한계를 이용하여 데이터를 효율적으로 줄인다.
시각적 특성,청각적 한계라 하면 이해가 어려울 수 있어 예시를 들어보자.
MP3 손실 알고리즘을 사용하여 mp3파일을 만든다 가정해보자.
압축률을 높이기 위해 사람의 가청 주파수 범위(20~20,000hz) 를 벗어나는 영역을 제거했을 때, 사람은 이 변화를 감지하지 못하고 결국 데이터 크기는 줄게 되는 것이다.
2.2. 비손실 압축
비손실 압축은 원본 데이터를 정확하게 복원할 수 있도록 데이터를 압축하는 방식이다. 특징으로는 데이터를 복원했을 때 (압축해제) 원본 데이터와 정확하게 일치하다는 것이다. 텍스트 파일이나 실행 파일, 데이터베이스 백업 파일 등이 이에 해당한다. 우리가 자주 사용하는 알집, 반디집, 7zip 같은 프로그램으로 압축하는것도 비손실 압축이다.
- ZIP : 여러 파일을 하나의 압축 파일로 묶으며, 각 파일을 비손실 방식으로 압축한다.
- PNG : 이미지 파일을 비손실 방식으로 압축하여, 원본 이미지 데이터를 정확하게 복원 가능하다.
- GZIP : 텍스트 데이터를 효율적으로 압축하는 알고리즘으로, 특히 웹에서 많이 사용된다.
손실 압축과 비손실 압축 알고리즘에는 위에 작성한 것들이 전부가 아니다. 아래 표를 보자.
| 무손실 압축 |
반복 길이 코딩 (run-length coding) | |
| 허프만 코딩 (Huffman coding) | ||
| 렘펠-지브 코딩 (Lempel-Ziv coding) | ||
| 차분 코딩 (Differential coding) | ||
| 손실 압축 | 변환 코딩 (transform coding) | FFT, DCT |
| 예측 코딩 (predictive coding) | DPCM, ADPCM, DM, ADM | |
| 양자화 (quantization) | ||
| 웨이블릿 코딩 (wavelet-based coding) | ||
| 보간법 (interpolation) | ||
| 프랙탈 압축 (fractal compression) | ||
| 혼성 압축(무손실+손실) | JPEG, GIF, MPEG, H.261, H.263 ... | |
*혼성 압축은 사실 손실 알고리즘이라 봐도 무방하다
3. 시계열 압축
회사의 데이터는 무결성을 유지해야 한다. 그러면 비손실 압축 방식을 채택해야 하는데 특히 시계열 데이터의 비손실 압축에 대한 연구가 불가피하다.
시계열 데이터 압축의 STA(State of the Art)를 가장 먼저 조사해보았는데 현재 시계열 압축의 알고리즘으로는 일반적으로 아래와 같다고 한다.
3.1. 고릴라(Gorilla) 알고리즘
시계열 데이터를 효율적으로 압축하기 위한 알고리즘으로, Hbase를 사용하던 페이스북이 Delta-of-Delta Encoding과 Xor Based Delta Encoding을 사용하여 만든 고릴라 시계열 데이터베이스에서 이름을 따온 알고리즘이다.
https://blog.acolyer.org/2016/05/03/gorilla-a-fast-scalable-in-memory-time-series-database/
Gorilla: A fast, scalable, in-memory time series database | the morning paper
Gorilla: A fast, scalable, in-memory time series database – Pelkonen et al. 2015 Error rates across one of Facebook’s sites were spiking. The problem had first shown up through an automated alert triggered by an in-memory time-series database called Go
blog.acolyer.org
https://www.vldb.org/pvldb/vol8/p1816-teller.pdf
3.2. LZ4
일반적인 LZ4 압축 알고리즘을 기반으로 시계열 데이터를 효율적으로 압축하기 위해 설계된 방식이다. LZ4는 고속 데이터 압축 알고리즘으로 특히 속도와 압축률 사이의 균형을 잘 맞추기 위해 설계되었다.
단점으로는 다른 고성능 압축 알고리즘에 비해 압축률이 낮고, 블록 크기에 영향을 많이 받는다.
https://en.wikipedia.org/wiki/LZ4_(compression_algorithm)
LZ4 (compression algorithm) - Wikipedia
From Wikipedia, the free encyclopedia Compression algorithm LZ4 is a lossless data compression algorithm that is focused on compression and decompression speed. It belongs to the LZ77 family of byte-oriented compression schemes. Features[edit] The LZ4 algo
en.wikipedia.org
3.3. Zstd(Zstandard)
LZ77과 FSE 압축 방식을 결합한 알고리즘으로, LZ77을 통해 반복 패턴을 찾고, FSE를 통해 패턴을 효율적으로 인코딩하여 높은 압축률을 자랑한다.
단점으로는 메모리 사용량이 높고, 높은 압축률을 위해서는 속도를 포기해야 한다.
https://facebook.github.io/zstd/
Zstandard - Real-time data compression algorithm
facebook.github.io
3.4. Snappy
Google에서 개발한 데이터 압축 알고리즘으로 속도에 중점을 둔 설계가 특징이다. 이는 특히 실시간 응용 프로그램에서 사용될 수 있도록 설계되었다. Snappy 알고리즘은 다른 고속 압축 알고리즘과 유사하게, 반복적인 데이터 패턴을 찾고 이를 참조로 변환하여 데이터를 압축한다.
단점으로는 주로 속도에 초점을 맞추기 때문에 압축률이 상대적으로 낮다.
https://en.wikipedia.org/wiki/Snappy_(compression)
Snappy (compression) - Wikipedia
From Wikipedia, the free encyclopedia Fast data compression and decompression library written in C++ by Google Snappy (previously known as Zippy) is a fast data compression and decompression library written in C++ by Google based on ideas from LZ77 and ope
en.wikipedia.org
3.5. LFZip
LFZip 시계열 압축 알고리즘은 Log-structured File System (LFS)의 아이디어를 기반으로 개발된 시계열 데이터 압축 알고리즘이다. LFZip은 시계열 데이터의 특성을 활용하여 효율적으로 데이터를 압축하고, 빠른 검색과 복원이 특징이다.
단점으로는 메모리 사용량이 높다.
https://sigport.org/sites/default/files/docs/slides_11.pdf
3.6. Chimp
시계열 데이터를 효율적으로 압축하기 위해 설계된 알고리즘으로, 특히 연속적이고 패턴이 있는 데이터를 압축하는 데 매우 효과적이다. 고릴라 알고리즘과 매우 유사한 방식으로 작동하지만 고릴라의 기본 개념을 확장하여 추가적인 최적화를 제공한다.
https://www.vldb.org/pvldb/vol15/p3058-liakos.pdf
3.7. Sprintz
고속의 압축 및 디컴프레션을 목표로 한 알고리즘으로 데이터의 주기성과 반복성을 활용하여 높은 압축률을 달성하며, 다른 알고리즘에 비해 훨씬 빠른 속도를 제공한다.
단점으로는 메모리 사용량이 높다.
https://dl.acm.org/doi/pdf/10.1145/3264903
추가적으로 자료조사를 해본 결과 시계열 데이터베이스의 압축에는 Gorilla 알고리즘을 일반적으로 많이 사용하는 것 같다.
요즘은 Gorilla 알고리즘의 확장형으로 여러 알고리즘들(Chimp, TSXor 등..)이 나타나긴 했지만 Gorilla 알고리즘을 알고 있어야 이해에 도움이 될 것 같다.
다음은 고릴라 알고리즘에 대한 포스팅을 해볼 예정이다.
'DEV > 기타' 카테고리의 다른 글
| 2024 회고 그리고 2025년 목표 (7) | 2024.12.26 |
|---|---|
| 시계열 데이터의 압축 - Gorilla Algorithm(고릴라 알고리즘) (1) | 2024.06.13 |
| 지속적 통합, 지속적 배포란? (CI/CD) (2) | 2023.05.15 |
| 클래스 다이어그램(Class - Diagram) (0) | 2022.11.15 |
| Eclipse MAC 단축키 (0) | 2022.11.14 |
