input-output-hk / iodb Goto Github PK

Multiversioned key-value database, especially useful for blockchain

License: Creative Commons Zero v1.0 Universal

Java 6.78% Scala 93.22%

iodb's Introduction

IODB - database engine for blockchain

IODB is embedded storage engine designed for blockchain applications. It is inspired by RocksDB. It provides ordered key-value store, it is similar to SortedMap<byte[], byte[]>. Its main advantage are snapshots with branching and fast rollbacks.

Main features include:

Ordered key-value store
Written in Scala, functional interface
Multi-threaded background compaction
Very fast durable commits
Atomic updates with MVCC isolation and crash protection
Snapshots with branching and rollbacks
Log structured storage, old data are never overwritten for improved crash protection

Getting started

IODB builds are available in Maven repository. Maven dependency snippet is bellow, replace $VERSION with :

<dependency>
    <groupId>org.scorexfoundation</groupId>
    <artifactId>iodb_2.12</artifactId>
    <version>$VERSION</version>
</dependency>

Code examples are in the src/test/scala/examples folder.

Documentation is in the doc folder.

Compile

IODB works with Intellij IDEA with Scala plugin.

Checkout IODB:

git clone https://github.com/input-output-hk/iodb.git

Install SBT
Compile IODB and install JAR files into local repository:

sbt publish

iodb's People

Contributors

Stargazers

Watchers

Forkers

wiltonlazary haiderny cuulee virdis andystv blockchain-for terjokhin luomeiqin devuri esquive gostkin scasplte2 topl

iodb's Issues

Examples link is broken on README

There a reference in the main README to an example folder that doesn't exist.

Perhaps update to alternate or new location if it has moved.

Referenced Readme line:

Code examples are in the src/test/scala/examples folder.

Provide Store.getAll()

Provide iterator over all key-value pairs at given version LogStore already has an iterator, so make this public and handle transitions between shards.

M1 with many keys fails with OOEM

M1 test fails with OOEM if the number of keys is set high.
It happens during distributeTask, while data are being merged. There are is too many updates. This is duplicate of #30

Solution could be:

apply back pressure (slow down updates)
increase memory
reduce memory overhead (replace Pair(Key,Value) with single byte[])

Command line:

sbt clean 'test:run-main io.iohk.iodb.smoke.M1Test 10000000'

Error log:

[info] KeyCount: 10000000                                                                                                                  
[info] Shard count: 16                                                                                                                     
[info] Dir: /tmp/iodb0.8201001663280878                                                                                                    
[info] Store populated, dir size: 1.0100049 GB                                                                                             
[info] rollback                                                                                                                            
[info] rollback                                                                                                                            
[info] rollback                                                                                                                            
[info] rollback                                                                                                                            
[info] rollback                                                                                                                            
[info] rollback                                                                                                                            
[info] rollback                                                                                                                            
[error] java.util.concurrent.ExecutionException: Background distribution task failed                                                       
[error]         at io.iohk.iodb.ShardedStore.$anonfun$new$4(ShardedStore.scala:81)                                                         
[error]         at io.iohk.iodb.Store.$anonfun$runnable$1(Store.scala:184)                                                                 
[error]         at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)                                         
[error]         at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)                                         
[error]         at java.lang.Thread.run(Thread.java:745)                                                                                   
[error] Caused by: java.lang.OutOfMemoryError: Java heap space                                                                             
[error]         at java.nio.ByteBuffer.wrap(ByteBuffer.java:373)                                                                           
[error]         at java.nio.ByteBuffer.wrap(ByteBuffer.java:396)                                                                           
[error]         at io.iohk.iodb.LogStore.fileReadData(LogStore.scala:1121)                                                                 
[error]         at io.iohk.iodb.LogStore$ret$2$.next(LogStore.scala:1184)                                                                  
[error]         at io.iohk.iodb.LogStore$ret$2$.next(LogStore.scala:1174)                                                                  
[error]         at scala.collection.Iterator$$anon$10.next(Iterator.scala:448)                                                             
[error]         at scala.collection.convert.Wrappers$IteratorWrapper.next(Wrappers.scala:28)                                               
[error]         at com.google.common.collect.Iterators$PeekingImpl.peek(Iterators.java:1194)                                               
[error]         at com.google.common.collect.Iterators$MergingIterator$1.compare(Iterators.java:1304)                                      
[error]         at com.google.common.collect.Iterators$MergingIterator$1.compare(Iterators.java:1301)
[error]         at java.util.PriorityQueue.siftUpUsingComparator(PriorityQueue.java:669)
[error]         at java.util.PriorityQueue.siftUp(PriorityQueue.java:645)
[error]         at java.util.PriorityQueue.offer(PriorityQueue.java:344)
[error]         at java.util.PriorityQueue.add(PriorityQueue.java:321)
[error]         at com.google.common.collect.Iterators$MergingIterator.next(Iterators.java:1327)
[error]         at scala.collection.convert.Wrappers$JIteratorWrapper.next(Wrappers.scala:40)
[error]         at scala.collection.Iterator$$anon$12.hasNext(Iterator.scala:501)
[error]         at scala.collection.Iterator$$anon$12.hasNext(Iterator.scala:500)
[error]         at scala.collection.Iterator$$anon$10.hasNext(Iterator.scala:447)
[error]         at io.iohk.iodb.ShardedStore.flushShard$1(ShardedStore.scala:229)
[error]         at io.iohk.iodb.ShardedStore.taskDistribute(ShardedStore.scala:251)
[error]         at io.iohk.iodb.ShardedStore.$anonfun$new$4(ShardedStore.scala:76)
[error]         at io.iohk.iodb.ShardedStore$$Lambda$17/1810132623.apply$mcV$sp(Unknown Source)
[error]         at io.iohk.iodb.Store.$anonfun$runnable$1(Store.scala:184)
[error]         at io.iohk.iodb.Store$$Lambda$16/760563749.run(Unknown Source)
[error]         ... 3 more
[error] Nov 08, 2017 12:44:40 AM io.iohk.iodb.Store $anonfun$runnable$1
[error] SEVERE: Background task failed
[error] java.lang.OutOfMemoryError: Java heap space
[error]         at java.util.concurrent.ConcurrentHashMap.putVal(ConcurrentHashMap.java:1043)
[error]         at java.util.concurrent.ConcurrentHashMap.putIfAbsent(ConcurrentHashMap.java:1535)
[error]         at java.lang.ClassLoader.getClassLoadingLock(ClassLoader.java:463)
[error]         at java.lang.ClassLoader.loadClass(ClassLoader.java:404)
[error]         at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:331)
[error]         at java.lang.ClassLoader.loadClass(ClassLoader.java:357)
[error]         at io.iohk.iodb.ShardedStore.$anonfun$new$2(ShardedStore.scala:65)
[error]         at io.iohk.iodb.ShardedStore$$Lambda$15/66233253.apply$mcV$sp(Unknown Source)
[error]         at io.iohk.iodb.Store.$anonfun$runnable$1(Store.scala:184)
[error]         at io.iohk.iodb.Store$$Lambda$16/760563749.run(Unknown Source)
[error]         at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
[error]         at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
[error]         at java.lang.Thread.run(Thread.java:745)
[error] 
[error] java.util.concurrent.ExecutionException: Background distribution task failed
[error]         at io.iohk.iodb.ShardedStore.$anonfun$new$4(ShardedStore.scala:81)
[error]         at io.iohk.iodb.Store.$anonfun$runnable$1(Store.scala:184)
[error]         at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
[error]         at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
[error]         at java.lang.Thread.run(Thread.java:745)
[error] Caused by: java.lang.OutOfMemoryError: GC overhead limit exceeded
[error]         at io.iohk.iodb.LogStore.$anonfun$loadKeyValues$5(LogStore.scala:786)
[error]         at io.iohk.iodb.LogStore$$Lambda$68/2008966511.apply(Unknown Source)
[error]         at scala.collection.Iterator$$anon$10.next(Iterator.scala:448)
[error]         at io.iohk.iodb.ShardedStore.flushShard$1(ShardedStore.scala:229)
[error]         at io.iohk.iodb.ShardedStore.taskDistribute(ShardedStore.scala:251)
[error]         at io.iohk.iodb.ShardedStore.$anonfun$new$4(ShardedStore.scala:76)
[error]         at io.iohk.iodb.ShardedStore$$Lambda$17/1810132623.apply$mcV$sp(Unknown Source)
[error]         at io.iohk.iodb.Store.$anonfun$runnable$1(Store.scala:184)
[error]         at io.iohk.iodb.Store$$Lambda$16/760563749.run(Unknown Source)
[error]         ... 3 more
[error] Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
[error] java.util.concurrent.ExecutionException: Background distribution task failed
[error]         at io.iohk.iodb.ShardedStore.$anonfun$new$4(ShardedStore.scala:81)
[error]         at io.iohk.iodb.Store.$anonfun$runnable$1(Store.scala:184)
[error]         at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
[error]         at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
[error]         at java.lang.Thread.run(Thread.java:745)
[error] Caused by: java.lang.OutOfMemoryError: GC overhead limit exceeded

