'오픈소스'에 해당되는 글 8건

  1. 2010.03.08 SQLite Hash Table (4)
  2. 2010.02.19 Fossil (4)
  3. 2009.11.19 GO (7)
  4. 2009.05.28 AspectJ 맛보기
  5. 2009.04.20 오라클 $5.6b 에 썬 마이크로 시스템즈 인수 (2)
  6. 2009.04.03 SQLite 사용자 함수 추가
  7. 2009.02.10 SQLite 페이지 핸들링(3) - 레코드 포맷 (3)
  8. 2008.07.22 SQLite R-tree 지원 예정 (3)

SQLite Hash Table

|


어쩌면 이 글은 앞번에 쓴 글의 연장이라고 볼 수도 있겠네요.

어느 정도 C를 배우신 분이면 이해가 가능할만한, SQLite에서 실제로 적용 중인 소스를 찾아 소개하게 되었습니다.
기본적인 형태에서 크게 벗어나지 않는 Hash Table에 대한 분석 글입니다. 이 자료구조는 SQLite 내에서 table, index, trigger 등을 저장하는 용도로 쓰입니다. 예를 들면 table 명을 키로 해서 테이블 이름에 해당되는 테이블 메타 데이터를 금방 찾기 위한 것이죠.
소스는 2010년 2월 말 경의 SQLite 소스 스냅샷을 받아 사용했습니다.


Data Structures


우선 가장 기본이 되는 해시 테이블의 구조체입니다.

struct Hash {
  unsigned int htsize;      /* 해시 테이블의 버킷 갯수 */
  unsigned int count;       /* 전체 엔트리 갯수 */
  HashElem *first;          /* 배열의 첫번째 엔트리 */
  
  struct _ht {              /* 해시 테이블(하나의 버킷) */
    int count;                 /* 현재 버킷의 엔트리 갯수 */
    HashElem *chain;           /* 현재 버킷의 첫번째 엔트리 */
  } *ht;
};

제가 쓸 용어와 주석에서의 용어가 약간 다를 수도 있는데 제가 임의로 번역을 해서 혼란이 있을 수도 있으니(아무래도 친숙한 용어로 설명하는게 더 쉬울 거 같아서요) 좀 더 깊이 보실 분은 실제 SQLite 소스를 참고하시기 바랍니다.

SQLite Hash Table은 여러 개의 버킷을 갖고 있으며 각각의 버킷은 동일한 해시 값을 키로 가지는 엔트리들을 0~N개 갖고 있습니다. 더블 링크드 리스트로요.
여기서 버킷은 위에 보이는 내부 구조체인 struct _ht이며 ht 필드에 배열로 저장이 되고, 각각의 엔트리는 HashElem이라는 나중에 설명할 구조체에 저장됩니다.
그리고 해시 테이블 안의 모~든 엔트리는 더블 링크드 리스트로 연결되어 있습니다. 어차피 버킷 안에서 더블리 링크드 리스트로 연결되어 있으므로 각 버킷끼리도 추가로 연결해 준 것에 불과합니다.

무선 순서가 있는 것도 아닌데 굳이 전체를 리스트로 묶을 필요가 있는가에 대한 의문이 생깁니다만 이유가 물론 있습니다.
첫번째는 해시를 클리어 할 때 편합니다. 물론 이것도 버킷마다 클리어하면 되므로 중요한 이유는 아니구요 -_-;
두번째 이유는 이 해시 테이블은 엔트리 갯수가 10개 미만일 때는 해시가 아니라 '그냥' 링크드 리스트로 동작하기 때문입니다. 물론 이 경우는 그냥 linear search로 엔트리를 찾게 되겠죠. 엔트리 갯수가 적을 때는 해시 테이블을 관리하는 데 들어가는 리소스보다 링크드 리스트 쪽이 훨씬 적게 들고 훨씬 빠르기 때문입니다.
그리고 마지막 이유가 또 있습니다. 이 해시 테이블은 버킷 갯수가 엔트리 갯수의 1/2이하로 떨어지면 rehash해서 버킷 사이즈를 늘리도록 되어 있습니다. rehash 할 때는 새로운 버킷 크기에 맞춰 해싱을 새로이 하게 되므로 그 때마다 버킷을 뒤지는 것보다는 링크드 리스트로 묶여 있는게 처리하기에 훨씬 빠르겠죠.
rehash를 하면 데이터가 많을 때 그 부담이 크지 않을까 생각하시는 분도 계시겠지만, 이 해시 테이블은 데이터 베이스의 데이터 관리를 위한게 아닙니다. 말씀드렸듯이 테이블 이름, 인덱스 이름 등을 저장하기 위한 구조체이며 SQLite 같은 DB에서는 아무리 많아도 그 갯수가 천단위를 넘어가진 않겠죠. 그리고 설령 엔트리 갯수가 10만개 정도라 하더라도 리해싱은 1초 미만입니다.

여튼 그러므로 엔트리 갯수가 10개 미만일 때는 htsize나 ht 배열이 각각 0, NULL일 수도 있습니다. 나머지 필드에 대해선 설명은 필요없겠죠?
다음은 HashElem 구조체입니다.

