uncp / mushroom Goto Github PK

View Code? Open in Web Editor NEW

331.0 26.0 48.0 1.15 MB

Distributed In-Memory Index 分布式内存索引

License: Other

Makefile 1.27% C++ 97.87% Shell 0.86%

raft b-link-tree tcp-library rpc palm-tree

mushroom's Introduction

这个 repo 已弃用，请移步 aili 查看最新进展

Mushroom（蘑菇）：分布式内存索引

English Version of README

Mushroom是一个C++11编写、不依赖第三方库的轻量级Linux环境分布式内存索引，它由并发B^link树索引，TCP通信库，RPC框架，Raft一致性算法组成。

Behold, the power of Mushroom!

尝试

首先运行脚本gen_test_data.sh生成测试数据，然后进入src目录
./run blink queue 100，测试多线程索引（通过队列），数量可以是1到1000万
./run blink thread 100，测试多线程索引，数量可以是1到1000万
./run art 100，测试Adaptive Radix Tree，数量可以是1到1000万
【失效】./run index 100，单机测试分布式索引，100是索引数量（因为Raft没有深入优化过，所以请将数量控制在1-1000）

版本信息

版本	备注
0.1.0
0.2.0	读写锁并发索引
0.2.1	锁管理器优化
0.3.0	引入前缀压缩，B^link树占用内存减少约 9.1 %
0.4.0	实现映射队列，减少程序使用内存超过 50 %
0.4.1	合并锁管理器与页面管理器，使每次操作减少1把锁
0.4.2	修改根节点分裂方式
0.4.3	增加测试策略，多线程不经过队列直接进行任务
0.4.4	重构锁管理器
0.5.0	修复从版本0.4.1到0.4.4一直存在的bug（原子操作bug）
0.6.0	共享内存映射支持多进程，修复搜索bug，正确实现并发B^link树
0.6.1	二次哈希页面管理器，实现页面的懒惰分配
0.6.2	减少对标准库的依赖，加快编译速度，减少程序体积约42.1%
0.6.4	使用posix自旋锁，优化MushroomDB和BLinkTree结构
0.7.0	日志结构合并树（LSM Tree）
0.8.0	TCP通信库、RPC框架
0.9.0	Raft
0.9.1	ACID (批操作)、修改加锁策略
0.9.2	优化Raft状态变化，提高Liveness
1.0.0	分布式内存索引
1.1.0	B^link树结点从1/2满提高到2/3满，降低内存使用率约12%
1.1.1	优化Raft内存使用（牺牲可读性）
1.2.0	Adaptive Radix Tree
1.2.1	移除锁管理器，每个页面一把锁，性能提升约10%
1.2.2	引入布隆过滤器进行读写优化（然并卵）

其他

你可以在这个知乎专栏里找到Mushroom的介绍
分布式索引只是完成了单机功能，我写完就放弃优化了，所以较新的版本里./run index这个命令并不支持

PS: Mushroom 是一次致力于获得极致存储性能的激进尝试，在阅读具体代码之前，请注意：

编程规范、代码可读性、内存使用、接口是否友好等等一切无条件为性能做出让步
但是核心 B link 树的并发算法实现很简洁
对于内存的使用很极端，比如映射队列，介绍文章上以及下
有一些指针的 Hack 操作，比如柔性数组
删除和插入都是写操作，所以只有 Put（写）和 Get（读）操作（即不支持物理删除）

mushroom's People

Contributors

Stargazers

Watchers

mushroom's Issues

./run index 100时提示没有../src/mushroom/db.hpp

是否支持持久化，持久化后性能如何

求教

你好，我想问一下我应该怎样跟着你的项目也来写一个数据库呢？希望能给些建议，我自身有c语言和数据结构的基础，希望能通过写数据库来练手，提高工程能力。

compile error on branch V1.2.1 & V1.2.2

hi, I am trying to compile your code in CentOS7 64bit，but i got this error on both two branch:

g++ -std=c++11 -Wall -Wextra -O3 -o distributed_index_test blink/page_pool.o blink/pool_manager.o blink/db.o blink/b_link_tree.o blink/page.o network/socket.o network/poller.o network/channel.o network/connection.o network/endpoint.o network/eventbase.o network/server.o network/buffer.o rpc/rpc_server.o rpc/rpc_connection.o raft/raft_server.o ../test/distributed_index.cpp -pthread
../test/distributed_index.cpp:12:34: fatal error: ../src/mushroom/db.hpp: No such file or directory
#include "../src/mushroom/db.hpp"
^
compilation terminated.
make: *** [distributed_index_test] Error 1

appreciate for any help!

Several compile warnings and errors

On macOS Sierra 10.12.1

$ clang --version
Apple LLVM version 8.0.0 (clang-800.0.42.1)
Target: x86_64-apple-darwin16.1.0
Thread model: posix

warning and error imformation:

$ make single_thread_btree_test
c++  -std=c++14 -Wall -O3 -pthread  -c -o slice.o slice.cpp
c++  -std=c++14 -Wall -O3 -pthread  -c -o latch.o latch.cpp
In file included from latch.cpp:8:
./latch.hpp:73:11: warning: moving a temporary object prevents copy elision
      [-Wpessimizing-move]
                        return std::move(os.str());
                               ^
./latch.hpp:73:11: note: remove std::move call here
                        return std::move(os.str());
                               ^~~~~~~~~~        ~
1 warning generated.
c++  -std=c++14 -Wall -O3 -pthread  -c -o latch_manager.o latch_manager.cpp
In file included from latch_manager.cpp:11:
In file included from ./latch_manager.hpp:14:
./latch.hpp:73:11: warning: moving a temporary object prevents copy elision
      [-Wpessimizing-move]
                        return std::move(os.str());
                               ^
./latch.hpp:73:11: note: remove std::move call here
                        return std::move(os.str());
                               ^~~~~~~~~~        ~
latch_manager.cpp:46:9: warning: moving a local object in a return statement
      prevents copy elision [-Wpessimizing-move]
        return std::move(res);
               ^
latch_manager.cpp:46:9: note: remove std::move call here
        return std::move(res);
               ^~~~~~~~~~   ~
latch_manager.cpp:56:9: warning: moving a local object in a return statement
      prevents copy elision [-Wpessimizing-move]
        return std::move(res);
               ^
latch_manager.cpp:56:9: note: remove std::move call here
        return std::move(res);
               ^~~~~~~~~~   ~
3 warnings generated.
c++  -std=c++14 -Wall -O3 -pthread  -c -o btree_page.o btree_page.cpp
btree_page.cpp:301:9: warning: moving a temporary object prevents copy elision
      [-Wpessimizing-move]
        return std::move(os.str());
               ^
btree_page.cpp:301:9: note: remove std::move call here
        return std::move(os.str());
               ^~~~~~~~~~        ~
1 warning generated.
c++  -std=c++14 -Wall -O3 -pthread  -c -o btree.o btree.cpp
In file included from btree.cpp:13:
In file included from ./btree.hpp:17:
In file included from ./latch_manager.hpp:14:
./latch.hpp:73:11: warning: moving a temporary object prevents copy elision
      [-Wpessimizing-move]
                        return std::move(os.str());
                               ^
./latch.hpp:73:11: note: remove std::move call here
                        return std::move(os.str());
                               ^~~~~~~~~~        ~
btree.cpp:31:11: error: variable-sized object may not be initialized
        char buf[BTreePage::PageByte + key_len_] = {0};
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
btree.cpp:156:11: error: variable-sized object may not be initialized
        char buf[BTreePage::PageByte + key_len_] = {0};
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
btree.cpp:172:11: error: variable-sized object may not be initialized
        char tmp[BTreePage::PageByte + key_len_] = {0};
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
btree.cpp:244:11: error: variable-sized object may not be initialized
        char buf[BTreePage::PageByte + key_len_] = {0};
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 warning and 4 errors generated.
make: *** [btree.o] Error 1