Store.getAll() and Store.get() should accept versionID

a new feature is a snamphottable transaction option as in rocksdb

Background exceptions

Right now the background tasks are failing with some exceptions:

OEM

this is related to issue #28

SEVERE: Background task failed
java.lang.OutOfMemoryError: Java heap space
        at io.iohk.iodb.LogStore.fileReadData(LogStore.scala:1109)
        at io.iohk.iodb.LogStore.$anonfun$fileReadKeyValues$1(LogStore.scala:1165)
        at io.iohk.iodb.LogStore.$anonfun$fileReadKeyValues$1$adapted(LogStore.scala:1163)
        at io.iohk.iodb.LogStore$$Lambda$1598/623407412.apply(Unknown Source)
        at scala.collection.TraversableLike.$anonfun$map$1(TraversableLike.scala:234)
        at scala.collection.TraversableLike$$Lambda$106/2134156020.apply(Unknown Source)
        at scala.collection.immutable.Range.foreach(Range.scala:156)
        at scala.collection.TraversableLike.map(TraversableLike.scala:234)
        at scala.collection.TraversableLike.map$(TraversableLike.scala:227)
        at scala.collection.AbstractTraversable.map(Traversable.scala:104)
        at io.iohk.iodb.LogStore.fileReadKeyValues(LogStore.scala:1163)
        at io.iohk.iodb.LogStore.$anonfun$loadKeyValues$1(LogStore.scala:758)
        at io.iohk.iodb.LogStore$$Lambda$1618/193971037.apply(Unknown Source)
        at scala.collection.TraversableLike.$anonfun$map$1(TraversableLike.scala:234)
        at scala.collection.TraversableLike$$Lambda$106/2134156020.apply(Unknown Source)
        at scala.collection.mutable.ResizableArray.foreach(ResizableArray.scala:59)
        at scala.collection.mutable.ResizableArray.foreach$(ResizableArray.scala:52)
        at scala.collection.mutable.ArrayBuffer.foreach(ArrayBuffer.scala:48)
        at scala.collection.TraversableLike.map(TraversableLike.scala:234)
        at scala.collection.TraversableLike.map$(TraversableLike.scala:227)
        at scala.collection.AbstractTraversable.map(Traversable.scala:104)
        at io.iohk.iodb.LogStore.loadKeyValues(LogStore.scala:758)
        at io.iohk.iodb.ShardedStore.taskDistribute(ShardedStore.scala:154)
        at io.iohk.iodb.ShardedStore.$anonfun$update$1(ShardedStore.scala:88)
        at io.iohk.iodb.ShardedStore$$Lambda$1606/164611973.apply$mcV$sp(Unknown Source)
        at io.iohk.iodb.Store.$anonfun$runnable$1(Store.scala:184)
        at io.iohk.iodb.Store$$Lambda$1607/1406013867.run(Unknown Source)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
        at java.lang.Thread.run(Thread.java:748)

file close race condition

ShardedStore#close() only blocks writers in other threads. If there is reader in other thread (most likely compaction or other background task), it fails with.

