README

此代码最初是为了实现 有界计数器 CRDT 的原型。

有界计数器

关于有界计数器的一些文章

• 基于状态的 CRDT：有界计数器
• 有界计数器：以高可用性维护数字不变性

有界计数器需要 pn_counter crdt，而pn_counter crdt 需要 g_counter crdt，因此也实现了这些类型。

树

接下来，添加了一个 crdt 树算法的原型。

参考

• 用于复制树和分布式文件系统的可高度可用移动操作
• CRDT：难点部分
• YouTube 视频：CRDT：难点部分

安装

您需要 PHP 7.0+ 和 composer。

在 Ubuntu 上

apt-get install php composer

安装为独立仓库并运行测试

$ git clone https://github.com/dan-da/crdt-php && cd crdt-php
$ composer install

在自己的项目中作为库使用

$ mkdir -p <project> && cd <project>
$ composer require dan-da/crdt-php:dev-master

测试

对于 b_counter，进入 tests 目录并运行 ./tester.php，如下所示

$ ./tester.php 
Running tests in b_counter...
Running tests in g_counter...
Running tests in pn_counter...
Running tests in v_clock...
[pass] 1 == 1  |  b_counter: replica_1->value() == 1
[pass] 7 != 1  |  b_counter: replica_0->value() != replica_1->value()  [before merge]
[pass] 7 != 2  |  b_counter: replica_0->value() != replica_2->value()  [before merge]
[pass] 1 != 2  |  b_counter: replica_1->value() != replica_2->value()  [before merge]
[pass] 10 == 10  |  b_counter: replicas 0 and 1 equal  [after merge]
[pass] 10 == 10  |  b_counter: replicas 0 and 2 equal  [after merge]
[pass] 10 == 10  |  b_counter: replica_0->value() == 10  [after merge]
[pass] 10 == 10  |  g_counter: replicas 0 and 1 equal
[pass] 10 == 10  |  g_counter: replicas 0 and 2 equal
[pass] 10 == 10  |  g_counter: replica_0->value() == 10
[pass] 6 == 6  |  pn_counter: replicas 0 and 1 equal
[pass] 6 == 6  |  pn_counter: replicas 0 and 2 equal
[pass] 6 == 6  |  pn_counter: replica_0->value() == 6
[pass] object == object  |  vclock: merge
[pass] 5 == 5  |  vclock: merge_less_left(5)
[pass] 6 == 6  |  vclock: merge_less_left(6)
[pass] 7 == 7  |  vclock: merge_less_left(7)
[pass] 5 == 5  |  vclock: merge_less_right(5)
[pass] 6 == 6  |  vclock: merge_less_right(6)
[pass] 7 == 7  |  vclock: merge_less_right(7)
[pass] 1 == 1  |  vclock: merge_same_id(1)
[pass] 1 == 1  |  vclock: merge_same_id(2)
[pass] 1 == 1  |  vclock: merge_same_id(3)
[pass] 1 == 1  |  vclock: ordering. a dominates
[pass] 1 == 1  |  vclock: ordering. a dominates
[pass] 1 == 1  |  vclock: ordering. a dominates
[pass] 1 == 1  |  vclock: ordering. b dominates
[pass] 1 == 1  |  vclock: ordering. b dominates
[pass] 1 == 1  |  vclock: ordering. b dominates
[pass] 1 == 1  |  vclock: ordering. concurrent
[pass] 1 == 1  |  vclock: ordering. concurrent
[pass] 1 == 1  |  vclock: ordering. concurrent
[pass] 1 == 1  |  vclock: ordering. a dominates
[pass] 1 == 1  |  vclock: ordering. a dominates
[pass] 1 == 1  |  vclock: ordering. a dominates
[pass] 1 == 1  |  vclock: ordering. b dominates
[pass] 1 == 1  |  vclock: ordering. b dominates
[pass] 1 == 1  |  vclock: ordering. b dominates
[pass] 1 == 1  |  vclock: ordering. equal
[pass] 1 == 1  |  vclock: ordering. equal
[pass] 1 == 1  |  vclock: ordering. equal


41 tests passed.
0 tests failed.

对于 tree，进入 src 目录并运行 php tree.php，如下所示

$ php tree.php Usage: tree.php <test>

<test> can be any of:
  test_concurrent_moves
  test_concurrent_moves_cycle
  test_apply_ops_random_order</test>

$ php tree.php test_concurrent_moves

Initial tree state on both replicas

- /
  - root
    - a
    - b
    - c

replica_1 tree after move

- /
  - root
    - b
      - a
    - c

replica_2 tree after move

- /
  - root
    - b
    - c
      - a

replica_1 state matches replica_2 state after each merges other's change. conflict resolved!

--replica_1 --

- /
  - root
    - b
    - c
      - a

--replica_2 --

- /
  - root
    - b
    - c
      - a