动态可扩展哈希表
每个线程都可能申请多个元数据锁，对于分配出去的每个元数据锁，AntDB-M都通过可扩展哈希表存放管理。一般可扩展的哈希表，会通过锁技术，并另外一次分配一个完整的哈希表空间来对哈希表空间进行扩展，同时还伴随着表中数据的迁移。表空间的整体扩展、锁、以及数据的迁移这些操作都会造成内存空间的浪费、访问延迟等性能问题。AntDB-M通过可扩展的哈希表，同时解决了内存浪费、访问延迟两大问题。1、哈希表结构
1）Split-Ordered_Lists
AntDB-M的哈希表的动态扩展能力来自Split-Ordered_Lists算法。该算法不同于通常的在哈希表的桶(bucket)间移动元素，而是在一个无锁的链表中移动桶，从而做到无锁、可扩展。该技术是如何做到高性能的同时，又节省内存空间呢？
2）无锁链表
Split-Ordered_Lists算法将所有数据保存在一个无锁的链表当中，该链表按照锁KEY计算出哈希值计算出在哈希表中的位置，链表按照位置先后顺序排列。后文无锁链表均指代该链表。3）如何确定先后位置
将哈希值按位逆序后，从小到大进行排序，即可保证按照在哈希表中的位置排序。这样既可以快速排序，也不必花费额外内存空间记录位置信息。为什么逆序排序就可以做到呢？哈希表按照当前大小的2倍进行扩展，首个大小为1。当前空间大小是2的i次方，那么一个数据的Hash值按2的i次方取模后的值决定了数据在哈希表中的位置（桶）。即哈希值的二进制的后i个位，决定了数据在哈希表中的位置。在哈希表扩展到2的i+1次方后，哈希值的二进制的后i+1位则起决定作用。也即哈希表的每次扩展，只是多了1位来影响数据在Hash表中的位置。由于影响排序位置的是哈希值的二进制的后几位，那么将值按位逆序后，可以非常轻松的实现排序，值越小，越靠前。并且在哈希空间扩展后，其排序后相对位置保持不变。
4）哈希扩展
由于无锁链表是按哈希位置先后排列，并且在哈希空间扩展后其相对位置保持不变，因此，哈希扩展要做的仅仅是对哈希空间大小原子更新为原来的2倍，不需要迁移数据。
5）虚拟节点
哈希表每个桶的首个节点是一个虚拟节点，该桶下的数据节点都按哈希值按位逆序后，按从小到大的顺序排在该节点之后，下个虚拟节点之前。如果哈希值相同，则对key进行比较大小。有了该虚拟节点，一个新的数据插入时，就以该虚拟节点为起点，向后遍历无锁链表找到位置即可插入。将哈希值逆序后最后一位置为1，用来标识该节点是虚拟节点。虚拟节点和无锁链表按顺序排列，可以确保节点的快速查找、插入、删除。2、高效动态数组
可扩展哈希表的实现有两部分，其一是上文说的无锁链表，另外一部分就是动态数组。动态数组的下标就是哈希值按照表空间大小取模后的值。动态数组以多级形式管理内存，整个数组分为4级，每级又依次分为0,1,2,3级，每个叶子级都可以存放256个元素，这样数组每级依次可以存放256,256*256,256*256*256,256*256*256*256个元素。
总共可以存储4,311,810,304个元素，足够满足锁资源个数的需求。
1）按需分配
根据数组下标来访问时，根据下标计算出所在的等级，按需分配出该级的内存，减少内存空间的浪费。内存的分配通过CAS操作来避免对同一个位置重复分配。
2）内存申请批量化
每次申请可以容纳256个元素的内存块，减少内存申请次数带来的的系统开销，并降低对内存资源的浪费。
3）空闲内存栈
不使用的内存暂不还给操作系统，而是存放到空闲内存栈中，后续重复使用，从而减少系统因为频繁地申请和释放内存所带来的开销。
无锁链表安全问题
对于无锁链表，经过哈希计算出的位置可能是锁链表中的任意位置，即对无锁链表的查询、插入、删除的位置是不确定的。这就要确保查询时，正在遍历的节点不能被删除，否则就会出现内存访问异常。插入和删除节点的前后节点不能被删除，否则更新失败，甚至出现ABA问题，导致链表被破坏。AntDB-M是通过什么机制来确保无锁链表的快速更新的呢？
1. 安全机制
AntDB-M通过两个机制来解决这两个问题：1）3阶段删除；2）PIN机制。1）3阶段删除
阶段1：标记删除
对要删除的节点通过CAS操作标记为已经删除。标识方式为当前节点中的下个节点指针的最低位置为1。因为所有节点对象都是从内存堆上申请的，边界必定对齐，即最低位必定为0。在查询链表时，将下个节点指针最低位调整为0即可正常遍历链表。
阶段2：队列中移除
任意线程遇到标记为删除的节点都可以进行删除操作。该删除操作是将节点从链表中移除，放入回收当前线程的回收队列中，并未做实际的节点内存释放。每个线程都会有一个节点回收队列，该队列实际只有一个队列指针，节点从无锁链表删除时，回收队列指针指向当前新删除的对象，该节点对象中的队列指针指向上个被删除对象，这样当前线程所有删除节点构成一个回收队列，并且无需开辟单独的队列空间。该队列为当前线程私有，可以不加锁安全操作。这里从队列删除中删除需要可靠的安全措施，避免删除过程破坏链表，该措施便是CAS操作，以及后文介绍的PIN机制，具体过程在后文介绍。
阶段3：对象内存释放
当一个线程回收队列中的对象超过10个时再触发真正的删除。在删除时，需要遍历当前所有线程，判断是否有线程正在访问该对象。通过后文将要介绍的PIN机制来进行判断。只有没有线程在访问时，该对象的内存才会被真正释放。
2）PIN机制
节点的删除、插入前都要先查找到该节点，节点的查找过程逻辑相同，包括节点查询本身。每个线程都会分配三个PIN，三个PIN分别代表当前访问节点、前置节点、后置节点。每个线程都会记录自己正在访问的节点，当一个节点被记录到PIN中时，该节点可以被标识删除，但是不会真的被释放。
a.查找节点
从bucket所在的节点开始遍历，由于bucket所在首个节点是虚拟节点，该节点在首次访问时创建，不会被删除，因此访问该节点对象一定是安全的。遍历过程先将前置节点记录到PIN[2], 该节点记录到PIN[1]，后置节点记录到PIN[0]。由于是无锁操作，可能在记录前节点已经被删除了，因此，记录后要检查记录前后对应节点是否有变化，有变化则重新记录变化后的节点，并对该过程循环处理，直到节点没有发生变更。然后根据哈希值以及KEY大小判断是否找到对应节点。
b.值相等
说明找到已经存在节点。要删除，则可以标记删除。要插入，说明插入冲突。
c.值比当前节点大
说明可以在该节点前插入。插入时通过CAS进行原子更新。由于前置节点被PIN住，因此不会被删除。但是有可能别的线程已经抢先在该位置做了插入，因此失败时要重新查找位置进行插入。
d.值比当前节点小
2.为何安全
1）读取安全
综合3阶段删除、以及PIN机制，确保正在访问节点，以及该节点的前置、后继节点都不会被从内存释放。可以安全的对节点进行读取。
2）插入安全
在前置与当前节点间一旦出现插入、删除操作后会出现两种结果。
a.中间多了新节点
因为当前节点的地址是唯一的，如果有新节点，则前置节点指向下个节点的指针必定变更，新节点进行插入的CAS操作会失败，此时重新进行位置查找进行插入操作。
b.和现状一样
可以认为没有发生过变更，不存在ABA的问题，此时可以成功的进行插入CAS操作。
3）删除安全
a.标记删除
只是修改当前节点的下个节点指针最后一位，因此前置节点的变化不会对标记删除操作产生影响，主要影响是其后置节点的变化。- 后置节点被标记删除，但依然在链表当中，不产生影响。
- 后置节点被从链表删除，则当前节点的下个节点指针会被修改，标记删除CAS操作会失败，进入下次查找过程。
b.链表中删除
要删除节点， 就要确保读取到当前节点的前置、后置节点都不能有变更。节点查找过程中，遇到标记删除的节点一定会尝试删除该节点，直到自己，或者其他线程将该节点删除，才会继续查找下个节点。因此，当前节点前后肯定不会插入新节点。前置节点被标识删除，会修改前置节点下个节点指针，因此当前节点删除CAS操作会失败，进入下次查找过程。当前线程能发现当前节点要被删除，说明查询过程中前置节点肯定没有标识删除，如果其他线程在当前线程查询后将前置节点标记删除，并执行删除动作，那么当前线程执行CAS操作一定失败，进行入下次查找过程。
同前置节点被从链表删除一个道理，因为当前节点就是后置节点的前置节点。后置节点能被删除，则说明当前节点的删除标记一定晚于后置节点的删除标记，后续节点的前置节点发生了变更，后置节点删除一定失败。无锁空闲栈
前文提到AntDB-M为每个客户端连接分配了1个PIN对象，该对象有一个唯一编号，从1开始递增。这些对象在前文提到的动态数组中维护。通过唯一编号可以高效的定位到PIN对象。客户端的连接可能不停地变化，因此对于已经释放的PIN对象通过无锁对象栈进行高效管理。空闲栈其实只有一个栈顶指针，即PIN对象的编号，即在动态数组中的下标。动态数组中的每个PIN对象上也带有一个指针，在PIN对象放入空闲栈时，用来指向下个空闲对象。通过栈顶指针即可将所有空闲对象构成一个空闲栈，并不需要额外地建立一个栈空间。AntDB-M对空闲栈的管理采用了无锁技术，通过原子变量和循环CAS技术来确保多个客户端连接对空闲栈的并发、高效、安全地更新。
栈更新安全问题
对于栈顶元素的更新，使用CAS技术，必须要解决ABA问题，因为ABA问题会造成客户端连接获取到错误的PINS对象，甚至破坏空闲栈。AntDB-M通过对栈顶指针增加版本号来解决ABA问题。栈顶指针为32位无符号整数，其中低16位为每个客户端连接分配的空间编号，高16位为版本号。对于空闲元素栈的每次放入、弹出，都会将栈顶指针中版本号递增，16位用完会循环从0重新开始。16位的版本号可以保障同时有65536个并发而不会产生版本号相同的问题，可以确保安全。总结
AntDB-M综合扩展动态哈希表、PIN机制、CAS机制、逆序排序、内存对齐、无锁链表、无锁栈等多种技术，给频繁访问的元数据对象锁提供了无锁、低内存的高效锁资源，为数据库的高性能提供了有力支撑。AntDB数据库始于2008年，在运营商的核心系统上，服务国内24个省市自治区的数亿用户，具备高性能、弹性扩展、高可靠等产品特性，峰值每秒可处理百万笔通信核心交易，保障系统持续稳定运行超十年，并在通信、金融、交通、能源、物联网等行业成功商用落地。「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文章的来源（墨天轮），文章链接，文章作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
