fullstop000 / wickdb Goto Github PK

View Code? Open in Web Editor NEW

621.0 621.0 69.0 992 KB

Pure Rust LSM-tree based embedded storage engine

License: Apache License 2.0

Rust 100.00%

database leveldb lsm lsm-tree rust storage-engine

wickdb's People

Contributors

Stargazers

Watchers

wickdb's Issues

util::slice::Slice might cause UBs

The implementation of Slice is unsafe and it requires extra concerns from users.

See https://github.com/Fullstop000/wickdb/pull/22/files/c5bbbf914a72b48458be407b438ca4bff2a7ce08#r350562173

BlockIterator could cause UB

Blocks #37
Relate to #24

wickdb/src/sstable/table.rs

Lines 181 to 185 in 8a87a80

 let mut block_iter = self.block_reader(cmp, data_block_handle, options)?; 

 block_iter.seek(key); 

 if block_iter.valid() { 

 return Ok(Some((block_iter.key(), block_iter.value()))); 

 }

As block_iter.key() returns an owned Slice which represents the key field in block_iter, UB occurs after block_iter is dropped.

Feature: introduce mmap based read ops for read-only files

For some read-only files, the mmap can be used to improve the reading performance in read-only situation a lot. For example, when doing major compaction, reading the input SSTables by mmap may be more sufficient than just calling read().

In origin leveldb fs layer env, PosixMmapReadableFile is introduced for such cases.

Add benchmark for essentials

Add benchmark for components below :

Recommended using https://github.com/bheisler/criterion.rs

Fix test_sparse_merge

Temporarily, it's marked as ignored

Unstable unit test sstable::tests::test_randomized_key

running 1 test
test sstable::tests::test_randomized_key ... FAILED

failures:

---- sstable::tests::test_randomized_key stdout ----
thread 'sstable::tests::test_randomized_key' panicked at 'called `Option::unwrap()` on a `None` value', src/db/iterator.rs:387:43

Add transaction feature

It is missing this important feature

Add file rotation for logger

Currently, we use a simple file to store all log messages:

wickdb/src/logger.rs

Lines 54 to 58 in 15c37cc

 let file = storage 

 .create(generate_filename(db_path, FileType::InfoLog, 0).as_str()) 

 .unwrap(); 

 slog_async::Async::new(FileBasedDrain::new(file)) 

 .build()

This could be a bad design as the log messages growing. Adding a file rotation by implementing a slog Drain might be a good solution.

sstable::table::tests::test_build_empty_table fails

failures:

---- sstable::table::tests::test_build_empty_table stdout ----
thread 'sstable::table::tests::test_build_empty_table' panicked at 'assertion failed: table.meta_block_handle.is_some()', src/sstable/table.rs:665:9
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:197
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:208
   4: <std::panicking::begin_panic::PanicPayload<A> as core::panic::BoxMeUp>::get
             at src/libstd/panicking.rs:474
   5: std::sync::once::Once::is_completed
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panicking.rs:408
   6: wickdb::sstable::table::tests::test_build_empty_table
             at src/sstable/table.rs:665
   7: wickdb::sstable::table::tests::test_build_empty_table::{{closure}}
             at src/sstable/table.rs:655
   8: core::ops::function::FnOnce::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libcore/ops/function.rs:231
   9: <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/liballoc/boxed.rs:704
  10: panic_unwind::dwarf::eh::read_encoded_pointer
             at src/libpanic_unwind/lib.rs:85
  11: test::run_test::run_test_inner::{{closure}}
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panicking.rs:272
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panic.rs:394
             at src/libtest/lib.rs:1468

Something wrong happens in table iterator

Add backoff to avoid infinite compact_mem_table fails

If compact_mem_table fails, the immutable memtable will be still there. And we re-schedule compaction after a compaction which means compact_mem_table will be called infinitely. To fix this, we can introduce a backoff to prevent the infinite compaction loop.
If compaction fails hits the backoff limit, prevent all writing requests to the wickdb could be a good choice.

