uncp / aili Goto Github PK

the fastest in-memory index in the East 东半球最快并发索引

License: BSD 3-Clause "New" or "Revised" License

Makefile 1.34% C 97.39% C++ 0.75% Shell 0.52%

parallel-algorithm concurrent-data-structure palm-tree mass-tree b-link-tree b-star-tree prefix-b-tree adaptive-radix-tree b-tree

aili's People

Contributors

Stargazers

Watchers

aili's Issues

mass_node_get_version 只使用了 acquire, 是否存在风险?

根据专栏文章 https://zhuanlan.zhihu.com/p/52624601 提供的伪代码,

uint32_t before = node_get_stable_version(n);
// read node here
uint32_t after = node_get_version(n); // no need to be stable, just latest version
if ((before ^ after == LOCK_BIT) || (before ^ after == 0))
    // neither insert nor split happened

acquire 保证之后的读操作不会重排至当前操作之前, 但不保证之前的读操作不重排至当前操作之后, 换言之, after 的值可能比 read node 过程中的值从全局时间线来看更早.

实际运行有没有可能是这样的?

uint32_t before = node_get_stable_version(n);
uint32_t after = node_get_version(n); // no need to be stable, just latest version
// read node here
// WE HAVE A BIG PROBLEM NOW
if ((before ^ after == LOCK_BIT) || (before ^ after == 0))
    // neither insert nor split happened

是不是用 memory_order_seq_cst 更安全一点?

X86 保证 load load 不乱序, 只要编译器不重排是没有问题的.

Delete operation on Multi ART

Hi! First of all, congratulations for the performance achieved on your implementation!

I would like to know if you plan to implement the delete operation on your Multi ART algorithm.

请问新手如何调试与执行源码? makefile 执行是成功的. 在clion 上运行报的错如下.

====================[ Build | aili | Debug ]====================================
/home/muxin/devTool/clion-2019.2.5/bin/cmake/linux/bin/cmake --build /home/muxin/IdeaProjects/aili/cmake-build-debug --target aili -- -j 4
Scanning dependencies of target aili
[ 3%] Building C object CMakeFiles/aili.dir/palm/metric.c.o
[ 6%] Building C object CMakeFiles/aili.dir/test/art_test.c.o
[ 9%] Building C object CMakeFiles/aili.dir/test/mass_node_test.c.o
[ 12%] Building C object CMakeFiles/aili.dir/test/mass_tree_test.c.o
/home/muxin/IdeaProjects/aili/palm/metric.c:12:10: fatal error: c_hashmap/hashmap.h: No such file or directory
#include <c_hashmap/hashmap.h>
^~~~~~~~~~~~~~~~~~~~~
compilation terminated.
CMakeFiles/aili.dir/build.make:257: recipe for target 'CMakeFiles/aili.dir/palm/metric.c.o' failed
make[3]: *** [CMakeFiles/aili.dir/palm/metric.c.o] Error 1
make[3]: *** Waiting for unfinished jobs....
/home/muxin/IdeaProjects/aili/test/mass_node_test.c:14:10: fatal error: ../mass/node.h: No such file or directory
#include "../mass/node.h"
^~~~~~~~~~~~~~~~
compilation terminated.
/home/muxin/IdeaProjects/aili/test/art_test.c: In function ‘test_adaptive_radix_tree_structure’:
/home/muxin/IdeaProjects/aili/test/art_test.c:171:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key1, 5, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:172:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key2, 6, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:173:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key3, 7, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:197:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key1, 7, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:198:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key2, 6, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
/home/muxin/IdeaProjects/aili/test/art_test.c:199:3: error: too many arguments to function ‘adaptive_radix_tree_put’
adaptive_radix_tree_put(art, key3, 5, 0);
^~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/muxin/IdeaProjects/aili/test/art_test.c:18:0:
/home/muxin/IdeaProjects/aili/test/../art/art.h:16:5: note: declared here
int adaptive_radix_tree_put(adaptive_radix_tree *art, const void *key, size_t len);
^~~~~~~~~~~~~~~~~~~~~~~
CMakeFiles/aili.dir/build.make:335: recipe for target 'CMakeFiles/aili.dir/test/mass_node_test.c.o' failed
make[3]: *** [CMakeFiles/aili.dir/test/mass_node_test.c.o] Error 1
CMakeFiles/aili.dir/build.make:309: recipe for target 'CMakeFiles/aili.dir/test/art_test.c.o' failed
make[3]: *** [CMakeFiles/aili.dir/test/art_test.c.o] Error 1
/home/muxin/IdeaProjects/aili/test/mass_tree_test.c: In function ‘test_mass_tree’:
/home/muxin/IdeaProjects/aili/test/mass_tree_test.c:135:3: warning: implicit declaration of function ‘mass_tree_validate’; did you mean ‘mass_tree_get’? [-Wimplicit-function-declaration]
mass_tree_validate(mt);
^~~~~~~~~~~~~~~~~~
mass_tree_get
CMakeFiles/Makefile2:75: recipe for target 'CMakeFiles/aili.dir/all' failed
make[2]: *** [CMakeFiles/aili.dir/all] Error 2
CMakeFiles/Makefile2:82: recipe for target 'CMakeFiles/aili.dir/rule' failed
make[1]: *** [CMakeFiles/aili.dir/rule] Error 2
Makefile:118: recipe for target 'aili' failed
make: *** [aili] Error 2

