'sqlite'에 해당되는 글 9건

  1. 2009/04/03 SQLite 사용자 함수 추가 by eminency
  2. 2009/02/10 SQLite 페이지 핸들링(3) - 레코드 포맷 by eminency
  3. 2008/09/30 SQLite 페이지 핸들링(2) - SQLite의 페이지 포맷 by eminency
  4. 2008/08/03 SQLite 페이지 핸들링(1) - SQLite의 구조 by eminency
  5. 2008/07/22 SQLite R-tree 지원 예정 by eminency (1)
  6. 2007/08/20 SQLite non-C API 소개 by eminency (3)
  7. 2007/08/08 SQLite C API 소개 by eminency (4)
  8. 2007/07/06 Thread-safe(3) : Lock in SQLite by eminency
  9. 2007/06/08 SQLite의 라이센스 by eminency
SQLite는 꽤 유연하게 만들어져 있습니다.
일종의 plug-in을 만들어 extension으로 로드도 가능하고, 일반적인 함수(substr) 혹은 aggregate 함수(sum,count,avg..)도 구현해서 붙일 수 있습니다.

근데 너무 유연해서인지 함수가 너무 부족하더군요 -_-;;;
바로 예전 글에서(http://jeminency.tistory.com/114) Perl로 구현하기 전에 Sed와 Python 스크립트로 구현했다고 적었는데 그 때 SQLite에 집어넣었었습니다.

마침 이번에 좀 복잡한 통계 데이터를 뽑을 일이 있어서 새로 Python 프로그램으로 SQLite에 저장된 DB를 활용했는데 그 통계라는 것에 분산이나 (표준)편차가 필요한 실정이었습니다. 다시 말하면 pow나 sqrt가 꼭 필요었는데 SQLite 함수에는 이게 없더군요 -_-;;;
SQLite의 단점이랄까요. 문서화가 잘 되어 있지만 업데이트가 잘 안된다는 점과(현재 버전이랑 내용에 차이가 있습니다) 기본적인 기능은 잘 구현되어 있으나 부가기능은 좀 없다는 거...
물론 파일 DB니까 너무 많은 걸 바라면 안되겠지요 -_-; 하지만 숫자 관련 함수가 abs, round 정도밖에 없다는 건 좀...ㅡㅡㅋ

좌우지간 그래서 pow 함수만이라도 간단하게 구현을 해보았습니다.
일단 함수를 등록하는 SQLite API에 대한 설명부터 간단히 해 보겠습니다.

int sqlite3_create_function(
  sqlite3 *db,
  const char *zFunctionName,
  int nArg,
  int eTextRep,
  void *pApp,
  void (*xFunc)(sqlite3_context*,int,sqlite3_value**),
  void (*xStep)(sqlite3_context*,int,sqlite3_value**),
  void (*xFinal)(sqlite3_context*)
);


만든 함수는 위의 함수로 등록합니다.

인자를 알아야겠죠?
db는 SQLite 3의 db 핸들러입니다. zFunctionName은 SQL에서 쓰일 함수의 이름이구요.
nArg는 함수에 들어갈 인자의 갯수입니다. SQL은 일종의 function overloading을 지원하죠. 그러므로 같은 이름의 함수에 인자 수가 다른 버전을 만들어 줄 수 있습니다. 예를 들면 substr(A,B)도 가능하고 substr(A,B,C)도 가능합니다.
eTextRep는 함수 인자가 어떤 텍스트 인코딩으로 들어올 지를 결정합니다. SQLite의 함수들은 UTF-8과 UTF-16을 모두 지원하도록 하여야 하지만 함수의 구현에 따라 특정 인코딩이 더 성능이 좋은 경우가 있으므로 그를 알려주기 위함입니다(제가 만들 함수는 인코딩과 상관없으므로 SQLITE_ANY를 줍니다).
다섯번째의 pApp는 사용자 데이터 포인터입니다. 함수 실행에 인자 외에 다른 데이터가 필요한 경우 저 인자를 통해 함수에 넘겨 줄 수 있습니다.

마지막의 함수 포인터 세 개가 핵심이라고 할 수 있는데요.
xFunc는 실제 함수의 구현입니다.
xStep과 xFinal은 aggregate 함수의 구현입니다. xStep은 매 레코드마다 실행할 함수이며 xFinal은 종료시 사용합니다. 예를 들어 sum이라면 xStep 함수는 더하기만 해주고 xFinal은 결과를 가공하고 판단해서 돌려주거나 에러를 내뱉는 식입니다.

구현 함수의 인자도 알아야겠죠? -_-
첫번째의 sqlite3_context*는 말 그대로 함수를 위한 컨텍스트 정보입니다만 굳이 함수 구현에서는 쓸 일이 없습니다. 함수 결과값을 돌려주기 위한 정도?
그리고 두번째는 받아 온 함수의 인자 갯수, 세번째는 인자의 배열입니다.

실제 구현을 그럼 보시면서...
구현은 SQLite extension으로 했습니다.

#include <stdio.h>
#include <sqlite3ext.h>
SQLITE_EXTENSION_INIT1  // api 함수 포인터 배열을 선언하는 매크로

typedef long long i64;

// 실제 pow 함수 구현
static void
powFunc(sqlite3_context *ctx, int argc, sqlite3_value **argv)
{
    // 8byte int형 인자 두 개를 받아 옴
    int i;
    i64 iVal1 = sqlite3_value_int64(argv[0]);
    i64 iVal2 = sqlite3_value_int64(argv[1]);
    i64 result = 1;

    // 곱해서 결과값 구함
    for (i=0; i<iVal2; i++)
        result *= iVal1;

    // context에 결과값 리턴
    sqlite3_result_int64(ctx, result);
}

// extension init 함수(실제 함수 구현과는 연관없음)
int
sqlite3_extension_init(sqlite3 *db, char **pzErrMsg, const sqlite3_api_routines *pApi)
{
    // SQLite3 엔진에서 받아 온 API 리스트 등록
    SQLITE_EXTENSION_INIT2(pApi);

    // 함수 등록
    sqlite3_create_function(db, "pow", 2, SQLITE_ANY, NULL, powFunc, NULL, NULL);
    return 0;
}

보시다시피 SQLite의 SQL 함수 구현이므로 SQLite의 API를 사용하는 것은 필수적입니다.
위에서만 해도 sqlite3_value_int64와 sqlite3_result_int64의 두 가지 api를 사용했죠. 이 두가지 함수는 8 byte int를 DB엔진에서 가져오고 되돌려주는 역할을 합니다. DB 타입이 C 타입과 완전히 똑같지는 않으므로 이런 레이어는 꼭 필요합니다.

처음의 SQLITE_EXTENSION_INIT1과 init안의 SQLITE_EXTENSION_INIT2(pApi); 매크로가 이 api들을 가져오는 역할을 합니다. 외부에서는 이 과정을 거치지 않으면 SQLite의 내부 api를 쓸 수 없으니까요(SQLite 소스에 직접 패치해서 쓴다면 위의 과정은 필요치 않고 func.c에 등록하는 함수들의 배열이 있는데 여기에 추가만 해주시면 됩니다)

그 다음에는 등록을 위해 sqlite3_create_function을 호출하죠.
마지막 함수 포인터 세 개 중 첫 번째만 쓰고 두세번째는 NULL인데 aggregate 함수라면 첫번째를 NULL로 하고 두세번째에 등록을 해주면 됩니다.

그 외 실제 함수 구현은 설명할게 별로 없군요. 보시는 대로입니다.
실행은 다음과 같습니다.

$ gcc -shared mathfunc.c -o math.so
$ sqlite3
SQLite version 3.4.2
Enter ".help" for instructions
sqlite> .load math.so
sqlite> select pow(2,3);
8
sqlite> select pow(2,10);
1024
sqlite> select pow(10,3);
1000

참 쉽죠? -_-

.load 커맨드는 내부적으로 dl_open()을 쓰는데 결국 공유라이브러리 링크와 마찬가지이므로 LD_LIBRARY_PATH에 math.so의 패스가 잡혀 있어야 합니다.

그리고 위의 함수는 그닥 stable 하지 않습니다. 그대로 갖다 쓰는 건 자제해 주세요 -_-;;
SQLite도 DB이므로 당연 데이터 타입들이 있는데 위의 코드는 타입 체킹도 전혀 하지 않고 오버플로우 처리 같은 것도 없기 때문에 문제를 일으킬 소지가 많습니다.

그럼 다음에 또 좀 더 detail한 내용으로...
이올린에 북마크하기(0) 이올린에 추천하기(0)
Posted by eminency
이전 목록:
SQLite 페이지 핸들링(1) - SQLite의 구조
SQLite 페이지 핸들링(2) - SQLite의 페이지 포맷

아마 페이지 핸들링 관련한 마지막 글이 될 것 같군요. B+ Tree에 대해 다룰까도 생각했는데 이건 워낙 유명한 알고리즘이고 하니 굳이 쓸 필요가 있을까 싶네요.


Record Format

예전 글들을 보시면 알겠지만 SQLite는 BTree의 leaf 페이지에 cell들을 저장한다고 표현했습니다. 이 cell이란 것이 테이블 페이지라면 곧 하나의 레코드가 되며, 인덱스 페이지라면 하나의 인덱스 엔트리가 됩니다.
search를 위한 자료구조는 보통 정렬 및 검색을 위한 key와 실제 값인 data의 페어로 하나의 아이템이 이루어지게 되는데 테이블 페이지의 경우 key는 row ID, data는 레코드가 되며 반대로 인덱스 페이지라면 key는 인덱스 키, data는 row ID가 됩니다.
row ID는 레코드를 구분하기 위해 레코드가 삽입될 때 DB 내부적으로 부여되는 숫자 키라고 보시면 되겠습니다. 즉 테이블은 row ID에 따라(결국 insert한 순서대로) 정렬되어 있고, 인덱스는 사용자가 지정한 키에 따라 정렬이 되어 있으며 데이터로는 실제 레코드의 위치를 찾기 위해 row ID를 갖고 있는 것입니다.

예를 들어 다음과 같은 스키마를 생각해 보죠.

CREATE TABLE employee (id INT, name TEXT, salary INT, title TEXT);
CREATE INDEX idx_title_salary ON employee(title, salary);


별로 좋은 예 같지는 않지만... 사원 테이블과 직급별 급여를 검색하기 위한 인덱스입니다 -_-;
그럼 위에 제가 설명한대로 페이지의 셀은

employee 테이블 페이지 :  < rowID || id, name, salary, title >
idx_title_salary 인덱스 페이지 : < title, salary || row ID >


대략 이런 식이 되겠죠.
그럼 이게 끝? ...일 리가 없겠죠? -_-

데이터의 길이가 레코드마다 다르니 Cell의 길이도 레코드마다 다를 수 밖에 없고 그럼 페이지에서 읽어올 때 어디까지 읽어와야 될 지 알 방법이 없습니다. 게다가 어디까지가 key이고 어디부터가 data인지도 알 수가 없죠. 이런 정보들이 Cell Header에 포함됩니다.
실제 Cell의 포맷은 다음과 같습니다.

 Bytes 내용 
 4  Left Child의 페이지 번호, leaf page에서는 생략 
 varint  data 부분의 바이트 길이, zerodata flag가 세팅되어 있으면 생략
 varint  key 부분의 바이트 길이, intkey flag가 세팅되어 있으면 key값을 그대로 저장
 *  Payload
 4  overflow 체인의 첫번째 페이지 번호. overflow가 아니면 생략

첫번째는 B+ Ttree의 internal 페이지일 때(leaf가 아닐 때) left child가 되는 페이지의 번호입니다. B+ tree에서 하나의 페이지에 매달리는 자식 페이지의 수는 (아이템 수+1)이 된다는 건 잘 아실겁니다. 가장 오른쪽 페이지 번호는 페이지 헤더에 저장되죠(이전 글 참조). 그러므로 leaf page에서는 필요없는 부분이구요.

두번째는 payload의 data 부분의 바이트 길이입니다. varint라고 표시되어 있는데 이는 Variable Integer를 의미하며 SQLite에서 사이즈를 줄이기 위해 구현한 특수한 Integer Type입니다. 이에 대해선 뒤에 다루겠습니다.
data 부분은 zerodata flag가 셋팅되어 있으면 생략됩니다만 거의 쓰이지 않습니다(이 flag는 바로 page header의 첫번째, 1바이트짜리 필드입니다).

세번째는 payload의 key 부분의 바이트 길이입니다. data 부분과 유사하게 intkey flag가 세팅되어 있으면 바이트 길이가 아니라 integer key 값을 그대로 저장합니다. 대신 payload의 key 부분이 생략되겠죠.

그리고 네번째의 payload는 실제 키/데이터 페어의 공간이며, 마지막의 overflow page number는 데이터가 오버플로우 될 경우 넘치는 부분의 데이터를 따로 오버플로우 페이지를 만들어서 저장하는데 그 첫번째 페이지 번호를 저장합니다. 물론 오버플로우가 아니면 생략이죠.


Variable Integer

여기서 varint란 것에 대해서 짚고 넘어가야겠네요.
예를 들어 row ID의 경우 최대값을 얼마로 잡아야 될까요? row ID 표현을 위해4바이트 int 타입을 쓸 경우, 웬만한 테이블의 경우 10만건을 넘는 경우가 드물다고 가정하더라도 대부분의 레코드에서는 각 레코드당 1~2바이트씩은 손해를 보게 되는 셈입니다.

이런 공간낭비를 절약하기 위해 SQLite에서는 Variable Integer라는 가변형 숫자 타입을 사용합니다.
기본 아이디어는 숫자 크기에 적절한 바이트를 사용하는 것이며 한 바이트의 첫번째 비트는 다음 바이트가 있는지 없는지를 표시합니다.
즉 한 바이트당 7비트를 사용해 수를 표시하는 거죠. 그리고 최대 9바이트를 사용하며 마지막 바이트는 8비트를 모두 쓰게 됩니다. 그러므로 7*8+8 = 64, 최대 9바이트를 써서 64비트 정수까지 표현하게 되는 겁니다.

로직을 다시 설명하면,

1. 한 바이트를 읽음
2. 첫 비트가 1이면 나머지 7비트를 저장해놓고 다음 바이트로 넘어감(1번에서 다시 반복)
3. 첫 비트가 0이면 저장된 값과 현재 바이트의 7비트를 합쳐 값 계산.
3-1. 9번째 바이트일 경우는 멈추고 저장된 값과 현재 바이트를 합쳐 값 계산.

대충 이런 식입니다.
물론 기본 int 타입에 비해 추가적인 오버헤드가 있겠지만 이 경우에는 공간 낭비를 줄이는게 더 현명한 선택이라고 판단한 거겠죠? 어떤 선택이든 trade-off는 있는 법입니다.

그럼 가볍게 -_- 일반 정수를 varint로 변환하는 함수를 한 번 살펴보겠습니다. 실제 소스의 util.c에 있습니다(주석은 물론 제가 단 거..).

/*
** varint의 인코딩 layout
**
** KEY:
**         A = 0xxxxxxx    데이터 7비트와 플래그 1비트(다음 바이트 없음)
**         B = 1xxxxxxx    데이터 7비트와 플래그 1비트(다음 바이트 있음)
**         C = xxxxxxxx    데이터 8비트
**
**  7 bit 정수 - A
** 14 bit 정수 - BA
** 21 bit 정수 - BBA
** 28 bit 정수 - BBBA
** 35 bit 정수 - BBBBA
** 42 bit 정수 - BBBBBA
** 49 bit 정수 - BBBBBBA
** 56 bit 정수 - BBBBBBBA
** 64 bit 정수 - BBBBBBBBC
*/


/*
* @name : sqlite3PutVarint
*
* @args
*   p : 변환된 varint 값(out)
*   v : 변환시킬 정수값(in)
*/

int
sqlite3PutVarint(unsigned char *p, u64 v)
{
    int i, j, n;
    u8 buf[10];

    /*
     * v의 most significant 바이트에 값이 있는지 검사
     * (즉, 가장 큰 바이트에 값이 있을 경우는 8바이트 정수이므로
     * 무조건 9바이트의 varint가 필요)
     */

    if( v & (((u64)0xff000000)<<32) )
    {
        /* v의 가장 작은 바이트 값이 p의 9번째 바이트에 assgin */
        p[8] = v;

        /* v를 1바이트 right shift */
        v >>= 8;

        /* 루프를 돌며 7비트씩 assign, 상위 1비트는 모두 1로 해줌 */
        for(i=7; i>=0; i--)
        {
            p[i] = (v & 0x7f) | 0x80;
            v >>= 7;
        }

        /* 바이트 길이(9)를 되돌려 주며 종료) */
        return 9;
    }

    n = 0;

    /*
     * 8바이트 크기 정수가 아닌 경우는 첫번째 비트를 1로 하면서
     * 7비트씩 차례로 buffer에 인코딩
     * (현 시점에서는 바이트 길이를 판단하기 힘드므로 가장 마지막 바이트
     * 를 buf[0]에 assign하면서 역순으로 처리)
     */

    do{
        buf[n++] = (v & 0x7f) | 0x80;
        v >>= 7;
    } while( v!=0 );

    /*
     * 인코딩 종료 후 마지막 바이트의 첫번째 비트를
     * 다시 0으로 만듬
     */

    buf[0] &= 0x7f;
    assert( n<=9 );

    /* output 변수에 바이트 순서를 뒤집어서 copy */
    for(i=0, j=n-1; j>=0; j--, i++)
    {
        p[i] = buf[j];
    }

    return n;
}

어때요, 참 쉽죠? -_-;;;

사족을 달자면, 로직과 실제 구현은 디테일한 부분에 있어서 간극이 생길 수 밖에 없습니다. 예를 들면 바이트 순서를 뒤집어 카피하는 부분같은 거 말이죠.
로직이나 알고리즘 등이 전략이라면 저런 디테일한 부분은 전술에 비유될 수 있겠네요. 어느 쪽이든 엔지니어의 역량이 발휘되어야 겠지만, 양쪽에 필요한 능력은 약간은 다른 것 같기도 합니다.


Payload Format

그럼 마지막으로 실제 key와 data가 담기는 Payload의 포맷을 살펴보겠습니다.
key와 data가 각각 동일한 레코드 포맷을 갖고 있으므로 아래 살펴 볼 포맷 두 개의 연속쌍이 하나의 payload라고 보시면 되겠습니다.
물론 intkey 셋팅인 경우는 key 파트가 생략되거나 하는 예외는 있습니다.

하나의 레코드는 다음과 같이 구성됩니다.

 hdr-size type 0  ...  type N-1  data 0  ...  data N-1 

N은 테이블 페이지라면 컬럼 갯수가 됩니다. 인덱스라면 키의 갯수겠죠.
hdr-size는 varint이며 레코드의 시작부터 data 0이 시작되는 부분까지의 바이트 길이입니다.
type 필드는 각각의 매치되는 data의 타입과 사이즈를 담고 있습니다. 역시 varint구요.
정수 타입 하나에 타입과 사이즈를 동시에 인코딩해 갖고 있다는게 이해가 살짝 안 될 수도 있지만 다음 설명을 보시면 알 수 있습니다. 여기서도 용량을 아끼기 위한 처절한 노력을 느낄 수 있습니다. -_-;;

각 타입의 번호와 설명입니다.

 type no. byte size  type description
 0  0   NULL 
 1  1  signed integer
 2  2  signed integer
 3  3  signed integer
 4  4  signed integer
 5  6  signed integer
 6  8  signed integer
 7  8  IEEE float
 8  0  integer 상수 0 (v3.3이상)
 9  0  integer 상수 1 (v3.3이상)
 10,11    예약
 12이상의 짝수  (N-12)/2  BLOB
 13이상의 홀수  (N-13)/2  text

다시 한 번 짚고 넘어가자면, SQLite는 data type 구분이 엄격하지 않습니다.
정수의 경우, 일반적인 RDBMS의 tiny int, short int, int, long int등은 SQLite에 존재하지 않으며 입력되는 시점에서 크기가 정해져서 insert됩니다.
고정길이 char 타입도 없으며 char(1)로 선언하든 varchar(10)으로 선언하든 모두 text 타입입니다(char (1)을 선언하고 긴 문자열을 insert해보세요). char나 varchar나 syntax는 받아들이지만 실제 처리는 다 같이 하는거죠 -_-;
그러므로 SQLite를 쓸 때는 data type의 사이즈를 어떻게 할 것인지 너무 고민할 필요는 없습니다.

표를 설명하자면, 0은 NULL이구요.
1~6까지는 바이트 길이에 따라 구분된 int 타입입니다.
7은 흔히 말하는 배정밀도 부동 소수(C의 double)입니다(아, 그러고보니 SQLite에는 Decimal 타입도 없습니다. 오라클의 NUMBER(M,N) 이런 거요).
8과 9는 v3.3 이후로 생긴 타입이라는데 integer 0과 1을 의미하는 상수입니다(1바이트라도 아끼려는 노력...-_-).
10과 11은 이후 버전의 확장성을 위해 비워놓은 타입이고요.
12 이후로 짝수는 BLOB, 홀수는 text 타입을 나타내는데 그 사이즈는 위에 보시는대로 각각 (N-12)/2, (N-13)/2입니다. 절묘하군요 -_-;
그래서 이 두 개의 variable length type이 타입번호에서 맨 뒤로 할당된 것입니다.


지금까지 살펴본대로 SQLite는 DB 페이지의 공간 절약을 위해 variable length data의 표현과 구현에 많은 공을 들인 것을 알 수 있습니다. 실제 데이터와 메타 데이터 양쪽에서 말이죠.
이 특징은 SQLite가 임베디드 분야에서 현재 높은 점유율을 보이는 중요한 특징 중의 하나가 아닐까 하는 생각이 듭니다. 임베디드 디바이스에서 DB를 쓴다면 데이터의 용량 문제는 피해갈 수 없는 난관이기도 합니다.
그러면서도 빠른 처리 속도를 유지하고 있다는 점은 역시 'Simple is the best'를 떠올리게 합니다. 네트웍 코드를 포함하지 않고 SQL 처리와 B+ tree 저장구조에 집중한 점은 바이너리 사이즈 역시 줄여주는 효과가 있었지요.

하지만 또 의외로, Full Text Search 인덱스나 R-tree 인덱스 같은 extension을 구현하여 용도를 다양하게 만드는 전략도 취하고 있는데요.
이후에 SQL을 파헤쳐 볼 지 extension을 다뤄볼지는 아직 고민중입니다만...

SQLite는 보면 볼 수록 재미있는 것 같습니다. 소스가 잘 되어 있는 편이라 오픈소스 입문용으로도 적당한 것 같고요.
다른 (잘 된) 소스를 많이 보는 것은 개발자의 skill level을 높이는데 큰 부분을 차지한다고 저는 생각하거든요 ^^
이올린에 북마크하기(0) 이올린에 추천하기(0)
Posted by eminency
이전 목록:
SQLite 페이지 핸들링(1) - SQLite의 구조

SQLite의 페이지는 대부분 Btree 페이지입니다.
테이블이나 인덱스는 B+ tree 구조로 저장되지요. 다시 말하면 각각의 B+ tree 페이지는 곧 B+ tree의 하나의 노드가 됩니다. 책에서 보던 B+ tree 노드는 대개 3~5개 정도의 아이템을 갖고 있지만 실제 SQLite같은 DB에서는 페이지 사이즈가 1K이므로 키가 int라면 4바이트, 단순히 계산하면 256개의 아이템이 저장되는 셈입니다.
B+ tree에서 하나의 노드는 아래와 같이 표현되지요.

  ----------------------------------------------------------------
  |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
  ----------------------------------------------------------------


Ptr은 자식 페이지를 가리키는 포인터(혹은 SQLite의 경우 페이지 번호), Key는 키값입니다.
Ptr(0)이 가리키는 페이지나 그 하위 페이지들은 Key(0)보다 작거나 같은 키값을 가지는 데이터를 갖고 있고, Ptr(1)은 Key(0) < k <= Key(1)인 k 키값의 데이터들을 갖고 있는 것입니다.
바이너리 트리에 비해 데이터가 매우 많아져도 낮은 depth로 데이터를 찾을 수 있습니다. 물론 페이지 내에서 또 binary search가 이루어지므로 그 비용을 포함하면 결국 검색횟수 자체는 비슷하겠지만요.

그러면 실제 SQLite의 페이지는 단지 위처럼 Key와 Ptr값만을 주루룩 저장하고 있느냐 하면 그것은 물론 아닙니다. 하나의 SQLite B+tree 페이지는 다음과 같은 구조로 이루어집니다(SQLite btreeInt.h의 주석에서 발췌).

    |----------------|
    | file header    |   100 바이트.  Page 1에만 있음.
    |----------------|
    | page header    |   leaf 페이지는 8바이트,  인터널 노드는 12바이트.
    |----------------|
    | cell pointer   |   |  셀당 2바이트, 정렬됨.
    | array           |   |  아래쪽으로 자라남.
    |                  |   v
    |----------------|
    | unallocated    |
    | space           |
    |----------------|   ^  위쪽으로 자라남.
    | cell content   |   |  순서는 불규칙. 중간에 산재된 free space 존재.
    | area            |   |  
    |----------------|

셀(cell)이란 것은 테이블 페이지라면 하나의 레코드가 됩니다. 레코드에 레코드 정보와 rowid를 덧붙여서 하나의 cell이 만들어집니다. 인덱스 페이지라면 키값과 키에 해당하는 데이터가 있는 rowid를 합쳐서 cell이 만들어집니다.
중요한 것은 B-tree 모듈에서는 이게 테이블인지 인덱스인지는 별로 상관이 없이 프로그래밍 되어 있다는 것입니다. 그냥 키/데이터로 이루어진 cell이 주어지면 key 순서에 맞게 저장하거나 찾아주기만 하면 되는거지요.

그럼 각각의 영역에 대해 알아볼까요.
파일 헤더는 첫번째 페이지에만 존재하는, DB 파일에 대한 정보를 담고 있습니다.
중요한 건 두번째인 페이지 헤더부터입니다. 페이지 헤더는 다음의 정보들을 갖고 있습니다.

- 1바이트, flags : 페이지가 leaf 페이지인지, 데이터없이 키만 저장하는지 등등을 나타냅니다.
- 2바이트, 첫번째 free block의 offset
- 2바이트, 이 페이지의 셀(아이템)의 갯수
- 2바이트, cell content area의 시작 바이트 옵셋
- 1바이트, 조각난 free byte 크기
- 4바이트, Ptr(N), leaf 페이지에서는 생략.

페이지 헤더 다음에는 cell pointer array가 있는데 이는 실제 데이터가 저장된 cell을 가리키는 포인터의 배열입니다. 그리고 cell은 마지막의 cell content area에 저장되죠. 이 포인터 배열은 페이지 헤더 다음부터 정방향으로 씌어지면서 영역이 늘어나게 되고, cell content area는 페이지의 끝에서부터 역방향으로 씌어지면서 늘어나게 됩니다. 그래서 unallocated space는 그 둘의 가운데에 위치하게 됩니다.

예를 간단히 들어보겠습니다. 1024 바이트 크기의 leaf 페이지가 깨끗한 상태라면 페이지 헤더 8바이트를 제외한 1016 바이트가 unallocated space가 되겠죠. 이 때 10바이트의 cell이 페이지에 들어온다면 현재 페이지는 빈 상태이므로 페이지의 맨 마지막에 씌어지게 됩니다. 그러면 시작 바이트는 1014바이트가 되겠죠? 이 값이 바로 cell pointer array의 첫번째에 씌어지게 됩니다.
그리고 마지막으로는 페이지 헤더의 셀 갯수가 0에서 1로 바뀌고 cell content area의 시작 바이트 옵셋이 1014로 기록됩니다.

그럼 페이지 레이아웃이 대략 다음과 같이 됩니다(클릭해서 보세욤).


cpa는 cell pointer array의 약자입니다. 아래의 숫자들은 페이지 옵셋이고요.

여기에 추가로 4바이트의 셀이 또 씌어진다고 하면 아래와 같이 변하겠죠.

즉 이런 식으로 content pointer array는 앞에서부터 씌어지고 cell content area는 뒤에서부터 씌어지게 됩니다. 이런 구조는 다른 데이터 베이스에서도 주로 쓰이는 형태입니다.
왜 이런 구조가 필요한가? 이는 근본적으로 들어오는 cell의 크기가 일정치 않기 때문입니다. fix된 크기의 데이터라면 관리가 쉽지만 그렇지 않을 경우 업데이트나 삭제, 삽입이 연속적으로 이루어질 경우 공간을 제대로 활용하기가 쉽지 않습니다.
그리고 실제 정렬은 개당 2바이트 크기의 cell pointer array에서만 이루어지기 때문에 훨씬 오버헤드가 적게 듭니다. cell 하나는 테이블일 경우 레코드 하나를 저장하게 되는데 이는 테이블 스키마에 따라 다르지만 크면 몇백바이트 이상이 될 수도 있습니다. 이런 크기의 cell들을 그때그때 정렬한다면 DB를 제대로 쓸 수 없겠죠.

그런데, 정렬이 되어 있지 않다 하더라도 cell content 영역에서 삭제가 일어나거나 업데이트가 일어나면 중간중간에 빈 공간이 생길 수 밖에 없겠죠. 즉, 위의 그림처럼 딱 맞게 content가 씌어진 상태가 되지는 않습니다.
뭐 빈 공간이 생기면 그때마다 앞에서 content를 밀어주면 되긴 하지만 그건 좀 비효율적이고 SQLite는 그래서 Unallocated space가 아닌, cell content 중간에 생기는 free space에 대해서는 관리를 따로 하고 있습니다.

일단 4바이트보다 큰 공간이 생기면 이는 free block이라고 하여 링크드 리스트로 관리됩니다. 위에 기술했던 페이지 헤더의 두번째 필드를 보시면 '첫번째 free block의 offset'이라고 되어 있습니다. free block이 처음 생기면 바로 이 필드에 그 시작 바이트 옵셋을 기록합니다. 그리고 free block의 처음 두 바이트는 또 다음 free block의 바이트 옵셋을 기록하고, 그 다음 두 바이트는 free block의 크기를 기록합니다.
그럼 4바이트보다 작은 free space가 생기면? 이는 따로 정보를 갖고 있지는 않고, 단지 페이지 헤더의 다섯번째 필드인 '조각난 free byte 크기'부분에 그 크기를 합산합니다.

그럼 이제 cell content가 자주 삽입 삭제가 일어난 후의 상황에서 10바이트의 cell을 써넣으라는 호출이 왔다고 가정하겠습니다. SQLite는 제일 먼저 page의 전체 free space의 크기와 cell의 크기를 비교해야겠죠. 일단 cell의 크기가 작다고 가정을 하겠습니다.
그러면 그 다음으로는 unallocated space의 크기와 cell을 비교합니다. 만약 cell이 더 크면? 빈 공간들이 cell content 영역에 산재되어 있다는 의미이므로 이를 모으는 defragment 작업부터 하고서(cell들을 밀어서 영역내의 빈 공간의 파편들을 없앱니다) 공간을 할당해 줍니다.
그렇지 않을 경우는 free block의 링크드 리스트를 뒤져 적합한 크기의 block을 먼저 찾아보고 있으면 그 block의 부분을 쓰도록 하며, 아니라면 역시 defragment를 하게 됩니다.

defragmentPage 소스를 한 번 살펴보겠습니다. 중요치 않은 부분의 코드는 삭제했으므로 원본의 소스와 다를 수 있습니다(3.6.2 버전의 btree.c를 참고하세요).

defragmentPage()


다음은 실제로 페이지 내에서 빈 공간을 확보하는 allocateSpace()의 코드입니다.

allocateSpace()


대충 여기까지 보셨으면 dara[hdr+n]이 페이지 헤더의 필드들을 의미한다는 것을 아셔야 됩니다.
get2byte(data[hdr+1])은 첫번째 free block 옵셋을 읽어들이는 것이고 get2byte(data[hdr+5])는 cell content 영역의 시작 옵셋을 읽어들이는 거지요.

디스크의 페이지를 메모리로 읽어들여서 그대로 data[]에 저장한 것이기 때문에 일반적인 방법인 구조체를 이용하여 정보를 읽어들이지 않는 것입니다.

이제 위의 두 함수와 연계하여 대망의 -_- 실제 cell insert코드를 보겠습니다.
insertCell() 함수의 일부입니다.

insertCell()



실제 insert 과정은 이것보다 조금 더 복잡하긴 합니다. Overflow Page와 관련된 부분들도 있고 실제 SQL문에서부터 여기까지 이르기에는 또다른 많은 험난한 과정들이 필요합니다 -_-;
하지만 실제 페이지에 insert 되는 과정을 살펴 보았으므로 보시는 분들은 페이지 구조에 대해서는 이제 충분히 감을 잡으셨으리라 생각됩니다. 그러므로 굳이 delete하는 부분은 볼 필요는 없겠죠. 궁금하면 소스를 뒤져보시길...-_-;

대신 다음에는 실제 cell의 포맷은 어떻게 구성되는지, 어떻게 레코드가 하나의 cell로 뭉뚱그려지는지 -_- 등에 대해 살펴보도록 하겠습니다.
이올린에 북마크하기(0) 이올린에 추천하기(0)
Posted by eminency

앞으로 시간 남는대로 SQLite의 소스 및 구조를 분석하는 올릴까 합니다. 예전에도 관련 글이 몇 가지 있지만 앞으로는 좀 더 상세하게 파헤칠까 합니다.
이번에는 가장 기본이 되는 SQLite의 기본적인 레이어 구조와 페이지 핸들링에 대해 다루어 보겠습니다.

사용자 삽입 이미지

Architecture of SQLite(출처:sqlite.org)

이 글을 관심있게 읽어 보실 분이라면 이미 SQLite를 몇 번은 다루어 보셨겠죠?
우리는 SQLite 쉘을 이용하거나 혹은 JDBC든 C API든 무언가를 통해 SQL을 SQLite에 보내게 됩니다. 이것이 좌상단의 Core레이어에 있는 Inteface입니다. 위에 말한 것들이 모두 Interface가 됩니다.

SQL문장은 우상단의 SQL처리 레이어(SQL Compiler)를 통해 SQLite Virtual DB Engine이 처리할 수 있는 OPcode로 번역됩니다.
Core 레이어 마지막의 Virtual Machine이 바로 OPcode를 받아 처리하는 역할을 합니다.
OPcode는 형태상으로 어셈블리와 비슷하며 SQL 처리 과정을 이해하기에 편한 구조를 지니고 있습니다.

Backend는 실제로 저장되는 데이터 구조를 다루는 부분입니다. Virtual Machine에서 무슨 테이블에 이거 집어넣어라, 무슨 인덱스에서 이거 삭제해라 등등 좀 더 세밀한 명령을 보내면 메모리와 디스크에 저장된 데이터를 조작하게 됩니다.
B-tree부분은 인덱스와 테이블 저장구조를 담당합니다. SQLite에서 인덱스는 당연히 B-tree로 이루어지며 일반 테이블 또한 row id를 키로 하는 B-tree입니다.
B-tree의 operation은 메모리 상에서 이루어지며 Pager(page cache)를 통해 메모리에 올라와 있던 B-tree 페이지가 디스크로 내려가고 또 불려 올라오게 됩니다.
디스크 I/O를 비롯한 부분은 OS마다 다르므로 OS Interface를 통해 각 OS마다 따로 구현되어 있습니다.

페이지 핸들링(길어서 접음)




 

이올린에 북마크하기(0) 이올린에 추천하기(0)
Posted by eminency
CVS 소스 트리에는 이미 포함되어 있긴 합니다만... (http://www.sqlite.org/cvstrac/dir?d=sqlite/ext/rtree)

SQLite는 확장성에도 나름 노력을 기울이고 있는데 User Collation(텍스트 컬럼의 경우 정렬방식을 사용자가 결정할 수 있음, 예를 들면 한글 데이터와 영어 데이터가 있을 경우 이를 한글이 먼저 나오게 할 수 있음)이나 User Function(SQL function을 유저가 정의) 등이 있으며  R-tree는 Extension Loading이라는 기능을 통해 지원됩니다.
Extension Loading은 리눅스라면 dlopen() 함수를 통해 shared library를 로딩하는 방식으로 이루어집니다(dlopen()을 활용하면 실행중에도 공유 라이브러리 링크가 가능합니다).

R-tree는 B-tree랑 유사한 방식의 트리 자료구조인데 주로 위치 정보나 공간 정보를 저장하는데 쓰입니다. 구글 맵 같은 기능을 구현하고 위치 정보를 좌표로 DB에 담는다면 B-tree로 인덱스를 구성해봤자 별로 도움이 안되겠죠. 위치 정보에서 중요한건 어디가 어디와 가깝느냐 이런게 중요하겠죠. 참고로 오라클 DB도 spatial 데이터 타입을 지원합니다.
자세한 건 위키피디아를 참조하시고...-_-;;

흥미있으신 분은 사전 지식을 쌓을 겸 둘러보시고 소스를 한 번 보시기 바랍니다. 2800라인 정도니 크게 부담가는 정도는 아닌 듯...;

여튼, 이런 예를 볼 때마다 오픈 소스의 장점이 유감없이 발휘된다는 걸 느끼고 감탄할 따름입니다. SQLite 같이 잘 나가는 프로젝트는 엔진만 있어도 알아서 JDBC, Python, Ruby, PHP, ... 등등의 Binding 뿐만 아니라 이건 extension까지 수많은 사람들이 달려들어 제작을 하니까요.
이런 확장성을 톨한 불특정 다수에 의한 개발의 예는 사실 오픈 소스가 아니라도 많지요. 대표적인게 WOW 아닐까요...ㅡㅡ;
이올린에 북마크하기(0) 이올린에 추천하기(0)

'Programming Story > SQLite' 카테고리의 다른 글

SQLite 페이지 핸들링(1) - SQLite의 구조  (0) 2008/08/03
SQLite R-tree 지원 예정  (1) 2008/07/22
SQLite non-C API 소개  (3) 2007/08/20
SQLite C API 소개  (4) 2007/08/08
Posted by eminency
이번 글도 간략한 소개에 가까운 글이 되겠네요.
C 외의 다른 언어들의 SQLite API에 대한 내용입니다.

SQLite의 특이점은 DB 엔진 자체에 C API 외에 Tcl API가 포함되어 있다는 점인데... Tcl은 제가 잘 모르는지라 다루지 않았습니다.
왜 Tcl 지원이 기본으로 들어가게 되었는 지에 대해서는 잘 모르겠지만, C 이외에 엔진을 컨트롤 할 수 있는 좀 더 가볍고 쉬운 문법의 언어가 지원된다는 것은 개발하는 입장에서나 사용하는 측에서 꽤 편한 것은 사실입니다(Tcl이 국내에서는 거의 안 쓰이긴 하지만요).
파이어 폭스의 XUL이라든가... 대표적으로 게임업계에서는 lua를 많이 쓴다고 들었습니다. 유명한 월드 오브 워크래프트에서 사용자가 만들어 쓸 수 있는 플러그인 스크립트도 lua이지요.

어쨌든 결론은...
아래의 API들은 단순한 소개 차원이며, SQLite에서 지원하는 것이라기 보다 SQLite를 쓰는 다른 개발자들이 해당 언어에 대한 바인딩을 개발한 것이라고 생각하시기 바랍니다.
혹 '일관성이 왜 이리 없어'라든가... SQLite 개발자에게 영어로 메일을 보내서 'ruby API에 이런 기능을 넣어주세요'라는 분이 있을까봐서...ㅡㅡ

우선, 파이썬 API입니다.

#!/usr/bin/python

from pysqlite2 import dbapi2 as sqlite

selectsql = "select * from testtbl where id=?"

# db connection
con = sqlite.connect("testdb")
cur = con.cursor()

for x in range(1,4):
        cur.execute(selectsql, (x,))

        for y in cur:
                print y[0],":",y[1]
예전 C API 소개와 프로그램 수행 로직은 동일합니다.
코드량은 확실히 적습니다 -_- 스크립트 언어의 강점이죵...

눈여겨 보실 부분은... 커서 클래스를 그대로 Iterator로 쓸 수 있다는 점이구요. JDBC를 비롯한 기본적인 사용방식처럼 next(), fetchone()도 가능합니다.
prepare가 없다는 점이 특이하군요.

다음은 Ruby입니다.

#!/usr/bin/ruby

require 'sqlite3'

db = SQLite3::Database.new("testdb")

stmt = db.prepare("select * from testtbl where id=?")

for x in 1..3
        stmt.bind_params(x)
        stmt.execute.each do |row|
                print row[0],":",row[1],"\n"
        end
end

파이썬만큼 간단합니다... 별로 쓸 내용이..-_-

마지막으로 펄입니다.

#!/usr/bin/perl

use DBI;

my $dbh = DBI->connect("dbi:SQLite:dbname=testdb","","");
my $sth = $dbh->prepare("select * from testtbl where id = ?");

my ($id, $name);

for ($i=1; $i<=3; $i++)
{
        $sth->bind_param(1, $i);
        $sth->execute();

        $sth->bind_columns(undef, \$id, \$name);

        while ($sth->fetch())
        {
                print "$id : $name\n";
        }
}

$sth->finish();

펄의 API는 다른 언어와는 좀 다릅니다. JDBC 처럼 펄에는 DBI라는 DB 인터페이스에 대한 공통적인 모듈이 존재하기 때문에 거기에 맞춰서 만들게 됩니다.
그래서 JDBC에서 jdbc를 import 하고 소스에서 커넥션 스트링으로 드라이버를 부르듯이 펄은 DBI 모듈만 부른 후 커넥션 스트링으로 DB와 연결하게 됩니다.

API란 건 '사용법'에 가깝죠. 그래서 API를 아는 것보다 얼마나 잘 쓰느냐가 중요합니다.
API가 복잡한 프로그램은 그만큼 쓰기가 어렵기도 하지만... 생각해 보면 좋은 제품이라도 API 디자인이 나쁘면 널리 쓰이긴 힘듭니다.
결국 프로그래밍이란 건 수많은 API를 사용해야 하는 작업이기도 하고요.

이만 잡설을 마치고... 다음엔 무거운 주제로 한 번..ㅡㅡ
이올린에 북마크하기(0) 이올린에 추천하기(0)

'Programming Story > SQLite' 카테고리의 다른 글

SQLite R-tree 지원 예정  (1) 2008/07/22
SQLite non-C API 소개  (3) 2007/08/20
SQLite C API 소개  (4) 2007/08/08
Thread-safe(3) : Lock in SQLite  (0) 2007/07/06
Posted by eminency
꽤 간단한 내용이지만, SQLite는 한글 매뉴얼이 별로 없는 탓에 끄적여 봅니다.

그간 C API를 써 본 DB들을 보면, ODBC와 비슷한 형태를 갖고 있는 경우가 많습니다. 오라클은 C API보다는 Pro*C를 쓰니 예외로 하고요.. 오라클 C API가 어떻게 되어 있는 지도 모르겠네요 -_-;

대략 Open-Prepare-Bind-Execute-(Fetch)-Close의 과정을 거치는데 open-close는 당연히 DB를 열고 핸들러(DB 정보 구조체)를 초기화하는 것과 종료하는 것이니 어려울 것 없고요.

Prepare는 DB에게 자기가 실행할 SQL 문장을 던져주고 미리 실행 플랜을 준비하도록 합니다. binding 할 값이 없다면 prepare 하지 않고 곧바로 execute도 가능합니다만, 예를 들어 문장은 동일한데 값만 바뀌는 쿼리를 여러 번 실행할 경우에 다이렉트로 그 때마다 실행을 한다면, 매번 DB 엔진은 SQL 문장을 해석하고 어떻게 실행할 지를 결정하고, 값에 따라 실행하게 되겠죠. 값만 달라진다면, 문장을 해석하고 실행할 지 결정하는 부분은 사실 한 번만 해도 되는데 말이죠.

그리고 bind는 실행하기 전 쿼리에 값을 할당하는 것입니다. 바인딩할 부분은 보통 '?'으로 표현하는데 'SELECT * FROM test WHERE id = ?' 이런 식으로 쿼리 문장을 표현할 수 있습니다. 이 문장 그대로 prepare를 딱 한 번만 한 다음 실행할 때는 '?'위치에 integer 변수를 binding 하여 여러 가지로 id 값을 주어서 결과를 가져올 수 있습니다.

Execute는 말 그대로 문장을 실행하는 것인데 DB에서는 select 쿼리가 실행 되었을 경우 result set 공간에 결과값을 저장해 놓습니다.
Fetch는 그런 result set의 값을 가져오는 과정입니다. insert-update-delete를 실행했을 경우는 당연히 필요없는 과정이죠.

상당히 대충 설명했는데 -_- 직접 예를 보겠습니다.
testtbl의 스키마는 'CREATE TABLE testtbl(id int, value text);' 입니다.

예제 프로그램은 id를 1부터 3까지 돌리며 해당되는 레코드를 긁어오는 것입니다.


#include        <stdio.h>
#include        <stdlib.h>
#include        <string.h>

#include        <sqlite3.h>

#define EXIT_WITH_ERROR(func, dbh) \
do {    \
        if (func != SQLITE_OK)  \
        {       \
                fprintf(stderr, "line %d: %s \n: %s\n", __LINE__        \
                                , #func ,sqlite3_errmsg(dbh));        \
                exit(sqlite3_errcode(dbh));     \
        }       \
} while(0)

int
main()
{
        sqlite3    *dbh;
        sqlite3_stmt    *stmt;
        int     i, j;
        char    *errmsg;

        char    *sql = "select * from testtbl where id=?";

        /* "testdb"라는 DB 파일을 연다 */
        EXIT_WITH_ERROR(sqlite3_open("testdb", &dbh), dbh);

        /* sql 문장에 대해 질의 플랜을 준비한다 */
        EXIT_WITH_ERROR(sqlite3_prepare(dbh, sql, strlen(sql)
                                , &stmt, NULL)
                        , dbh);

        for (i=1; i<=3; i++)
        {
                /* '?' 위치에 i 값을 바인딩한다 */
                EXIT_WITH_ERROR(sqlite3_bind_int(stmt, 1, i) , dbh);

                /* sql 쿼리 실행 */
                while (sqlite3_step(stmt) != SQLITE_DONE)
                {
                        /* 실행된 결과값을 받아와 출력 */
                        printf("%d : %s\n" , sqlite3_column_int(stmt, 0)
                                        , sqlite3_column_text(stmt, 1));
                }

                sqlite3_reset(stmt);
        }
        sqlite3_finalize(stmt);
}

EXIT_WITH_ERROR는 에러 체크를 위해 제가 작성한 매크로입니다. 실제 sqlite3_ 로 시작하는 함수들만 보시면 됩니다.

처음에 DB 오픈을 하고 sql 문장에 대해 prepare를 수행하죠?
prepare의 마지막 NULL 인자는 원래 char *가 들어가는 곳입니다. sql 문장이 하나가 아니라 여러 개일 경우는 첫번째 것만 prepare하고 마지막 인자의 포인터 변수에 두번째 문장이 시작하는 위치를 가리키도록 되어 있습니다.
순차적으로 수행되어야 할 sql 문이라면 변수를 따로 안 두고 실행 단위별로 sql 문을 선언하여 쓸 수 있다는 장점이 있습니다(자세한 설명은 sqlite3_prepare()의 매뉴얼 페이지를..).

그 다음에는 for 문을 돌며 바인딩-실행-결과 페치를 반복합니다.
바인딩은 for 문의 변수인 i를 그대로 이용합니다. 바인딩 함수의 두번째 인자는 binding variable의 순서입니다. 첫번째니까 '1'이죠. 여러 개 있으면 앞에서부터 1,2,3,..이 됩니다. 숫자이므로 sqlite3_bind_int를 썼고, 그 외에 _null, _text 등 다양한 바인딩 함수가 있습니다.

그리고 sqlite3_step()을 써서 실행을 하는데 특이한 점은 이 함수가 실행과 페치를 동시에 수행한다는 점입니다.

예를 들어 MySQL이라면, mysql_query()로 실행하고, mysql_store_result()로 결과 셋을 가져 온 후, mysql_fetch_row()을 반복 실행하여 한 건씩 긁어오는 과정을 거칩니다.

반면 SQLite는 sqlite3_step을 실행하면 실행하고 결과 셋의 첫번째 레코드를 가져오는 과정까지 거칩니다.
그 다음은 각 컬럼을 sqlite3_column_* 함수들을 써서 가져오면 됩니다(컬럼 번호는 0부터 시작합니다).
그리고, 두번째 이후로 sqlite3_step()을 실행하면 sql을 실행하지는 않고 결과 셋의 다음 레코드들을 가져오게 되는 것이죠. 만약 가져올 결과 레코드가 없으면 SQLITE_DONE을 리턴합니다.
즉, 만약 결과가 실행할 때마다 한 건씩만 있다면 굳이 while 문을 돌릴 필요는 없습니다. 실행 결과는 다음과 같습니다.

1 : aaa
1 : ddd
2 : bbb
3 : ccc

만약 while 문을 쓰지 않았다면 결과에는 1:ddd가 나오지 않을 것입니다. id 컬럼이 unique 하다면 while문을 쓰지 않아도 되겠지만, 방어적인 프로그래밍을 위해서는 while을 사용하는 스타일이 나을 듯 합니다 ^^

그리고 결과셋을 다 긁어왔다면 sqlite3_reset을 실행해서 바인딩 된 변수들을 초기화 해 주어야 합니다.
그렇지 않을 경우 두번째 bind를 할 때에 에러가 납니다.

이상으로 간단히 SQLite의 C API에 대해 살펴 보았습니다, 간단하죠? ^^
개인적으로는 다른 DB에 비해 비교적 API 사용법이 쉽다는 느낌이 듭니다. DB 데몬이 없기 때문에 API를 더욱 간략하게 만들 수 있었는 지도 모르겠습니다.

하지만 C를 쓸 경우는 아무래도 다른 언어보다는 조금 번거롭죠.
pysqlite 같은 걸 쓸 경우는 훨씬 편합니다. 이후에는 C언어 이외의 SQLite API에 대해 한 번 보도록 하겠습니다.
이올린에 북마크하기(0) 이올린에 추천하기(0)

'Programming Story > SQLite' 카테고리의 다른 글

SQLite non-C API 소개  (3) 2007/08/20
SQLite C API 소개  (4) 2007/08/08
Thread-safe(3) : Lock in SQLite  (0) 2007/07/06
SQLite의 라이센스  (0) 2007/06/08
Posted by eminency

무지무지 오랜만의 포스팅이군요. 별로 바쁘지도 않았던 거 같은데...ㅡㅡ

시간 날 때마다 SQLite 소스를 보는 터라 -아직도 많이 부족하지만- thread-safe에 대한 포스팅을 몇 했던 만큼 SQLite의 Locking 메커니즘에 대해 간략히 적어볼까 합니다.
하지만 아시는 분은 다 아시듯 쓰고 보면 별로 안 간략하다는 거...


개  요

우선 DB에서의 lock이란 어떻게 보면 상당히 추상적인 개념이라고 할 수 있습니다.
semaphore나 pthread의 mutex같은 것은 거의 가장 하위 레벨의 원자적인 락을 위한 구현이고, DB에서의 락은 이런 것들을 이용해 좀 더 고차원적인 동시성 제어를 구현한 것입니다. 그러므로 DB의 Lock과 OS 차원에서 말하는 세마포어나 뮤텍스 등등의 락은 의미가 서로 다름을 염두에 두시기 바랍니다.




Locking Logic

SQLite는 데이터를 페이지 단위로 관리하며 페이지 단위로 락을 겁니다. 실제 데이터 파일은 페이지의 모음인 셈이지요.
SQLite의 락에는 다섯가지의 레벨이 있습니다. pthread의 rw락의 확장 스타일이라고 보면 되겠습니다(rw락은 읽기-쓰기 락이라고도 하는데 읽기 락은 동시에 여러 쓰레드가 락을 잡을 수 있지만 쓰기 락은 단 하나의 쓰레드만이 잡을 수 있습니다, 읽기만 하는 경우는 데이터 변경이 일어나지 않으므로 여러 개의 쓰레드가 동시에 읽어도 문제가 없으므로 듣기엔 꽤 좋습니다만.... 일반 mutex 락보다 느립니다 -_-).

다섯가지 레벨은 각각 Unlocked, Shared, Reserved, Pending, Exclusive인데 Shared는 읽기 락입니다. 동시에 여러 개의 쓰레드가 Shared 락을 갖고 읽을 수 있는 것입니다.
Reserved는 '내가 좀 있다 쓰기를 시작 할 거야'라는 의미의 락입니다. Reserved 락의 쓰레드가 하나 존재하면 다른 쓰레드들은 Reserved 락을 획득할 수 없습니다. 하지만 Shared를 획득하여 읽는 것은 가능합니다.
실제로 쓸 준비가 되면 Reserved 락의 쓰레드는 Pending 락을 획득합니다. Pending 상태가 되면 이제 더 이상 Shared 락이 추가되는 것이 금지되고 기존의 Shared락을 갖고 읽기를 수행하는 쓰레드들이 종료되기를 기다립니다(Shared락도 락을 얻기 전 먼저 Pending 락을 획득합니다).
Shared 락을 가진 쓰레드들이 모두 없어지면 Pending 락은 Exclusive 락으로 바뀌고 쓰기 작업을 수행합니다.

실제로 락을 요구할 때는 static 함수인 pager_wait_on_lock()을 이용해 호출하게 되는데 이는 일종의 wrapper함수이며 내부에서는 각 OS 별로 구현된 Locking 함수를 호출하게 됩니다. 컴파일시에 어떤 OS의 locking 함수를 호출할지가 결정되겠죠.

SQLite는 오라클, MySQL, PostgreSQL 등등의 여타 DB들처럼 DB 서버가 뜨고 클라이언트 툴이나 API를 이용하는 서버-클라이언트 방식이 아닌, 라이브러리를 통해 DB 파일에 직접 억세스하는 방식입니다. 다른 DB들처럼 로드 밸런싱이나 쓰레드 풀을 관리할 필요도 없고, 사용자 권한 같은 것도 관리할 필요가 없어지니(파일에 대한 Unix 계정 권한이 곧 DB권한이 되는 셈이니까요) 편하기는 하지만 서버 데몬에서 동시성 관리를 해 줄 수가 없다는 점도 있지요.

그래서 SQLite는 라이브러리 코드 내에서 mutex를 써서 멀티 쓰레드에 대한 대비를 해주면서 또한 멀티 프로세스를 위해 DB 파일에 fcntl()을 이용해 락을 겁니다.
즉, 프로세스간에든 쓰레드간에든 위에 언급한 Shared-Reserved-Pending-Exclusive 락의 구조는 동일하며 fcntl을 사용하는지 mutex를 사용하는 지가 다를 뿐입니다.


구  현

사설이 길었네요 ^^ 실제 코드를 잠깐 보지요.
실제 락을 다루는 함수는 OS별로 달리 구현되어 있지만(윈도우, 유닉스, OS/2 세 가지로 구현되어 있군요) 아는게 유닉스(or 리눅스)밖에 없으니 이 쪽만 살펴보겠습니다.

락을 거는 unixLock() 함수는 다음의 순서를 거칩니다.

1. mutex 락 획득(추가로 파일 락에 대한 ownership을 가진 쓰레드인지 확인(뒤에 설명))
2. Shared 락의 경우 다른 Shared 락이나 Reserved 락이 존재하면 락의 카운트만 증가시키고 종료
3. Pending 락을 파일에 건다.
4. Share 락인 경우 read lock을 파일에 걸고 Pending 락은 해제
5. Reserved나 Exclusive인 경우 write lock을 파일에 건다(다른 락이 진입을 시도하다가 Pending락을 발견하고 락 획득을 취소시켜야 하므로 Pending은 해제하지 않는다)
6. mutex 해제

위에서 5번 같은 경우 Reserved나 Exclusive랑 Pending이 같이 걸릴 수 있는 것 처럼 써놨는데 실제로 같이 걸립니다. fcntl은 파일 전체에 락을 거는게 아니라 원하는 옵셋에 원하는 바이트만큼 락을 걸기 때문에 SQLite는 Shared, Pending, Reserved 영역을 구분해 놓고 락을 걸도록 되어 있습니다(Exclusive는 Shared와 Pending에 동시에 락을 걸게 되므로 영역이 따로 없습니다).

경우에 따라 순서가 다르긴 하지만 기본적으로는 fcntl을 상황에 따라 다르게 사용하는 코드이므로 모두 볼 필요는 없고 4번의 경우를 한 번 보겠습니다(indentation이 좀 이상하군요 -_-).




/* SHARED_LOCK인 경우 fcntl으로 SHARED에 read 락을 걸고
** PENDING 락은 해제한다
*/

if( locktype==SHARED_LOCK ){
/* SHARED_LOCK의 지정 옵셋에 read-lock 획득,
** l_type은 이미 3번 과정에서 지정됨 */

lock.l_start = SHARED_FIRST;
lock.l_len = SHARED_SIZE;
s = fcntl(pFile->h, F_SETLK, &lock);

/* 임시로 걸었던 PENDING 락 해제 */
lock.l_start = PENDING_BYTE;
lock.l_len = 1L;
lock.l_type = F_UNLCK;
if( fcntl(pFile->h, F_SETLK, &lock)!=0 ){
rc = SQLITE_IOERR;
goto end_lock;
}
if( s ){
rc = (errno==EINVAL) ? SQLITE_NOLFS : SQLITE_BUSY;
}else{
pFile->locktype = SHARED_LOCK;
pFile->pOpen->nLock++;
pLock->cnt = 1;
}
}









물론 SHARED_FIRST, SHARED_SIZE, PENDING_BYTE등은 매크로로 지정되어 있는 숫자들이구요.
마지막에는 구조체의 파일 락 카운트와 락 카운트를 1씩 증가시키고 끝냅니다. pFile->pOpen->nLock은 파일에 대한 락의 갯수이며, pLock->cnt는 락 자체의 카운트입니다(SHARED가 아니라면 1을 넘어갈 수 없겠죠).

위의 코드는 파일에 대한 락이므로 프로세스 간에는 관리가 되지만, 실제 파일을 다루지 않고 있던 쓰레드가 파일에 대한 락을 획득하려고 할 경우는 뮤텍스와 상관없이 문제가 될 수 있습니다.
이를 위해서 SQLite는 락 정보에 대한 해쉬 테이블을 유지하면서 필요시마다 thread id를 비교하여 올바른 쓰레드만이 파일 락에 접근할 수 있도록 제어하고 있습니다. 이 부분이 1번 과정의 ()의 내용에 대한 것입니다.

그럼 마지막으로 위의 과정들을 수행하기 전 뮤텍스 락을 어떤 방식으로 획득하는지 살펴 보지요.
단순히 pthread_mutex_lock만 하는 건 아니거든요. ^^


void sqlite3UnixEnterMutex(){
        /* 보조 뮤텍스 획득 */
        pthread_mutex_lock(&mutexAux);

        /* 메인 뮤텍스가 풀려 있는 상태거나
         * 현재 메인 뮤텍스를 가진 쓰레드가 아닐 경우 */

        if( !mutexOwnerValid || !pthread_equal(mutexOwner, pthread_self()) ){
                /* 보조 뮤텍스 풀고 메인 뮤텍스 획득 */
                pthread_mutex_unlock(&mutexAux);
                pthread_mutex_lock(&mutexMain);

                /* 다시 보조 뮤텍스 획득 */
                pthread_mutex_lock(&mutexAux);

                /* 뮤텍스 소유자로 쓰레드 자신을 지정,
                 * 소유 플래그 셋팅 */

                mutexOwner = pthread_self();
                mutexOwnerValid = 1;
        }

        /* 카운터 증가시키고 보조 뮤텍스 해제 */
        inMutex++;
        pthread_mutex_unlock(&mutexAux);
}


보시다시피, 실제로는 두 개의 mutex 변수를 쓰고 있습니다.
하나는 실제 락을 위한 메인 뮤텍스이며 하나는 뮤텍스 정보 저장을 위한 변수 억세스에 쓰이는 보조 뮤텍스입니다.
mutexOwner는 메인 뮤텍스를 갖고 있는 쓰레드의 tid, mutexOwnerValid는 뮤텍스를 갖고 있는 쓰레드가 있으면 1로 세팅되는 플래그 변수이며 inMutex는 같은 쓰레드가 여러 번 뮤텍스를 요구할 경우 증가하는 카운터입니다.

실제로 뮤텍스를 같은 쓰레드가 새로 획득하려고 시도하는 것은 Undefined Behavior입니다. 리눅스 같은 경우 데드락이 걸리더군요. Recursive Mutex를 위해서는 뮤텍스 타입을 PTHREAD_MUTEX_RECURSIVE으로 지정하면 되긴 합니다만, 위와 같은 방식이 아마 성능이 좀 더 낫다든가 하는 이유가 있겠죠 -0-

...아직도 잘 모르는 처지에 나름대로 소스 분석을 하고 글까지 쓰려니 시간이 많이 드는군요. 아직 저도 이해 안되는 부분들도 있고...^^;
소스는 SQLite-3.3.6 기준이므로 현재 버전과는 차이가 좀 있을 수 있습니다.

이번 글은 여기서 마치며... 담에 기회되면 다른 주제로 또 쓰도록 하겠습니다. 질문있는 분은 허심탄회하게 댓글로~

이올린에 북마크하기(0) 이올린에 추천하기(0)

'Programming Story > SQLite' 카테고리의 다른 글

SQLite non-C API 소개  (3) 2007/08/20
SQLite C API 소개  (4) 2007/08/08
Thread-safe(3) : Lock in SQLite  (0) 2007/07/06
SQLite의 라이센스  (0) 2007/06/08
Posted by eminency
SQLite는 라이센스가 없습니다 -_-;;
아무렇게나 소스를 써도 됩니다. 개발자들이 존경스럽지요.
리눅스나 gcc 같은 것들은 GPL을 따르기 때문에 소스를 공개해야 된다는 제약이 있습니다. 그리고 BSD 라이센스는 아무렇게나 써도 되지만 라이센스는 명시해야 될 겁니다(아마도.. 기억이 잘..).
하지만 SQLite는 라이센스가 없기 때문에 정말로 '아무렇게나' 써도 됩니다.

소스 코드의 앞 부분에는 주석으로 다음과 같은 내용이 있습니다. hash.c의 내용입니다.

/*
** 2001 September 22
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the implementation of generic hash-tables
** used in SQLite.
**
** $Id: hash.c,v 1.18 2006/02/14 10:48:39 danielk1977 Exp $
*/

번역하면 다음과 같은 뜻이 되겠습니다.

2001. 9. 22

저자는 이 소스 코드에 대한 저작권을 요구하지 않습니다. 법률적인 주의사항을 대신하여 여기 축복의 글을 씁니다.

선을 행하되 악을 행하지 않기를.
당신 자신과 타인에 대한 용서를 구하기를.
자유롭게 나눠 가지며, 당신이 준 것 이상 바라지 않기를 기도합니다.

********************************************************************

이 소스는 SQLite에서 쓰는 일반 해시 테이블에 대한 구현입니다.

~~~ (소스 수정 정보)


가슴이 왠지 찌르르 하군요 -_-;
기술 유출과 관련해 악다구니를 부리는 사람들에게 이 글을 바치고 싶습니다...ㅡㅡㅋ

다음에 기회가 되면 SQLite에 대해 분석한 내용에 대해 포스팅 할까 합니다(별로 본 건 없지만 -_-).
이올린에 북마크하기(0) 이올린에 추천하기(0)

'Programming Story > SQLite' 카테고리의 다른 글

SQLite non-C API 소개  (3) 2007/08/20
SQLite C API 소개  (4) 2007/08/08
Thread-safe(3) : Lock in SQLite  (0) 2007/07/06
SQLite의 라이센스  (0) 2007/06/08
Posted by eminency