search

mafintosh / todo

I add my TODOs as issues in this repository.
3 stars 0 forks source link

a simple on disk kv store #11

Open mafintosh opened 8 years ago

mafintosh commented 8 years ago

first proof of concept, https://github.com/mafintosh/smalltable

mafintosh commented 8 years ago

@sorribas sent me this link as well, http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice.html

mafintosh commented 8 years ago

how leveldb works, https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

mafintosh commented 8 years ago

main problem with smalltable right now is growing the table means rewriting all old values. simple fix would be a "level" approach where we allocate a new file and write new entries to that whilst reading old values using a union approach across all levels. in the background old levels would be merged in when the table is idle

mafintosh commented 8 years ago

if we merge old values in old levels from the end of the file to the beginning (backwards seek) we could truncate the file as we go a long as well making it detect statically that a value isn't in an old level (offset > length)

mafintosh commented 8 years ago

https://infosys.uni-saarland.de/publications/DJ11.pdf