臺灣博碩士論文加值系統

隨著手持裝置的用戶不斷增加，應用程式的設計者不斷在效能和其他議題上絞盡腦汁，期望獲得更多使用者的青睞。在資料一致性議題上，許多的應用程式都使用SQLite來管理它們的資料，但根據研究顯示SQLite會產生過多的檔案同步操作 (fsync()呼叫)；而實際上fsync()呼叫存在許多的缺點，會導致應用程式的效能不佳：首先，fsync()是一個阻塞呼叫，若其在操作過程中缺乏效率，則會影響應用程式的回應時間；其次，fsync()是一個同步呼叫，它會產生許多小筆且隨機的寫入，這對於使用快閃記憶體為儲存體的安卓裝置造成諸多不利，包括頻繁的垃圾收集和減少快閃記憶體壽命。
本篇研究提出更有效率的檔案同步處理方式，我們命名為迫切同步，並將其實作在F2FS檔案系統上。我們藉由增加平均寫入要求的大小，減輕 I/O處理負擔，並降低寫入串流的個數改善寫入循序度；此外降低整體的寫入量，進而延長快閃儲存裝置的壽命。我們在Google Nexus 7上進行一連串的實驗且結果顯示，在多個受歡迎的安卓應用程式的工作量下，平均和最大的fsync()延遲能分別減少68%和82%，且區塊階層的總寫入量最多可減少20%。

Nowadays, more and more users start to use hand-held device. They care about not only the price but also the application performance. Therefore, programmers always try their best to improve application performance and concern other design issues. To maintain the consistency of data, many popular applications manage their data using SQLite. However, Recent research pointed out that the SQLite involves frequent file synching operations (i.e., fsync() calls). Fsync() calls have many shortcomings which may degree the application performance: First, fsync() is a blocking call that applications could suffer from poor response if the fsync() implementation is inefficient. Second, fsync() is a synchronous call that would cause a lot of small-sized and random write operations. These write operations might incur frequent garbage collections as well as shorten the lifetime of flash-storage-based Android device.
This work purposes an efficient design of fsync() called eager synching. We have implemented eager synching on F2FS file system. By increasing the size of average block request and decreasing write streams, we can alleviate I/O overhead and improve write sequential ratio respectively. Besides, the lifetime of the underlying NAND flash storage would be extended by reducing block write traffic. We conducted a series of experiments on Google Nexus 7 tablet. Our experimental results show that, under the workloads of popular Android applications, the average and max fsync() latencies were reduced by up to 68% and 82%, respectively, and the block-level write traffic was reduced by up to 20%.

中文摘要 i
英文摘要 ii
致謝 iii
目錄 iv
表目錄 v
圖目錄 vi
一、緒論 1
二、相關研究 4
三、命題論述 6
3.1 安卓應用程式檔案存取 6
3.2 F2FS檔案系統 7
3.2.1 磁碟資料結構 7
3.2.2 讀寫流程 9
3.2.3 檔案同步 9
3.2.4 垃圾收集 10
3.2.5 斷電後復原 10
3.2.6 F2FS的fsync() 議題 10
四、 迫切同步：設計和實作 12
4.1 概述 12
4.2整合迫切同步到F2FS 12
4.3 損壞恢復 15
五、 實驗結果 17
5.1 實驗環境和效能指標 17
5.2工作量特徵 18
5.3 實驗結果 19
5.4 迫切日誌vs F2FS垃圾收集 23
5.5 復原測試 25
5.6 動態應用程式回播 25
5.6.1 環境設置和效能指標 25
5.6.2 實驗結果 28
六、 結論 33
參考文獻 34