Use Generic instead of Trait Object

In most instances, codes perform faster when using Generic than Trait Object.
We can replace some trait objects by Generic (not all of them) to benefit from inline function in compile time.

Introduce unencoded WriteBatch

Currently, the WriteBatch follows the original implementation of leveldb, which is a Vec<u8> with encoded entries. When we call put, the entry will be encoded into variant length based encoded bytes, fill the bytes into a WriteBatch and then be inserted into MemTable, However, when inserting the batch into MemTable, it needs to be decoded into entires first.

For a more efficient inserting style, we might just let WriteBatch hold unencoded entries, and deliver them to the MemTable without any serde.

Feature: support concurrently insert batches into memtable

In the origin version of leveldb, the write path is like below:

          write
  write     +         write
    +       |   write   +
    |       |     +     |
    |       |     |     |
    |       |     |     |
+---v-------v-----v-----v---+
|                           |
|        Mutex<queue>       |
|                           |
+-------------+-------------+
              |
              |
              |  group batch
              | <single thread>
              |
              v
     +--------+--------+
     |                 |
     |     Memtable    |
     |                 |
     +-----------------+

Writing batches concurrently will result in a single thread ingestion into memtable and then notify all the relate blocked write request threads.
Maybe we can support concurrently inserting batches into memtable , which should improve the write performance a lot.

This feature includes following tasks:

