并行数据结构-p-tree

并行数据结构

并行数据结构的几个概念

non-blocking

一个线程被挂起或中断不会导致其他线程执行被block
lock-free

保证整个系统的执行进度是不断推进的
wait-free

保证每个线程的执行进度是不断推进的

通常需要做到lock-free,不要求wait-free(较难实现，性能较差)

lock-free:

auto expected = x.load();
do {
     bool ok = x.compare_exchange_strong(expected, new_value);
} while(!ok)
//compare_exchange_strong 解释。
// if true, 则x和expected相等，使用new_value替换x的值
//if false, 则x和expected不相等，并expected会被修改成x的值

（否则需要spin lock）

仅仅使用串行数据结构+锁远远不能达到要求（还可能导致死锁）

涉及的数据结构

CSDS（并行查找数据结构）

链表，跳表，哈希表
主要实现：查找，插入，删除
- 查找：遍历
- 插入删除，先找到位置，再进行操作
关键
- 速度快，避免耗时操作（写操作），等待和重试
- 细粒度，修改尽量设计较小的范围，需要用锁：细粒度锁

非查找数据结构：

队列，栈，竞争点都在头/尾，队尾竞争激烈

并行数据结构设计

单链表

串行数据结构的单链表的增删改查都相对容易，在并发中容易遇到的问题：

删除和插入，插入和插入，删除和删除，都会引发问题
内存管理问题：对已删除的节点，需要释放内存，但如果其他线程持有在该点的操作，不能立即释放
ABA问题：插入某节点时，该节点的前驱刚被释放且空间被分配到另一个节点（内存复用），导致链表乱序
线性化问题：遍历链表得到的遍历结果不一定是历史存在过的链表版本数据（解决方案：不提供遍历操作即可，只提供插入删除和查找，这三个操作可以是线性化的）

解决方案（大部分的问题都是删除操作、释放空间产生的）

节点不删除，先标记再集中GC，GC加锁
- s删除导致的GC会出现短暂阻塞，出现长尾
节点删除但不释放内存
- 内存会不断增长
节点删除并释放内存
- 使用引用计数的方式管理链表内存释放，每次遍历对节点进行引用计数（对性能影响较大）

插入删除冲突的解决

关键在于：被删除节点的next不能被改变，可以将被删除节点的next添加标记符1（next&1），阻止其他线程改变该节点的值。

bool del_node(ListNode* pre_del_node) {
        ListNode* del_node = pre_del_node->next.load();
        //1. 标记del_node->next;
        ListNode* excepted_next = del_node->next.load();
        //2. next指针添加标记位
        if (!del_node->next->compare_exchange_strong(excepted_next, excepted_next&1)) {
            return false;
        }
        //3. 修改前驱节点next指针
        if(!pre_del_node->next.compare_exchange_strong(del_node, del_node->next)) {
            return false;
        }       
        return true;
}

如果修改不成功将退出，插入也类似。

compare_exchange_strong

ABA问题的解决

使用tagged pointer解决（在指针上带上版本号进行管理）

使用指针的最高16尾存储指针的版本信息，每次指针内容发生变化时改变版本号（指针一般64位，CPU内存远远不及）参考

内存管理问题解决

风险指针Hazard Pointers

原理：

每个线程把自己访问的节点的地址放在全局可见的地方，这样的全局可见的指针被称为风险指针，访问完节点后清除自己的风险指针
每个线程维护一个freelist：
- 当某个结点A被删除后，放到freelist里
- 检查其他线程的风险指针，看看有没有和A相同的地址，如果没有其他节点正在访问A，A可以被释放

优化：风险指针自身也要保证线程安全，需要高效实现——shared_ptr

使用shared-ptr组织链表，每个ListNode*都是智能指针。

存在的问题：

遍历链表时，每走过一个节点，该节点引用数+1，离开时引用数-1，原子操作比较慢，因此搜索速度慢，不满足CSDS的原则
采用递归方式释放整个链表，或者链表中的一段，可能会导致栈溢出
如果一个线程获得一个结点的引用计数，但被卡住了一段时间之后才会释放这个计数，该节点所有的后继节点都会被延迟释放

并行扩张树P-tree

SunYihan Parallel Ordered Sets Using Join 2016,PAM: Parallel Augmented Maps 2018,Join-based Parallel Balanced Binary Trees 2019

对于存储在磁盘上的上万个图节点，在做图算法时，对图进行虚拟化。虚拟图可以使用如下两种方式来动态构建：1. “中断”式的构建；2. 多线程的构建，即存在一个扫描线程，后台扫描满足要求的节点，加载到虚拟图中。

所谓“中断”式的构建，是指要遍历到的下一个节点不在虚拟图上，触发“中断”，开始从磁盘加载一批新的图节点进来。而多线程构建方式，则是动态卸载已经访问过的节点，同时动态加载新的节点。为了提高对虚拟图读写的并发性，就需要使用一种数据结构：Parrellel Auguemented Map.

两个基本函数：

join(l,k,R)，表示以k为根节点连接的左右两棵子树LR

expose(T)表示以树T的根k作为分裂节点，将树分裂为L，k，R并返回

相关函数：

split ()以k为节点划分树，返回左子树，右子树和是否null

split(T,k)
    	if T = null 
            (null,false,null)
        else (L,m,R)=expose(T)
        	if k = m 
            	(L,true,R)
            else if k < m
                (LL,b,LR)=split(L,k)
                (LL,b,join(LR,m,R))
            else 
                (RL,b,RR)=split(R,k)
                (join(L,m,RL),b,RR)

insert（）插入一个新节点

insert(T,k)
 	(TL,m,TR)=split(T,k)
    join(TL,k,TR)

splitlast() 移除T最大值的节点（即右子树的最下方的值，返回移除后的平衡树和移除的节点）

splitlast(T)
    (L,k,R)=expose(T)
    if R=null
        (L,k)
    else
        (T',k')=splitLast(R)
        (join(L,k,T'),k')

join2() 将两棵树拼接起来，根节点为左子树的最大根

join2(TL,TR)
    if TL = null
        TR
    else
       	(TL',k)=splitlast(TL)
       	join(TL',k,TR)

delete()从T中删除一个节点k

delete(T,k)
    (TL,m,TR)=split(T,k)
    join2(TL,TR)

以上的几个函数未涉及并发，在以上的基础上，使用并发进行实现以下函数：(用来处理节点过多的情况，提高效率)

其中，||表示左右两边的函数可以并发进行

union()将两个树合并成一个新的树

union(T1,T2)
    if T1 = null 
        T2
    else if T2 = null
        T1
    else
        (L2,k,R2)=expose(T2)
        (L1,m,R1)=spilt(T1,k)
       	TL=union(L1,L2)|| TR=union(R1,R2)
        join(TL,k,TR)

difference(T1,T2) 将T1中包含T2的节点删除，可以用来批量删除节点

difference(T1,T2)
    if T1=null
        null
    else if T2=null
        T1
    else
        (L2,k,R2)=expose(T2)
        (L1,m,R2)=split(T1,k)
        T1=difference(L1,L2) || T2=difference(R1,R2)
        join2(T1,TR)