[讨论]“锁”还是“无锁”

同不知道pthread能不能在win上用，但是不是可以写个包裹函数，用包裹函数屏蔽底层的不一致呢？ 锁的话，就是粗锁和细锁的区别吧，无论如何肯定要加锁的。算法盲，不懂B+ tree。 菜鸟路过。。。

吐槽：上次搞btrfs然后就陷入了“策略”与“机制”的争论中。没人说的清优化应该在哪一层做。日。 不理解：get_node不算一种操作吗？那么操作是指什么呢？

wrapper是个好方法 目前打算只对整个node加锁，不打算细化到某个key的程度，但不排除将来有这样的需求。现在纠结的问题是这锁该是由下层实现呢（在->insert()中实现，树中不显式调用lock()之类的函数），还是由树本身实现（在树中使用tree_lock_node()，或者提供一个->lock_node()的接口）。 如果以后需要细化到某个key的lock，那可能接口就变成这样（参数越来越多，自己都晕了）： [quote] struct tree_node* (*get_node)(struct tree_root *root, struct tree_node *parent, le32 idx, int lock_type, void *context); [/quote] 不知道有没有好的方法？ 【 在 zxsword 的大作中提到: 】 : 同不知道pthread能不能在win上用，但是不是可以写个包裹函数，用包裹函数屏蔽底层的不一致呢？ : 锁的话，就是粗锁和细锁的区别吧，无论如何肯定要加锁的。算法盲，不懂B+ tree。 : 菜鸟路过。。。

【 在 wks 的大作中提到: 】 : 吐槽：上次搞btrfs然后就陷入了“策略”与“机制”的争论中。没人说的清优化应该在哪一层做。日。 : 不理解：get_node不算一种操作吗？那么操作是指什么呢？ ~~~~~~~~~~~~~~~~~~~~~~不理解问题的意思…… get_node()是取一个节点。目前的打算是，因为树的key和value的大小和数量都是由用户指定的，所以索引的存放方式和node的大小也由用户指定。当需要某个节点时调用->get_node()，用户填充node里面的信息，返回一个struct tree_node

原文提到： 1 在->get_node()等函数***中***实现，也就是目前的方法。这样整个tree看起来像一个单线程的程序，但是需要保证->get_node()返回的节点是可用的（可读或可写，若不行则等待或cow），具体节点内存分配也下放到下一层了。 2 在***操作***前加上锁的操作，内存节点的分配和回收都在本层实现： 不理解：1. get_node()“中”，具体是什么地方呢？是不是“进入get_node的时候加锁，离开get_node的时候解锁”？ 2. “操作”指的是哪些操作？这一条与第一条区别开，这个“操作”应该指的不是get_node。insert算不算一种“操作”？ 3. 目前是实现一个纯内存的数据结构吗？（是不是用u32比lt32更好一些呢？）

【 在 wks 的大作中提到: 】 : 原文提到： : 1 在->get_node()等函数***中***实现，也就是目前的方法。这样整个tree看起来像一个单线程的程序，但是需要保证->get_node()返回的节点是可用的（可读或可写，若不行则等待或cow），具体节点内存分配也下放到下一层了。 : 2 在***操作***前加上锁的操作，内存节点的分配和回收都在本层实现： : 不理解：1. get_node()“中”，具体是什么地方呢？是不是“进入get_node的时候加锁，离开get_node的时候解锁”？ ->get_node()是指获取树节点的函数，而->insert()函数则是插入用户自定义数据的操作。如下图，->get_node()是获取tree.idx里的节点，而->insert()则是插入words.idx里的操作。 [quote] +-----------------------------+ | user-defined methods | v | (user data) => (hash key, data) | +-~-~-~-~-~-~-~-~-~-~-~-~--~-~-~-~-~/~-~-~-~-~-~-~-~-~-~-~-~-~-~-~~-~-~-+ | | tree.idx: / | | | / | | | +-----+-----------+----------+-------------+-----+ | | | | ... | child (i) | hash (i) | child (i+1) | ... | | | | +-----+-----------+----------+-------------+-----+ | | | / \ | | | +-----+--------+------+-----+ +-----+--------+------+-----+ | | | | ... | offset | hash | ... | -> | ... | offset | hash | ... | -> ... | | | +-----+--------+------+-----+ +-----+--------+------+-----+ | | | / | | +-~-~-~-~-~-~-~-~-~-~-~-~--~-~-~-~-~-~-~-~-~/~-~-~-~-~-~-~-~-~-~-~~-~-~-+ | / | +--------+-----+----------+------+---------+-----+ | words.idx: | header | ... | word_len | word | doc_idx | ... | | +--------+-----+----------+------+---------+-----+ | / <-------+ [/quote] ->get_node()是加锁，另有一个->put_node()是解锁。或者这样说，->get_node()返回一个可用的节点，而->put_node()则告诉下层节点已经用完了。一个可能的实现： [quote] static struct bpt_node* tree_idx_get_node(struct bptree_root *root, struct bpt_node *parent, le32 idx, void *context) { struct bpt_node *node; node = mem_alloc(sizeof(struct bpt_node)); read(fd_tree_idx, node, sizeof(struct bpt_node)); /* lock */ return node; } static void tree_idx_put_node(struct bptree_root *root, struct bpt_node *node, le32 idx, void *context) { /* unlock */ mem_free(node, sizeof(struct bpt_node)); } [/quote] 例如一个tree_lookup()函数： [quote] int bptree_lookup(struct bptree_root *root, le32 key, const void *second_key, void *buf, int len) { int pos, ret, flag = 1; struct bpt_node *n; struct bpt_path *path = NULL, *p; n = root->bops->get_root(root, context); if (n == NULL) return -1; if (n->height > 0) { flag = 0; do { p = mem_alloc(sizeof(struct bpt_path)); p->node = n; p->next = path; path = p; if (lookup_key(n, key, &pos) < 0 || pos == n->nr_key) path->pos = pos; else path->pos = pos + 1; n = root->bops->get_node(root, n, n->idx[path->pos], context); } while (n->height > 0); } ret = -1; if (lookup_key(n, key, &pos) == 0) ret = root->bops->lookup(n->idx[pos], second_key, buf, len); if (flag == 0) { root->bops->put_node(root, n, path->node->idx[path->pos], context); while (path->next != NULL) { p = path->next; root->bops->put_node(root, path->node, p->node->idx[p->pos], context); mem_free(path, sizeof(struct bpt_path)); path = p; } n = path->node; mem_free(path, sizeof(struct bpt_path)); } root->bops->put_root(n, context); return ret; } [/quote] : 2. “操作”指的是哪些操作？这一条与第一条区别开，这个“操作”应该指的不是get_node。insert算不算一种“操作”？ 都算操作，只是->get_node()是对tree index（图中的tree.idx）的操作，而->insert()是对user-defined data（图中的words.idx）的操作，见主贴tree_operations的注释 : 3. 目前是实现一个纯内存的数据结构吗？（是不是用u32比lt32更好一些呢？） 不算是纯内存数据结构，tree index也保存在磁盘上，只是tree node的存储方法也需要用户定义。目前的实现tree_node的内存和磁盘格式相同，就先写成这样了

算法盲不懂b+tree实现，不过pthread倒是有在win环境的实现，可以去http://sourceware.org/pthreads-win32/ 看看