Security Note

SQLite는 하나의 데이터베이스를 하나의 파일로 관리한다.

그에 사용되는 데이터베이스 파일은 다음의 구조로 이루어져 있다.

1. Header page
   1) Database header (size: 0x64)
   : Database에 대한 정보를 가지고 있다.
   - DB size, Text Encoding 방식, page size, number of pages 등

   2) Schema Table
   : Database내에 있는 table, index 테이블에 대한 스키마 정보를 가지고 있다.
   - 테이블 유형(table / index), root page offset, CREATE 시 사용한 query 텍스트
   - 데이터베이스 내에 있는 하나의 테이블에 대한 정보가 Schema Table의 하나의 레코드로 저장되어 있다.
   ** 여기 자체로 또 하나의 page 구조를 보이고 있어서, 여기의 상위를 Header page라고 표현했지만
      사실상 그냥 Database file header와 Schema page가 있다고 생각하는 게 더 간편하다.

2. Interior Page, Leaf Page (B+Tree)
: Schema Table에서 얻을 수 있는 root의 offset을 이용하여 각 테이블의 root page에 접근할 수 있다.
테이블 내에 저장된 레코드가 하나의 page를 넘어가지 않을 경우 단일 leaf page에 저장되고 root page offset은 이 leaf page를 가리키게 된다. 그러나 레코드의 개수가 하나의 페이지를 넘어설 경우 여러 leaf page를 통해 저장되고 이 여러 leaf page들의 offset을 포인터로 가지는 interior page의 offset이 root page offset에 저장된다.

3. Overflow Page, Free Page
- Overflow Page : 데이터를 한 페이지에 전부 담을 수 없는 경우 생성되는 페이지
- Free Page : overflow page를 가지고 있던 레코드가 삭제된 경우 overflow가 free page로 전환되어 생기는 페이지

여기까지 설명한 데이터베이스 구조를 도식화시키면 다음과 같다.

아래는 Header page에 있는 Database Header와 그 이후의 Schema Table을 가리키는 header 정보를 캡처한 것이다.
header 정보를 이용하여 Schema를 찾아가는 법에 대해서는 곧바로 나올 page 구조에 대해 이해하면 알 수 있다.

위에서 page라는 용어를 계속 사용하였는데, 이는 SQLite에서 채택한 구조인 B+Tree에서의 하나의 노드라고 생각하면 된다.

데이터베이스 파일 내에서 사용되는 페이지의 유형은 Header Page를 제외하고 크게 Interior page와 Leaf page로 나눌 수 있다.

Interior page에는 Leaf page를 가리키는 cell만이 존재할 뿐 실제 DB 데이터는 모두 Leaf page에 저장되어 있다. 따라서 레코드 탐색 시 각 table의 Schema Table에 있는 root page offset에서 시작하여 Leaf page가 나올 때까지 순회한다.

Leaf page도 Interior page와 구조는 비슷하나, cell에 Leaf page의 offset이 아닌 실제 데이터베이스에 저장된 데이터가 있다. 하나의 cell에는 데이터베이스 내의 하나의 레코드에 해당하는 데이터가 있다.

이러한 Page는 다음의 구조로 구성된다.

1. Page Header
   (size: 0x0C - Interior / 0x08 - Leaf)
   : Page에 대한 정보를 가지고 있다. page의 유형에 따라 header의 크기가 달라진다.
   - Offset 0 : 0x05 - Interior / 0x0D - Leaf

2. Cell Offset
(2 bytes array)
: 배열 형태로 각 cell에 대한 offset을 저장한다.
배열에 저장된 각 offset이 가리키고 있는 cell은 페이지의 마지막부터 채워진다.
page header와 cell offset이 페이지 상단부터 채워지고, cell의 데이터가 페이지의 하단부터 채워지는 구조이다. 이것에 의해 페이지의 중간에 free space가 생기게 된다.

파일 구조를 따라가다 보면 number와 offset이라는 용어를 마주하게 된다.

number는 주로 page를 찾아갈 때 사용되고, offset은 셀을 찾아갈 때 사용된다.

이 둘은 계산하는 방법이 조금 다른데,