struct HashElem {
  HashElem *next, *prev;       /* 다음의 엔트리와 이전 엔트리에 대한 포인터 */
  void *data;                  /* 엔트리의 데이터 */
  const char *pKey; int nKey;  /* 엔트리의 키값과 키의 바이트 길이 */
};

흠, 여기에 대해서도 굳이 설명은 필요없을 것 같네요 -_-;


Hash Function

해시가 뭔지 모르시는 분은 없겠지만 혹시나 싶어 해시 함수에 대해서도 설명을 하겠습니다.

static unsigned int strHash(const char *z, int nKey){
  int h = 0;
  assert( nKey>=0 );
  while( nKey > 0  ){
    h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
    nKey--;
  }
  return h;
}

이게 답니다. 스트링 값을 한자씩 읽어서 계속 현재 h값과 h<<3 값으로 지수곱을 해줍니다.
해시 함수는 만들기 나름이고 특별한 규칙은 없는 데다가 수많은 해시 함수가 세상엔 존재하므로 이건 하나의 예일 뿐이구요(당연한 얘기지만 직접 만드셔도 되겠죠), 실제 해시값은 여기서 리턴된 h값을 버킷 사이즈로 나눈 나머지 값이 됩니다. 버킷이 10개라면 0~9까지의 값이 해시 값이 되는 거지요.
실제 키값을 해시해서 나온 0~9까지의 값이 ht 배열의 인덱스 값이 되는 겁니다. 그러므로 같은 해시값을 갖지만 서로 다른 키들이 해당 버킷에 줄줄이 링크드 리스트가 되어 달리겠지요. 이 구조체는 테이블명이나 인덱스명을 위해 쓰이므로 당연히 같은 키값은 존재하지 않게 설계되어 있습니다. 같은 키값을 허용할 수도 있겠죠, 물론 필요하다면.

덧붙여 말하면 해시 함수에 특별한 규칙이 없다고 했는데 가장 좋은 해시 함수는 해시값이 일정한 규칙이 없는게 제일 좋습니다. 예를 들면 abc를 해시한 값과 abd를 해시한 값이 완전히 달라야 좋을테고, 키값에 비례해서 해시값도 커진다거나 하면 곤란하죠. 해시 함수의 가장 좋은 예는 MD5나 SHA1 같은 것들입니다(시간 나면 이것들도 한 번 분석해 보고 싶군요, 머리가 굳어서 되려나 -_-).


Searching

그럼 가장 핵심이 되는 findElementGivenHash()에 대해 설명하겠습니다. 이 함수는 static 함수로 외부에 노출되지는 않지만 실제 검색 함수인 sqlite3HashFind()는 단지 키값을 해싱하여 findElementGivenHash()를 호출하는 역할만 할 뿐이므로 실제 검색인 이 함수가 담당한다고 볼 수 있습니다. 또한 insert 시에도 먼저 이 함수를 호출하여 해당 키값이 존재하면 replace 하게 하고, 없으면 insert하는 그런 목적으로도 쓰이며, 엔트리를 삭제할 때도 당연히 쓰입니다. 찾아야 삭제를 하죠 -_-

static HashElem *findElementGivenHash(
  const Hash *pH,     /* 검색을 하게 될 해시 구조체 */
  const char *pKey,   /* 검색 대상 키값 */
  int nKey,           /* 키값의 바이트 길이 */
  unsigned int h      /* 키에 대한 해시 값 */
){
  HashElem *elem;                /* 루프 내에서 HashElem을 저장할 임시 변수 */
  int count;                     /* 검색을 위해 남은 엔트리 갯수 */

  if( pH->ht ){
    struct _ht *pEntry = &pH->ht[h];
    elem = pEntry->chain;
    count = pEntry->count;
  }else{
    elem = pH->first;
    count = pH->count;
  }
  while( count-- && ALWAYS(elem) ){
    if( elem->nKey==nKey && sqlite3StrNICmp(elem->pKey,pKey,nKey)==0 ){ 
      return elem;
    }
    elem = elem->next;
  }
  return 0;
}

함수 인자인 h는 위의 strHash 함수로 생성된 후 버킷 사이즈로 % 연산을 한 값입니다. 그래서 함수명 뒤에 GivenHash가 붙는거죠.
첫번째 if는 pH->ht 배열이 생성되어 있는지를 검사하는 것입니다. 생성되어 있으면 h에 해당하는 버킷(&pH->ht[h])의 첫번째 아이템을 elem에 포인팅하고 버킷의 count 값을 세팅하며, else면 단순한 링크드 리스트 형태이므로 전체 리스트의 순차적 검색을 위해 elem과 count에 pH의 first와 count를 세팅합니다.
그 다음의 while 문은 count 갯수만큼 리스트를 traverse하며 키 바이트 길이와 키값이 일치하는 지를 검사합니다. 간단하죠?


Insertion