Introduce an thread-safe concurrent skiplit (#85)
Make the current queue scale with inserting threads

Potential CI issue in macOS

https://travis-ci.org/Fullstop000/wickdb/jobs/588278442
CI failed in macOS because of the lack of lib six for lldb:

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/Library/Developer/CommandLineTools/Library/PrivateFrameworks/LLDB.framework/Resources/Python/lldb/__init__.py", line 98, in <module>
    import six
ImportError: No module named six
Traceback (most recent call last):
  File "<string>", line 1, in <module>

And it's wired that sstable::tests::test_simple_empty_key hangs when running kcov but works fine in other places.

Relative issue: rust-lang/rust#38380

Remove Slice in trait Iterator

Current Iterator trait returns owned Slice from key() and value(), which is really unsafe.
Use lifetime bounded &'a [u8] instead.

This is part of #24

Add solid test cases

Increase the coverage of test cases over 90%.
See https://codecov.io/gh/Fullstop000/wickdb

Most essential parts:

Building kcov failed on Windows

https://travis-ci.org/Fullstop000/wickdb/jobs/602617170

Done. Your build exited with 0.
CMake Error at C:/Program Files/CMake/share/cmake-3.15/Modules/FindPackageHandleStandardArgs.cmake:137 (message):
  Could NOT find ZLIB (missing: ZLIB_LIBRARY ZLIB_INCLUDE_DIR)
Call Stack (most recent call first):
  C:/Program Files/CMake/share/cmake-3.15/Modules/FindPackageHandleStandardArgs.cmake:378 (_FPHSA_FAILURE_MESSAGE)
  C:/Program Files/CMake/share/cmake-3.15/Modules/FindZLIB.cmake:115 (FIND_PACKAGE_HANDLE_STANDARD_ARGS)
  src/CMakeLists.txt:8 (find_package)
/c/Users/travis/.travis/functions: line 109: make: command not found
/c/Users/travis/.travis/functions: line 109: make: command not found
/c/Users/travis/.travis/functions: line 109: ./kcov-build/usr/local/bin/kcov: No such file or directory
bash: /dev/fd/63: No such file or directory

Use associated type for Iterator trait

Current Iterator trait just returns Slice in key() and value()

wickdb/src/iterator.rs

Lines 59 to 65 in 6029534

 fn key(&self) -> Slice; 

 /// Return the value for the current entry. The underlying storage for 

 /// the returned slice is valid only until the next modification of 

 /// the iterator. 

 /// REQUIRES: `valid()` 

 fn value(&self) -> Slice;

This can limit the usage of Iterators. We might want a non-slice key or value.

Consider using an advanced trait with associated type instead:

pub trait Iterator {
    type Key;
    type Value;

    fn key(&self) -> Self::Key;
    fn value(&self) -> Self::Value;
}

Block #49

没法cargo add wickdb ?

如题

Make getter/setters to fit RFC 344

Relative link RFC/0344.

Clearly, we just need to rename set_ methods in normal structs.

见截图，为啥卡住put这一步了？

如题

Introduce YCSB style bench module

Add an individual module for benchmark through customized YCSB workload.
Refer to https://github.com/cockroachdb/pebble/blob/master/cmd/pebble/ycsb.go

Use slog as logging system

Use slog as the project logging

Introduce slog and slog-term to support terminal logging output
Use slog-async to support file-based logging output

版本没兼容导入的模块得使用extern修饰

我使用win10的操作系统，rust-version是1.3.1，cargo test时候，报出如下错误

error[E0658]: imports can only refer to extern crate names passed with `--extern` on stable channel (see issue #53130)
  --> src\lib.rs:50:9
   |
34 | mod compaction;
   | --------------- not an extern crate passed with `--extern`
...
50 | pub use compaction::ManualCompaction;
   |         ^^^^^^^^^^
   |
note: this import refers to the module defined here
  --> src\lib.rs:34:1
   |
34 | mod compaction;
   | ^^^^^^^^^^^^^^^

error[E0658]: imports can only refer to extern crate names passed with `--extern` on stable channel (see issue #53130)
  --> src\lib.rs:51:9
   |
35 | pub mod db;
   | ----------- not an extern crate passed with `--extern`
...
51 | pub use db::{WickDB, DB};
   |         ^^
   |
note: this import refers to the module defined here
  --> src\lib.rs:35:1
   |
35 | pub mod db;
   | ^^^^^^^^^^^

CI's running time could be too long

There are several steps in the CI that could produce a binary like wickdb-*** under target/debug. And kcov will try to generate a Codecov report for every binary existed due to it has no idea which is the latest, which results in very long processing time (it re-run all the tests with every binary every time)

arena tests might fail on mac OS due to unsafe memory handling

Get result from cargo test:

test db::filename::tests::test_generate_filename ... ok
test db::format::tests::test_pack_seq_and_type ... ok
test db::filename::tests::test_parse_filename ... ok
test db::format::tests::test_internal_key_encode_decode ... ok
wickdb-4ab306f68f44e64d(32405,0x700008904000) malloc: *** error for object 0x11147a038: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
test mem::arena::tests::test_alloc_nodes ... ok
error: process didn't exit successfully: `/Users/fullstop000/rust/wickdb/target/debug/deps/wickdb-4ab306f68f44e64d` (signal: 6, SIGABRT: process abort signal)

But it is confused that all the tests are green if you use cargo test <mod name> for every mod.

And this only happens in mac OS.

	let mut block_iter = self.block_reader(cmp, data_block_handle, options)?;
	block_iter.seek(key);
	if block_iter.valid() {
	return Ok(Some((block_iter.key(), block_iter.value())));
	}

	let file = storage
	.create(generate_filename(db_path, FileType::InfoLog, 0).as_str())
	.unwrap();
	slog_async::Async::new(FileBasedDrain::new(file))
	.build()

	fn key(&self) -> Slice;

	/// Return the value for the current entry. The underlying storage for
	/// the returned slice is valid only until the next modification of
	/// the iterator.
	/// REQUIRES: `valid()`
	fn value(&self) -> Slice;

fullstop000 / wickdb Goto Github PK

wickdb's People

Contributors

Stargazers

Watchers

Forkers

wickdb's Issues

Recommend Projects

Recommend Topics

Recommend Org