1、ELF: An Efficient Log-Structured Flash File System For Micro Sensor NodesBy Hui Dai, Michael Neufeld, Richard HanTalk given by Mingqu YueOutlineBackgroundsDesign OverviewImplementationData structuresFile operationsGarbage collectionCrash recoveryPerformance EvaluationDesign OverviewDesign Objectives

2、Characteristics of data that are expected to handlePersistent storage attributes on sensor nodesLog-Structured File System Techniques in ELFELF Architecture OverviewObjectivesTo provide a practical, efficient and reliable file system for micro sensor nodes that employ flash memory for persistent sto

3、rage.Characteristics of data that are expected to handleSensor dataThe majority of the dataWritten sequentially (append)Configuration dataWill experience modification and updates Demands higher level of reliabilityBinary program imageRequires the highest level of reliabilityPersistent Storage attrib

4、utes on Sensor Nodes Two kinds of persistent storage mediums are used in sensor nodesFlash memory - storing sensor data, metadata and etc.EEPROM storing the directory structure and crash recovery dataLog-Structured File System Techniques in ELFTraditional LFS:creates a new sequential log entry for e

5、ach write operationVery good wear leveling many small appends will rapidly make memory representation grow to unwieldy size.LFS Techniques in ELFWrite-Append operations: utilize an existing log entry on a flash page if one is availableFor reliability considerations, ELF keeps each log entry on a sep

6、arate flash pageWrite-Modify operations: modifications will be written to a new page and a log entry is created.Other standard file operations, not sophisticatedELF Architecture OverviewResource Abstraction: in-memory representations of open files, cleaning policy and other configuration dataGeneral

7、 File Operations: logical abstraction of all file/directory operations.ELF Maintenance Tasks: maintaining a snapshot of directory structure and file metadata in EEPROM, garbage collection task. ImplementationOn-Flash Data StructuresIn-Memory Data StructuresIn-EEPROM Data Structures and Related Opera

8、tionsFile Operations in ELFResource Management and Garbage CollectionCrash RecoveryOn-Flash Data StructuresPhysical NodesThe log in ELF consists of a sequence of physical nodes.ELF_DIR: a directory entryELF_FILE: metadata, file content.ELF_COMMON: a write modification, a deletion operation, or a ren

9、aming operation Each flash page contains at most one physical node PerMetadataIn-Memory Data StructuresFile AbstractionStores the metadata of the fileSuch as the length of the file, number of opened handles, and a pointer to the list of physical node abstractions.Node AbstractionEach physical node o

10、f the file on flash has a corresponding abstraction in RAM.Only contains the necessary summary information of the physical nodeIn-EEPROM Data StructuresELF caches its directory in EEPROM for access to filesAlso stores a snapshot of the system in EEPROMFast startup and crash recoveryFile Operations i

11、n ELFOpen file “foo”Examine whether “foo”s file abstraction is in RAMCreate fileAllocate a free flash pageCreate a physical nodeCreate file abstraction and physical node abstraction in RAMAssigning a file descriptor to the applicationFile Operations in ELFAppendPolicy: delaying updates to a files ph

12、ysical node on the flash given a sequence of appendsFile Operations in ELFWrite(modify)Allocates a new flash page and created a new physical nodeCreates the corres- ponding new node abstraction in RAM and appends it to the node abstraction listFile Operations in ELFRead/SeekUses two pointers to read

13、If the log is long, then the performance of the read operation will degrade.File Operations in ELFRenameRenaming a fileCreating a new physical node and corresponding node abstractionRenaming a directoryA new directory node is allocatedAll data structures within the old directory node are copied to t

14、he new nodeFile Operations in ELFDeletionAdding a physical node to indicate the delete statusThe allocated space will be reclaimed during garbage collectionResource Management and Garbage CollectionResource ManagementTraditional approach: block listELF approach: bitmapImproved approach: the newly al

15、located blocks are combined with existing blocks if possible Resource Management and Garbage CollectionGarbage CollectionThe number of free pages is trackedThe cleaner reclaims the pages occupied by deleted, renamed or obsolete files.If the space is still not enough, de-fragmenting file to reclaim m

16、ore pagesRAM consumption is fairly low: 10bytes without defragmentation and fewer than 40 bytes with it.Crash RecoveryCheckpoints only store the status of a file. It is not enough, so we need tracking the current operation and a list of past operations (snapshot) When the system crashes, ELF compare

17、s the last finished action and the current action, if they match and CRC checksum is correct, then the file will be confirmed. Otherwise, roll back.Performance Evaluation (compared with Matchbox)Sequential Read PerformanceSequential Write PerformanceRandom Read PerformanceRandom Write PerformanceWea

18、r Levelling PerformanceEnergy ConsumptionSequential Read PerformanceFirst filled the entire memory with a 500 KB log file and the performed sequential readsSequential Write Performance Appending 16 bytes of sensor data to the file in each write until the whole flash is consumedSequential Write Memory ConsumptionSequential Write ThroughputRandom Read