void *sqlite3HashInsert(Hash *pH, const char *pKey, int nKey, void *data){
  unsigned int h;       /* 해싱 값 */
  HashElem *elem;       /* 아이템을 가리키는 커서 역할의 포인터 */
  HashElem *new_elem;   /* 새로 insert 될 아이템 */

  assert( pH!=0 );
  assert( pKey!=0 );
  assert( nKey>=0 );
  
  if( pH->htsize ){
    h = strHash(pKey, nKey) % pH->htsize;
  }else{
    h = 0;
  }
  
  /* 키값이 존재하는지 체크 */
  elem = findElementGivenHash(pH,pKey,nKey,h);
  if( elem ){
    void *old_data = elem->data;
	
	/* data가 NULL이면 아이템 삭제, 아니면 replace */
    if( data==0 ){
      removeElementGivenHash(pH,elem,h);
    }else{
      elem->data = data;
      elem->pKey = pKey;
      assert(nKey==elem->nKey);
    }
    return old_data;
  }
  if( data==0 ) return 0;
  
  /* insert 할 아이템 셋팅(new_elem) */
  new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );
  if( new_elem==0 ) return data;
  new_elem->pKey = pKey;
  new_elem->nKey = nKey;
  new_elem->data = data;
  pH->count++;
  
  /* count가 10이상이며(10 미만일 때는 단순 링크드 리스트)
   * 아이템 갯수가 버킷 사이즈의 2배를 초과하면 버킷 리사이징
   * (버킷 갯수를 아이템 갯수의 2배로 늘림)
   */
  if( pH->count>=10 && pH->count > 2*pH->htsize ){
    if( rehash(pH, pH->count*2) ){
      assert( pH->htsize>0 );
	  
	  /* 버킷 갯수가 바뀌었으므로 해시값도 다시 계산 */
      h = strHash(pKey, nKey) % pH->htsize;
    }
  }
  
  if( pH->ht ){
    insertElement(pH, &pH->ht[h], new_elem);
  }else{
    insertElement(pH, 0, new_elem);
  }
  return 0;
}

외부에 노출된 insert 함수입니다. 로직을 간단히 설명하면 인자로 들어온 키값으로 findElementGivenHash()를 호출하여 값이 있는지를 찾고, 있으면 replace, 없으면 insert를 수행합니다. 만약 data 인자가 NULL이면 찾은 값을 삭제하는 removeElementGivenHash()를 호출합니다. removeElementGivenHash()는 링크드 리스트의 삭제 로직과 거의 동일하므로 생략합니다.

실제 insert하는 내부 함수 insertElement 역시 removeElementGivenHash와 마찬가지로, 어떤 버킷에 삽입될 지에 대한 해시값 계산 및 버킷 판단은 이미 앞에서 다 했기 때문에 이 insertElement가 하는 일은 링크드 리스트의 삽입 로직과 별다르지 않습니다. 역시 생략...-_-;


Rehashing(Hash Table Re-organization)

마지막으로 이 해시 테이블의 특징을 잘 나타내는 rehash 함수를 한 번 살펴 보겠습니다.

static int rehash(Hash *pH, unsigned int new_size){
  struct _ht *new_ht;            /* 새로 교체될 해시 테이블(ht 배열)을 저장하는 변수 */
  HashElem *elem, *next_elem;    /* 루프용 커서 포인터 */

/* DB 설정에 따라 메모리 사용량을 제한하는 부분 */
#if SQLITE_MALLOC_SOFT_LIMIT>0
  if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){
    new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht);
  }
  if( new_size==pH->htsize ) return 0;
#endif

  /* 메모리 할당 */
  sqlite3BeginBenignMalloc();
  new_ht = (struct _ht *)sqlite3Malloc( new_size*sizeof(struct _ht) );
  sqlite3EndBenignMalloc();
  
  if( new_ht==0 ) return 0;
  sqlite3_free(pH->ht);
  
  /* ht 배열 교체 및 초기화 */
  pH->ht = new_ht;
  pH->htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht);
  memset(new_ht, 0, new_size*sizeof(struct _ht));
  
  /* 각 아이템에 대해 해시값을 다시 계산하여 insert */
  for(elem=pH->first, pH->first=0; elem; elem = next_elem){
    unsigned int h = strHash(elem->pKey, elem->nKey) % new_size;
    next_elem = elem->next;
    insertElement(pH, &new_ht[h], elem);
  }
  return 1;
}

역시 로직은 간단합니다.
새로운 ht 배열을 새로운 크기에 맞게 malloc->기존 배열 free 및 포인터 교체->링크드 리스트의 아이템들을 순차적으로 리해싱하여 insert, 이 정도네요.
sqlite3BeginBenignMalloc()과 End 함수는 DB와 관계되는 작업이라 굳이 신경쓰실 필요는 없습니다. 시간이 많이 걸릴 수 있는 작업을 하는 중이라고 DB에 세팅하는 절차 정도?

