The challenge tackled in this research action is threefold: (1) revisit classical data management techniques (e.g., RDBMS engine, full-text search engine) to cope with the strong hardware constraints of smart objects, (2) address more advanced data types (e.g., spatio-temporal data such as trajectory data) in the context of new storage devices based on Flash and (3) consider flash storage in a more general context, studying and proposing new optimizations on the host side, the controller side as well as between both (interface).
Log-only databases: Mass-storage secure portable tokens are emerging today and provide a real breakthrough in the management of sensitive data. They can embed data and/or meta-data referencing documents stored encrypted in the Cloud and 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 proposed a new database organization called Log-Only trying to reconcile three a priori contradictory objectives: (1) massively indexing the database, (2) producing only sequential writes in Flash and (3) consuming a tiny amount of RAM, independent of the database size and the queries complexity. To this end, the complete database (raw data but also indexes, buffers and more generally all data structures managed by the DBMS engine) is organized into Log Containers, that is purely sequential persistent recipients. There is however a scalability limit beyond which performance severely degrades. To tackle this issue, the database is periodically reorganized in background to produce another log-only database with close to optimal performance. The flash memory of mass-storage token being generally not secured, the on-board data is cryptographically protected against four forms of tampering: modification, substitution, deletion and replay of data items. Cryptographic overheads are minimized by (1) adapting the granularity of encryption primitives to the granularity of the data items accessed and (2) proposing cryptographic conscious flash page organization.
Embedded keyword indexing: In this line of works, we revisit the traditional problem of information retrieval queries over large collections of files in an embedded context. A file can be any form of document, picture or data stream, associated with a set of terms. A query can be any form of keyword search using a ranking function (e.g., TFIDF) identifying the top-k most relevant files. The proposed search engine can be used in sensors to search for relevant objects in their surroundings, in cameras to search pictures by using tags, in personal smart dongles to secure the querying of documents and files hosted in an untrusted Cloud, or in a personal cloud securely managed using a tamper resistant smart object. A search engine is usually based on a (large) inverted index and queries are traditionally evaluated by allocating one container in RAM per document to aggregate its score, making the RAM consumption linear with the size of the document corpus. To tackle this issue, we designed a new form of inverted index which can be accessed in a pure pipeline manner to evaluate search queries without materializing any intermediate result. Successive index partitions are written once in Flash and maintained in the background by timely triggering merge operations while files are inserted or deleted from the index. By combining this new index and the corresponding evaluation techniques, our embedded search engine is capable of reconciling high insert/delete/update rate and query scalability. We have demonstrated the search engine on a secure USB token in the context of a personal cloud, and have conducted in depth performance evaluations on a development board representative for different smart objects characteristics.
Spatio-temporal indexing in Flash storage: The convergence of mobile computing, wireless communications and sensors has raised the development of many applications exploiting massive flows of spatio-temporal data such as in location-based services, participatory sensing, or traffic management. Spatio-temporal data indexing is among the most active research topics in this area. Nevertheless, since a few years a new fundamental parameter has made its entry on the database scene: the NAND flash storage. The peculiar characteristics of flash memory require redesigning the existing data storage and indexing techniques that were devised for magnetic hard-disks. TRIFL is an efficient and generic TRajectory Index for FLash, designed around the key requirements of both trajectory indexing and flash storage. TRIFL is generic in the sense that it is efficient for both simple flash storage devices such as the SD cards and more powerful devices such as the solid state drives. In addition, TRIFL includes an online self tuning algorithm that allows adapting the index structure to the workload and the technical specifications of the flash storage device to maximize the index performance. Moreover, TRIFL achieves good performance with relatively low memory requirements, making it appropriate for many application scenarios.
Flash-storage optimization: For decades, the block device interface has been a simple and robust abstraction that hides the complexity of I/O management on hard disk drives, without sacrificing performance for a large range of applications including database systems. The advent of SSDs challenges this stability: SSDs provide orders of magnitude improvements in terms of throughput and latency, they implement a full mapping of the logical address space onto the physical address space, and they deal with a high level of parallelism. Today, complex decisions about mapping and scheduling are taken on both sides of the block device interface. In the context of the Clyde Project, in collaboration with IT University of Copenhagen, we focused on theses decisions and revisited the device interface. On the host side, we considered IOs with future SSDs whose latency lies in the microsecond range. We proposed and evaluated some techniques based on IO speculation that can avoid overheads due to blocking or asynchronous IOs. We built an SSD simulator, LightNVM which exposes itself as a block device to the OS kernel and can either simulate flash chips with real applications, storing data in RAM, or interact with real flash chips, thus acting as a flash controller on the host side. On the SSD side , we built a more classical simulator, EagleTree, operating in virtual time, simulating all the layers from the hardware to the application, and thus allowing conducting large and complex design-space explorations involving hundreds of experiments, in a tractable way. We studied, thanks to EagleTree, different alternatives to reduce every source of write amplification (number of physical writes for one logical write). Between the host and the device, we revisited the block device interface: we have shown that the block device interface leads to waste of resources, sub-optimal performance and bottlenecks and gave our vision of how modern database systems should interact with secondary storage. Recently, we proposed AppNVM, a software defined application-driven SSD The objective is to reorganize the way applications, OS and SSDs communicate, based on a rule-based interface where rules, defined by applications, are enforced by the SSD controller.
