MEMS storage devices and flash memory are new non-volatile secondary storages that have outstanding advantages over magnetic disks. MEMS storage devices are much different from magnetic disks in the structure and access characteristics in the following ways. They have thousands of heads called {\it probe tips} and provide the following two major access facilities: (1) {\it flexibility}: freely selecting a set of probe tips for accessing data, (2) {\it parallelism}: simultaneously reading and writing data with the set of probe tips selected. Flash memory also has access characteristics much different from those of magnetic disks in the following ways. It does not have seek and rotation latency. In order to overwrite existing data, an erase operation must be performed before writing new data. We propose new methods for effectively handling those new storage devices in the DBMS.
In the first part of this dissertation, we propose a simple logical model called the {\it Region-Sector} ({\it RS}) model that abstracts major characteristics affecting data retrieval performance, such as flexibility and parallelism, from the physical MEMS storage model. We also suggest heuristic data placement strategies based on the RS model. To show the usability of the RS model, we derive new data placements for relational data and two-dimensional spatial data by using these strategies. Experimental results show that the proposed data placements improve the data retrieval performance by up to 4.7 times for relational data and by up to 18.7 times for two-dimensional spatial data of approximately 320 Mbytes compared with those of existing data placements. Further, these improvements are expected to be more marked as the database size grows.
In the second part of this dissertation, we propose an effective and efficient method of storing data called {\it page-differential logging} for flash-based storage systems. The primary characteristics of our method are: (1) it writes only the difference (which we define as the {\it page-differential}) between the original page in flash memory and the up-to-date page in memory; (2) the page-differential is computed and written only once at the time the page needs to be reflected into flash memory. The former characteristic distinguishes itself from existing page-based methods that write the whole page including both changed and unchanged parts of data or from log-based methods that keep track of the history of all the changes in a page. Our method allows existing disk-based DBMSs to be reused as flash-based DBMSs just by modifying the flash memory driver, i.e., it is DBMS-independent. Besides, it improves the longevity of flash memory by reducing the number of write operations. Experimental results show that the proposed method is superior in I/O performance, except for some special cases, to existing page-based or log-based methods. It improves the performance of update operations by 0.90 $\sim$ 3.18 times over the page-based method and by 0.97 $\sim$ 8.15 times over the log-based one. It also improves the performance of various mixes of read-only and update operations by 0.50 (the special case when all transactions are read-only on updated pages) $\sim$ 2.97 times over the page-based method and by 0.97 $\sim$ 3.08 times over the log-based one for synthetic data of approximately 1 Gbytes.
We summarize the contributions of this dissertation as follows. First, we have proposed a logical model that allows users to easily understand and to effectively use the complex MEMS storage device. Then, we have suggested heuristic data placement strategies based on the model and have derived new data placements for relational data and two-dimensional spatial data by using these strategies. Second, we have proposed a DBMS-independent method of storing data into flash memory that improves the overall performance of flash-based storage systems. Finally, we have shown the effectiveness of the proposed methods by extensive experiments.
MEMS 저장장치와 플래시 메모리는 마그네틱 디스크에 비해 매우 뛰어난 장점들을 가진 비휘발성 보조 기억 저장장치이다. MEMS 저장장치는 디스크와는 매우 다른 구조와 액세스 특성들을 가진다. MEMS 저장장치는 {\it probe tips}이라 불리는 수천 개의 헤더들을 가지며, 두 가지 중요한 액세스 특성인 (1) {\it flexibility}: 데이타를 액세스하기 위한 probe tip들을 자유롭게 선택할 수 있는 특성과 (2) {\it parallelism}: 선택된 probe tip들을 가지고 데이타를 동시에 읽거나 쓸 수 있는 특성을 가진다. 플래시 메모리 역시 디스크와는 매우 다른 액세스 특성들을 가진다. 플래시 메모리는 탐색 시간과 회전 대기 시간을 가지지 않으며, 기존 데이타를 덮어쓰기 위해서는 새로운 데이타를 기록하기 전에 삭제 연산이 먼저 수행되어야 하는 특성을 가진다. 본 학위논문에서는 DBMS에서 이러한 새로운 저장 장치들을 효과적으로 핸들링하기 위한 방법들을 제안한다.
본 학위논문의 첫 번째 파트에서는 물리적 MEMS 저장장치 모델로부터 flexibility와 parallelism과 같이 데이타 retrieval 성능에 영향을 미치는 중요한 특성들을 추상화한 {\it Region-Sector} ({\it RS})라 불리는 간결한 논리적 모델을 제안한다. 그리고, 제안된 RS 모델에 기반한 휴리스틱 데이타 배치 전략들을 제안한다. 또한, RS 모델의 유용성을 보이기 위하여 제안된 데이타 배치 전략들을 사용하여 관계형 데이타와 2차원 공간 데이타를 위한 새로운 데이타 배치들을 도출한다. 실험 결과, 도출된 데이타 배치들은 기존 연구들의 데이타 배치들에 비해 관계형 데이타에 대해서는 최대 4.7배, 2차원 공간 데이타에 대해서는 최대 18.7배 데이타 retrieval 성능을 향상시켰다. 이러한 성능향상은 데이타베이스 크기가 증가할수록 더욱 두드러질 것으로 기대된다.
학위논문의 두 번째 파트에서는 플래시 기반 저장 시스템을 위한 {\it page-differential logging}이라 불리는 효과적이면서도 효율적인 데이타 저장 방법을 제안한다. 제안된 방법의 주요한 특징은 (1) 플래시 메모리 내의 원본 페이지와 메모리 내의 최신 페이지간의 차이점 ({\it page-differential}이라 정의함)만을 기록한다는 것과 (2) page-differential은 페이지가 메모리 상에서 갱신될 때마다 계산되어 기록되는 것이 아니라 갱신된 페이지가 플래시 메모리에 반영될 필요가 있을 때에만 계산되어 기록된다는 점이다. 이러한 특징들은 본 방법을 데이타의 변경된 부분과 변경되지 않은 부분 모두를 포함하는 페이지 전체를 기록하는 기존 페이지 기반 방법들 또는 페이지 내의 변경사항들(changes)의 기록을 모두 유지하는 기존 로그 기반 방법들과 구별 지어 준다. 본 방법은 단지 플래시 메모리 드라이버(driver)만을 고침으로써 기존 디스크 기반 DBMS들이 플래시 기반 DBMS들로 재사용될 수 있도록 해 준다. 즉, 본 방법은 DBMS-independent하다. 또한, 쓰기 연산의 횟수를 줄임으로써 플래시 메모리의 수명을 향상시킨다. 실험 결과, 제안된 방법은 몇 가지 특별한 경우를 제외하고는 기존 페이지 기반 방법들과 로그 기반 방법들에 비해 더 뛰어난 성능을 가진다. 제안된 방법은 update 연산들의 성능을 페이지 기반 방법에 비해 0.90 $\sim$ 3.18배, 로그 기반 방법에 비해 0.97 $\sim$ 8.15배 향상시켰다. 또한, 약 1Gbytes의 합성 데이타에 대해 read-only와 update가 다양한 비율로 혼합된 연산들의 성능을 페이지 기반 방법에 비해 0.50(모든 트랜잭션들이 갱신된 페이지에 대해 읽기 연산만을 수행하는 특별한 경우임) $\sim$ 2.97배, 로그 기반 방법에 비해 0.97 $\sim$ 3.08배 향상시켰다.
본 학위논문의 공헌을 요약하면 다음과 같다. 첫째, 복잡한 MEMS 저장장치를 사용자들이 쉽게 이해하고 효과적으로 사용할 수 있게 해 주는 논리적 모델을 제안하였다. 그리고, 제안된 모델에 기반한 휴리스틱 데이타 배치 전략들을 제시하였고, 제시한 전략들을 이용하여 관계형 데이타와 2차원 공간 데이타에 대해 새로운 데이타 배치 방법을 도출하였다. 둘째, 플래시 기반 저장 시스템들의 전반적인 성능을 향상 시켜주는 DBMS에 독립적인 방식으로 플래시 메모리에 데이타를 저장하는 방법을 제안하였다. 마지막으로, 다양한 실험을 통해 제안된 방법들의 유효성을 입증하였다.