어쨌든 로직은 무식할 정도로 간단하죠 -_- 그냥 해시를 모조리 새로 생성하는 겁니다. DB를 위한 Hash 인덱스가 아니기 때문에 이런 방법이 가능한 거겠죠.
대개는 B+ tree니 하는 있어 보이는 알고리즘에 집착하는 경향이 있습니다만(저도 -_-) 규모가 크지 않은 작업은 간단하게 처리해 주는 것이 best라는 것을 보여준다고 할 수 있겠습니다. 예전에 폰 개발을 할 때 누군가가 폰의 전화번호부에 B+ tree를 적용하는게 어떠냐고 제안했던게 생각나는군요. ready-made DB를 써서 하는게 아니라면 좀 뻘짓인 듯...-_-;

다 쓰고 보니 소스에 비해 글은 얼마 안되는군요. 뭐 그만큼 이해하기 쉽게 소스가 만들어져 있다고 생각합니다.
개인적인 생각인데 초보는 잘 모르니까 쉬운 것도 지저분하고 보기 어렵게 짜고, 중수는 실력 과시를 위해 일부러 쉬운 것도 어려운 테크닉을 써서 어렵게 짜고, 고수는 어려운 것도 쉬워 보이게 짜는 것 같습니다. 저도 고수 반열에 이르지는 못했습니다만...;
다시 말하면 쉬워 보이지만 저렇게 만드는 건 생각보다 쉽지는 않을겁니다.

기회가 닿으면 다음에는 좀 더 재미있는 부분을 분석해 올리도록 하겠습니다.

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

SQLite Hash Table  (4) 2010.03.08
Fossil  (4) 2010.02.19
SQLite 사용자 함수 추가  (0) 2009.04.03
SQLite 페이지 핸들링(3) - 레코드 포맷  (3) 2009.02.10
Trackback 0 And Comment 4

Fossil

|


많이들 쓰고 있으니 CVS나 SVN에 대해서는 잘 아시거나 들어본 적이 있으실 겁니다.
이런 툴들이 해주는 역할을 SCM(Source Configuration Management) 이라고 하는데 말 그대로 소스 형상관리를 의미하지요. 쉽게는 버전관리 라고들 부릅니다만 단순한 버전관리 보다는 좀 더 넓은 의미로 봐야합니다.

SCM 툴에 대해서는 예전에 간단하게 쓴 글이 있는데 한 번 참고하시고(지금 읽어보니 손발이 오그라드네요 -_-) 그 글에 보면 '구조' 부분에서 분산 관리방식 툴에 대해서 얘기하고 있는데요.
GIT와 Mercurial, Darcs에 대해 언급했는데 몇 가지 첨언하자면, GIT는 리누스 토발즈가 만든 툴이며 리눅스 커널의 관리를 위해 쓰이고 있습니다. 써봤는데 설명하기 힘들지만 여튼 독특합니다. Mercurial은 Python으로 만들어졌는데 SVN이랑 비슷한 방식이라 가장 많이 쓰이고 있구요. Darcs는 Haskell로 만들어졌는데 역시 많이 쓰입니다만 특히 헤스켈 사용자들의 전폭적인 지지를 업고 있습니다 -_-

그리고 최근에 Fossil이라는 새로운 DSCM (Distributed SCM) 툴을 알게 되었습니다 위에 링크한 글을 쓸 때도 알고는 있었는데 그 때 잠시 써 본 바로는 별로 땡기지도 않았고 해서 언급하지는 않았었는데 그 사이에 뭐가 많이 바뀐 거 같더군요. 제가 저번에 써 볼 때 제대로 안 살펴본 건지...
무엇보다 SQLite가 CVS로 원래 관리되고 있었는데 어느 순간 Fossil로 바뀌었습니다 -_-; 그래서 SQLite 소스를 받기 위해 Fossil을 써보게 되었는데... 맘에 듭니다 -_-;

사실 SQLite를 만든 Dr. Hip은 Fossil의 저작자이기도 합니다.
그게 큰 이유겠지만 어쨌든 제가 가장 흥미로웠던 점은 Fossil이 SQLite를 쓴다는 것입니다. 다른 도구들처럼 working copy 안에 hidden directory를 갖고 있고 그 안에 소스 복사본이나 메타 데이터를 때려넣는 구조가 아니라 SQLite database 파일 하나만 달랑 갖고 있습니다 -_-;
소스 복사본을 갖고 있는 것보다는 느릴 수도 있긴 하지만, 체감하기엔 사실 큰 차이가 나지 않는 것 같습니다.

그리고 가장 독특한 점은 Database 파일 안에는 Issue Tracking과 Wiki를 위한 테이블도 만들어져 있습니다. 다시 말하면 버전 관리를 위한 메타데이터에 버그 관리 기능도 같이 들어 있는 셈입니다. SVN과 Trac을 합쳐 놓은 것과 마찬가지입니다. Fossil 홈페이지에서도 이 기능을 첫째로 소개하고 있습니다.