[1]http://www.gartner.com/newsroom/id/2996817. Smartphone sales in 2014, Gartner, Inc.
[2]Kisung Lee and Youjip Won. 2012. Smart layers and dumb result: IO characterization of an android-based smartphone. In Proceedings of the tenth ACM international conference on Embedded software (EMSOFT '12). ACM, New York, NY, USA, 23-32.
[3]Hyojun Kim, Nitin Agrawal, and Cristian Ungureanu. 2012. Revisiting storage for smartphones. Trans. Storage 8, 4, Article 14 (December 2012), 25 pages.
[4]Hyeong-Jun Kim and Jin-Soo Kim. Tuning the ext4 filesystem performance for Android-based smartphones. In: Frontiers in Computer Education. Springer Berlin Heidelberg, 2012. p. 745-752.
[5]Changman Lee, Dongho Sim, Joo-Young Hwang, and Sangyeun Cho. 2015. F2FS: a new file system for flash storage. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST'15). USENIX Association, Berkeley, CA, USA, 273-286.
[6]Li-Pin Chang; Po-Han Sung; Po-Hung Chen, "Fast file synching for applications in flash-based Android devices," Non-Volatile Memory Systems and Applications Symposium (NVMSA), 2014 IEEE , vol., no., pp.1,6, 20-21 Aug. 2014.
[7]http://man7.org/linux/man-pages/man2/fsync.2.html. Definition of fsync() in POSIX.
[8]S. Jeong, K. Lee, S. Lee, S. Son, and Y. Won. I/O stack optimization for smartphones. In Proceedings of the 2013 USENIX Annual Technical Conference, pages 309–320. USENIX, 2013.
[9]Hyukjoong Kim and Dongkun Shin. 2013. Optimizing storage performance of Android smartphone. In Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication (ICUIMC '13). ACM, New York, NY, USA, , Article 95 , 7 pages.
[10]Daeho Jeong, Youngjae Lee, and Jin-Soo Kim. 2015. Boosting quasi-asynchronous I/O for better responsiveness in mobile devices. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST'15). USENIX Association, Berkeley, CA, USA, 191-202.
[11]Hyun Jin Choi, Seung-Ho Lim, and Kyu Ho Park. 2009. JFTL: A flash translation layer based on a journal remapping for flash memory. Trans. Storage 4, 4, Article 14 (February 2009), 22 pages.
[12]Woon-Hak Kang, Sang-Won Lee, Bongki Moon, Gi-Hwan Oh, and Changwoo Min. 2013. X-FTL: transactional FTL for SQLite databases. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD '13). ACM, New York, NY, USA, 97-108.
[13]Adam Leventhal. 2008. Flash storage memory. Commun. ACM 51, 7 (July 2008), 47-51.
[14]Junghoon Kim; Changwoo Min; Young Ik Eom, "Reducing excessive journaling overhead in mobile devices with small-sized NVRAM," Consumer Electronics (ICCE), 2014 IEEE International Conference on , vol., no., pp.19,20, 10-13 Jan. 2014.
[15]R. Y. Wang, T. E. Anderson, and D. A. Patterson. Virtual log based file systems for a programmable disk. In Proceedings of the third symposium on Operating systems design and implementation, OSDI ’99, pages 29–43, Berkeley, CA, USA, 1999. USENIX Association.
[16]Tzi-cker Chiueh, Lan Huang. Trail: A Fast Synchronous Write Disk Subsystem Using Track-Based Logging. Technical Report, Paper ID:360, Computer Science Department State University of New York at Stony Brook, 1999.
[17]Wen-Huei Lin; Li-Pin Chang. Dual Greedy: Adaptive garbage collection for page-mapping solid-state disks. In Design, Automation &; Test in Europe Conference &; Exhibition (DATE), 2012 , vol., no., pp.117,122, 12-16 March 2012.
[18]BAN, Amir. Flash file system. U.S. Patent No 5,404,485, 1995.
[19]Jesung Kim; Jong Min Kim; Noh, S.H.; Sang Lyul Min; Yookun Cho, "A space-efficient flash translation layer for CompactFlash systems," Consumer Electronics, IEEE Transactions on , vol.48, no.2, pp.366,375, May 2002.
[20]Sang-Won Lee, Dong-Joo Park, Tae-Sun Chung, Dong-Ho Lee, Sangwon Park, and Ha-Joo Song. 2007. A log buffer-based flash translation layer using fully-associative sector translation. ACM Trans. Embed. Comput. Syst. 6, 3, Article 18 (July 2007).
[21]Chanik Park, Wonmoon Cheon, Jeonguk Kang, Kangho Roh, Wonhee Cho, and Jin-Soo Kim. 2008. A reconfigurable FTL (flash translation layer) architecture for NAND flash-based applications. ACM Trans. Embed. Comput. Syst. 7, 4, Article 38 (August 2008), 23 pages.
[22]Aayush Gupta, Youngjae Kim, and Bhuvan Urgaonkar. 2009. DFTL: a flash translation layer employing demand-based selective caching of page-level address mappings. SIGARCH Comput. Archit. News 37, 1 (March 2009), 229-240.
[23]Li-Pin Chang and You-Chiuan Su. 2011. Plugging versus logging: a new approach to write buffer management for solid-state disks. In Proceedings of the 48th Design Automation Conference (DAC '11). ACM, New York, NY, USA, 23-28.
[24]Heeseung Jo; Jeong-Uk Kang; Seon-Yeong Park; Jin-Soo Kim; Joonwon Lee, "FAB: flash-aware buffer management policy for portable media players," Consumer Electronics, IEEE Transactions on , vol.52, no.2, pp.485,493, May 2006.
[25]Sooyong Kang; Sungmin Park; Hoyoung Jung; Hyoki Shim; Jaehyuk Cha, "Performance Trade-Offs in Using NVRAM Write Buffer for Flash Memory-Based Storage Devices," Computers, IEEE Transactions on , vol.58, no.6, pp.744,758, June 2009.
[26]http://sourceware.org/systemtap/. SystemTap.
[27]Jens Axboe and Alan D. Brunelle. Blktrace User Guide. February 2007
[28]http://www.hmailserver.com/. hMailServer.
[29]http://developer.android.com/tools/help/systrace.html. Systrace.
[30]Gomez, L.; Neamtiu, I.; Azim, T.; Millstein, T., "RERAN: Timing- and touch-sensitive record and replay for Android," Software Engineering (ICSE), 2013 35th International Conference on , vol., no., pp.72,81, 18-26 May 2013.
[31]Tom Yeh, Tsung-Hsiang Chang, and Robert C. Miller. 2009. Sikuli: using GUI screenshots for search and automation. In Proceedings of the 22nd annual ACM symposium on User interface software and technology (UIST '09). ACM, New York, NY, USA, 183-192.
[32]Li-Pin Chang; Po-Hung Chen. A study of the effect of file synching latency on Android APP GUI response.
[33]http://developer.android.com/tools/debugging/debugging-tracing.html. Traceview.
[34]Ying-Dar Lin, Cheng-Yuan Ho, Yuan-Cheng Lai, Tzu-Hsiung Du, Shun-Lee Chang, Booting, browsing and streaming time profiling, and bottleneck analysis on android-based systems, Journal of Network and Computer Applications, Volume 36, Issue 4, July 2013, Pages 1208-1218, ISSN 1084-8045.