page number로부터 파일 내에서의 page offset을 구하기 위해서는 다음의 수식이 사용된다.
page offset = (page number - 1) * page size
page size는 database header의 offset 0x10에 있는 2 bytes를 통해 알 수 있다.

주어진 cell offset으로부터 파일 내에서의 offset을 구하기 위해서는 다음의 수식이 사용된다.
(파일) cell offset = 해당 page의 시작 offset + (주어진) cell offset

여기까지의 내용을 가지고 Header page에서부터 특정 테이블의 record에 접근하는 과정을 따라가 보면 다음과 같다.

연두색으로 형광표시해둔 곳을 대표로 따라가 보았다.
여기서는 root page로 곧바로 leaf page가 나와서 금방 record에 도달할 수 있었는데, interior page가 나오는 경우에 대해서도 보자면 다음과 같다.

마지막으로 레코드 안에 있는 각 칼럼의 데이터를 파싱 하기 위한 레코드 구조에 대해 살펴보려고 한다.

SQLite에서는 파일 용량을 절약하기 위한 방법으로 variable length integer(일명 varint)를 사용한다.
이는 1~9 byte의 크기를 가지는 가변 길이 정수를 말하는데, 각 바이트의 MSB는 다음 바이트의 유무를 나타내는 비트로 사용하고 실제 데이터는 나머지 7개의 비트에 저장한다. MSB가 1일 경우 표현하려는 정수가 7비트의 표현 범위를 넘어가 다음의 추가적인 바이트를 사용한다는 의미를 가지며, 0일 경우는 해당 바이트가 해당 필드의 마지막 바이트라는 것을 의미한다. 이러한 표현방식을 이해하기 위해 다음의 예제를 살펴보자.

ex. varint 0x8106 이 나타내는 정수는?
0x8106 = 10000001 00000110 (2진수)
첫 번째 바이트는 MSB가 1이고 1의 데이터를 가진다. 첫 번째 바이트의 MSB가 1인 것에 의해 두 번째 바이트도 살펴봐야 되는 상황이 되었는데, 두 번째 바이트의 MSB는 0이므로 더 이상의 추가적인 바이트를 사용하지 않는다.
따라서,
(첫 번째 바이트의 하위 7비트) : (두 번째 바이트의 하위 7비트) = 1 0000110 (2진수) = 0x86 의 정수를 나타내는 varint임을 알 수 있다.
(콜론(:)은 두 묶음의 7비트들을 나란히 이어붙이는 것을 의미한다.)

아래의 record 구조에 등장하게 되는 cell header와 record의 length of data header에서 이러한 varint 타입을 사용하여 값을 표현한다.

cell offset을 통해 레코드에 접근한 후 순차적으로 Length of Record와 Row ID의 값을 구하고 이어서 Length of Data Header도 구할 수 있게 된다. 이때 구하게 되는 Data Header의 길이는 Length of Data Header 필드가 차지하는 길이도 포함된 값이므로, data field만의 길이를 구하기 위해서는 Length of Data Header의 값에서 이 필드가 차지하는 길이만큼을 빼주어야 한다.

이러한 작업을 통해 data field의 갯수를 구하게 된 뒤에는 이 갯수만큼 data header의 값을 순차적으로 읽고 다시 그 값만큼의 데이터를 읽어 나가는 방식으로 데이터를 파싱하면 된다.

그 과정에서 만나게 되는 data header의 size of field에는 각 칼럼에 해당하는 데이터 타입 및 크기에 대한 정보가 저장되어 있다.
각 값에 따른 데이터 타입 및 크기에 대한 정보는 다음의 표를 참고하면 알 수 있다.

여기까지의 정보를 이용하면 아래와 같이 record 내의 필드값을 파싱해낼 수 있다.

이 글에서 다룬 내용을 이용하여 하나의 테이블 내에 있는 하나의 레코드의 값을 구하는 흐름을 정리하면 아래와 같다.

이 글은 2021년 11월, Windows 10 Chrome Disk Cache ver 2.0을 기준으로 한 분석 내용임을 밝히고 시작한다.
Chromium Project disk cache 문서의 내용을 바탕으로 분석을 시작하였는데, 실제 로컬에 저장된 내용과 차이가 있는 부분이 있어서 그러한 내용을 중심으로 글을 작성하였다.

