DataCross

A Passively Synchronizing Eventual-Consistency Storage

不依赖中心的数据同步服务，要同步数据可以将数据目录设置到同步盘

选型

用 sqlite 持久化数据，用日志跟踪最近操作

数据冲突

在我们多机写, 多机读的场景下, 特制定以下允许冲突的存储模式：

每个机器一个 wal 文件，该文件有与机器名相同的文件名，但还有一个唯一 id 号

每个机器只写自己的 wal 文件，每个 key 从版本 0 开始，每次操作也分配一个版本号，为基于的版本号+1，每次操作还有一个全局唯一的 id 号

如果同一个 key 从某一次操作开始，出现了多个版本号序列，就说明该 key 冲突，需要用户手动选择保留哪个版本，此时，就在解决冲突的机器执行操作：保留版本x(x为操作 id 号)

如果重复解决冲突, 即同时执行了保留版本x1, 和保留版本x2, 那该将 key 退回到冲突状态, 直到冲突解决, 所有机器同步到最新数据

持久化

持久化即将日志文件持久化至 sqlite db 文件

类 git 方式

每个机器维护独立的目录，里面包含 sqlite 数据文件和日志，实例启动时，读取自己的目录，然后尝试合并其他机器的数据文件

合并完成，写入sqlite，记录合并时所有机器版本号

合并过程中：

• 无冲突，直接写入
• 有冲突，保留自己的修改，保留其他机器的修改

不立即解决冲突：

写入冲突的版本，本机版本依然可以操作，也可以随时解决冲突

添加机器：

创建空目录，做一次合并即可

其他: 一个表一个文件, 字段级别操作

再其他: 每个参与者都要公开已同步日志位置, 便于其他参与者剪裁自己的日志(取所有参与者最久远同步位置作为剪裁终点) 2. 让用户确认所有参与者列表以确保没有未上线的?

日志格式可以有多种, 定义日志接口

有机器永久离线，导致其他机器无法剪裁日志怎么办？ 用户可以管理（删除）机器，或者离线时间过长的机器自动降级为单向同步（可以同步给其他机器，不可以从其他机器同步）

日志组织为多个小文件，提高可靠性，也方便剪裁

不定期创造日志文件同步条件 日志文件同步条件是什么

处理冲突，用deny代替accept

每个key，记录创建者

用户可以指定计算机名，程序要验证数据文件属于该计算机

已同步到的每个参与者最后一条记录的时间

每个key都是一棵树： 每个key的修改记录链接其上一条记录，所有修改记录构成一棵树，每个叶子节点就形成一个版本

每个机器都可以基于自身的同步情况，建设这棵树，在客观上以及对于每个机器最终，都能得到一棵完整的树

sqlite存的是本机器跟踪的分叉最新值

一条日志允许多个操作，以便一次性（原子地）删除多条分叉

问题：
    同步时，base结点不存在？
    日志如何剪裁？
    
    sqlite保存目前已知的叶子情况，并且标注哪个版本是本机跟踪的
    
上次同步开始,轮流遍历日志建树
用map重建树，找出上次同步产生的key列表

尽力同步，有可能因为一个key卡死

标记本节点为部分同步状态
机器永久离线？那就会卡死同步
sqlite记录的是上次同步所有叶子节点

正式同步方案：
有一个机器一直不同步？就剪裁不了日志

向用户提示每个peer的最后同步内容

---

树方案最终版：

日志：

日志顺序存储对每个key的操作，每一个操作的格式如下：

操作类型，key，value，gid，上一条日志gid，上一条日志运行完的值，seq，产生本操作机器名，产生上一操作机器名

操作类型有：modify，del，discard，也可以增加其他类型

• key即操作的对象，value为对应的值
• 每条日志会生成一个全局唯一的gid，并且会链接到上一条日志
• 一个key刚创建，第一条日志seq为0，链接到它的日志seq=seq+1

每一条日志可以记录多个操作