SEVERE: Background task failed
java.nio.channels.ClosedChannelException
        at sun.nio.ch.FileChannelImpl.ensureOpen(FileChannelImpl.java:110)
        at sun.nio.ch.FileChannelImpl.read(FileChannelImpl.java:721)
        at io.iohk.iodb.Utils.readFully(Utils.java:213)
        at io.iohk.iodb.LogStore.fileReadData(LogStore.scala:1111)
        at io.iohk.iodb.LogStore.$anonfun$fileReadKeyValues$1(LogStore.scala:1165)
        at io.iohk.iodb.LogStore.$anonfun$fileReadKeyValues$1$adapted(LogStore.scala:1163)
        at scala.collection.TraversableLike.$anonfun$map$1(TraversableLike.scala:234)
        at scala.collection.immutable.Range.foreach(Range.scala:156)
        at scala.collection.TraversableLike.map(TraversableLike.scala:234)
        at scala.collection.TraversableLike.map$(TraversableLike.scala:227)
        at scala.collection.AbstractTraversable.map(Traversable.scala:104)
        at io.iohk.iodb.LogStore.fileReadKeyValues(LogStore.scala:1163)
        at io.iohk.iodb.LogStore.$anonfun$loadKeyValues$1(LogStore.scala:758)
        at scala.collection.TraversableLike.$anonfun$map$1(TraversableLike.scala:234)
        at scala.collection.mutable.ResizableArray.foreach(ResizableArray.scala:59)
        at scala.collection.mutable.ResizableArray.foreach$(ResizableArray.scala:52)
        at scala.collection.mutable.ArrayBuffer.foreach(ArrayBuffer.scala:48)
        at scala.collection.TraversableLike.map(TraversableLike.scala:234)
        at scala.collection.TraversableLike.map$(TraversableLike.scala:227)
        at scala.collection.AbstractTraversable.map(Traversable.scala:104)
        at io.iohk.iodb.LogStore.loadKeyValues(LogStore.scala:758)
        at io.iohk.iodb.ShardedStore.taskDistribute(ShardedStore.scala:154)
        at io.iohk.iodb.ShardedStore.$anonfun$update$1(ShardedStore.scala:88)
        at io.iohk.iodb.Store.$anonfun$runnable$1(Store.scala:184)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
        at java.lang.Thread.run(Thread.java:748)

Two phase commit feature ?

There is 2pc transaction ?

QuickStore.rollbackVersions() gives wrong versions after rollback

There is a bug in QuickStore.rollbackVersions(). It gives wrong versionIDs after rollback. Release 0.3.2 is affected, 0.4 branch (lsmstore2) is already fixed

LSMStore get() after close() causes fatal error on the JVM

I think there might be a problem in the get function from the LSMStore, when trying use get to access the LSMStore after it was closed I get the following error: A fatal error has been detected by the Java Runtime Environment: SIGSEGV. This only seems to happen when previously any update has been done to the LSMStore. I'm using the 0.1.1 version of IODB.

Test that fails

test("LSMStore get after close fails") {
    val TestKeySize = 32
    val testByteArray = (0 until TestKeySize).map(_.toByte).toArray

    val dir: File = File.createTempFile("iodb", "iodb")
    dir.delete()
    dir.mkdir()

    val lSMStore: LSMStore = new LSMStore(dir = dir, keySize = TestKeySize)
    lSMStore.update(ByteArrayWrapper(testByteArray), Seq(), Seq())

    lSMStore.close()
    lSMStore.get(ByteArrayWrapper(testByteArray)) //JVM Crashes
  }

NPE if test folder does not exist

File.listFiles() returns null (instead of empty array) if directory does not exists. That causes following exception:

info] IODBSpecification:
[info] - writeKey test
Feb 06, 2017 12:29:05 PM io.iohk.iodb.LSMStore$$anon$1 run
SEVERE: Background task failed
java.lang.NullPointerException
at scala.collection.mutable.ArrayOps$ofRef$.newBuilder$extension(ArrayOps.scala:197)
at scala.collection.mutable.ArrayOps$ofRef.newBuilder(ArrayOps.scala:193)
at scala.collection.TraversableLike.filterImpl(TraversableLike.scala:246)
at scala.collection.TraversableLike.filterImpl$(TraversableLike.scala:245)
at scala.collection.mutable.ArrayOps$ofRef.filterImpl(ArrayOps.scala:193)
at scala.collection.TraversableLike.filter(TraversableLike.scala:259)
at scala.collection.TraversableLike.filter$(TraversableLike.scala:259)
at scala.collection.mutable.ArrayOps$ofRef.filter(ArrayOps.scala:193)
at io.iohk.iodb.LSMStore.shardListSortedFiles(LSMStore.scala:305)
at io.iohk.iodb.LSMStore.shardNewFileNum(LSMStore.scala:310)
at io.iohk.iodb.LSMStore.createEmptyShard(LSMStore.scala:331)
at io.iohk.iodb.LSMStore.$anonfun$taskShardMerge$1(LSMStore.scala:782)
at scala.collection.immutable.Range.foreach$mVc$sp(Range.scala:156)
at io.iohk.iodb.LSMStore.taskShardMerge(LSMStore.scala:776)
at io.iohk.iodb.LSMStore.$anonfun$taskSharding$11(LSMStore.scala:732)
at io.iohk.iodb.LSMStore$$anon$1.run(LSMStore.scala:456)
at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
at java.lang.Thread.run(Thread.java:745)

Expose incremental journal replay

I have a counter to update every add and remove . This counter is in memory for evoiding overhead in writes . A periodic thread save the values in db . The problem is if there is crash before last update is done . For solving it i might set the limit for compactation .
Pseudo code
Update counter and snapshot sequence values in a kv cell.
Update the tail limit for compactation(go forward )

If there is a crash the last part of log file is not re compacted . On bots trap It is possible to scan db from last sequence assoacied to counter(surely there are few rows )i can reads add and remove commands and I can restore very Fastly the correct status of counter without scanning entire db

repo description: s/usefull/useful

Multiversioned key-value database, especially usefull for blockchains

LogStore file handles leak

With many updates, LogStore might run out of available file handles. This manifests in LogStoreTest#concurrentKeyUpdate() test case:

java.lang.RuntimeException: java.nio.file.FileSystemException: /mnt/test/tmp/iodb0.578450809262877/store4058.journal: Too many open files

	at io.iohk.iodb.ForkExecutor.rethrow$1(ForkExecutor.scala:33)
	at io.iohk.iodb.ForkExecutor.finish(ForkExecutor.scala:38)
	at io.iohk.iodb.StoreTest.concurrent_key_update(StoreTest.scala:254)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)

Caused by: java.nio.file.FileSystemException: /mnt/test/tmp/iodb0.578450809262877/store4058.journal: Too many open files
	at sun.nio.fs.UnixException.translateToIOException(UnixException.java:91)
	at sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:102)
	at sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:107)
	at sun.nio.fs.UnixFileSystemProvider.newFileChannel(UnixFileSystemProvider.java:177)
	at java.nio.channels.FileChannel.open(FileChannel.java:287)
	at java.nio.channels.FileChannel.open(FileChannel.java:335)
	at io.iohk.iodb.LogStore.fileChannelOpen(LogStore.scala:842)
	at io.iohk.iodb.LogStore.fileOpen(LogStore.scala:835)
	at io.iohk.iodb.LogStore.startNewFile(LogStore.scala:270)
	at io.iohk.iodb.LogStore.compact(LogStore.scala:653)
	at io.iohk.iodb.LogStore.clean(LogStore.scala:697)
	at io.iohk.iodb.StoreTest.$anonfun$concurrent_key_update$4(StoreTest.scala:246)
	at io.iohk.iodb.ForkExecutor.$anonfun$execute$1(ForkExecutor.scala:21)
	at io.iohk.iodb.TestUtils$.$anonfun$runnable$1(TestUtils.scala:95)

We need to

ensure that compaction is always triggered after N updates (~1000)
throttle updates until compaction finishes with M updates (~2000)
ensure that older files are closed and deleted

Allow non mmap files for Windows

Memory mapped files have some issues on Windows. If mmap handle is not correctly released (JVM crashes, store was not closed) the files can not be deleted until after Windows reboots.

IODB needs an option to operate on top of regular RandomAccessFile or FileChannel

Too many mmaped files

IODB fails with out of memory exception followed by JVM crash:

Caused by: java.lang.OutOfMemoryError: Map failed
    at sun.nio.ch.FileChannelImpl.map0(Native Method)
    at sun.nio.ch.FileChannelImpl.map(FileChannelImpl.java:937)
    ... 17 more
Java HotSpot(TM) 64-Bit Server VM warning: Attempt to deallocate stack guard pages failed.
Java HotSpot(TM) 64-Bit Server VM warning: INFO: os::commit_memory(0x00007fd92aac1000, 12288, 0) failed; error='Cannot allocate memory' (errno=12)

Problem is that too many files are memory mapped. Here is a way to diagnose it:

I have seen these error before when running out of resources such as running out of swap space or running out of allowed memory mapping. Have a look at sudo cat /proc/$PID/maps | wc -l compared with cat /proc/sys/vm/max_map_count

Default limit is 64K mmaps per process. Total number of files in folder was 400 at crash, there is single mmap per file. Mmap handle is released when DirectByteBuffer is GCed, so the GC does not collect buffers fast enough.

Solution is to unmap buffers using cleaner hack from MapDB.

Compaction is broken

VersionID expansion #5 introduced problem in compaction. Two smoke tests in LSMStoreBurnTest are now failing. Problem is likely in a way merge files are produced.

Remove Main Log, add Journal, make shards durable

Main Log is suppose to be central component, where all data are stored and which provides durability. Shards are suppose to provide faster lookups.

However there is design flaw; if all data are in single Log, it becomes large and impossible to compact/clean in reasonable time.

It also leads to data duplication. Data are stored twice; in Main Log and in Shards.

So we need to:

remove Main Log
make Shards durable
provide temporary durable Journal for storing N last updates
- do not store all data in Journal, just Updated data
Sharding Task takes data from Journal and distributes them into Shards
once data are durably written to Shards, Sharding Task deletes Journal
Modify Key Lookup to first look into Journal, than Shards

FileChannel is slow, use memory mapped files and unsafe

Store#get() is slowed down by FileChannel random seeks. We should add Memory Mapped Files to speedup get operations.

Use checksum

Each log file should be protected by 64bit checksum to protect from data corruption. This checksum will be verified when store is opened. Non crypto checksum will be sufficient (XXHash).

Multithreaded compaction

Multithreaded code should:

Find Key without lock, just semaphore to prevent file from being delete
- JVM crash if MappedByteBuffer is released during file traversal
separate background task to delete unused and invalidated files
- files are unmodifiable, unless invalidated and their semaphore is released
per-file locking for Updates
Structural Lock for creating new files, branching, cleanup and rollback
Store Open code traverses all files, parallelize per file

OutOfMemory during compaction

Background compaction process crashes with OutOfMemoryException. Merging loads all data on heap and heap gets exhausted. We need to:

replace ByteArrayWrapper with byte[] in internal structures. Profiler shows 50% rmemory eduction with 32 byte keys/values
modify compaction to use streaming, rather than full memory load

Exceptions:

io.iohk.iodb.LSMStore$$anon$1 run
SEVERE: Background task failed
java.lang.OutOfMemoryError: GC overhead limit exceeded
	at io.iohk.iodb.FileAccess$FILE_CHANNEL$.readData(FileAccess.scala:299)
	at io.iohk.iodb.FileAccess$FILE_CHANNEL$.$anonfun$readKeyValues$2(FileAccess.scala:337)
	at io.iohk.iodb.FileAccess$FILE_CHANNEL$.$anonfun$readKeyValues$2$adapted(FileAccess.scala:335)
	at io.iohk.iodb.FileAccess$FILE_CHANNEL$$$Lambda$102/710072189.apply(Unknown Source)
	at scala.collection.TraversableLike.$anonfun$map$1(TraversableLike.scala:234)
	at scala.collection.TraversableLike$$Lambda$9/1068934215.apply(Unknown Source)
	at scala.collection.immutable.Range.foreach(Range.scala:156)
	at scala.collection.TraversableLike.map(TraversableLike.scala:234)
	at scala.collection.TraversableLike.map$(TraversableLike.scala:227)
	at scala.collection.AbstractTraversable.map(Traversable.scala:104)
	at io.iohk.iodb.FileAccess$FILE_CHANNEL$.readKeyValues(FileAccess.scala:335)
	at io.iohk.iodb.FileAccess$SAFE$.readKeyValues(FileAccess.scala:394)
	at io.iohk.iodb.LSMStore.$anonfun$keyValues$1(LSMStore.scala:945)
	at io.iohk.iodb.LSMStore$$Lambda$25/644460953.apply(Unknown Source)
	at scala.collection.immutable.List.map(List.scala:276)
	at io.iohk.iodb.LSMStore.keyValues(LSMStore.scala:941)
	at io.iohk.iodb.LSMStore.taskShardMerge(LSMStore.scala:786)
	at io.iohk.iodb.LSMStore.$anonfun$taskSharding$11(LSMStore.scala:751)
	at io.iohk.iodb.LSMStore$$Lambda$101/1892423954.apply$mcV$sp(Unknown Source)
	at io.iohk.iodb.LSMStore$$anon$1.run(LSMStore.scala:473)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
	at java.lang.Thread.run(Thread.java:745)

