Giter VIP home page Giter VIP logo

nebuchadnezzar's Introduction

Nebuchadnezzar

Build Status

"This is my ship...the Nebuchadnezzar, it's a hovercraft." ― Morpheus, The Matrix

High performance, rich typing RAMCloud implementation. Distributed in-memory Key-Value store, optional transaction, made to power the Morpheus project.

  • In-memory, persistant storage
  • Shared-nothing distributed architecture
  • Rich-typed schema (scalar, array, map, nested, length-variable data types)
  • Hash based low overhead primal key-value operations
  • Timestamp transactions, read committed
  • Non-blocking LSM-tree (B+ tree based) for range query

Nebuchadnezzar (aka Neb) have already been converted from it's former Clojure version and will stay with rust afterwards.

Copyright © 2021 Shisoft Research

Distributed under the GNU Lesser General Public License v3.0 or any later version.

nebuchadnezzar's People

Contributors

shisoft avatar

Stargazers

avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar

Watchers

avatar avatar avatar avatar avatar avatar avatar avatar

Forkers

bonedaddy tiany7 iq-scm iyefeng

nebuchadnezzar's Issues

Investigate schema isolation problem

It was observed that different server on the same application, schemas will affect each other. Not sure if the problem is on bifrost or neb itself.

Only schema discovered have such problem. It should be fine if one application have one server, but this issue makes testing harder.

read_cell_by_key function is needed

Although Morpheus will use it's internal encoder to archive this, it will be great if Nebuchadnezzar can provide such function in both client and transaction.

As a reminder, key encoder for write have been implemented by Cell::new, Cell::new_with_id function will bypass this procedure.

Dynamic cell schema

Nebuchadnezzar inherently requires schema for each cell. It is also possible to provide schemaless and partial schemaless feature by appending a reserved field with data type Any to store undefined fields (that will also introduce performance and memory efficiency downfalls when heavily been used). Data in this field may contain a Map, it's keys are unexpected cell keys and values should be serializable by serde (bincode).

This feature would only support top level fields for partial schemas. That means if a field is defined in schema, it's sub-fields cannot be dynamic, the system would just drop those sub-fields like before.

Investigate transaction deadlock on reading internal cell meta