ArtNode256的count值可能溢出

ArtNode256结点孩子数可能为0到256，用8bit表示count值刚好表示不下吧？

BLinkTree 正确性的疑问

请问插入的时候，为什么不会发生这样的情况：

树的各个节点均已满，一个线程P企图插入，它下降到了某个叶节点，此时另外几个线程也开始插入，它们下降了不同的叶节点然后插入结束，导致旧root分裂，新root生成，并且导致旧root所在那一层再次满了，这时线程P向上回溯，回溯到旧root后依然要进行分裂，可是线程P并不知道旧root的parent（也就是新root）是谁。

您的代码中，下面这行代码

aili/blink/blink_tree.c

Line 133 in a2f3225

assert(blink_node_is_root(left));

似乎表明这样的情况并不会发生，如果您还记得这篇paper的话，可以解答一下吗？谢谢！

 char *key = (*alloc)(16); 

 key[0] = 8; 

 *(uint64_t *)(key + 1)= rng_next(&r); 

 assert(adaptive_radix_tree_put(ta->tree.art, (const void *)(key + 1), 8) == 0);

这里插入为什么要malloc16个byte，同时空出第一个byte，是有什么concern吗

Nits

aili/mass/mass_tree.c

Lines 261 to 293 in a2f3225

 switch ((uint64_t)ret) { 

 case 0: // key existed 

 mass_node_unlock(n); 

 return 0; 

 case 1: // key inserted 

 mass_node_unlock(n); 

 return 1; 

 case -1: { // need to create a deeper layer 

 create_new_layer(n, key, len, off, val); 

 mass_node_unlock(n); 

 return 1; 

 } 

 case -2: { // mass_node is full, need to split and promote 

 uint64_t fence = 0; 

 mass_node *n1 = mass_node_split(n, &fence); 

 assert(fence); 

 uint64_t cur = get_next_keyslice(key, len, off); 

 // equal is not possible 

 if (mass_compare_key(cur, fence) < 0) 

 assert((uint64_t)border_mass_node_insert(n, key, len, off, val, 0 /* is_link */) == 1); 

 else 

 assert((uint64_t)border_mass_node_insert(n1, key, len, off, val, 0 /* is_link */) == 1); 

 mass_tree_promote_split_mass_node(mt, n, fence, n1); 

 return 1; 

 } 

 default: // need to go to a deeper layer 

 mass_node_unlock(n); 

 r = (mass_node *)ret; 

 // if we need to advance to next layer, then key offset will not exceed key length 

 off += sizeof(uint64_t); 

 goto again; 

 }

这里ret是uint_64类型, case里面包含-1和-2，不合适

Node48 add_child

https://github.com/UncP/aili/blob/master/art/art_node.c#L395
这里是不是写错了？ add_child 增加节点应该是往 children pointers 的末尾append一个 node. 所以不应该是 an48->child[get_count(version)] = child; 才对吧？

uncp / aili Goto Github PK

aili's People

Contributors

Stargazers

Watchers

Forkers

aili's Issues

mass_node_get_version 只使用了 acquire, 是否存在风险?

Delete operation on Multi ART

请问新手如何调试与执行源码? makefile 执行是成功的. 在clion 上运行报的错如下.

ArtNode256的count值可能溢出

BLinkTree 正确性的疑问

palm tree在多线程情况下会出现卡死的情况

想问一下在b-link tree里面 mapping_array这部分的作用

art插入的疑问

Nits

Node48 add_child

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent

	char key = (alloc)(16);
	key[0] = 8;
	(uint64_t )(key + 1)= rng_next(&r);
	assert(adaptive_radix_tree_put(ta->tree.art, (const void *)(key + 1), 8) == 0);

	switch ((uint64_t)ret) {
	case 0: // key existed
	mass_node_unlock(n);
	return 0;
	case 1: // key inserted
	mass_node_unlock(n);
	return 1;
	case -1: { // need to create a deeper layer
	create_new_layer(n, key, len, off, val);
	mass_node_unlock(n);
	return 1;
	}
	case -2: { // mass_node is full, need to split and promote
	uint64_t fence = 0;
	mass_node *n1 = mass_node_split(n, &fence);
	assert(fence);
	uint64_t cur = get_next_keyslice(key, len, off);
	// equal is not possible
	if (mass_compare_key(cur, fence) < 0)
	assert((uint64_t)border_mass_node_insert(n, key, len, off, val, 0 /* is_link */) == 1);
	else
	assert((uint64_t)border_mass_node_insert(n1, key, len, off, val, 0 /* is_link */) == 1);

	mass_tree_promote_split_mass_node(mt, n, fence, n1);
	return 1;
	}
	default: // need to go to a deeper layer
	mass_node_unlock(n);
	r = (mass_node *)ret;
	// if we need to advance to next layer, then key offset will not exceed key length
	off += sizeof(uint64_t);
	goto again;
	}