Adapting Linear Hashing for Flash Memory Constrained Embedded Devices
This research explores the adaptation of linear hashing for improved data handling on flash memory-constrained embedded devices. Motivated by the increasing data collection by IoT devices, the study focuses on implementing database structures like a linear hash table for efficient data processing. The background highlights the constraints faced by embedded devices and introduces concepts such as SD card performance and Arduino Mega limitations. The study delves into the details of linear hash tables, addressing insertion, hashing techniques, and splitting approaches to optimize data storage and retrieval. Experimental results and future work prospects are discussed to enhance the use of linear hashing in resource-constrained environments.
Uploaded on Sep 27, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Adapting Linear Hashing for Flash Memory Resource- Constrained Embedded Devices Andrew Feltham Supervisor: Dr. Ramon Lawrence 1
Outline Motivation Background Implementation Experimental Results Future Work and Conclusions 2
Motivation Embedded devices and sensors collecting more data (Internet of Things) Processing data on the device is more energy efficient Implementing database structures such as a linear hash table allows for improved data handling on embedded devices 3
Embedded Devices Constrained by RAM and processing power File system or raw access Rated by maximum sequential read or write speed 5
SD Card performance Time per Block operation (ms) Average of 1000 operations 10 Time per block operation (ms) 9 8 7 6 5 4 3 2 1 0 Sequential Read Sequential Write Random Read Random Write 8GB Class 6 16 GB Class 10 2 GB 6
Arduino Mega 2560 Limited Memory (8KB) Slow clock (16Mhz) Flash storage 7
Linear Hash Table Litwin in 1980 Key value storage Dynamically resizable hash table Constant time complexity 8
Linear Hash Table Index 0 1 2 3 4 5 9
Addressing Insert 6 Hash: 6 mod 12 Binary: 00110 10 Keys hashed using SDBM Optional function pointer Fritter, M., Ould-Khessal, N., Fazackerley, S., & Lawrence, R. (2018). Experimental Evaluation of Hash Function Performance on Embedded Devices. 10
Splitting Index 01 10 00 0 1 6 3 12 11
Splitting Index 01 10 00 0 1 6 3 12 12
File Reading and Writing Read and write blocks at a time Align buckets to file blocks 2 block buffers required Immediate writes 14
Delete Implementation Write only changed buckets Empty buckets kept Shift records only in buckets 15
Delete Implementation Delete 1 Bucket 1 3 1 7 9 1 12 16
Delete Implementation Delete 1 Bucket 3 1 7 9 1 12 17
Delete Implementation Delete 1 Bucket 3 1 7 9 1 12 18
Delete Implementation Delete 1 Bucket 3 7 9 1 12 19
Delete Implementation Delete 1 Bucket 3 7 9 1 12 20
Delete Implementation Delete 1 Bucket 3 7 9 1 12 21
Delete Implementation Delete 1 Bucket 3 7 9 12 22
Delete Implementation Delete 1 Bucket 3 7 9 12 23
Delete Implementation Bucket 0 10 Records Bucket 1 10 Records Bucket 2 10 Records 24
Deletion Implementation Bucket 0 5 Records Bucket 1 0 Records Bucket 2 6 Records 25
Deletion Performance Read All buckets Write Best case: 0 Worst case: all buckets 26
Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 27
Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 28
Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 29
Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 30
Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 31
Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 32
Get Performance Read Best case: 1 Worst case: All buckets Write None 33
Update Implementation Simple linear scan Reads All buckets Writes Best case: No writes Worst case: All buckets 34
Splitting Splitting New Bucket 4 6 86 12 46 2 82 Overflow 35 186
Splitting Splitting New Bucket 6 4 12 82 86 46 2 Overflow 36 186
Splitting Overflow New Bucket 186 4 32 8 86 46 12 2 46 2 84 37
Splitting Overflow New Bucket 186 4 32 8 86 46 12 2 46 2 84 38
Splitting Read Read all buckets Write All changed split buckets All new buckets 39
Implementation Variations Mostly changes for insertion 3 Variations File based Bucket map Non random writes 40
File Implementation - Storage Index Logical 0 1 2 3 4 5 6 Bucket 0 1 2 3 4 5 6 42
File Implementation - Storage Index Logical 0 1 2 3 4 5 6 Bucket 0 1 2 3 4 5 6 Logical 0 1 2 3 4 5 6 Overflow Bucket 43
File Implementation - Storage Index Logical 0 1 2 3 4 5 6 Bucket 0 1 2 3 4 5 6 Logical 0 1 2 3 4 5 6 Overflow Bucket 44
Insert Logical 0 1 2 3 4 5 6 Bucket 0 1 2 3 4 5 6 Bucket size: 10 Bucket 0 9 Records 10 Records 45
Insert Logical 0 1 2 3 4 5 6 Index Bucket 0 1 2 3 4 5 6 Bucket size: 10 Overflow 1 Records Bucket 0 10 Records Logical 0 1 2 3 4 5 6 Overflow 46
Insert Best case 1 Read, 1 Write Worst Read all buckets 2 writes 47
File Implementation Advantages Easily expandable Minimum memory Minimal overflow chains Disadvantages Extra writes for overflow buckets Two data files 48
Bucket Map Logical 0 1 2 3 4 5 6 Data File 50