The internal implementation for locking affected cells as a whole is meta data locking in a hash map. The deadlock can occur even when there is no parallel transaction. This may caused by possible reentering locking or trying to lock two hash map items in the same bucket. Possible solution is use fine grained lock for each cell meta in a hash map

  thread #2: tid = 16757, 0x00007fd854c46499 libc.so.6`syscall + 25 at syscall.S:38, name = 'tests::graph::r', stop reason = signal SIGSTOP
    frame #0: 0x00007fd854c46499 libc.so.6`syscall + 25 at syscall.S:38
    frame #1: 0x000055d90ab303c7 morpheus-4a54a2b51213d322`parking_lot_core::thread_parker::ThreadParker::park::h41457925d1e10d51 + 87 at linux.rs:50
    frame #2: 0x000055d90ab32d75 morpheus-4a54a2b51213d322`parking_lot_core::parking_lot::park_internal::h3f4c2fb9f885ef6d + 837 at parking_lot.rs:548
    frame #3: 0x000055d90aa46199 morpheus-4a54a2b51213d322`parking_lot_core::parking_lot::park::hc773471ba7a562d6 + 361 at parking_lot.rs:498
    frame #4: 0x000055d90aa4a3cd morpheus-4a54a2b51213d322`parking_lot::raw_rwlock::RawRwLock::lock_exclusive_slow::h429e1dc040e1dea6 + 605 at raw_rwlock.rs:244
    frame #5: 0x000055d90a49883e morpheus-4a54a2b51213d322`parking_lot::raw_rwlock::RawRwLock::lock_exclusive::hb6a328b98360cd35 + 110 at raw_rwlock.rs:52
    frame #6: 0x000055d90a55be2d morpheus-4a54a2b51213d322`_$LT$parking_lot..rwlock..RwLock$LT$T$GT$$GT$::write::h69a1e8941b8b4c15 + 29 at rwlock.rs:253
    frame #7: 0x000055d90a545230 morpheus-4a54a2b51213d322`_$LT$chashmap..Table$LT$K$C$$u20$V$GT$$GT$::lookup_or_free::h457af9594d7c12b1 + 544 at lib.rs:323
    frame #8: 0x000055d90a5531fb morpheus-4a54a2b51213d322`_$LT$chashmap..CHashMap$LT$K$C$$u20$V$GT$$GT$::alter::h700ef110a4522553 + 251 at lib.rs:840
    frame #9: 0x000055d90a725076 morpheus-4a54a2b51213d322`neb::server::transactions::data_site::DataManager::get_cell_meta::h9d23c684d723cb81 + 118 at data_site.rs:118
    frame #10: 0x000055d90a72a58d morpheus-4a54a2b51213d322`_$LT$neb..server..transactions..data_site..DataManager$u20$as$u20$neb..server..transactions..data_site..Service$GT$::prepare::h83ac443d2ab66f02 + 1293 at data_site.rs:294
    frame #11: 0x000055d90a758650 morpheus-4a54a2b51213d322`neb::server::transactions::data_site::AsyncServiceClient::prepare::h2e20d314d1aac57a + 512 at <service macros>:93
    frame #12: 0x000055d90a71bad7 morpheus-4a54a2b51213d322`neb::server::transactions::manager::TransactionManager::site_prepare::h146d355f5b2a6973 + 711 at manager.rs:201
    frame #13: 0x000055d90a71cd76 morpheus-4a54a2b51213d322`neb::server::transactions::manager::TransactionManager::sites_prepare::_$u7b$$u7b$closure$u7d$$u7d$::h040271d5292a1704 + 502 at manager.rs:235
    frame #14: 0x000055d90a5a9d79 morpheus-4a54a2b51213d322`core::ops::function::impls::_$LT$impl$u20$core..ops..function..FnOnce$LT$A$GT$$u20$for$u20$$RF$$u27$a$u20$mut$u20$F$GT$::call_once::ha4fc94bf3c36b65d + 89 at function.rs:191
    frame #15: 0x000055d90a51b3f5 morpheus-4a54a2b51213d322`_$LT$core..option..Option$LT$T$GT$$GT$::map::hdcdd32e1d6d52ead + 261 at option.rs:398
    frame #16: 0x000055d90a6e0027 morpheus-4a54a2b51213d322`_$LT$core..iter..Map$LT$I$C$$u20$F$GT$$u20$as$u20$core..iter..iterator..Iterator$GT$::next::h568c7bb6139df530 + 71 at mod.rs:1073
    frame #17: 0x000055d90a6eb53a morpheus-4a54a2b51213d322`_$LT$alloc..vec..Vec$LT$T$GT$$u20$as$u20$alloc..vec..SpecExtend$LT$T$C$$u20$I$GT$$GT$::from_iter::hf092485d09cabbab + 218 at vec.rs:1782
    frame #18: 0x000055d90a6ebeb6 morpheus-4a54a2b51213d322`_$LT$alloc..vec..Vec$LT$T$GT$$u20$as$u20$core..iter..traits..FromIterator$LT$T$GT$$GT$::from_iter::h080b8febcb37b56e + 214 at vec.rs:1695
    frame #19: 0x000055d90a5d2173 morpheus-4a54a2b51213d322`core::iter::iterator::Iterator::collect::h1fea69a5fcca9c6c + 179 at iterator.rs:1302
    frame #20: 0x000055d90a71c7e2 morpheus-4a54a2b51213d322`neb::server::transactions::manager::TransactionManager::sites_prepare::h3cc7c05c79d3010c + 354 at manager.rs:233
    frame #21: 0x000055d90a7228e8 morpheus-4a54a2b51213d322`_$LT$neb..server..transactions..manager..TransactionManager$u20$as$u20$neb..server..transactions..manager..Service$GT$::prepare::ha43532d502e887d4 + 1288 at manager.rs:524
    frame #22: 0x000055d90a754954 morpheus-4a54a2b51213d322`neb::server::transactions::manager::SyncServiceClient::prepare::h851f878cf6410753 + 324 at <service macros>:73
    frame #23: 0x000055d90a734578 morpheus-4a54a2b51213d322`neb::client::transaction::Transaction::prepare::h5789c4bcada856dc + 136 at transaction.rs:97
    frame #24: 0x000055d90a380adb morpheus-4a54a2b51213d322`neb::client::Client::transaction::h069d7471b04691c2 + 1643 at mod.rs:111
    frame #25: 0x000055d90a46b191 morpheus-4a54a2b51213d322`morpheus::graph::Graph::graph_transaction::hcb6848abedafea02 + 177 at mod.rs:199
    frame #26: 0x000055d90a46b464 morpheus-4a54a2b51213d322`morpheus::graph::Graph::link::ha1410620c20cb58a + 292 at mod.rs:207
    frame #27: 0x000055d90a473dce morpheus-4a54a2b51213d322`morpheus::tests::graph::relationship::hf2c6e273f2b7e9eb + 12958 at mod.rs:164
    frame #28: 0x00007fd855aa7d82 libtest-9bc7c35e688285f2.so`rust_metadata_test_578d6d33bea1f959deed314ad20f8801 - 18446603506582651517 at lib.rs:1477
    frame #29: 0x00007fd85580e65d libstd-bea72aea09c9701c.so`rust_metadata_std_1c75f9341d66c00752d4419c0dc36e2d - 18446603506585377186 at lib.rs:98
    frame #30: 0x00007fd855a9674d libtest-9bc7c35e688285f2.so`rust_metadata_test_578d6d33bea1f959deed314ad20f8801 - 18446603506582722738 at panicking.rs:458
    frame #31: 0x00007fd855a97543 libtest-9bc7c35e688285f2.so`rust_metadata_test_578d6d33bea1f959deed314ad20f8801 - 18446603506582719164 at mod.rs:364
    frame #32: 0x00007fd85580e65d libstd-bea72aea09c9701c.so`rust_metadata_std_1c75f9341d66c00752d4419c0dc36e2d - 18446603506585377186 at lib.rs:98
    frame #33: 0x00007fd855aa04d3 libtest-9bc7c35e688285f2.so`rust_metadata_test_578d6d33bea1f959deed314ad20f8801 - 18446603506582682412 at panicking.rs:458
    frame #34: 0x00007fd8557ddb0c libstd-bea72aea09c9701c.so`rust_metadata_std_1c75f9341d66c00752d4419c0dc36e2d - 18446603506585576691 at boxed.rs:692
    frame #35: 0x00007fd85512c6ba libpthread.so.0`start_thread + 202
    frame #36: 0x00007fd854c4c3dd libc.so.6`__clone + 109 at clone.S:109