일단 홈페이지에서 소개하는 기능들을 살펴보겠습니다. 번역은 제 맘대로 대충...

  1. 버그 트래킹 & 위키 - 위에서 설명
  2. 웹 인터페이스 - Fossil은 실행 파일 내에 built-in 웹 인터페이스를 제공함으로써 사용자들이 쉽게 버그 DB나 위키에 접근할 수 있게 해 줍니다.
  3. 자동 sync - 보통의 DSCM은 다른 개발자들과 개발 내용을 공유하기 위해서 수동으로 원격 저장소에 push를 해주어야 하는데 Fossil은 autosync모드를 지원해서 서버에 자동으로 수정 내용이 동기화 된다는군요. CVS나 SVN처럼 동작하게 할 수 있는 거죠.
  4. self-contained (뭐라 번역해야 될 지 -_-) - Fossil은 실행파일 하나로 이루어지고 PATH에 갖다놓기만 하면 동작합니다. 빌드도 설치도 매우 쉽습니다. 
  5. 간단한 네트워킹 - 원격 네트워킹에 기본적인 HTTP 프로토콜만을 쓰기 때문에 매우 빠르고 효율적입니다. 심지어 전화선 모뎀을 쓰더라도 사용할만한...-_-; 
  6. CGI 가능 - 원격 작업을 위해서는 당연히 서버로도 동작 가능한데 간단하게는 두 줄짜리 CGI 스크립트로도 동작하도록 되어 있다는군요. 
  7. 안정적 - SQLite에 메타데이터를 저장하기 때문에 데이터베이스의 복구 및 트랜잭션 관리 기능이 그대로 적용되므로 안정적입니다.


사실 CGI 같은 건 저도 안해봐서 잘 모르겠네요 -_-
여튼 꽤 흥미로운 SCM 툴인 것 같습니다. SQLite도 그렇지만 Fossil 역시 소스가 잘 정리되어 있더군요. 존경스럽습니다 ㅡㅡ;

SQLite와의 결정적인 차이점은 -서로 완전히 다른 종류의 소프트웨어이긴 합니다만- 라이센스입니다. SQLite는 Public Domain, 즉 공공 영역에 공개한 라이센스가 없는 DBMS지만 Fossil은 GPL이 적용되어 있습니다. 어느 쪽이든 그냥 사용하는 데는 문제가 없겠지만 SQLite는 No license였기에 아이폰이나 안드로이드에 적용되고 널리 쓰일 수 있었겠죠.
다시 말하면 Fossil은 SQLite처럼 임베딩하는 용도로 기업들이 갖다 쓸 수는 없겠군요.

아직 널리 쓰이는 것 같지는 않지만 충분히 쓸만한 물건인 것 같습니다. 저런 것들을 뚝딱 만들어내는 분들은 정말 존경스럽군요 -_-;
우리나라는 end-user를 위한 어플리케이션은 개인 개발자에 의해 만들어지는 것들이 많습니다만 저런 개발의 기반이 되는 툴은 개인 개발자에 의해 만들어지는 것이 거의 없는 것 같은 느낌이 드는데 무슨 이유인지 잘 모르겠습니다. 저런 것에 대해 고민할만큼 소프트웨어 개발이 연구차원으로 주목받지 못해서일까요?

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

SQLite Hash Table  (4) 2010.03.08
Fossil  (4) 2010.02.19
SQLite 사용자 함수 추가  (0) 2009.04.03
SQLite 페이지 핸들링(3) - 레코드 포맷  (3) 2009.02.10
Trackback 0 And Comment 4

GO

