Comments (4)
Thanks for raising this.
You are correct that fragmentation is an issue. It's a hard problem to solve though. Two of the key goals of TicKV are:
* Power loss resilient
* Maintain data integrity and detect media errors
So implementing a garbage collection is difficult as we want to ensure that no data is lost on power loss.
The first solution I would like to propose would be a per-region operation.
* Called when a key is invalidated/zeroized.
I don't think this is a good idea. This would add over head to removing keys, which the user doesn't necessarily want. If we do add a defrag option it should be something that is explicitly called.
* Checks how much space of the region would be recovered by performing the operation. This would likely be a % of the region. * Valid keys that are inside the region would be appended to nearby regions. This would be done as it would if the current region was already full. * After all valid keys are appended elsewhere, the region is erased.
Do we move the keys back? If not that increases lookup time for future gets. If we do move them back we are fragmenting other parts.
The benefit of this solution is that it would maintain uniform wear in the regions and would not require a reserved region. The drawback is that the keys will exist outside their original regions, which would raise the lookup time. Additionally, I am unsure as to what threshold would be best. I would appreciate feedback on what the optimal threshold would be.
Exactly!
The threshold really is going to be application specific. We could make it an option, but that seems confusing. It might be best to just defrag the first region that can be and then return. Allowing an application to call the function until all regions have been searched. That way applications can do it in the background when required, without taking the entire overhead of going through all of flash.
from tock.
The second solution I would like to propose would be a part-wide operation. This one is similar to the idea listed in the SPEC, with a few optimizations to limit the amount of wear on the chip.
* Move the valid keys across multiple regions to the reserved region * When the reserved region is full, erase the regions that have their valid keys in the reserved region * Move the valid objects back to their original regions * Erase the reserved region
This still ensures that we don’t lose data on power loss, but still has the same problems as the solution in the SPEC. There would have to be a garbage collecting state to restore after power loss, and the requirement on wear leveling would still be broken on the reserved region. I also don’t know when this could be called.
That's a good improvement but still lots of drawbacks
from tock.
I don't have any other solutions.
Is fragmentation an issue for you? If it's blocking a use case of yours then we should focus on a solution. I would lean towards your first option. One big worry is what happens if we loose power after copying the keys. We end up with two copies of the data on resume.
I do think having a defrag function that is specifically called and only runs on one or a small number of regions is the way to go. That way we don't block flash accesses for long while doing this.
Either way we somehow need to track state to resume the operation if we get interrupted. That might be easier with a reserved region
from tock.
Fragmentation is a blocking use case for me.
I am going to assume that we would utilize parts of my first solution proposal, but applying it to one region and allowing it to be explicitly called. For power loss, setting the state and tracking the region that we are defragmenting to restart/resume the process would prevent copying the key as trying to append a key that exists would return an error code KeyAlreadyExists. Similar functionality for region tracking is built into the garbage collect with the State and Rubbish State.
The threshold will have to be application specific, but we will need a threshold else we could end up calling this function every time there in an invalidate/zeroise key which would cause unnecessary wear on the part. This threshold would just be a % of the region that is able to be recovered.
from tock.
Related Issues (20)
- Add an Asynchronous Process Loader HOT 3
- Tracking: OpenThread Support HOT 9
- Hard code require kernel version in process loading HOT 8
- Shared references of mutable static warnings HOT 8
- Move implementations of kernel configuration tools to capsules
- Kernel Unit Testing HOT 4
- tock_memory_usage: SyntaxWarning: invalid escape sequence '\S'
- AppID Roadmap HOT 1
- RFC: Expand Alarm Range HOT 8
- License checker incorrectly rejects `.txt` files HOT 1
- Tracking: Tockbot HOT 1
- IEEE 802.15.4: Receive Raw
- RFC: Flash Storage with Isolation HOT 8
- Tracking: Implement Configuration Boards
- Writing the Tock OS kernel to the stm32f303discovery development board failed. HOT 5
- 6LoWPAN Indexing Bug HOT 3
- Alarm: Change prescaler for NRF 5x boards HOT 2
- Tracking: WiFi Support
- Process loading: applications' FLASH order must be the same as RAM order; otherwise loading fails for some HOT 2
- Tockloader: erase does not erase all apps HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from tock.