Cache Directory 경로

C:\Users\<username>\AppData\Local\Google\Chrome\User Data\Default\Cache

Disk Cache 구조

Chrome에서는 각 캐시 데이터를 entry 단위로 저장한다.
disk cache에 저장되는 모든 데이터는 그것이 저장되어 있는 위치를 가리키는 cache address를 가지고 있다.
앞서 캐시 데이터 저장에 사용된다고 했던 entry 역시 그러한 cache address를 가지고 있다.
이 정도의 정보를 가지고 아래의 구조도를 보도록 하자.

Chromium design document disk_cache 문서에 의하면 disk_cache는 다음의 세 가지 유형에 해당되는 파일로 이루어져 있다.

- index : 캐시 데이터 추적의 시작.
  캐시 데이터가 다운로드된 url의 해시값을 키로 하고 그에 대응되는 값으로 entry의 cache address를 가지는 해시 테이블이 저장된 파일. header가 존재한다(그림 1).

- data_x (block file) : 리소스 데이터가 저장된 파일.
  HTTP header부터 시작해서 실제 캐시의 raw 데이터까지 저장되어 있다. header가 존재한다(그림 2).
  각 파일별로 주로 저장되는 데이터의 유형이 다르다.. (ex. data_1 에는 entry가 저장된다.)

- f_0000xx (separate file) : 크기가 큰 캐시 데이터를 저장하는 파일.
  캐시 데이터가 kMaxBlockSize 보다 클 경우 block file 내에 저장되지 못하고 별도의 파일에 저장된다. (kMaxBlockSize = 16KB)
  separate file은 index, block file과 달리 파일 자체의 헤더가 존재하지 않고 오로지 캐시의 raw 데이터만 저장된다.

- 참고: block file의 body내용은 offset 0x2000부터 있다.

이 내용을 바탕으로 실제 내 컴퓨터 환경의 disk cache를 분석하였는데, index file에서 해결되어야 할 entry의 cache address가 data_0 file에 담겨있었다. 아래 (그림 3)에서도 볼 수 있다시피 해시 테이블이 시작되어야 할 위치인 0x160 이후로 데이터가 매우 드물게 존재하고 있다. 반면에 data_0 파일에서는 0x24 bit 단위로 캐시 데이터가 저장되어 있으며 이 중 빨간색으로 표시된 부분이 entry address이다.

이밖에도 11월 14일 기준으로 확인해봤을 때 data_0 파일과 달리 index 파일은 여전히 마지막 수정일이 10월 29일에 멈춰있다.

이러한 정황들을 통해 index 파일보다는 data_0 파일의 entry address가 더 신뢰성 있다고 판단하여 이를 가지고 분석을 이어나갔다.

Cache Address 읽는 법

Chromium disk cache 문서에 의하면 cache address는 크게 3가지 유형으로 나뉜다.

- 0x00000000 : 정의되지 않음

- 0x8000002A : separate file (file name: f_00002A)

- 0xA0010003 : data_1 block file의 0x0003번째 block

정의되지 않은 경우와 separate file 의 경우는 이 정보만을 가지고 데이터를 찾아갈 수 있다.
하지만 block file에 저장된 데이터의 경우 이 정보만으로는 실제 위치를 알아내기가 어렵다..
그래서 추가적으로 조사한 결과 아래와 같은 규칙을 찾았다.

data_1에 저장된 경우 : 0xA0010003
-> 0x0003 * 0x100 + 0x2000 = 0x2300 (data_1 file)

data_2에 저장된 경우 : 0xA0020004
-> 0x0004 * 0x400 + 0x2000 = 0x3000 (data_2 file)

data_3에 저장된 경우 : 0xA0030005
-> 0x0005 * 0x1000 + 0x2000 = 0x7000 (data_3 file)

cache address로부터 해당 주소가 어느 파일에 저장된 경우인지를 얻은 후,
block number와 각 파일별로 가지는 block size를 곱해주고 파일 body의 시작 offset인 0x2000을 더하면 해당 데이터의 진짜 offset을 얻을 수 있다.

