Capsule: An Energy-Optimized Object Storage System forMemory-Constrained Sensor DevicesGaurav Mathur, Peter Desnoyers, Deepak Ganesan, Prashant Shenoy{gmathur, pjd, dganesan, shenoy}@cs.umass.eduDepartment of Computer ScienceUniversity of Massachusetts, Amherst, MA 01003AbstractRecent gains in energy-efficiency of new-generation NAND flash stor-age have strengthened the case for in-network storage by data-centric sensornetwork applications. This paper argues that a simple file system abstrac-tion is inadequate for realizing the full benefits of high-capacity low-powerNAND flash storage in data-centric applications. Instead we advocate arich object storage abstraction to support flexible use of the storage systemfor a variety of application needs and one that is specifically optimized formemory and energy-constrained sensor platforms. We propose Capsule, anenergy-optimized log-structured object storage system for flash memoriesthat enables sensor applications to exploit storage resources in a multitude ofways. Capsule employs a hardware abstraction layer that hides the vagariesof flash memories for the application and supports energy-optimized imple-mentations of commonly used storage objects such as streams, files, arrays,queues and lists. Further, Capsule supports checkpointing and rollback ofobject states to tolerate software faults in sensor applications running oninexpensive, unreliable hardware. Our experiments demonstrate that Cap-sule provides platform-independence, greater functionality, more tunability,and greater energy-efficiency than existing sensor storage solutions, whileoperating even within the memory constraints of the Mica2 Mote. Our ex-periments not only demonstrate the energy and memory-efficiency of I/Ooperations in Capsule but also shows that Capsule consumes less than 15%of the total energy cost in a typical sensor application.Categories and Subject DescriptorsD.4.2 [Software ]: Operating Systems Storage Manage-ment Secondary storage; D.2.13 [Software ]: Software En-gineering Reusable Software Reusable librariesGeneral Termsdesign, performance, experimentationKeywordsstorage system, flash memory, energy efficiency, objects,embedded systems, sensor network, file systemPermission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. To copy otherwise, to republish, to post on servers or to redistributeto lists, requires prior specific permission and/or a fee.SenSys’06,November 1–3, 2006, Boulder, Colorado, USA.Copyright 2006 ACM 1-59593-343-3/06/0011 ...$5.001 IntroductionStorage is an essential ingredient of any data-centric sen-sor network application. Common uses of storage in sen-sor applications include archival storage [9], temporary datastorage [6], storage of sensor calibration tables [10], in-network indexing [20], in-network querying [19] and codestorage for network reprogramming [7], among others. Untilrecently, sensor applications and systems were designed un-der the assumption that computation is significantly cheaperthat both communication and storage, with the latter two in-curring roughly equal costs. However, the emergence of anew generation of NAND flash storage has significantly al-tered this trade-off, with a recent study showing that flashstorage is now two orders of magnitude cheaper than com-munication andcomparable in cost to computation[11]. Thisobservation challenges conventional wisdom and argues forredesigning systems and applications to exploit local storageand computation whenever possible in order to reduce ex-pensive communication.While the case for in-network storage has strengthenedwith the emergence of high-capacity energy-efficient NANDflash memories, existing storage systems built for flash de-vices (see Table 1) have a number of drawbacks:Mismatch between storage abstraction and applicationneeds: Many flash-based storage systems, such as YAFFS,YAFFS2 [25], Matchbox [5] and ELF [3], provide a file sys-tem abstraction to the application. While a file-based ab-straction is useful in many scenarios, it is a poor fit for han-dling the varied needs of sensor applications. For instance, acommon use of local storage is to store a time series of sen-sor observations and maintain a index on these readings tosupport queries. A data stream abstraction—an append-onlystore of time series data—and hash-based index structures, asproposed in MicroHash [27] are better suited for these needs.However, even supporting only this abstraction is restrictive,since it does not enable flash to be used for other purposessuch as for “live” application data storage, calibration tables,packet queues for radio transmission, hibernation, etc. In-stead, we argue that the storage substrate should support a“rich” object storage abstraction with the ability to create,store and retrieve data objects of various types such as files,streams, lists, arrays, queues, etc. This will enable sensorapplications to exploit flash storage in a multitude of ways.Supporting Use as a Backing Store: Current flash-based storage systems use flash as a persistent data storageTable 1. Comparison of Capsule to related efforts.StorageDevicesEnergyOptimizedMemoryOptimizedWearLevelingCheckpointing Abstraction Usage ModelsMatchbox NOR No Yes No No Filesystem File storage; Calibration TablesMicroHash MMC Yes No Yes No Stream/Index Stream Storage and IndexingELF NOR No Yes Yes No Filesystem Same as MatchboxYAFFS NAND No No Yes No Filesystem Portable devicesCapsule NAND,NORYes Yes Yes Yes Object Data Storage and Indexing; PacketQueues; Temporary Arraysmedium. However, memory is often a scarce commodity onsmall sensor platforms, with Telos and Mica motes contain-ing 10KB and 4KB of RAM, respectively. With empiricalstudies showing the energy cost of accessing flash approach-ing that of RAM, it is now possible for applications to usehigher-capacity flash for storing live application data andmanipulating it in an energy efficient manner. For instance,tasks can exploit flash as a form of backing store to storelarge data structures, intermediate results for data processingtasks, etc. It is also feasible to implement local data process-ing algorithms that manipulate data sets larger than the sizeof RAM. Such use of flash as a backing store also argues forsupporting a