SQLite 이준희 *, 신민철 **, 장용일 ***, 박상현 **** LG. 요약 Abstract SQLite is a popular relational database management system(rdbms) mainly used in local application, embedded device, and smartphone. In order to preserve transactional atomicity and durability, SQLite uses recovery schemes that are based on physical logging. Physical logging generates large log file, because whole page is stored even if only a small portion of page is modified. Therefore, log maintenance cost of physical logging is expensive, and it causes delay in applications that use SQLite. In this paper, we propose a new recovery scheme for SQLite, Delta-WAL. Delta-WAL is a recovery scheme based on logical logging, and reduces log size by storing only operation code and input values. In experiment, Delta-WAL generated smaller log compared to existing recovery schemes, and also showed improved transaction throughput. Keywords SQLite, recovery scheme, logical logging, DBMS LG MC Chief Research Engineer ž Received: Oct. 28, 214, Revised: Nov. 17, 214, Accepted: Nov. 2, 214 ž Corresponding Author: Sanghyun Park Dept. of Computer Science, Yonsei University, 533-1, 3rd Engineering Building Sinchon-dong, Seodaemun-gu, Seoul-si, 69-756, Korea, Tel.: +82 2 2123-7757, Email: sanghyun@cs.yonsei.ac.kr
182 SQLite (DBMS, Database Management System). DBMS /. DBMS DBMS SQLite[1], MySQL[2], PostgreSQL[3], Oracle[4]. DBMS. DBMS. DBMS 1 ACID [5]. DBMS (,, ). DBMS (Atomicity). DBMS,. SQLite DBMS (Rollback Journal) Write-Ahead Logging(WAL). WAL. SQLite [6][7], SQLite. SQLite Delta-WAL( DWAL). DWAL,.. 2 DBMS SQLite. 3 SQLite DWAL 4 DWAL. 5 DWAL 6. DBMS. (Physical Logging). (Undo), (Redo). /. (Logical Logging)
..,. physiological logging. /. / /. SQLite D.Richard Hipp 2 8. SQLite ANSI-C.,.,,, [8]. SQLite 3.8.6. 2.2.1 SQLite SQLite [9][1] WAL., ( < >-journal ),.. WAL. WAL, WAL WAL( < >-WAL ). WAL. WAL (1) (WAL ) (2). WAL WAL WAL. WAL. WAL. 2.2.2 SQLite SQLite DBMS B-. SQLite 1. SQLite DBMS SQLite I/O. 1. 1byte [11].,,, sqlite_master.
184 SQLite Database Header (1 byte) Schema Table Page 2 Page 3 (sqlite_master) Page 1 (Header Page) B-Tree Pages Database Header Schema Table (sqlite_master) Header Page 11 Pgno 28 Pgno Non-leaf Node 11 Pgno 18 Pgno 28 Pgno 3 Pgno 35 Pgno 11 Record 16 Record 18 Record 24 Record Leaf Node 28 Record 29 Record Non-leaf Node Page Header ptr 1 ptr 2 ptr 3 ptr 4 ptr 5 Rightmost child s pgno Cell Pointer Array Leaf Node Page Header ptr 1 ptr 2 ptr 3 ptr 4 ptr 5 key5 pgno5 key4 pgno4 key3 pgno1 Rec 5 Rec 4 pgno3 key2 pgno2 key1 pgno1 Cell Rec 3 Rec 2 Rec 1 SQLite B- B- rowid (Attribute) B- (Key). B- B-. B- 2(a) B+ non-leaf leaf. 2(b) B-. slotted-page [12] (Cell). Non-leaf
. leaf. SQLite ( B- ), non-leaf ( row id). 2.2.3 SQLite Jeong [13] I/O trace 9% SQLite SQLite. Kang FTL X-FTL [14]. X-FTL SQLite I/O., X-FTL copy-on-write DWAL. SQLite. [15][16] SQ Lite,.. DWAL WAL,. DWAL. 3.1 DWAL. 3.2 3.3 3.4 3.5 DWAL. 3.6 DWAL SQLite. DWAL. 2 2.
186 SQLite 1) SQLite. 2) SQLite DWAL. DWAL (Cell_Insert, Cell_Drop), (Page_alloc, Page_empty, Page_erase, Page_ stressed), B- (Copy_Cells, Assemble_Page),,,. Page_ stressed SQLite (Buffer Management Policy). SQLite. SQLite SQLite Pager Stress.. 3.2. DWAL DWAL. 3. Opcode Page Version Number Page Number Cell index Data Opcode 2. Page Number, Cell index. Cell index Data Opcode. 2 Page_stressed. SQLite., Pager Stress. DWAL PagerStress Data. Page Version Number(PVN). PVN 1 PVN 1., PVN DWAL PVN 4. DWAL SQLite. slotted-page 4..,, (lower, upper),. (offset, length). Pointer n byte n.
Lower Page Header Pointer 1 (offset, length) Pointer 2 (offset, length) Pointer 3 (offset, length) Free Space Log Entry 3 Log Entry 2 Log Entry 1 Upper pointer. DWAL. 2. DBMS.. DWAL 1. DWAL ( 1 1). ( 2) ( < >-DWAL ) ( 3-5). os fsync ( 6). ( 7-8). DWAL.,. fsync, fsync. DWAL fsync. Fsync.
188 SQLite fsync. DWAL SQLite,. 2. DWAL (Backward Traversal) Page_stressed ( 2 1-2 ).. ( 3)., PVN PVN ( 4-5). PVN ( 6). (Forward Traversal), 2 SQLite ( 7-9). DWAL WAL. WAL WAL ANR (Application Not Responding). DWAL (fsync). ACID. DWAL..,,. DWAL,. Pager_stressed ( 2 1-3 ). Pager_stressed..
,.,.. 3.5 DWAL. 1). 4.1 Pager_stressed ( 2 1-3 ). 2). DWAL ( 3),.. SQLite.. DWAL.. DWAL SQLite, WAL. 3 TPC-C [17]. TPC-C TPC-C. DWAL,, 3. 1 1 1. 1 1. 3, 2, 2.
19 SQLite 5. WAL 3 DWAL.. WAL 2 DWAL. WAL DWAL.. SQLite B-. B- B-. SQL B-. WAL..... DWAL. WAL,. DWAL. 25 25 25 Elapsed Time(ms) 2 15 1 5 Elapsed time(ms) 2 15 1 5 Elapsed time(ms) 2 15 1 5 1 2 3 4 5 6 Number of index 1 2 3 4 5 6 Number of index 1 2 3 4 5 6 Number of index 8 7 21 18 7 6 Size of log file(bytes) 6 5 4 3 2 Size of log file(bytes) 15 12 9 6 Size of log file(bytes) 5 4 3 2 1 3 1 1 2 3 4 5 6 Number of index 1 2 3 4 5 6 Number of index 1 2 3 4 5 6 Number of index
DWAL (real workload). TPC-C 8 scale factor 1 35MB. TPC-C 5 (New Order, Payment, Delivery, Order Status, Stock Level) Order Status Stock Level.,. 4 1 6. 6 2 2 3 Overall. Transaction per Second(txn/s) 2 16 12 8 4 DELIVERY NEW_ORDER PAYMENT OVERALL Transaction TPC-C DWAL. DWAL 3 DELIVERY, NEW_ORDER 2 PAYMENT WAL. 2 5 ( 6 Overall) DWAL. DBMS SQLite DWAL. DWAL SQLite, WAL. DWAL TPC-C WAL. DWAL. DWAL. DWAL. SQLite. SQLite DWAL (UX). [1] SQLite, http://sqlite.org/ [2] MySQL, http://www.mysql.com/ [3] PostgreSQL, www.postgresql.org/ [4] Oracle Database, http://docs.oracle.com/cd/e11882_ 1/server.112/e25789/intro.htm [5] S. Abraham, K. Henry, and S. Sudarshan, "Database System Concepts 6th edition", McgrewHill, pp.
192 SQLite 628, 211. [6] H. Kim, N. Agrawal, and C. Ungureanu, "Revisiting storage for smartphones", In Proceedings of USENIX Conference on File and Storage Technologies, 212. [7] K. Lee and Y. Won, "Smart Layers and Dumb Result: IO Characterization of an Android-Based Smartphone", In Proceedings of ACM EMSOFT, pp. 23-32, 212. [8] Well-Known Users of SQLite, http://www.sqlite. org/famous.html [9] V. Prabhakaran, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau, "Analysis and Evolution of Journaling File Systems", In proceedings of USENIX Annual Technical Conference, pp. 15-12, 25. [1] D. Woodhouse, "JFFS : The Journalling Flash File System", In Proceedings of the Ottawa Linux Symposium, 21. [11] SQLite Database Header, http://www.sqlite.org/ fileformat2.html#database_header [12] S. Abraham, K. Henry, and S. Sudarshan, "Database System Concepts 6th edition", Mcgrew Hill, pp. 1147, 211. [13] S. Jeoung, K. Lee, S. Lee, S. Son, and Y. Won, "I/O Stack Optimization for Smartphones", 213 USENIX Annual Technical Conference, 213. [14] W. Kang, S. Lee, and B. Moon, "X-FTL: Transactional FTL for SQLite Databases", SIGMOD 13, 213. [15] S. Jeon, J. Bang, K. Byun, and S. Lee, "A recovery method of deleted record for SQLite database", Personal and Ubiquitous Computing, Vol. 16, Issue 6, pp. 77-715, Aug. 212. [16] Gyu-Won Lee, Seung-Jei Yang, Hyun-Uk Hwang, Kibom Kim, Taejoo Chang, and Ki-Wook Sohn, "A Recovery Scheme for the Deleted Overflow Data in SQLite Database", Journal of KIIT, Vol. 1, No. 11, pp. 143-153, Nov. 212. [17] Transaction Processing Performance Council, TPC BENCHMARK C Standard Specification Revision 5.11, 21. 이준희 (Joonhee Lee) 신민철 (Mincheol Shin) 장용일 (Yongil Jang) 박상현 (SangHyun Park)