单机情况，每次对key操作，都基于并链接到上一条最新日志（如果有的话），该key所有日志形成一条链，顺序运行这条链所有日志即可得出key最新状态（值）

多机情况，每个机器都可以对key操作，并可以链接到上一条日志（不一定是最新的），客观上，每个机器对key操作都是在新增节点，所有节点形成一棵树（或多棵树），从该树根节点出发运行至该树每个叶子节点都得出该key的一个冲突版本

多机情况，如果树有分叉且值不同，可以手动解决冲突，方法是在不想要的分支末端增加discard操作，直至这棵树只剩下一个有效分支

小节：

每个机器都有自己独立的日志文件，日志中包含操作节点，所有机器的日志记录的所有节点客观上可以构建出多棵树（每个key对应一棵树或多棵树），而创建节点这个操作本身是不会有冲突的，因为为一个父节点创建多少子节点都可以，因此，在日志层面，多机不会有冲突

任意机器可以获得其他机器创建的节点信息，取决于获得信息的完整度，它可以还原出多棵完整的树或部分树，但最终，它一定可以获取目前为止，所有节点的信息（亦即当前客观的、完整的树），从而达到最终一致性

sqlite：

sqlite用于存储本机当前已知多个key部分树（或完整树）所有叶子节点的值，存储的字段有：

key，value，seq，gid，prev_gid，is_deleted, is_discarded，is_main，machine_id, prev_machine_id

• key和树是一对多的，代表这是哪个树叶子节点的值
• value即对应的值
• seq叶子节点日志的seq
• gid为叶子节点日志的gid
• prev_gid即叶子节点父节点gid
• is_deleted代表分支已删除
• is_discarded代表该叶子节点无效（在解决冲突时执行了discard操作）
• is_main表示这是本机跟踪的分支
• machine_id表示产生本节点的机器名
• prev_machine_id表示产生父节点的机器名

当sqlite已存储当前已知部分树或完整树的叶子节点的值，这些树完整的结构（中间节点是怎么样的）就不重要了，实质上就是，旧的操作日志就不重要了

sqlite中还记录上一次同步其他机器的情况，记录其他每个机器的：机器名-上次同步最后一条日志的gid

同步时，从每台机器上次同步的最后一条日志开始，遍历新的日志，扩展本机已知的树，该过程会参考sqlite中存储的所有叶子节点，将新的操作日志分为以下四种情况：

1. seq==0: 表示要创建一棵新树
2. seq<=某key所有叶子节点的seq，说明是该key的又一分叉节点
   1. 如果日志的上一日志机器名为本机，将该节点当成新的叶子节点
   2. 否则，说明该节点父节点不可知，最终会知道
3. seq==某叶子节点seq+1，分两种情况
   1. prev_gid==叶子节点gid，说明是更新的叶子节点
   2. prev_gid!=叶子节点gid，说明该节点父节点还不可知，最终会知道
4. seq>所有叶子节点的seq+1，说明是叶子节点的未来节点，所属日志暂停遍历，直到获得叶子节点到未来节点的中间节点

日志遍历完成，sqlite中部分key的叶子节点更新为新叶子节点，或创建了新key，有的日志运行到了最新位置，有的由于存在中间节点未知的未来节点，尚未运行到最新位置，等待下次同步，但最终，如果所有机器网络正常，所有机器日志在本机都会运行到最新位置

最后，记录一下每个机器日志已运行的位置情况

部分树的还原：

树方案本质是多机在不断扩展树的森林，可以把同步定义为根据已知日志对森林的部分还原

为了节约空间，在还原时，我们不存储树的中间节点，只存储叶子节点，这样还可以保存中间状态，不用每次都从根节点开始还原

首先，改造日志，每条操作记录自己是本日志的第几条操作（即编号），以及额外记录父操作的创建机器和编号

还原算法如下：

顺序运行所有已知日志