Investigate transaction wait deadlock

Transaction have wait feature to deal with resolvable transaction unrealization (read written cell need to wait for owned transaction to finished). Some time for some reason, the deadlock can occur, even when there is no parallel transaction.

This may because release instruction did not delivered well from previous transaction when it was ended.

  thread #2: tid = 15824, 0x00007fea414cb360 libpthread.so.0`__pthread_cond_wait + 192, name = 'tests::graph::r', stop reason = signal SIGSTOP
    frame #0: 0x00007fea414cb360 libpthread.so.0`__pthread_cond_wait + 192
    frame #1: 0x00007fea41b475ff libstd-bea72aea09c9701c.so`rust_metadata_std_1c75f9341d66c00752d4419c0dc36e2d - 18446603429608131072 at condvar.rs:72
    frame #2: 0x00007fea41b62290 libstd-bea72aea09c9701c.so`rust_metadata_std_1c75f9341d66c00752d4419c0dc36e2d - 18446603429608021359 at blocking.rs:81
    frame #3: 0x000055ecc782973d morpheus-4a54a2b51213d322`_$LT$std..sync..mpsc..oneshot..Packet$LT$T$GT$$GT$::recv::h0f6131c68372a59d + 461 at oneshot.rs:163
    frame #4: 0x000055ecc779ce7c morpheus-4a54a2b51213d322`_$LT$std..sync..mpsc..Receiver$LT$T$GT$$GT$::recv::hfb24cc1e21df94f6 + 364 at mod.rs:1200
    frame #5: 0x000055ecc79710a5 morpheus-4a54a2b51213d322`neb::server::transactions::manager::AwaitingServer::wait::h3af9bd2aa683c7c9 + 69 at manager.rs:609
    frame #6: 0x000055ecc7971541 morpheus-4a54a2b51213d322`neb::server::transactions::manager::AwaitManager::txn_wait::ha141f8ee0b34d2e4 + 81 at manager.rs:639
    frame #7: 0x000055ecc7966edc morpheus-4a54a2b51213d322`neb::server::transactions::manager::TransactionManager::read_from_site::h7a52dd66b9fa1ea5 + 1148 at manager.rs:130
    frame #8: 0x000055ecc796c84a morpheus-4a54a2b51213d322`_$LT$neb..server..transactions..manager..TransactionManager$u20$as$u20$neb..server..transactions..manager..Service$GT$::read::h4abf70d9803d6396 + 1530 at manager.rs:385
    frame #9: 0x000055ecc79a03e0 morpheus-4a54a2b51213d322`neb::server::transactions::manager::SyncServiceClient::read::h46b315283007201c + 384 at <service macros>:73
    frame #10: 0x000055ecc7980262 morpheus-4a54a2b51213d322`neb::client::transaction::Transaction::read::h5f814889bceba16f + 210 at transaction.rs:39
    frame #11: 0x000055ecc76b17b8 morpheus-4a54a2b51213d322`morpheus::graph::id_list::IdList::get_root_list_id::h7b7e6f1bee3daf5f + 2248 at id_list.rs:151
    frame #12: 0x000055ecc76b2b89 morpheus-4a54a2b51213d322`morpheus::graph::id_list::IdList::iter::h3bc1e9b7af8deb31 + 73 at id_list.rs:195
    frame #13: 0x000055ecc76b2fbf morpheus-4a54a2b51213d322`morpheus::graph::id_list::IdList::count::he2eddbe569e39672 + 79 at id_list.rs:210
    frame #14: 0x000055ecc76b91ed morpheus-4a54a2b51213d322`morpheus::graph::GraphTransaction::degree::h8ce9893c42dcc85a + 525 at mod.rs:325
    frame #15: 0x000055ecc76b86d7 morpheus-4a54a2b51213d322`morpheus::graph::Graph::degree::_$u7b$$u7b$closure$u7d$$u7d$::h7cd451d03a1b08b0 + 103 at mod.rs:217
    frame #16: 0x000055ecc76b8241 morpheus-4a54a2b51213d322`morpheus::graph::Graph::graph_transaction::_$u7b$$u7b$closure$u7d$$u7d$::h9109abf4f9fa7684 + 129 at mod.rs:194
    frame #17: 0x000055ecc75cea3f morpheus-4a54a2b51213d322`neb::client::Client::transaction::hb12b058693a6525f + 1183 at mod.rs:105
    frame #18: 0x000055ecc76b80a5 morpheus-4a54a2b51213d322`morpheus::graph::Graph::graph_transaction::hb8b8cd95906c034c + 165 at mod.rs:199
    frame #19: 0x000055ecc76b8628 morpheus-4a54a2b51213d322`morpheus::graph::Graph::degree::h3a09c7cadc890745 + 216 at mod.rs:216
    frame #20: 0x000055ecc76c151a morpheus-4a54a2b51213d322`morpheus::tests::graph::relationship::hf2c6e273f2b7e9eb + 14826 at mod.rs:183
    frame #21: 0x00007fea41e40d82 libtest-9bc7c35e688285f2.so`rust_metadata_test_578d6d33bea1f959deed314ad20f8801 - 18446603429605012093 at lib.rs:1477
    frame #22: 0x00007fea41ba765d libstd-bea72aea09c9701c.so`rust_metadata_std_1c75f9341d66c00752d4419c0dc36e2d - 18446603429607737762 at lib.rs:98
    frame #23: 0x00007fea41e2f74d libtest-9bc7c35e688285f2.so`rust_metadata_test_578d6d33bea1f959deed314ad20f8801 - 18446603429605083314 at panicking.rs:458
    frame #24: 0x00007fea41e30543 libtest-9bc7c35e688285f2.so`rust_metadata_test_578d6d33bea1f959deed314ad20f8801 - 18446603429605079740 at mod.rs:364
    frame #25: 0x00007fea41ba765d libstd-bea72aea09c9701c.so`rust_metadata_std_1c75f9341d66c00752d4419c0dc36e2d - 18446603429607737762 at lib.rs:98
    frame #26: 0x00007fea41e394d3 libtest-9bc7c35e688285f2.so`rust_metadata_test_578d6d33bea1f959deed314ad20f8801 - 18446603429605042988 at panicking.rs:458
    frame #27: 0x00007fea41b76b0c libstd-bea72aea09c9701c.so`rust_metadata_std_1c75f9341d66c00752d4419c0dc36e2d - 18446603429607937267 at boxed.rs:692
    frame #28: 0x00007fea414c56ba libpthread.so.0`start_thread + 202
    frame #29: 0x00007fea40fe53dd libc.so.6`__clone + 109 at clone.S:109

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.