Last Updated on 5월 18, 2022 by Jade(정현호)
안녕하세요
이번 포스팅은 Database Internals 의 번역본인 데이터베이스 인터널스 책에 대해서 스터디한 내용에 대해서 기술해보려고 합니다.
해당 포스팅은 내용을 모두 숙지 또는 이해한 상태로 작성된 상태가 아님에 따라 내용이 틀리거나 미흡할수 있는 부분이 있으므로 참고 정도만 하시기 바랍니다.
본 포스팅은 다음 책을 정리한 내용 입니다.
Contents
Intro
디스크 접근 방식과 메인 메모리 접근 방식은 많은 차이가 있다
디스크는 시스템 호출(System Call) 을 통해 접근이 이루어지게 된다
대상 파일내의 오프셋을 직접 지정 해야 하며, 디스크상의 표현을 메인 메모리에서 읽을 수 있는형태로 변환 해야 한다.
효율적인 디스크 기반 자료 구조를 설계 하려면 이러한 차이점을 간안해야 하며, 그러려면 생성, 수정, 해석이 쉬운 파일 포맷이 무엇인지 알아한다.
이번 장에서는 B-트리 뿐만 아니라 여러 형태의 디스크 기반 자료 구조 설계에 관한 일반적인 원칙과 구현 방법에 대해서 소개 되어 있다.
파일 포맷의 중요성
파일 포맷 설계는 메모리 모델이 비 관리형(unmanaged)인 프로그래밍 언어로 자료 구조를 설계하는 것과 여러모로 유사 하다.
큰 메모리 청크 또는 가변 길이의 자료 구조는 포인터를 사용해 참조 한다.
메모리 모델이 비 관리형인 프로그래밍 언어에서는 연속된 메모리 세그먼트의 존재 여부, 메모리 단편화(fragmentation) 여부 , 메모리 해제 이후의 상황 등을 신경 쓰지 않고 필요하면 언제든지 메모리를 추가 할당 시켜 준다.
반면 디스크상에서의 가비지 컬렉션과 단편화를 모두 직접 관리해야 한다.
자료 구조를 효율적으로 디스크에 저장 하려면 영속적 저장 장치의 특성을 이해하고 빠르게 접근 할 수 있는 형태로 저장 해야 하며, 바이너리 포맷 구조를 설계하고 효율적으로 데이터를 직렬화하고 역직렬화하는 수단이 있어야 한다.
Note
직렬화는 객체를 저장매체(파일이나 메모리와 같은)에 저장하거나 바이너리(이진) 형태로 네트워크를 통해 전달하기 위해 저장하는 과정이다. 이(객체를 직렬화한) 연속된 바이트나 포맷은 다시 원래 객체가 가지고 있던 상태로 객체를 재생성하는데 사용할 수 있다. 이렇게 객체를 직렬화하는 과정은 디플레이팅(deflating) 또는 마샬링(marshalling)이라고도 부른다. 직렬화와는 반대로 연속된 바이트로부터 어떤 데이터 구조를 추출해내는 과정을 역직렬화(deserialization)라고 한다. 역직렬화는 인플레이팅(inflating) 또는 언마샬링(unmarshalling)이라 불리기도 한다.
https://en.wikipedia.org/wiki/Serialization
데이터를 메인 메모리에 저장하면 메모리 레이아웃과 관련한 대부분의 문제가 생기지 않거나 쉽게 해결 할 수 있다.
- 가변 길기의 필드
- 크기를 초과한 데이터
메모리 할당과 포인터를 사용할 수 있으므로 이러한 데이터를 어떤 특별한 레이아웃으로 저장하지 않아도 된다.
바이너리 인코딩
데이터를 효율적으로 디스크에 저장 하려면 컴팩트하고 직렬화와 역직렬화가 쉬운 포맷으로 인코딩을 해야 한다.
디스크에 저장된 데이터는 malloc 과 free 와 같은 원시 함수로 제어할 수 없고 오직 read 와 write 함수만을 사용할 수 있기 때문에 접근방식이 다르고 이에 맞는 형식으로 데이터를 저장 해야 한다.
효율적인 페이지 레이아웃을 설계하는데 중요한 몇가지 원칙 있으며, 파일과 직렬화 포맷, 통신 프로토콜 등의 모든 바이너리 포맷에도 같이 적용되는 원칙이다.
기본형
키와 값은 integer, date, string 등의 지정된 자료형이 있고 바이너리 형식(직렬화의 결과 형식이자 역직렬화의 입력 형식) 으로 표현 할수 있다.
대부분 숫자형은 고정 길이 자료형 이며, 멀티바이트 숫자형 사용시 인코딩과 디코딩 모두 같은 바이트 순서를 사용해야 한다.
엔디언
빅 엔디언
- 최상위 바이트(MSB, Most-Significant Byte) 부터 시작해서 내림차순으로 저장
- 즉 MSB를 가장 낮은 주소에 저장
리틀 엔디언
- 최하위 바이트(LSB, Leat-Significant Byte) 부터 높은 자리 바이트까지 오름차순으로 저장
[https://genesis8.tistory.com/37]
빅 엔디언은 사람이 숫자를 쓰는 방법과 같이 큰 단위의 바이트가 앞에 오는 방법이고 리틀 엔디언은 반대로 작은 단위의 바이트가 앞에 오는 방법이다.
빅 엔디언 <- 높은 주소 - - - - 낮은 주소 - >
리틀 엔디언 <- 낮은 주소 - - - - 높은 주소 - >
따라서, 프로그래밍 과정에서 서로 약속된 데이터 들과 통신 장치와 기기 들의 특성을 잘 파악하여 리틀->빅, 빅->리틀의 변환 과정을 거쳐 정확한 값을 서로 주고 받을 수 있도록 하는 것이 중요하다.
엔디언 별 사용 시스템
Sun Sparc, Motorola m64k, Power PC(PPC) 등 대부분의 RISC CPU: Big Endian
AIX on POWER AmigaOS on PowerPC and 680x0 HP-UX on Itanium and PA-RISC Linux on MIPS, SPARC, PA-RISC, POWER, PowerPC, 680x0, ESA/390, and z/Architecture Mac OS on PowerPC and 680x0 Mac OS X on PowerPC MVS and DOS/VSE on ESA/390, and z/VSE and z/OS on z/Architecture Solaris on SPARC
IBM 370, Intel x86, Atmega, MSP430: Little Endian
Linux on x86, x64, Alpha and Itanium Mac OS X on x86, x64 OpenVMS on VAX, Alpha and Itanium Solaris on x86, x64, PowerPC Tru64 UNIX on Alpha Windows on x86, x64 and Itanium
만약 플랫폼의 엔디언과 실제 엔디언이 일치 하지 않으면 Endian Transform 함수를 사용해 바이트 역순으로 읽음
레코드
레코드는 숫자, 문자열 , 불리언 과 같은 기본형과 이들의 조합으로 구성된다.
레코드는 바이트 시퀀스 형태로 네트워크를 통해 전송되고 디스크에 저장한다.
따라서 전송 및 쓰기 전에 우선 직렬화(해석할 수 있는 바이트 시퀀스로 변환) 하고 수신 및 읽기 전에 역 직렬화(바이트 시퀀스를 원래 레코드 형태로 반환) 해야 한다.
숫자형 크기는 다양함
- byte 형은 8비트
- short 는 2바이트(16비트)
- int는 4바이트(32비트)
- long은 8바이트(64비트)
부동소수점(float 과 double)
263.3 같은 실수를 2진수로 표현해 보면
263 => 100000111 0.3 => 0.01001100110011......(0011)의 무한 반복이다.
이렇게 2진수로 표현하지 못하는 소수가 발생하며, 어쩔 수 없이 컴퓨터에는 표현할 수 있는 가장 근사치의 값이 저장된다.
이 근사 값을 저장하는 방법에는 두 가지가 있으며(float 과 double) 이러한 근사값을 부동소수점 이라고 한다.
고정소수점(decimal)
정수 16 bit, 소수 15 bit를 사용하도록 약속해 놓은 시스템에 있다고 가정시에 263.3을 표현하면 (0)0000000100000111.010011001100110 이렇게 표현된다.
정수를 표현하는 bit를 늘리면 큰 숫자를 표현할 수 있지만 정밀한 숫자를 표현 하기는 어렵다.
부동소수점
부동소수점(Float 과 double) 은 부호(sign) 와 가수(fraction), 지수(exponent) 로 구성된다.
부동 소수점을 표현하는 방식도 정하는 방식에 따라 다를 수 있지만 일반적으로 사용하고 있는 방식은 IEEE에서 표준으로 제안한 방식이다.
우선 고정 소수점으로 나타낸 263.3을 2진수 부동 소수점 방식으로 변환하면
100000111.010011001100110... 으로 표현되던 것을 맨 앞에 있는 1 바로 뒤로 소수점을 옮겨서 표현하도록 변환
그러면 1.00000111010011001100110... * 2^8(2의 8승) 으로 표현 된다.
2^8의 8을 지수라고 하고 하늘색 부분에 기록한다 (IEEE 754 표현 방식에서는 127 + 지수를 기록)
소수점 이후 숫자열 전체를 가수라고 하고 연두색 부분에 기록하며, 이 방식에 따라서 263.3을 기록하면
부호 비트(1 bit) : 0 (양수) 지수 비트(8 bit) : 10000111 (127 + 8 = 135) 가수 비트(23 bit) : 00000111010011001100110
이렇게 표현할 수 있게 된다
하지만 여기서도 0.010011001100110은 정확히 0.3을 나타낼 수는 없으며 10진수로 나타내 보면 0.29998779296875을 나타낸다
참고) https://steemit.com/kr/@modolee/floating-point
double 형도 배정도(double precision) 를 표현하며 대부분의 프로그램 언어는 부동 소수점을 바이너리로 인코딩과 디코딩하는 함수의 표준 라이브러리를 포함한다.
문자열과 가변 길이 데이터
모든 기본형 데이터의 크기는 고정되어 있다.
문자열과 가변 길이 자료형(고정 길이 데이터 배열)은 배열의 크기 또는 문자열의 길이를 나타내는 숫자와 size 바이트 크기의 실제 데이터로 구성된다
이러한 형식을 UCSD 문자열 또는 파스칼 프로그래밍 언어의 이름을 따서 파스칼 문자열 이라고 부른다.
널 종단 문자열
- 파스칼 문자열의 대안은 널 종단(null terminated) 문자열 이다.
- 널 종단 문자열 : C 문자열 컴퓨터 프로그래밍에서 문자열 및 널 문자('\0', ASCII에서는 NUL)로 끝나는 배열로 저장되는 문자열
- 바이트 단위로 문자열 끝 기호에 도달할 때 까지 읽는다.
파스칼 문자열
- 파스칼 문자열은 내용을 확인하지 않고 길이를 상수 시간 안에 알 수 있다는 장점이 있다.
- 메모리에서 size 바이트만큼 자른 바이트 배열을 문자열 생성자에 전달하면 언어별 문자열 구성 가능
비트 묶음형 데이터 : 불리언, 열거형, 플래그
불리언 자료형
불리언 자료형은 단일 바이트 또는 true 와 false 를 1과 0 으로 인코딩한 값을 표현
불리언은 두 개의 값만 표현할 수 있기 때문에 바이트 전체를 사용하는 것은 낭비
따라서 8개의 불리언 값이 1비트씩 사용하도록 묶어쓰기도 함(묶음형 packed 블리언)
비트의 값이 1이면 설정 상태, 0이라면 미설정 또는 빈 상태로 표현(false)
ENUM
열거형, enumerated type 의 줄임말이며, 숫자를 표현하며 바이너리 포맷과 통신 프로토콜에서 주로 사용된다.
가짓수가 적고 자주 반복해서 나오는 값을 표현할 때 사용한다.
플래그
묶음형 불리언 과 열거형의 조합인 플래그
상호 배타적이지 않은 불리언 값들을 표현할 수 있다.
페이지의 값 보유 여부와 특정 값 크기의 고정 또는 가변 여부, 특정 노드의 페이지에 오버플로우 발생 등을 나타낼 때 사용된다.
모든 비트가 플래그(o or 1)이기 때문에 2의 거듭 제곱만 지정할 수 있음
파일 포맷 설계 원칙
일반적으로 파일 포맷을 설계할 때 주소 지정 방식(address) 부터 결정 해야 하며, 파일을 단일 블록 또는 연속된 여러 블록으로 구성된 같은 사이즈의 페이지로 나눌것인지 선택 해야 한다.
고정된 페이지 크기를 사용하는 경우 읽기와 쓰기가 비교적 쉽다
전용 자료 구조도 페이지 단위로 쓰는 경우가 많음
레코드를 순차적으로 추가하고 페이지가 가득 차면 디스크로 플러시(flush) 한다.
파일은 고정 크기의 헤더(header) 로 시작하며 끝 부분에 고정 크기의 트레일러(trailer)가 있을 수도 있다.
파일의 나머지 부분을 디코딩 하는데 필요한 보조 정보가 들어간다.
대부분의 데이터 스토어에는 테이블을 구성하는 필드 수, 순서 , 형식이 고정된 스키마 등이 있다.
필드에는 고정 길이 필드 와 가변길이 필드가 있습니다.
고정 길이 방식 필드
- 필드가 고정 길이를 갖는 방식이다.
- 고객 코드는 6byte, 이름은 9byte ... 이런식으로 필드에 고정 길이를 주는 방식이다.
- 구조나 구현이 간편하지만 공간 낭비가 있다.
가변 길이 방식 필드
- 가변 길이 방식 필드에는 길이 지시자, 구획 문자, 키워드=값 구조 3가지 방식이 있다.
- 길이 지시자 방식은 필드값 앞에 길이를 적는 방식이다. 06A-0001|03홍길동|08123-4562|...
- 구획 문자 방식은 필드별로 문자를 두어 구분하는 방식이다. A-0001|홍길동|123-4562|전국|A
- 키워드=값 구조는 키워드와 값을 입력하는 방식이다. 고객코드=A-0001|이름=홍길동|전화번호=123-4562|주소=전국|고객등급=A
더 복잡한 파일 구조에는 더 많은 계층이 필요
필드는 기본형, 셀은 필드, 페이지는 셀, 섹션은 페이지, 리전은 섹션으로 구성되지만 파일 포맷을 설계 시 반드시 따라야 하는 규칙은 없다
어떤 형식의 데이터 포맷을 설계 하느냐가 중요
페이지 구조
데이터베이스 시스템은 데이터 레코드를 데이터 파일과 인덱스 파일에 저장한다.
파일은 여러 파일 시스템 블록을 합친 고정 크기의 페이지로 구성되며, 블록 크기는 4kb부터 16kb까지 다양하다.
블록의 크기는 데이터베이스 시스템 마다 다르다.
B-tree 노드는 아래와 같이 나눌 수 있다.
- B-Tree 노드는 키와 데이터 레코드가 쌍으로 저장하는 리프 노드
- 키와 다른 노드(다른 단계, 다른 depth) 를 가리키는 포인터를 저장 : 루트 와 브런치 노드 (비 리프 노드)
B-tree 노드는 단일 페이지 또는 연결된 여러 페이지로 구성된다.
따라서 B-트리 맥락에서 노드와 페이지(또는 블럭)의 의미는 같다.
B-tree 를 처음 발표 한 논문은 고정 길이 데이터의 페이지 구조로 설명하고 있다.
아래 그림과 같이 페이지는 여러 트리플렛(triplet) 으로 연결한 구조이고 키는 K 로 , 값은 V 로 , 포인터는 P 로 표시하고 있다.
위의 이미지와 같은 구조는 단순하지만 다음과 같은 단점이 있다.
- 오른쪽 빈 공간이 아닌 곳에 키 추가 시 여러 원소를 재배치해야 한다.
- 고정 길이 레코드 저장에 적합하지만 가변 길이 레코드를 효율적으로 관리 및 저장할 수 없다.
슬롯 페이지
가변 길이 레코드 사용시 발생되는 가장 큰 문제는 삭제된 레코드에 대한 공간 회수 관련한 공간 관리에 대한 이슈가 가장 큰 문제가 되게 된다.
길이가 m 인 레코드를 저장 하였던 위치에 길이가 n인 레코드를 저장할때 m==n 이 아니라면 이 공간을 최대한 활용하려고 한다.
m - n 인 만큼의 또 다른 레코드가 필요하게 된다.
페이지를 여러 개의 고정 길이 세그먼트로 분할하게 되면 가변 길이 레코드를 저장할 수 있다.
하지만 여전히 공간 낭비는 피할 수 없다.
예를 들어 세그먼트 크기가 64바이트 일 때 레코드 길이가 64의 배수가 아니라면 64-(n modulo 64) 바이트가 낭비 된다
(n은 레코드 길이)
따라서 레코드의 길이가 64의 배수가 아니라면 블록의 일부는 사용하지 않는다.
공간 회수 시에 페이지를 재작성 하고 일부 레코드를 재배치 하게 된다.
다만 다른 페이지에서 재배치 된 데이터를 참조할 수 있기 때문에 레코드의 오프셋은 유지해야 한다.
동시에 메모리를 낭비하지 않도록 주의해야 한다.
페이지 포멧은 다음 조건을 충족해야 한다.
- 최소한의 오버헤드로 가변 길이 레코드 저장
- 삭제된 레코드의 메모리 회수
- 페이지의 레코드를 정확한 위치와 상관 없이 참조
슬롯 페이지 또는 슬롯 디렉터리 를 사용하면 문자열, BLOB(비랍,블랍,Binary large object) 과 같은 가변 길이 자료형을 효율적으로 저장할 수 있다.
참고로 PostgreSQL 이 방식을 사용한다.
페이지는 슬롯 또는 셀의 집합이며, 페이지 내 독립적인 영역에 포인터와 셀을 분리해서 저장한다.
따라서 레코드의 논리적 순서는 셀을 가리키는 포인터의 순서로 제어할 수 있다.
레코드 삭제 시 해당 포인터를 삭제하거나 NULL 로 설정 하게 된다.
슬롯 페이지의 고정 길이 헤더에 페이지와 셀에 대한 중요한 정보를 저장하게 된다.
[https://duynguyen-ori75.github.io/slotted-page-format]
셀 에는 키와 포인터, 레코드 등 임의의 데이터를 저장할 수 있으며 셀 마다 크기는 다를 수 있다.
슬롯 페이지는 앞서 설명한 조건을 모두 충족한다.
- 오버헤드 최소화 : 실제 레코드 위치를 가리키는 포인터 배열 사용이 유일한 오버헤드
- 공간 회수 : 단편화 제거 및 페이지 재구성을 통해서 공간을 회수할 수 있다
- 동적 레이아웃 : 슬롯은 ID를 통해 페이지 외부에서 접근하기 때문에 정확한 위치는 페이지 내부에서만 필요함
셀 구조
플래그와 열거형, 기본형을 사용해 셀 레이아웃을 설계할 수 있습니다.
- 셀을 병합하면 페이지가 됨
- 페이지를 병합하면 트리가 됨
셀은 키 셀과 키-값 셀로 나눌 수 있다.
키 셀에는 구분 키와 인접한 두 키 사이의 페이지를 가리키는 포인터 정보가 들어가 있다.
키-값 셀에는 키와 해당 데이터 레코드가 들어있다.
따라서 셀에 관한 정보를 셀마다 중복 저장하지 않고 페이지 레벨에서 저장해도 된다.
키 셀의 구성 요소
- 셀 종류(페이지 메타데이터로 부터 알아 낼 수 있음)
- 키 인수
- 셀이 가리키는 자식 페이지의 ID
- 키 바이트 수
가변 길이 키 셀은 다음과 같은 구조로 저장 된다.
0 4 8 +-----------------+----------------+-------------+ | [int] key_size | [int] page_id | [bytes] key | + ----------------+----------------+-------------+
고정 길이 필드는 앞쪽에 저장되고 key_size 바이트 크기의 필드는 따로 모아서 저장할 수도 있다.
반드시 따라야 하는 구조는 아니지만 오프셋 계산이 쉽다는 장점이 있다.
미리 계산된 정적 오프셋을 통해 고정 길이 필드에 접근 할 수 있고 가변 길이 데이터의 오프셋만 따로 계산하면 된다.
키-값 셀은 자식 페이지 ID 대신 실제 데이터를 저장한다 다른 구성 요소는 키 셀과 유사하다.
- 셀 종류(페이지 메타데이터로 부터 알아 낼 수 있음)
- 키 길이
- 값 길이
- 키 바이트
- 데이터 레코드 바이트
오프셋과 페이지ID 는 정확히 구분해야 한다.
고정 크기의 페이지는 페이지 캐시가 관리하기 때문에 페이지ID 를 통해 룩업 테이블에서 오프셋을 참조할 수 있다.
반면 셀 오프셋은 페이지 내부에서 시작 오프셋으로 부터 상대적인 위치를 나타낸다.
이렇게 하면 비교적 적은 숫자를 사용해 위치를 나타낼 수 있다.
셀 병합으로 슬롯 페이지 구성
위의 그림과 같이 페이지의 셀은 오른쪽(끝 쪽)에 추가 하고 셀 오프셋/포인터는 왼쪽에 추가 한다.
키는 삽입 순서대로 추가하고 셀 오프셋 포인터는 키 순서대로 저장하면 논리적 순서를 유지할 수 있게 된다.
이 방식은 셀을 삽입 또는 업데이트, 삭제해도 다른 셀을 재배치 않아도 되게 된다.
이름이 지정된 페이지를 예로 보면, 페이지에 Tom 과 Leslie 순서로 이름을 삽입한다.
하지만 그림 3-7의 페이지를 보면 셀의 논리적 순서(알파벳순)와 삽입순서(페이지에 추가 된 순서)는 일치 하지 않는다. 셀은 삽입 순서대로 배치 되고 오프셋은 이진 탐색이 가능하도록 정렬한다.
다음으로 Ron 이라는 레코드를 삽입한다. 이 레코드는 페이지의 빈 공간의 오른쪽에 추가 하지만 셀 오프셋은 사전식 순서를 유지 해야한다(Leslie, Ron, Tom)
따라서 아래 그림과 같이 Ron 셀을 가리키는 포인터의 공간을 확보하기 위해 포인터 삽입 지점 뒤의 포인터를 오른쪽으로 이동 하시게 됩니다.
가변 길이 데이터 관리
페이지 레코드 삭제 시 실제로 셀을 지우고 할당 해제된 공간으로 다른 셀을 옮길 필요는 없다 그 대신 삭제된 셀이라고 표시하고 메모리에 저장된 사용 가능 목록에 회수된 메모리 크기와 해당 위치를 가리키는 포인터를 업데이트 해도 된다.
사용 가능 목록에는 사용할 수 있는 세그먼트의 크기와 위치가 저장된다.
새로운 셀을 삽입하기 전에 먼저 이 목록에서 적합한 세그먼트가 있는지 확인한다.
아래는 사용 가능한 세그먼트가 남아 있는 단편화된 페이지를 나타낸다.
SQLite 에서는 사용 중이지 않은 세그먼트를 프리블록(Freeblock) 이라고 부르고 첫 번째 프리블록을 가리키는 포인터를 페이지 헤더에 저장한다.
단편화 제거 후 새로운 레코드를 한 페이지에 저장할 수 있을지 빠르게 판단할 수 있도록 페이지에 남아 있는 바이트 수를 저장한다.
세그먼트는 다음 두 가지 전략에 따라 선택할 수 있다.
최초 적합(First fit)
첫 번째로 찾은 적합한 세그먼트를 선택하는 방식이다. 하지만 남은 공간이 또 다른 셀을 저장해 크기가 작을 수 있기 때문에 오버헤드가 발생할 수 있다.
최적 적합(Best fit)
탐색하여 공간 중에서 제일 적절하게 들어갈 수 있는 세그먼트를 선택하는 방식이다.
새로운 셀을 저장할 수 있는 연속된 공간이 없을 수도 있다.
단편화된 부분의 집합 크기가 충분할 경우 모든 셀을 읽고 재배치해 페이지의 단편화를 제거하면 새로운 셀을 연속된 공간에 저장할 수 있다.
만약 단편화를 제거해도 공간이 부족하다면 오버플로우 페이지를 생성해야 한다
B-트리 구조를 단순화하기 위해 각 노드의 크기는 페이지 크기를 넘지 않는다고 가정하자
페이지는 고정 길이 헤더와 셀 포인터 블록,셀로 구성된다
셀에는 키와 자식 노드 또는 해당 데이터 레코드를 가리키는 포인터를 저장한다.
B-트리는 단순한 계층형 포인터로 구성된다. 페이지 식별자로 트리파일에서 자식 노드를 찾고 셀 오프셋으로 페이지에서 셀을 찾을 수 있다.
버전 관리
데이터베이스 시스템 개발사는 신규 기능 추가와 버그 수정, 성능 개선 등을 포함하는 업데이트를 지속적으로 제공한다. 이 과정에서 바이너리 파일의 구조가 변경 될 수 있다.
일반적으로 스토리지 엔진은 한 개 이상의 직렬화 포맷을 지원한다. 따라서 파일 버전은 매우 중요한 정보다.
다양한 파일 버전 관리 규칙이 존재한다. 아파치 카산드라는 파일명 접두사에 버전을 기록한다. 따라서 파일을 열지않고 버전을 알수 있다.
버전 4.0 이후 데이터 파일은 na-1-bigData.db 와 같이 na로 시작한다. 4.0 이전 버전의 접두사는 ma 이었다.
버전 정보를 개별 파일에 기록하는 방법도 있다. PostgreSQL 은 PG_VERSION 파일에 버전을 기록 한다.
인덱스 파일 헤더에 버전을 명시하기도 한다. 이 경우 헤더의 버전 정보(또는 헤더 전체)는 반드시 모든 버전에서 읽을 수 있는 형식으로 인코딩 해야 한다.
파일 버전을 파악한 뒤에 해당 버전의 리더를 사용해 파일을 읽을 수 있기 때문이다.
체크섬
디스크에 저장된 파일은 소프트웨어 버그와 하드웨어 장애 등으로 인해 손상 될 수 있게 된다.
그에 따라서 이런 상황을 사전에 파악하고 손상된 데이터가 다른 서브 시스템에 전파되는 것을 방지 하기 위해 체크섬(checksum) 과 CRC(Cyclic Redundancy Check) 를 사용한다.
체크섬(checksum) 검사
체크섬(checksum)은 중복 검사의 한 형태로, 오류 정정을 통해, 공간(전자 통신)이나 시간(기억 장치) 속에서 송신된 자료의 무결성을 보호하는 단순한 방법이다.
체크섬은 나열된 데이터를 더하여 체크섬 숫자를 얻고, 정해진 비트수의 모듈라로 정해진 비트수로 재구성 한다.
단순 덧셈 방식과 순환 중복 검사의 계산 방식과는 차이가 있으나, 많은 경우 순환 중복 검사의 결과를 체크섬이라고 말하므로 단순 덧셈만을 의미하지는 않는다.
단순한 체크섬의 예는 다음과 같다
- 다음과 같이 4 바이트의 데이터가 있다고 치자: 0x25, 0x62, 0x3F, 0x52
- 1 단계: 모든 바이트를 덧셈하면 0x118이 된다.
- 2 단계: 캐리 니블(1바이트의 절반으로 보통 4비트를 가리키는 컴퓨터 환경의 용어)을 버림으로써 0x18을 만든다.
- 3 단계: 0x18의 2의 보수를 얻어 0xE8을 얻게되며, 이것이 체크섬 바이트이다.
- 체크섬 바이트를 테스트하려면 원래 그룹의 바이트에 체크섬 바이트까지 모두 더하면 0x200이 된다.
- 다시 캐리 니블을 버림으로써 0x00이 된다. 0x00이라는 뜻은 오류가 없다는 뜻이다. (하지만 오류가 있어도 우연히 0x00이 될 수도 있다.)
-참조: widipedia
체크섬은 보장성이 매우 낮으며 다중 비트 오류를 감지 할 수 없다. 대부분 XOR과 패리티 검사 또는 합(summation) 을 사용한다.
CRC(Cyclic Redundancy Check)
CRC는 순환 중복 검사 라고 번역 되며, 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.
데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다.
이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것 임을 알 수 있다.
<송신부>
-
임의의 CRC 발생코드를 선정한다.
-
CRC 발생코드의 최고차 차수만큼 원래 데이터의 뒤에 '0'을 붙인다.
-
확장데이터(= 원래 데이터 + 데이터 뒤에 붙인 '0')를 modulo-2 연산을 사용하여 CRC 발생코드로 나눈다.
-
나머지가 '0'이면 확장데이터를 그대로 전송한다.
-
나머지가 '0'이 아니면 원래데이터에 나머지를 붙여 전송한다.
<수신부>
-
수신장치(Receiver)는 수신된 코드를 동일한 CRC 발생코드로 나눈다.
-
나머지가 '0' 이면 오류가 발생하지 않은 것이고 나머지가 '0' 이 아니면 전송과정에서 오류가 발생한 것이다.
CRC 처리과정에서 modulo-2 연산이 사용되는데, modulo-2 연산은 Exclusive-OR(EX-OR) 연산과 동일하다.
CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 오류들을 검출하는 데 탁월하다.
하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.
Reference
Reference book
• 데이터베이스 인터널스
Reference URL
• https://steemit.com/kr/@modolee/floating-point
• https://genesis8.tistory.com/37
• https://en.wikipedia.org/wiki/Serialization
• https://blog.naver.com/newbongman/222031618154
• https://blog.naver.com/seo0511/10131936944
Principal DBA(MySQL, AWS Aurora, Oracle)
핀테크 서비스인 핀다에서 데이터베이스를 운영하고 있어요(at finda.co.kr)
Previous - 당근마켓, 위메프, Oracle Korea ACS / Fedora Kor UserGroup 운영중
Database 외에도 NoSQL , Linux , Python, Cloud, Http/PHP CGI 등에도 관심이 있습니다
purityboy83@gmail.com / admin@hoing.io