여기서 block size는 각 block file header의 entry_size 필드의 값으로부터 얻을 수 있다.
(data_1 : 0x100, data_2 : 0x400, data_3 : 0x1000)

이러한 정보를 이용하여 cache address를 따라가 보면 다음과 같이 entry를 만날 수 있다.

Chromium 문서에 의하면 하나의 entry에 data stream이 4개까지 존재할 수 있다고 하는데, 이렇게만 들으면 잘 와닿지 않는다.
그래서 직접 각각의 data stream cache address를 따라가보면 또 하나의 규칙을 발견할 수 있다.

1. data stream[0] 에는 주로 meta data 가 저장된다. 그 캐시가 저장된 http header가 저장되어 있고 이곳에서 content-type, filename 등의 정보를 얻을 수 있다. 이 meta data를 가리키는 cache address는 C로 시작된다는 것 외에는 이전에 봤던 유형과 크게 다르지 않다.
0xC103406E : data_3 block file의 0x406E번째 block
-> 0x406E * 0x1000 + 0x2000 = 0x4070000 (data_3 file)

2. data stream [1] 이후에는 주로 캐시 데이터가 저장된다. separate file을 가리키는 주소일 수도 있고, block file 내에 저장된 데이터를 가리키는 주소일 수도 있다.

이렇게 하나하나 따라가다 보면 아래와 같은 흐름으로 캐시 데이터를 얻을 수 있게 된다.

참고 자료

- Chromium disk cache docs
https://www.chromium.org/developers/design-documents/network-stack/disk-cache
- Chromium disk cache v3 docs
https://www.chromium.org/developers/design-documents/network-stack/disk-cache/disk-cache-v3
- Chromium disk cache, disk_format.h
https://chromium.googlesource.com/chromium/src/net/+/15905ac8d688a9910055170314839dc7dc7b2f75/disk_cache/disk_format.h

하드디스크 구조에 대해 공부한 것을 간단히 정리했다.

하드디스크를 크게 6가지 구성으로 나누면 다음과 같다.
1. 전원 커넥터(Power Connector) : 하드디스크에 전원을 공급하는 역할
2. 데이터 커넥터(IDE Connector) : 하드디스크와 컴퓨터 사이의 데이터를 송수신하는 역할
3. 헤드(Head) : 데이터를 읽는 역할.
4. 액츄에이터암(ActuatorArm) : 데이터를 읽을 위치로 헤드를 이동하는 역할
       헤드와 암은 플래터의 위아래 모두 존재할 수 있으며 한 쌍으로 생각할 수 있다.
5. 플래터(Platter) : 실제 데이터가 저장되는 곳
6. 스핀들(Spindle) : 플래터를 회전시키는 역할

이 중 데이터를 저장하는 곳인 플래터를 단면으로 살펴보면 다음과 같다.

A. 트랙 : 중심으로부터 같은 거리에 있는 섹터들의 모음. 원심 전체를 하나의 트랙이라고 한다.
B. 섹터 : 하드 드라이브의 최소 기억 단위이자 디스크 시스템에 데이터가 쓰여지거나 읽혀지는 물리적인 단위.
              트랙의 일부를 일정 단위로 자른 것.
              전통적으로 하드 디스크 드라이브(HDD)는 512byte, 신형 HDD(Advenced Format, AF)는 4096byte 섹터를 사용한다.
              섹터 헤더, 데이터 영역, 오류 정정 코드(ECC)로 이루어진다.
              - 섹터 헤더 : 디스크와 컨트롤러가 사용하는 정보(동기 바이트, 주소 식별 정보, 결함 플래그, 헤더 패리티 바이트)
              - 데이터 영역 : 기록된 사용자의 데이터
              - 오류 정정 코드(ECC) : 데이터에 유입될 수 있는 오류를 검사, 정정하는데 사용