Another possible problem is exception thrown after compaction fails. We need better recovery for failed background tasks:


[error] Exception in thread "main" java.lang.IllegalArgumentException: Negative position                                       [error]         at sun.nio.ch.FileChannelImpl.read(FileChannelImpl.java:718)
[error]         at io.iohk.iodb.Utils.readFully(Utils.java:189)
[error]         at io.iohk.iodb.FileAccess$FILE_CHANNEL$.readInt(FileAccess.scala:313)                                         
[error]         at io.iohk.iodb.FileAccess$FILE_CHANNEL$.getValue(FileAccess.scala:260)
[error]         at io.iohk.iodb.FileAccess$SAFE$.getValue(FileAccess.scala:376)
[error]         at io.iohk.iodb.LSMStore.getUpdates(LSMStore.scala:660)                                                        [error]         at io.iohk.iodb.LSMStore.get(LSMStore.scala:691)
[error]         at io.iohk.iodb.bench.SimpleKVBench$.$anonfun$bench$7(SimpleKVBench.scala:80)
[error]         at io.iohk.iodb.bench.SimpleKVBench$.$anonfun$bench$7$adapted(SimpleKVBench.scala:79)                          [error]         at scala.collection.Iterator.foreach(Iterator.scala:929)
[error]         at scala.collection.Iterator.foreach$(Iterator.scala:929)
[error]         at scala.collection.AbstractIterator.foreach(Iterator.scala:1406)                                              [error]         at scala.collection.IterableLike.foreach(IterableLike.scala:71)
[error]         at scala.collection.IterableLike.foreach$(IterableLike.scala:70)
[error]         at scala.collection.AbstractIterable.foreach(Iterable.scala:54)                                                [error]         at io.iohk.iodb.bench.SimpleKVBench$.$anonfun$bench$5(SimpleKVBench.scala:79)
[error]         at scala.collection.immutable.Range.foreach$mVc$sp(Range.scala:156)
[error]         at io.iohk.iodb.bench.SimpleKVBench$.$anonfun$bench$4(SimpleKVBench.scala:72)
[error]         at io.iohk.iodb.TestUtils$.runningTimeUnit(TestUtils.scala:65)                                                 
[error]         at io.iohk.iodb.bench.SimpleKVBench$.bench(SimpleKVBench.scala:70)
[error]         at io.iohk.iodb.bench.SimpleKVBench$.main(SimpleKVBench.scala:26)
[error]         at io.iohk.iodb.bench.SimpleKVBench.main(SimpleKVBench.scala)

Distribute task loads data on memory

ShardedStore and LogStore getAll() methods use TreeMap to merge results from multiple updates. Use merging iterator instead.

StoreShard.taskDistribute fails under heavy load with OOEM

If there are too many inserts, the distribute tasks will run out of heap and fail.

The data merging uses lazy iterator and does not load all data into memory.
Problem is in serialization. The entire data set is serialized into on-heap byte[], and that causes OOEM.

Solution is to serialize data into FileChannel and latter transfer it into log file

ShardedStore rollback is not propagated to shards

If ShardedStore#rollback() is called, journal is rolled back and the shard pointers are updated.
However the internal state (data) remains unchanged. So on next taskDistribute the rolled back data in shard are restored.

