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.

• Linear Hashing
• Flash Memory
• Embedded Devices
• IoT
• Data Handling

quaranta_k Follow

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.

Presentation Transcript

1. Adapting Linear Hashing for Flash Memory Resource- Constrained Embedded Devices Andrew Feltham Supervisor: Dr. Ramon Lawrence 1

2. Outline Motivation Background Implementation Experimental Results Future Work and Conclusions 2

3. 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

4. Background

5. Embedded Devices Constrained by RAM and processing power File system or raw access Rated by maximum sequential read or write speed 5

6. 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

7. Arduino Mega 2560 Limited Memory (8KB) Slow clock (16Mhz) Flash storage 7

8. Linear Hash Table Litwin in 1980 Key value storage Dynamically resizable hash table Constant time complexity 8

9. Linear Hash Table Index 0 1 2 3 4 5 9

10. 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

11. Splitting Index 01 10 00 0 1 6 3 12 11

12. Splitting Index 01 10 00 0 1 6 3 12 12

13. Implementation

14. File Reading and Writing Read and write blocks at a time Align buckets to file blocks 2 block buffers required Immediate writes 14

15. Delete Implementation Write only changed buckets Empty buckets kept Shift records only in buckets 15

16. Delete Implementation Delete 1 Bucket 1 3 1 7 9 1 12 16

17. Delete Implementation Delete 1 Bucket 3 1 7 9 1 12 17

18. Delete Implementation Delete 1 Bucket 3 1 7 9 1 12 18

19. Delete Implementation Delete 1 Bucket 3 7 9 1 12 19

20. Delete Implementation Delete 1 Bucket 3 7 9 1 12 20

21. Delete Implementation Delete 1 Bucket 3 7 9 1 12 21

22. Delete Implementation Delete 1 Bucket 3 7 9 12 22

23. Delete Implementation Delete 1 Bucket 3 7 9 12 23

24. Delete Implementation Bucket 0 10 Records Bucket 1 10 Records Bucket 2 10 Records 24

25. Deletion Implementation Bucket 0 5 Records Bucket 1 0 Records Bucket 2 6 Records 25

26. Deletion Performance Read All buckets Write Best case: 0 Worst case: all buckets 26

27. Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 27

28. Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 28

29. Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 29

30. Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 30

31. Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 31

32. Get Implementation Get 2 Bucket 4 6 8 12 46 2 89 32

33. Get Performance Read Best case: 1 Worst case: All buckets Write None 33

34. Update Implementation Simple linear scan Reads All buckets Writes Best case: No writes Worst case: All buckets 34

35. Splitting Splitting New Bucket 4 6 86 12 46 2 82 Overflow 35 186

36. Splitting Splitting New Bucket 6 4 12 82 86 46 2 Overflow 36 186

37. Splitting Overflow New Bucket 186 4 32 8 86 46 12 2 46 2 84 37

38. Splitting Overflow New Bucket 186 4 32 8 86 46 12 2 46 2 84 38

39. Splitting Read Read all buckets Write All changed split buckets All new buckets 39

40. Implementation Variations Mostly changes for insertion 3 Variations File based Bucket map Non random writes 40

41. File Implementation

42. File Implementation - Storage Index Logical 0 1 2 3 4 5 6 Bucket 0 1 2 3 4 5 6 42

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 43

44. 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

45. 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

46. 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

47. Insert Best case 1 Read, 1 Write Worst Read all buckets 2 writes 47

48. File Implementation Advantages Easily expandable Minimum memory Minimal overflow chains Disadvantages Extra writes for overflow buckets Two data files 48

49. Bucket Map

50. Bucket Map Logical 0 1 2 3 4 5 6 Data File 50

Load More ...