C. 트랙 섹터 : 같은 구역에 있는 섹터의 집합
D. 클러스터 : 섹터를 일정한 단위로 묶어서 데이터의 입출력 단위로 사용하는 것. 기본 4096byte
              파일을 저장하도록 할당될 수 있는 가장 작은 논리 디스크 공간이므로, 만약 파일 크기에 비해 클러스터 크기가 크다면 그만큼의 디스크 공간이 낭비되게 된다. (이 때 낭비되는 공간을 slack space라고 한다.) 하지만 클러스터가 커질 경우 입출력 시 오버헤드와 단편화가 줄어들어 읽기 속도와 쓰기 속도 모두를 개선할 수 있다. 
              클러스터로 묶여있는 섹터들은 논리적으로 인접해있기 때문에 꼭 물리적으로 인접해있을 필요는 없다.

**
디스크 팩 : 보다 큰 용량의 데이터를 저장하기 위해 하나 이상의 플래터들을 모아 같은 중심축에 쌓아 놓은 것.
실린더 : 하나의 디스크 팩에서 반지름의 길이가 같은 위치에 있는 트랙들의 집합.
             아래 그림에서 3개의 플래터에 표시되어 있는 부분이 모두 하나의 실린더를 의미한다.
             일반적으로 데이터를 순차적으로 저장할 때 실린더 단위로 저장한다.

Slack Space

: 논리적인 크기와 물리적인 크기의 차이로 인해 낭비되는 공간

- 램 슬랙(RAM Slack) : 섹터에 할당하고 남은 비할당 영역. 섹터 크기보다 작은 파일이 할당될 경우 발생.
- 파일 슬랙(File Slack) 또는 드라이브 슬랙 : 클러스터에 할당하고 남은 비할당 영역. 
         하나의 클러스터 안에 여러 섹터가 존재할 때, 섹터 내에 남은 공간은 램 슬랙, 다른 남은 섹터가 있을 경우 이들을 파일 슬랙이라고 함.
- 볼륨 슬랙(Volume Slack) : 하드디스크를 논리 단위인 파티션으로 할당한 후 남는 영역.
- 파일시스템 슬랙(File System Slack) : 하드디스크를 논리 단위인 클러스터로 할당하고 남는 영역.
         볼륨 슬랙과 파일시스템 슬랙은 메모리를 원하는 단위로 나누고 남은 나머지. 파일을 할당하고 남은 것이 아님.

주소지정방식

각 섹터에 있는 데이터를 읽어오기 위해서는 해당 위치의 주소를 이용하여 접근해야한다.
이를 위해 섹터별로 가지고 있을 주소가 필요한데 이 주소를 지정하는 방식에 대한 논의이다.

1. CHS(Cylinder-Head-Sector) 방식
: 실린더, 헤드, 섹터의 물리적인 구조에 기반을 둔 방식.
실린더, 헤드, 섹터 각각의 위치가 지정되고 하드디스크 컨트롤러에 의해 그 위치로 이동하여 데이터를 읽는 것.
CHS(19, 2, 10)일 경우 2번째 헤드를 19번째 실린더, 10번째 섹터에 위치하도록 한다.
하드웨어 입출력 과정에 관여하는 BIOS에 한계가 있어 고용량 디스크에 사용되기 어려워 현재는 쓰이지 않는 방식이다.

2. LBA(Logical Block Addressing) 방식
: 각 섹터별로 논리적인 번호를 부여하는 방식. 
논리적인 번호와 해당 섹터의 위치 간 관계는 디스크 컨트롤러에서 관리한다.

섹터는 1부터 시작하기 때문에 LBA 주소가 0이라면 CHS 주소는 (0, 0, 1)이 된다.
LBA 주소가 1이라면 CHS주소는 (0, 0, 2)가 된다.

이를 이용하여 CHS와 LBA 간의 주소 변환 과정을 살펴보면 다음과 같다.

최근의 디스크들은 ZBR(Zone Bit Recording)이라고 하는 방식을 사용하는데, 이는 바깥쪽 트랙이 안쪽 트랙보다 길이가 더 길다는 점을 이용하여 바깥쪽 트랙에 더 많은 섹터를 할당하는 방식이다. 따라서 이러한 방식을 사용하는 디스크의 경우에는 CHS와 LBA 변환 시 트랙별로 섹터 갯수가 달라지는 것까지 고려해야할 것이다.