We need to:

taskDistribute() must attach versionID from journal to shards
on ShardedStore#rollback find versionID of last distribution and rollback all shards to this versionId

VersionID should be bigger

VersionID is currently long. 8 bytes are not enough, so increase it. Also versionID does not have to be sequential, but will be randomly generated.

M1 acceptance test fails

With default parameters (1M keys) the M1Test fails after several inserts with wrong data (wrong value associated with the key). Exception:


rollback
Ver: 27 - disk size: 6.859775052 GB
rollback
Ver: 30 - disk size: 6.964930982 GB
rollback
rollback
rollback
Exception in thread "main" org.scalatest.exceptions.TestFailedException: Some(ByteArrayWrapper[D89CB8196F0EFB6892F94D68FCCC2C35F0B84609E5F12C55DD85ABA8D5D9BEF76808F3B572E5900112B81927BA5BB5F67E1BDA28B4049BF0E4AED78DB15D7BF2FC0C34E9A99DE4EF3BC2B17C8137AD659878F9E93D]) was not equal to None
	at org.scalatest.MatchersHelper$.indicateFailure(MatchersHelper.scala:340)
	at org.scalatest.Matchers$AnyShouldWrapper.shouldBe(Matchers.scala:6864)
	at io.iohk.iodb.smoke.M1Test$.$anonfun$main$5(M1Test.scala:106)
	at io.iohk.iodb.smoke.M1Test$.$anonfun$main$5$adapted(M1Test.scala:102)
	at scala.collection.immutable.Range.foreach(Range.scala:156)
	at io.iohk.iodb.smoke.M1Test$.main(M1Test.scala:102)

Full log is here:
https://gist.github.com/jankotek/c7e2c52ce54764264e1c35fe7af15266

Store.get should return Option[V]

Store should mimic Map behaviour. Get returns option, apply returns value or throws an exception

Deleted keys reappear after rollback

There is mistake in journal replay, it does not handle tombstones correctly.

Optional In-memory storage of all the data in current version

Make a flag in database constructor to store all the data (current version only) in memory (guarantee is not needed, so if it is impossible to store the whole dataset in memory, dump it on disk anyway).

Rework Clean Task, merge it with compaction

Clean (destroy all but last N snapshots) right now runs in foreground; user code has to call it and wait until clean up finishes.

However full cleanup moves lot of data and should be ran as part of compaction in background. Also cleanup should be incremental.

So:

rework compaction so that some snapshots are 'valid' and 'invalid'
- invalid shapshots are compacted and destroyed
- rework compaction code to preserve valid snapshots
cleanup method only invalidates snapshots, and returns immediately
heurestic in compaction to merge Shard every N Updates.
- Log can have multiple Merged updates in linked-list?
- based on file size, rather than number of updates?

Merge multiple Updates into single file

IODB right now stored each Update in separate file. That leads to problem where file handles are exhausted and JVM crashes. Default maximal number of opened files is around 64K. It can be modified at OS level, but IODB should not require that.

This also reads to huge memory overhead, since each update consumes about 400 bytes of heap space for file handle, versionID etc.

So we need to change format, so that multiple Updates are stored within single file (and single file handle).
Use linked-list of updates as outlined here: http://www.mapdb.org/blog/lsm_store_and_updates/

Changes:

drop log as a component
find efficient way to represent single update
- use primitive collections, so memory consumption should 8 bytes per update, file# and offset?
- versionID is byte[] so perhaps use hashcode multimap to identify Updates?
append-only files can not be written with mmap files
- JVM crash with sparse files if disk space runs out
- use FileOutputStream to write data
- readonly mmap huge region of file, which was not yet written. Data should become readable by mmap, once they are written by FileOutputStream
reopen code needs to traverse all updates and assemble linked tree of Updates
- multithreaded?

Unit test durability, data should survive JVM crash

MapDB has unit test which causes JVM process to seg-fault while data are written to disk. It tests that commits are durable, and commited data survive JVM crash. We should port this code to IODB and test IODB similar way.

Relevant code is here:
https://github.com/jankotek/mapdb/blob/master/src/test/java/org/mapdb/crash/CrashJVM.kt