- 叶节点最多存放15个 key，permutation（8字节，64位）分为16份，1份表示 key 数量，另外表示每个 key 在节点中的位置，key 的插入是顺序插入 - lock： - 节点锁：只有一个线程可以对当前节点进行写操作； 解决write-write竞争 - 乐观并发控制： - 利用节点 version，解决 read-write 竞争  - 读开始和结束后获取当前节点的最新 version，来判断读过程中是否发送了写入（insert 或 分裂） - 插入key前，设置 version 的 inserting 标记，完后后 vinsert + 1 - 分裂之前，设置 version 的 splitting 标记；完成后 vsplit + 1 - 加锁顺序：  -  同一 layer 的节点：从下往上  - 不同 layer：从上到下  -  节点的 parent 指针：受 parent 节点的 lock 保护  -  节点的 prev 指针：受 prev 节点的 lock 保护 - layer 新 root 节点的更新是懒惰的，即等后面读到该 layer 的旧 root 节点时发现不是 root 时再更新 ，避免实时更新需要锁上一层 layer - version是32位  - keylenx 128代表layer，64代表是后缀  - modestate 0是insert，1是remove，  2是deleted_layer - leaf叶节点删除逻辑： 如果自己是leaf的链表头 则不删除自己 > Masstree readers treat splits and inserts differently. Inserts retry locally, while splits require retrying from the root > > Masstree must therefore update the version counter’s vinsert field when removed slots are reused. > > Border nodes, unlike interior nodes, can handle splits using their links.  Splits and deletes can modify highkey(n), but lowkey(n) remains constant over n’s lifetime. - 写锁： spin lock - node的parent指针由node的parent的锁保护； 这样分裂的时候，可以直接操作它的children的parent的指针而不用获取children的锁 - 分裂和删除需要一个writer同时获取多个锁； - 比如分裂时，需要同时获取自己的锁、parent的锁和新兄弟节点的锁； - border node的prev指针有previous sibling的锁保护； - 更新操作： - 使用aligned write instructions来原子地更新value； - 因此update不需要更新version，也不会引起reader重试； - 但是writer在所有并发reader完成检查前，不能删除old values；  - gc问题（epoch-based reclamation）  - permutation代表了正确的key顺序和当前keys的数量； - Get操作不会写共享的数据结构，因此不会 dirty shared cache lines - Border insert原子地修改permutation，没有key rearrangement，没有version increment。 写kv 跟更新permutation之间需要加fence； - 重试逻辑：insert locally retry； split retry from root； - 最开始有一个border node，来存放leftmost keys，除非整个树被删除，否则该node一直在。 - Leftmost node 的 low key 是 -∞ - Rightmost node 的 high key 是 +∞