MILo-DB: a personal, secure and portable database machine

Mass-storage secure portable tokens are emerging and provide a real breakthrough in the management of sensitive data. They can embed personal data and/or metadata referencing documents stored encrypted in the Cloud and can manage them under holder’s control. Mass on-board storage requires efficient embedded database techniques. These techniques are however very challenging to design due to a combination of conflicting NAND Flash constraints and scarce RAM constraint, disqualifying known state of the art solutions. To tackle this challenge, we proposes a log-only based storage organization and an appropriate indexing scheme, which (1) produce only sequential writes compatible with the Flash constraints and (2) consume a tiny amount of RAM, independent of the database size. We show the effectiveness of this approach through a comprehensive performance study.

1. http://www.kuppingercole.com/.

2. http://cyber.law.harvard.edu/projectvrm/Main_Page.

3. A recent Microsoft survey states that “58 percent of the public and 86 percent of business leaders are excited about the possibilities of cloud computing. But more than 90 percent of them are worried about security and privacy of their data as it rests in the cloud” http://news.cnet.com/8301-1009_3-10437844-83.html.

4. Bloc nested loop Join is often the only Join algorithm provided in embedded DBMS products (e.g., for SQLite see http://www.sqlite.org/optoverview.html).

5. This is not the case in high-end SSDs which can use relatively large RAM (e.g., 16 MB) to handle those constraints.

6. Tests on 20 recent SD cards have shown that random writes are in average 1300 times more costly than sequential writes (min 130×, max 5350×) [30].

7. A first layer (the Hardware Adaptation Level) of the controller software manages Low Level Drivers (LLD), Error Correction (ECC) and Bad Block Management (BBM). The second layer is the FTL, and it can be bypassed on most platforms.

8. Moreover, the Flash Translation Layer becomes useless (thereby saving translation costs) and the garbage collection and wear leveling mechanism can be greatly simplified.

9. While the strategy for handling deletes and updates is rather simple, the details on query compensation is a bit tricky and cannot be included in the paper due to size constraint.

10. For the sake of clarity, we make here the assumption that at most one join path exists between two tables (e.g., a snowflake schema). The indexing scheme can be extended trivially to the multiple paths case.

11. For example, the false positive rate using 4 hash functions and allocating 16 bits per value is 0.24 % [10]. Hence, Bloom Filters provide a very flexible way to trade space with performance.

12. The result tuple identifiers are produced in reversed order, from the most recently inserted to the least recent inserted, which is suitable with the definition of Tselect Index \(\mathrm{I}_{\mathrm{T}_{j}.a\to \mathrm{T}_{i}}\) given in Sect. 4.1.

13. Since TJoin indexes behave as normal tables, they are handled in the same way by the Merge operations, and thus, are not discussed here.

14. The work required to recover from a crash during the reorganization can be minimized by storing on Flash the current state of each operation and analyzing this log at recovery time.

15. Actually, it is worth managing a very small buffer (e.g., 1 page) in RAM to buffer several insertions of the same transaction.

16. This calibration is important to take into account aspects that cannot be captured by the simulator (e.g., synchronizations problems when accessing the Flash memory). It impacts negatively the performance shown here roughly by a factor of 1.4.

17. Note that giving a value of p for simple Flash devices like SD cards is difficult since FTL code is proprietary. It is however necessarily rather large because of their reduced cache capabilities. This is confirmed by the ratio between sequential and random writes (between 130 and 5350! [30])

This work has been partially funded by the French ANR KISS project under grant No. ANR-11-INSE-0005. The authors also wish to thank Philippe Bonnet for his accurate comments on early versions of this paper.

Authors and Affiliations

1. INRIA Paris-Rocquencourt, Le Chesnay, France

   Nicolas Anciaux, Luc Bouganim, Philippe Pucheral, Yanli Guo & Lionel Le Folgoc

2. PRISM Laboratory, University of Versailles Saint-Quentin-En-Yvelines, Versailles, France

   Nicolas Anciaux, Luc Bouganim, Philippe Pucheral, Yanli Guo & Lionel Le Folgoc

3. University of Cergy Pontoise, Cergy-Pontoise, France

   Shaoyi Yin

Corresponding author

Correspondence to Nicolas Anciaux.

Communicated by Elena Ferrari.

Reprints and permissions