• 对于一个结点，如果父节点id为空，说明是根节点，直接创建
• 否则，父节点id不为空，分两种情况：
  • 父节点存在，替换父节点
  • 父节点不存在，又分两种情况：
    • 父节点编号>所属日志已运行位置（编号），说明父节点还未创建，暂停本日志的执行，切换到下一日志
      • 未创建的父节点一定会被创建的证明：假设现在所有日志已经同步到事实的最新，由于父节点还未创建是卡住日志执行的唯一原因，被卡住日志外的日志不可能都因父节点未创建而卡住，而它们也不与本日志产生死锁，因此被卡住日志外的日志总会有日志能够运行，直到卡住本日志的“未创建父节点”被创建出来
    • 父节点编号<=所属日志已运行编号，说明父节点被其他同父节点替换，本节点可以在没有父节点的情况下创建

日志运行过程是否会产生死锁：

死锁的条件为，有任意两个日志A、B，A日志当前节点a1依赖B日志未运行节点b2，B日志当前节点b1依赖A日志未运行节点a2

这是不可能的，如果A日志当前节点a1依赖B日志未运行节点b2，就说明A机器创建当前节点a1时，B机器已创建未运行节点b2，说明B机器在创建那个节点（b2）前已经创建b1，在创建过程中成功引用了A机器未创建节点a2

多机解决冲突：

一般的冲突的处理办法为：用户选择保留的分支，系统为其他所有分支加上discard节点，表示放弃

可能会出现多机同时解决冲突（即解决冲突操作本身冲突了），如果多机保留的是相同分支，那最终，这个分支不变，其他分支分别加上多个discard节点

如果多机保留的是相异分支，那最终，保留的分支分别至少有一个discard节点（也有可能没有），其他分支有多个discard节点，结果为所有的分支被删除

在这个过程中，不影响哪些从来没被同步到的分支，每台机器解决冲突只解决了已知的冲突，全局可能仍然有冲突存在

如果多机保留的是相异分支，希望最终保留的分支都存在，其他分支被放弃，可以怎么做呢？

给用户选择保留的分支添加空操作，其他分支添加discard操作，这样保留的分支至少有一个空分支和多个（也可能没有）discard分支，实现了最终的保留

但用户选择保留相同的分支则会产生冲突，这种情况可以考虑加入自动冲突解决算法：

由于用户选择保留相同的分支，则会创建该分支多个空操作，这些操作 seq 相同，value相同，每个机器对于seq相同，value相同的多个分支，自动放弃 gid 比较小的那些，由于全局一定存在 gid 最大的分支，所以多机同时操作时，全局 gid 最大的那一个不会被任何机器discard

日志的剪裁：

每台机器同步其他机器的情况（其他机器名--日志位置）都向其他机器公开，假设本机要剪裁日志，统计其他机器记录的本机日志已同步位置，找出最老的那一条，这之前的日志就可以删除了。

is_main的管理：

不能依赖日志执行顺序确定is_main，因为多次运行日志的顺序是不一样的，导致单机每次运行看到的键-值不断变化。而且容易卡死在死分支（某分支成为main后，不再更新）

那么就需要一种确定的“确定main的算法”，保证每次运行的结果相同

这种算法保证最终is_main每次运行都相同，就说明在运行过程中，需要经常修改is_main

于是，不适合将is_main存储在主要的数据结构中

拟创建单独的表确定main分支，每条主表key对应一条记录，记录一些信息

算法现确定为： 非本机key，以seq的大小确定main分支，seq最大的分支将成为本机的main分支，seq相同就以machine_id的大小确定

本机创建过、修改过的分支，直接成为main分支，除非分支被删除、被放弃，如果分支被放弃就找其他分支seq最大的，作为main分支

如果main分支被放弃，就找其他分支seq最大的，作为main分支

本机创建、修改而成为main分支的“main”属性可以继承，多个分支继承main？本机修改次数最多的，成为main分支，如果一样多，最终叶子节点seq大的成为main分支

简化一下，每个结点记录一下本机修改次数就可以了

其他：

能否发展为通用分布式存储 可以用gorm的migrate？

降低数据同步频率和数据量