|
구글에서 GO란 언어를 내놓은 것을 이미 아시는 분은 아시겠죠(http://golang.org/).
C 개발자 출신인 저에게는 꽤 흥미롭습니다.

Java가 나오면서 C와 C++을 많이 대체하는 듯 했지만 한계는 존재하죠. 대표적인 건 임베디드라고 할 수 있을 듯 합니다. Java를 시스템 프로그래밍 언어라고 부를 수는 없으니까요.
흠, Objective-C라면 임베디드 쪽에도 써볼만 하지 않을까 싶은 생각이 문득 들긴 하는데...-_-
여튼 Java 이후로 스크립트 언어들도 많이 나왔습니다만 시스템 프로그래밍이랑은 거리가 더더욱 멀었죠. 생산성 높은 언어들은 많이 나왔지만 제각기 다른 자리를 찾아 갔고(역시 대부분 웹...) 임베디드 분야에서는 C/C++ 말고는 여전히 별로 선택권이 없습니다.

여튼 OS와 자체적인 개발언어를 가진 확고한 플랫폼 벤더인 애플이 아이폰을 내놓게 되고... 구글도 안드로이드를 내놓고 크롬 OS를 내놓으며 플랫폼 싸움에 발을 들이게 됩니다(그리고 스마트폰 바람이 불게 되죠, 우리 나라는 좀 아닌 거 같지만...).

GO 프로젝트의 시작이 거의 2년 전이군요. 추측일 뿐이지만 아마 안드로이드든 무엇이든 OS가 아니더라도 검색엔진을 비롯한 gmail 등등 구글이 갖고 있는 플랫폼의 Backend로 C언어를 계속 가져가는 것은 생산성이나 유지보수 측면에서 한계가 있다고 생각했을 지도 모르겠습니다. 좀 더 상상의 나래를 펴자면 구글도 애플의 Obj-C 같은 것을 갖고 싶었을 지도...? -_-

홈페이지에는 GO를 만든 이유에 대해 다음과 같이 써 있네요.

 

Go was born out of frustration with existing languages and environments for systems programming. Programming had become too difficult and the choice of languages was partly to blame. One had to choose either efficient compilation, efficient execution, or ease of programming; all three were not available in the same mainstream language. Programmers who could were choosing ease over safety and efficiency by moving to dynamically typed languages such as Python and JavaScript rather than C++ or, to a lesser extent, Java.

Go is an attempt to combine the ease of programming of an interpreted, dynamically typed language with the efficiency and safety of a statically typed, compiled language. It also aims to be modern, with support for networked and multicore computing. Finally, it is intended to be fast: it should take at most a few seconds to build a large executable on a single computer. To meet these goals required addressing a number of linguistic issues: an expressive but lightweight type system; concurrency and garbage collection; rigid dependency specification; and so on. These cannot be addressed well by libraries or tools; a new language was called for.


요약하자면, 인터프리터 언어의 용이한 프로그래밍 스타일, 효과적이고 안전한 다이나믹 타이핑을 가진 컴파일 언어 -_- 이면서 현대적이고 네트웍과 멀티코어 컴퓨팅이 지원되고 빠른 -_-;; 시스템 프로그래밍 언어가 필요해진 시대의 요구(이건 제가 쓴 말 -_-)에 발맞추어 나왔다... 정도가 되겠습니다.

네, 이런 건 위에 나온 말처럼 아무리 좋은 라이브러리나 툴이 나온다고 해결이 되는게 아니죠. 근데 그렇다고 새로운 언어를 뚝딱 만들어서 해결할 능력을 지닌 조직이 많은 것도 아닙니다 -_-;;;
GO가 정말 그렇게 뛰어난 지는 아직 제가 판단할 수 있는 문제는 아닌 거 같군요. 하지만 프로젝트 멤버들의 면면은 화려하긴 합니다.
Robert Griesemer, Rob Pike, Ken Thompson... 유닉스 역사책에나 나올 법한 이름이 있죠? ㅡㅡ;

여튼 이 프로젝트가 안정화 되면 GO는 구글 플랫폼의 Backend 언어가 될 가능성이 높아 보이네요. 물론 이것도 사견..-_-

GO의 feature들을 몇 가지 정리하자면...


1. OOP 언어는 아닙니다. 인터페이스나 리플렉션을 지원하지만 기본적으론 시스템 프로그래밍에 촛점이 맞추어져 있습니다.
2. 컴파일 언어입니다. 자바나 닷넷처럼 vm이 끼어드는는 방식이 아닌 순수 컴파일 언어입니다.
3. Dynamic Typing을 지원합니다....만 왠지 스무스해 보이진 않네요 -_-
4. map 타입도 지원합니다. 때론 편하죠 -0-;
5. 포인터를 지원합니다. 하지만 포인터 연산은 지원하지 않습니다. 메모리 침범 에러의 소지는 없어진 셈입니다.
6. 같은 맥락에서 배열의 []도 첨자가 배열의 크기를 벗어나지 못합니다. C에서는 그냥 포인터의 더하기 연산자였기 때문에 배열 크기랑 상관없었습니다.
7. Java처럼 문자열이 immutable하게 바뀌었습니다. 이것도 메모리 오류를 막아주게 되었군요.
8. UTF-8 지원이 포함되어 있습니다.
9. 배열에서의 slice 연산도 지원합니다(Python처럼).
10. Concurrent 프로그래밍 요소들을 지원합니다.

이것 말고도 물론 많은데 다 쓸 수는 없고...;
다음 링크도 보세요.

http://www.cowlark.com/2009-11-15-go/

Go와 Brand X라는 언어를 비교한 글입니다. 브랜드 X의 정체는 마지막에...

Go는 흥미롭긴 한데 사실 아직은 왠지 다듬어지지 않은 느낌이 드네요. 추후의 추이에 관심이 생깁니다.

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

프로그래밍 커뮤니티의 존재 가치  (6) 2009.12.18
GO  (7) 2009.11.19
기술 교육  (0) 2009.10.01
회의는 왜 하나요  (6) 2009.08.30
Trackback 0 And Comment 7

AspectJ 맛보기

|

최근에 AOP 기술이 주목받고 있는데요. 저도 우연찮게 기회가 되어 AspectJ를 공부할 기회가 생겼습니다. 뭐 아는 분은 아시다시피 지금은 C 프로그래머가 아니기 때문에...-_-;

첨엔 문법도 생소하고 해서 좀 힘들었는데 개념 자체가 새로운(?) 것이라 그렇지 이해하기에는, 혹은 초기 수준의 접근은 크게 어려운 건 아니더군요. 깊이 파고 들면 또 어려운 부분이 나오지 않을까 합니다만...

뭔가 새로운 기술 혹은 언어를 익힐 때는 manual보다는 사실 tutorial을 선호하는 편입니다. 아무래도 '백문 백견이 불여일타'이듯 문서 백날 봤자 튜토리얼 따라 해보면서 review를 하는게 훨씬 남게 됩니다.
근데 AspectJ는 아직 대중적인 툴이 아니라 그런지 맘에 드는 tutorial이 별로 없더군요. 마침 괜찮은 tutorial을 찾아 소개 겸 블로그에 올립니다. 단, 너무 짧고 간단한게 흠입니다 -_-

(이후는 http://www.tutorialhero.com/click-46615-intro_to_aspect_oriented_programming_with_aspectj.php 의 번역입니다)

이제 당신은 프로젝트를 모두 마치고 런칭할 준비가 되었습니다. 두 달이 지나 고객은 기능 추가를 결정합니다. 다시 말하면 당신은 나름 괜찮은 구조를 가진 코드의 중요한 부분들을 기존 스펙에도 없던 사소한 요구사항들 때문에 뜯어 고쳐야 합니다. 코드를 직접 수정하지 않고 부가적인 기능을 추가할 방법이 존재했었더라면... (ㅠㅠ)

그런게 바로 있습니다! 그게 바로 AOP(Aspect Oriented Programming가 존재하는 이유입니다. 이름만 듣고 두려워하지 마세요. AOP란건 당신의 코드를 수정하지 않고 추가 코드를 넣을 수 있게 해주는 것을 의미할 뿐입니다.

헷갈리시나요? 설마요. Aspect라는 깔끕한 자바 라이브러리만으로 해결됩니다. 일단 간단한 getter/setter 클래스를 하나 만들죠, Car라는 이름으로요. 클래스는 차의 색깔에 대한 getter와 setter를 가지고 있습니다(getColor/setColor).
이제 차의 색깔이 바뀔 때마다 print문이 호출되도록 할 겁니다. 위의 Car 클래스는 수정하지 않고 말이죠.

첫번째로 Car 클래스를 만듭니다. 다음 코드처럼요.

이제 우리가 필요한 것은 컴파일러에게 setColor가 호출될 때마다 추가적인 코드를 실행해 달라고 말해주는 겁니다. 이를 위해 컴파일러는 프로그램 실행을 가로채고 추가 코드를 삽입할 지점을 알아야겠죠. 이 특정 지점은 POINTCUT이라 불리며 ASPECT라 불리는 파일에 정의됩니다. setColor에서 뭔가 해 주기 위한 포인트컷 스펙의 문법은 다음과 같습니다.

이 부분은 단순히 컴파일러에게 setColorCall이라는(역주:본문에는 setColorPointCut이라고 되어 있으나 오류로 보임), String 인자를 지니는 public void형의 setColor란 메써드가 호출 될 때를 위한 새로운 포인트컷을 만든다고 말해줍니다.
포인트컷은 또한 와일드카드를 받아들입니다. 만약 예를 들어 Car 클래스의 모든 메써드 호출을 가로채고 싶다면 다음과 같이 하면 됩니다.

포인트컷이 준비되었으면 이제 실제 우리가 실행할 코드를 추가합니다. 이는 ADVICE라 불리며 다음 과 같이 작성합니다.

이는 컴파일러에게 위의 코드를 포인트컷 이전에 실행해달라는 요청입니다. "before"대신에 "after"를 쓸 수도 있냐구요? 예리하십니다.

이 모든 코드는 aspect라 불리는 파일에 들어갑니다. 다음과 같이 되겠죠.

파일 이름은 CarAspect.aj라고 합니다. 확장자는 자바 클래스가 아니라 AspectJ의 aspect임을 뜻합니다. 이제 Car 클래스를 호출하는 운전자 클래스를 만들어서 제대로 동작하는지 살펴볼 겁니다.

일단 AspectJ 툴이 깔려 있어야 CLI(Commnad Line Interface)에서 다음 커맨드로 컴파일이 가능합니다.

ajc CarAspect.aj CarDriver.java Car.java

AspectJ는 http://www.eclipse.org/aspectj 에서 다운 받으시고 aspectjrt.jar는 클래스 패스에 들어가 있어야 합니다. 아니면 제대로 안 돌아가겠죠. 이제 다음을 실행해 봅시다.

java CarDriver

그럼 출력은 다음과 같을 겁니다.

The car color has changed!

AspectJ는 매우 강력한 툴이며 이 간단한 예제보다 매우매우 흥미롭고 인상적인 일들을 할 수 있습니다. 일단 http://www.eclipse.org/aspectj 에 들러서 문서들을 훑어 보시기를 권합니다. 여기는 또한 괜찮은 aspect 이클립스 플러그인 사이트이기도 합니다(역주: AspectJ 플러그인을 받아서 이클립스로 간단하게 작성 가능).

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

일하면서 배우기  (8) 2009.06.18
AspectJ 맛보기  (0) 2009.05.28
막장 프로젝트  (4) 2009.05.06
Head First Software Development  (2) 2009.04.25
Trackback 0 And Comment 0

오라클 $5.6b 에 썬 마이크로 시스템즈 인수

|
원래 뉴스성 글은 잘 안 올립니다만... 야밤에 정신이 번쩍 들어서...ㅡㅡ;
저랑 관계가 있다면 관계가 있는 뉴스이기도 하고...

http://blogs.zdnet.com/BTL/?p=16598

여튼 내일되면 한글 뉴스가 뜨겠지만서도... 정말 놀라운 소식이네요, 뭐라 할 말이...-_-

요약하면 대략 56억 달러에(썬의 부채 포함 74억) 오라클이 썬 마이크로 시스템즈를 인수하기로 했다는 거고요. 발표에 덧붙여 '자바는 오라클이 가진 S/W중 가장 중요한 것이 될것이다' 이런 코멘트도 했네요.
HP와 잠시 하드웨어 협업을 했었지만(엑사데이터 얘기죠) 이제 완전히 다른 회사로 태어났다..는 얘기도 있고...

DB를 제외하면 오라클의 미들웨어 라인업은 자바를 빼놓고 얘기할 수 없고.. DB를 위한 하드웨어도 얻은 셈이 됐네요.
DB 아랫쪽의 플랫폼이 아쉽던 오라클에겐 확실히 괜찮은 딜인 것으로 보이긴 합니다만... 언브레이커블 리눅스 같은 뻘-_-짓은 더이상 안해도 되겠군요.

기사엔 여러가지 시나리오를 장난스럽게 써놓았는데..

  • 오라클이 IBM에게 성가신 상대가 된다
  • MySQL이 사라진다(이건 좀 우려스럽네요)
  • 오라클이 Sun에서만 돌아간다(이것도 좀..-_-)
  • Sun은 강력한 S/W 시리즈를 갖는다(비싸게 팔 수 있겠죠)

음.. 그리고 썬이 그렇게 싼 회사라고 생각진 않는데 피플 소프트나 시블에 비해 싼 가격으로 인수했다고 써 있네요.

http://blogs.zdnet.com/Burnette/?p=1050

이 기사를 보면 Sun이 10센트에 영혼을 팔았다..고 제목을 달아 놓았습니다.
주당 $9.4로 IBM과 협상 결렬됐는데 오라클과는 주당 $9.5에 합의했다는 얘기죠 -_-;

그리고 의미심장한 말이 있는데...
"개발자들이 땀흘려 MySQL을 만들어냈던 이유는 오라클 같은 상용 DB에 대한 반대급부의 해결책을 제공하는 것이었는데 이제 그들이 만든 자식같은 S/W가 그동안 힘들게 맞서 싸워왔던 오라클에게 팔린다"
이 말에 제목의 의미가 다 들어 있군요. 썬이 그동안 오픈소스를 지원한게 뭐가 되냐...는 얘기인가요.
(근데 오라클엔 오픈소스 DB의 원조격이자 MySQL의 모태인 Berkley DB도 있죠. 이것도 산거지만... 어쨌든 아직은 오픈소스... -_-;)

그러고보니 두번째 링크는 첫번째 링크에 비해 굉장히 부정적인 기사군요.
심지어 '썬에 오라클보다 더 나쁜 파트너가 있을 수 있을지 상상이 안간다'는 말도...ㅡㅡ;
차라리 IBM으로 갔으면 IBM의 자바 라인업과 썬의 자바팀이 좋은 시너지 효과를 냈을 거라고도 썼네요. 이클립스와 넷빈즈도 서로 좋은 영향을 줄 수 있었을 거라면서...

뭐... 저는 좋다 나쁘다는 말을 하긴 좀 그렇군요.
저도 오픈소스 애호가이다보니 MySQL이나 넷빈즈가 사라지는 건 원치 않습니다만... 저변이 넓든 좁든 오픈소스이든 클로즈드 소스이든 라인업은 다양하게 존재하는게 좋지 않을까요. 마이너리티도 세상엔 있죠.
이클립스가 득세한다고 그 외의 IDE를 다 없애버릴 이유는 없는 거 아닌가요. 물론 오라클 입장에서는 네이티브 IDE인 JDeveloper와 BEA에서 온 이클립스 기반의 워크샵까지 있는 마당에 넷빈즈는 눈길이나 줄런지 몰겠지만...-_-;

여튼 저는 충격 속에 이만..ㅡㅡ;


*p.s. : 그리고 옮길 만한 (괜찮은) 회사가 없어진다는 것도 점점 와닿네요(모 지인의 말씀).
Trackback 1 And Comment 2

SQLite 사용자 함수 추가

|
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 
#include 
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한 내용으로...

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

Fossil  (4) 2010.02.19
SQLite 사용자 함수 추가  (0) 2009.04.03
SQLite 페이지 핸들링(3) - 레코드 포맷  (3) 2009.02.10
SQLite 페이지 핸들링(2) - SQLite의 페이지 포맷  (0) 2008.09.30
Trackback 0 And Comment 0

SQLite 페이지 핸들링(3) - 레코드 포맷

|
이전 목록:
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을 높이는데 큰 부분을 차지한다고 저는 생각하거든요 ^^
Trackback 0 And Comment 3

SQLite R-tree 지원 예정

|
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 아닐까요...ㅡㅡ;

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

SQLite 페이지 핸들링(1) - SQLite의 구조  (5) 2008.08.03
SQLite R-tree 지원 예정  (3) 2008.07.22
SQLite non-C API 소개  (3) 2007.08.20
SQLite C API 소개  (4) 2007.08.08
Trackback 0 And Comment 3
prev | 1 | next