::: 삼성전자 소프트웨어멤버십 블로그 :::

블로그에 글을 처음 써보네요;
사용법이 익숙하지 않아 이상하더라도 양해 부탁드립니다!
우선, 구현에 앞서 논문과 각종 책, 소스를 분석하며 정리한 내용들을 올릴까 합니다.

지금 작업하고 있는 DB library에 관련 된 부분으로 대략 정리해보겠습니다.
원래, Flash DB의 대략적 모습을 그리고 시작하는 것이 좋겠지만, 현재 정리하고 있는 자료가 이 쪽 부분이라,
추후에 저희 팀이 개발하고 있는 DBMS의 전체 모듈을 올리도록 하겠습니다.
우선, DB library는 DB에 접근하는 방식에 따라 두 가지로 분류할 수 있습니다. 각각이 일장 일단을 갖고 있겠지만,

저희가 선정 / 구현 중인 모델은 Decentralized access 입니다.

1) Centralized Approach
이 모델은 DB Manager라는 process를 두어 오직 이 process 만이 DB와 통신을 하도록 하는 것입니다.
그리고 다른 process들은 IPC를 통해 DB manager에게 요청을 하고 응답을 받을 수 있는 것이죠.
이렇게 함으로써 취할 수 있는 장점으로는 우선, DB 접근 연산에 대한 사용자 튜닝이 쉽다는 것입니다.
즉, 외부 프로세스(요청 프로세스)들 간의 우선 순위를 DB manager를 통해 쉽게 결정 지을 수도 있습니다.
이런 것은 중앙형 모델에서 나타나는 관리의 편의성, 그런 것과 연관이 있다고 생각이 됩니다.
또 다른 장점으로는 Recovery가 쉽다는 것인데, 이는 어느 임의 상태의 정보가 모두 DB manager에게 있게 되므로,
쉽게 어떤 상태로의 회귀가 편하다는 점이겠죠. 이는 복구가 쉬운 반면, DB manager가 복구 불가능이 될 경우,
심각한 사태를 가져올 수 있는 면도 있다는 생각이 듭니다.
반면, 단점은 한 프로세스만이 DB와 통신을 하니까 전달에 대한 오버헤드(한 단계 거치게 되는 점...),
중앙 프로세스가 죽어버리면 전체 DB가 죽는다는 점 등, 일반적인 중앙형 모델에서 나타나는 단점이 되겠네요.

2) Decentralized Approach
이 모델은, 모든 process가 DB와 통신이 가능하지만, 대신 데이터의 일관성 유지를 위해 Locking이라는 메카니즘이 필요합니다.
장점으로는 모든 프로세스가 DB에 접근이 가능하니까 운용에 있어 탄력이 있다할 수 있습니다.
또한 DB 운용에 있어 안전성을 갖는다 할 수 있습니다. Centralized model과 같이 DB manager가 죽는다고
그래서 DB 전체가 죽는 일은 생기지 않게 됩니다.
Linux 환경에서는 Decentralized model로 DB를 구현하는 것이 시스템 운용적 측면에서도 더 적당하다는 생각에
저희 project는 dectralized model로 DB library를 구현하고 있습니다.



다음으로, Key의 저장을 위한 Data structure입니다.
Key는 수많은 DB record 중에서 어느 특정 record를 식별할 수 있는 식별자라 할 수 있습니다.
따라서 key로 그 전체 record를 검색하게 되는 것입니다. 검색에 있어 효율성을 가져오기 위해 key를 저장하는데에는
빠르고 효율적인 검색을 위한 자료구조가 필요합니다.

일반적으로 상업용 DB는 B+ tree를 사용하고 있지만, flash memory 상에서 B+ tree는 적당한 자료구조라 할 수 없습니다.
데이터의 삽입 / 삭제를 위해서 해당 엔트리의 삭제 이외의 전체 구조 유지(깊이를 일정하게 유지하는 등)를
위한 추가적 삭제 / 쓰기 연산이 발생하기 때문입니다.
장점으로는 시퀀셜 검색에서 빠른 성능을 보일 수 있다는 것입니다. 이는 B tree의 개선으로 각 leaf 노드 간에도
링크를 갖도록 하였기 때문입니다. 제자리 검색을 지원한다는 점, 깊이를 항상 일정하게 유지하도록 하므로
평균 검색 시간이 좋고, 정렬 된 상태로 데이터 구조를 갖으므로 속도가 빠르다는 점입니다.

또 다른 자료구조로는 Hash가 있습니다. Hash는 충돌을 가능한 적게 발생시킬 수 있도록 적당한 hash function의 선정이
필요하고, dynamic hashing 기법 등으로 한 chain이 무한히 길어지게 될 경우에 대한 대처방안을 세울 수 있습니다.
찾고자 하는 값이 어떤 값이던, index file 내에서 chain이 형성이 안되어있는 경우라면, O(1)의 시간 복잡도를
갖게 됩니다. 하지만 일반적으로 chain이 형성되어 우선 hash table로 hash 값을 검색 후, 해당 chain에 대해선
linear search를 하게되므로 이에 대해서 복합적인 자료구조를 선정 / 적용한다면 좀 더 효과적일 수 있습니다.
무엇보다 Hash를 쓰게 되면 좋은 점은 구현이 단순하므로 내부 운용을 위한 오버헤드가 적다는 것입니다.

하지만 Hash의 경우, chain 내부에 입력 순서로 key가 저장되지 않아(free list를 적용) 제자리 검색이 안된다고
합니다. 이 부분은 좀 더 이해가 필요한 부분이라 차후 보충할 수 있도록 하겠습니다.

이상은 DB library의 구현을 위한 부분입니다. 이에 부가적으로 Buffer manager의 구성을 생각해 볼 필요가 있을
거 같습니다. Buffer는 dram 상에 존재하므로 flash memory 접근 보다 빠르게 작동할 수 있습니다.
또한, 쓰기 / 삭제 연산 역시 buffer 내부에서는 자유로우므로 flash memory의 단점을 보완할 수 있는 좋은 계층
이라 할 수 있습니다. 하지만 문제는 전원이 나갈 시, 데이터를 그대로 날릴 수 있다는 점이지요...
Buffer 관리에서는, 언제 flush를 할 것인지, 내부 구조는 어떤 식으로 유지할 것인지, 그 용량은 어느 정도가 적
당한지 등에 대한 고려가 필요하며 이 부분에 대해서는 계속적으로 회의를 통해 이야기 하고 있는 중입니다.

우선, 아래 그림은 Hash를 사용하였을 경우 index file과 data file의 구조입니다.
DB의 disk 상 구성은 가장 간단한 형태인 index file과 data file을 생각하고 있지만 필요에 따라 변동 될 수 있을
것 같습니다. Index file은 key와 그 key가 식별하는 data의 data file내 위치를 담으며, 삭제 연산 발생 시는,
free list pointer를 통해 삭제 된 field를 관리합니다. data file은 말 그대로 record 전체를 담고 있게 됩니다.

이상은 현재 구현을 위해 정리해 놓은 내용들입니다. 앞으로는 좀 더 자주 블로그를 이용하도록 하겠습니다.

좋은 하루 되세요 ^^

PS. 수업 시간 다가와서 빨리 올리려고 허둥거리다 날리고 다시 쓴 거랍니다. ㅡㅜ