1I1111/111111111111111111111111Design of Flash-Based DBMS :An In-Page Logging Approach1111I1I11/1111/111Tsung111-1Computer Science, RUC11111111福11111111111V111111111111-1
Design of Flash-Based DBMS :An InPage Logging Approach Tsung Computer Science , RUC
1OutlineCharacteristics of Flash Memory1Main ldea of In-Page LoggingDesign Manifesto && Data structure of IPLRead ,Update && Merge Algorithms of IPLWithout Transaction111Support for transaction11Experiments of IPL1福1Conclusion1E-E1111111/111111
Outline ▪ Characteristics of Flash Memory ▪ Main Idea of In-Page Logging ▪ Design Manifesto && Data structure of IPL ▪ Read ,Update && Merge Algorithms of IPL Without Transaction ▪ Support for transaction ▪ Experiments of IPL ▪ Conclusion
CharacteristicsofFlashMemory(NAND)Structure of NAND Flash MemoryPage(512k) ±11Erase Unit(16 Pages) ↓F11Flash Chip (*G Units) Flash Memory(**G is available)吉春祥Key hardware limits of Flash Memory1Electronic device (Uniform access speed)Different granularity (Read/Write> page ,Erase→ unit)Erase before write (Can't overwrite)Sequential write (From page 0 ,1,2 →> page 15)1Finite number of erase cycles (Typically up to 100,000)47
Characteristics of Flash Memory (NAND) ▪ Structure of NAND Flash Memory Page(512k) ↓ Erase Unit(16 Pages) ↓ Flash Chip (*G Units) ↓ Flash Memory(**G is available ) ▪ Key hardware limits of Flash Memory Electronic device (Uniform access speed) Different granularity (Read/Write→ page ,Erase→ unit) Erase before write (Can’t overwrite) Sequential write (From page 0 ,1,2 → page 15) Finite number of erase cycles (Typically up to 100,000)
CharacteristicsofFlashMemory(NAND)稻景1Impact onsoftware design11NoIn-PlaceUpdate→111HowtoAvoid&&BufferUpdate111Howto maintainindex withouthigh cost1111NoMechanical Latency→1Clustering Storagemakenosensenow,招票1we canscatterinformationaroundthememorywithoutsubstantialpenalty11/AsymmetricSpeedofRead/Write/Erase→11Traditionall/Otimesmakeno sensenow,1What's more,we can avoid writein ordertoavoiderasein the expenseof read-111111111
Characteristics of Flash Memory (NAND) ▪ Impact on software design No In-Place Update → How to Avoid && Buffer Update How to maintain index without high cost No Mechanical Latency → Clustering Storage make no sense now , we can scatter information around the memory without substantial penalty Asymmetric Speed of Read/Write/Erase → Traditional I/O times make no sense now , What’s more ,we can avoid write in order to avoid erase in the expense of read
Main Idea of In-Page Logging1TraditionalIn-Place Update11*No in-place updateUselogtobufferwrite,socancombinewritesLog-StructuredanddecreaseerasesApproach-*Nomechanical latency<Takeadvantageof*Fast read speedUniformsequentialandrandomwriteto co-In-Page Logginglocatethepageand itsApproach一login oneunit
Main Idea of In-Page Logging Use log to buffer write ,so can combine writes and decrease erases Take advantage of Uniform sequential and random write to colocate the page and its log in one unit