[웹 개발자를 위한 대규모 서비스를 지탱하는 기술]Chapter 6

이 글은 절판도서 "웹 개발자를 위한 대규모 서비스를 지탱하는 기술" 을 개인적인 용도로 정리한 글입니다. 모든 내용을 정리한 것이 아니라 필요한 부분만 정리했다는 점 양해 부탁드립니다

문제/오류가 있을 시 댓글로 알려주면 감사하겠습니다

---

압축 프로그래밍

데이터 크기, I/O 고속화와의 관계 인식하기

• 압축과 I/O 고속화는 끊을 수 없는 관계이다
• VB Code(Variable Byte Code) 알고리즘으로 과제를 진행한다

정수 데이터를 컴팩트하게 가져가기

과제 : 정수열이 기록된 CSV를 바이너리로 해서 컴팩트하게 가져가기

• 정수의 부호화를 연구해서 텍스트로 152MB인 CSV 데이터를 절반 이하의 크기로 해서 처리
• 원본을 복원할 수 있어야 한다

• 단순히 바이너리 파일로 만드는 것이 아니라 압축, 구체적으로는 부호화를 연구해서 크기를 절반 이하로 하는 것이 과제

| 출제 의도

과제를 통해 얻어갈 수 있는 것들

• 이 과제를 해결하면 큰 정수열을 컴팩트하게 가져가는 방법을 알게 되는 것이다
• 큰 데이터를 압축해서 컴팩트하게 만들면 디스크 I/O를 줄일 수 있다(큰 데이터를 다룰 때는 압축한다는 것을 항상 염두에 둘 것)
• RDBMS에서는 보통 정수를 고정길이로 가져가기 위해 크기가 늘어나게 되는데, 이를 적당히 작은 크기로 줄여서 처리하는 방법을 알게 된다
• VB Code 알고리즘을 이용해 빠른 프로그램의 속도를 체감한다
• 검색엔진 개발에 응용할 수 있고, 기계 학습, 데이터 마이닝 시에도 큰 크기의 정수열을 다룰 때가 많은데 이 때 사용해도 좋다
• 데이터형의 크기, 바이너리의 크기, 스크립트 언어가 갖는 데이터 크기의 오버헤드에 의식을 기울이는 것도 신경쓰는 것이 좋다

| 과제에서 다루는 파일의 내부

• 데이터는 하테나에서 실제로 사용하는 데이터를 덤프해둔 것으로 사용
• 특정 태그가 있고, 태그를 포함해 엔트리의 ID 가 기록되어 있는 데이터(152MB)

VB Code와 속도 감각

• VB Code(Variable Byte Code, 가변 길이 바이트 부호)를 사용한다

| VB Code

• 구현 면에서는 간단하고 속도가 빨라 손쉽게 사용 가능
• 압축 알고리즘이라기보다는 정수의 부호화 방법 중 하나

ex) 현대 컴퓨터에서는 숫자 5를 고정길이 32비트로 0...0000 0101 과 같이 바이너리 부호로 표현한다 이와 같이 VB Code는 또 다른 규칙에 따라 정수를 부호화 한다 

• ex) 5와 130을 바이너리와 VB Code로 각각 부호화한 비트열을 나타내보았다

5
Binary : 00000000 00000000 00000000 0000101
VB Code : 10000101(5)

130 
Binary : 00000000 00000000 00000000 00000000
VB Code : 00000001(128) 10000010(2)

• 바이너리로 부호화 할 경우 32비트(4바이트)를 모두 사용해야하지만 VB Code는 앞 부분의 불필요한 바이트를 제거하고 최소한의 바이트로 정보를 표기한다
• VB Code는 첫 1비트가 플래그(continuation 비트)로 되어있고 남은 7비트로 바이너리 부호를 표현한다
• 첫 1비트 플래그는 이 정수의 비트열이 이 바이트에서 끝나는지 여부를 알려준다(1 : 끝, 0 : 안끝남)
  ex) 10000101 <- 이 바이트가 끝
  ex) 00000001 <- 이 바이트 다음에 다른 바이트가 있음

| VB Code의 의사코드

• 128은 10000000으로 외워두면 좋다
• continuation 비트가 1인지 여부를 조사하기 위해 128과의 대소 관계를 비교한다
• VB Code의 수도코드
• 작은 숫자를 4바이트가 아닌 더 작은 바이트 수로 부호화 하는 방법

| 정렬 완료된 정수를 'Gap'으로 가져가기

• 정수열을 압축할 경우에는 더 연구가 필요하다
• 정수가 정렬 되어있다면, 이전 숫자와의 차분으로 표현해준다(그럼 역으로 복원할 때 처음부터 더해가면 원래 정수열로 복원할 수 있다)

[3, 5, 20, 21, 23, 76, 77, 78]
-> [3, 2, 15, 1, 2, 53, 1, 1]

• 위와 같이 할 경우 갭이 작으면 1, 2와 같은 작은 숫자가 나오고 VB Code로 압축할 때 훨씬 압축률이 높아지게 된다

| 압축의 기초(보충1)

• 기호의 출현 빈도를 보고 빈번하게 출현하는 기호에 짧은 부호를 부여하고 그렇지 않은 기호에는 긴 부호를 부여한다(기호의 출현확률분포를 생각해서 최적인 부호를 생성)

| 대상이 정수인 경우 - 배경에 있는 이론

• 텍스트를 압축할 때에는 범용적인 압축 방법을 사용한다(정수, 알파벳, 기호 등)
  ex) 허프만 부호 : 각 문자의 출현 빈도를 살펴가며 확률 분포를 조사한 후 그 확률 분포에 최적인 부호를 생성하는 알고리즘
• 정수일 경우 압축대상 기호 자체가 값으로 의미를 가지고 있고 이를 이용해서 확률분포를 변형시키는 것이 본질적이다
• 정수열의 Gap 분포는 기하분포로 되어있다

과제에 대한 상세 설명과 응답 사례

1. 테스트용 데이터 파일을 Gap + VB Code로 부호화한 것을 저장하는 프로그램을 만든다
2. 저장한 바이너리를 복원하는 프로그램을 만든다
3. 원본 텍스트 파일보다 얼마나 작아졌는가 확인한다
4. 수월에게 끝냈다면 VB code 이외에 부호화 방법을 시험해본다( γ 분포, δ 분포 등)

• 1, 2번은 세트로 만들어야 한다

평가 기준은 다음과 같다(중요도 체크 가능)

1. 확실한 동작, 압축률 (4점)
2. 부호/복호화의 속도(2점)
3. 코드의 가독성(2점)
4. 구현에 대한 연구(2점)

| 코드 구현

• Perl로 VB Code를 구현하기 위해서는 pack() 함수를 사용하며, 내부 데이터 구조를 바이너리로 내보내는 역할을 한다
• Java에서는 JBBP를 사용할 수 있다
• 반대는 unpack() 을 이용한다
• VB Code로 바이트열을 생성하는 곳에서 사용
  -> 의사 코드의 bytes[]는 unsigned char로 pack해서 단일 바이너리로 만든다
• java에서는 다음 코드로 작성 가능하다

| 프로파일러

• 결과물의 속도를 확인할 때는 프로파일러를 사용한다