Git 是纯函数式数据结构

2021-02

最近一直在学习 Git，但是一直不知道它的原理是什么，直到看到国外的一个大牛的博客。这篇博文给了我很大的启发，所以翻译过来和大家分享。

原文链接

虽然近几年像 Git 这种分布式版本管理系统很火，但它看起来还是比像 SVN 这样的集中式版本控制系统复杂。我猜这可能是因为我们总是会把二者相比较：在 SVN 中这样做，但在 Git 中却需要那样做。

我认为 Git 的真实含义应该是一个纯粹的函数式据结构。所以，如果你在学习熟练地使用 Git，那你也就是在学习处理数据结构。那么我们就先来探讨一下纯函数式数据结构。

不变性

函数式编程中一个很重要的概念就是不变性( immutablity )。就是说一个对象的状态在构造完成以后不可改变

比如有一个典型列表 [3,2,1]。如果这个列表是可变的，我们可以在他的头部插入一个元素4，即 [4,3,2,1]。现在它变成了一个全新的列表，之前的那个列表丢失了。如果此时其他的小伙伴也在操作这个列表，他们便会不幸地得到一个异常.

而函数式编程便不会发生这种情况。因为当我们在列表头部插入 4 时，它会创建一个新列表 [4,3,2,1]，而不会修改原始列表。所以两个列表会同时存在。

可是如果我们每次迭代这个列表都会生成一个全新的列表，这样不仅浪费，而且效率很低啊。

实际上，函数式数据结构的效率在很大程度上取决于对它们执行的操作。对于刚刚那种（单链接）列表，如果我们只是想在它的头部插入数据，完全可以用更有效率的方法：

  +---+    +---+    +---+    +---+
  | 4 +--->+ 3 +--->+ 2 +--->+ 1 |
  +---+    +---+    +---+    +---+
    |        |
new list  original

我们将新元素 4 放在一个新节点中，并将它指向列表的其余部分。你看，之前的列表得到了复用，之前我们发现的那些问题全都解决了。

可是如果其他人想要在 [3,2,1] 之前插入 9 呢？当然也可以用这个方法啦：

              +---+      +---+    +---+    +---+
new list 1 -> | 4 +---+->+ 3 +--->+ 2 +--->+ 1 |
              +---+  /   +---+    +---+    +---+
                    /      |
              +---+/    original
new list 2 -> | 9 +
              +---+

我们当然也可以将这样的元素存储为可变列表（non-immutable list），但是这很危险。假如我们更新列表中的元素 [3]，那部分可是公共的，你的修改会影响到他人，那些需要 [9,3,2,1] 列表的人可不喜欢你这么干。

但是......如果我确实需要将元素 3 变成 5，该怎么办？还是用老方法啊：

                +---+    +---+
updated list -> | 4 +--->+ 5 +
                +---+    +---+\    
                               \    
                +---+    +---+  \ +-+-+    +---+
  new list 1 -> | 4 +--->+ 3 +--->+ 2 +--->+ 1 |
                +---+  / +---+    +---+    +---+
                      /    |
                +---+/  original
  new list 2 -> | 9 +
                +---+

你看，它现在可以表示四个列表：

  • 最初的的列表 [3,2,1]
  • list 1 [4,3,2,1]
  • list 2 [9,3,2,1]
  • list 2 [4,5,2,1]

纯函数数据结构在多线程编程中非常有用，因为来自不同线程的更改不会相互干扰。

和 Git 的关系

可是，我们之前讨论的不变性和 Git 的版本控制功能有什么关系呢？那我们就一起来对比以下它们俩的异同吧。

  • 在版本控制系统中我们想要完成的是：
    1. 使用新版本的文件更新我们的代码仓管库，旧版本文件也要保留。
    2. 当你和你的小伙伴门在同一个个代码库上进行协作时，不会以不可预测的方式相互干扰。
  • 不可变的数据结可以：
    1. 更新数据结构的同时保留老的数据结构。
    2. 在一个线程中对数据结构更改不会影响到其他线程

怎么样，是不是觉得它们俩很像。

事实上，我门甚至可以说 Git 基本上就是是一个纯粹的函数式数据结构，让你使用命令行客户端在其上执行操作。

要完成这个类比，我们需要把上面的数字替换成 Commit。

Git commints 是工作历史中特定时间点的全部工作状态的独立副本，即工作目录的完整快照。我们可以把示例中的链表看成是 Git 中的历史记录。

比如说我们有一个代码仓库，它的 master 分支包含三个按顺序的 commit : A，B，C。也就是我们让 Git 在整个开发过程中完整地存储了我们的工作目录三次。

这就是历史纪录啊，用图说话：

+---+    +---+    +---+
+ C +--->+ B +--->+ A |
+---+    +---+    +---+
  |
master

Git commit

当我们执行 commit 的时候，这就可以类比成我们将一个数据提交到了这个历史纪录的开头。而 Git 甚至用 HEAD 代表当前的 commit。

+---+    +---+    +---+    +---+
+ D +--->+ C +--->+ B +--->+ A |
+---+    +---+    +---+    +---+
  |        |
master   master^

当 Git 执行 commit 时，它会移动当前分支指针，将 master 指向 [D,C,B,A]。我们仍然
可以通过名称 master^ 指向 [C,B,A]，并且不会影响到其他人。

Git amend

如果你使用过 Git，你或许知道可以使用 commit --amend 来更新最近一次的 commit ，但你真的可以更新 commit 吗？

事实上，你不能。Git 只是创建一个新的 commit （下图中 E）并将 branch 指针指向它。你仍然可以使用 git reflog 命令看到它，并且可以通过它的 hash value 来引用（假设他的 hash value 是 ef4d34）。

          +---+    +---+    +---+    +---+
ef4d34 -> | D +--+>+ C +--->+ B +--->+ A |
          +---+ /  +---+    +---+    +---+
               /     |
          +---+    master^
master -> | E |
          +---+

Git branch

如你所见，每次执行 commit --amend 时，实际上都会创建一个新分支。分支的唯一功能就是给我们能引用的 commit 起个名字。我们甚至可以使用 git checkout -b branch ef3d34 命令在那个被丢弃的 commit ef3d34 上创建一个新分支。

          +---+    +---+    +---+    +---+
branch -> | D +--+>+ C +--->+ B +--->+ A |
          +---+ /  +---+    +---+    +---+
               /     |
          +---+  master^
master -> | E |
          +---+

通常，我们通过为当前的工作流 HEAD 创建一个新名称来在 Git 中进行分支，但是如果你将 Git 理解为一个函数式数据结构，你就可以随心所欲地在这个树状图上的任何一个 commit 上创建分支了。

Git rebase

当我们在上边的示例列表中更新一个节点时,我们必须把列表中的每个节点添加到在更新后的元素之前（在我们的示例中，这是单个节点 4，但可以是任意数量的节点）。在 Git 中，这称为重新提交（replaying commits），执行此操作的命令称为变基（rebase）。要更新旧提交，我们添加 -i 参数来执行一个在 Git 中称被叫做「交互式 rebase」的操作。

比如说，我们想要用一个新的 commit message 来更新 commit C。我们需要切换到 commit D，然后输入 git rebase -i c 。

> git checkout D
> git rebase -i C

在窗口中包含一下内容：

pick cd3ff32 <C's commit message>
pick a65a671 <D's commit message>

# some helpful comments from git

如果我们想编辑 cimmit C，Git 允许我们在重放后续提交之前编辑该提交。

edit cd3ff32 <C's commit message>
pick a65a671 <D's commit message>

当我们保存文件并关闭它时，Git 会开始一个 rebase 。它会在 commit C 停止，这样我们可以修改它。

Stopped at cd3ff32... <C's commit message>
You can amend the commit now, with

        git commit --amend

Once you are satisfied with your changes, run

        git rebase --continue

窗口中的消息说明了一切。我们可以根据需要随意编辑 commit 后我们调用 commit --amend 创建更新的 commit，然后使用「继续 rebase」指令： git rebase --continue。
当我们选择命令时，其余的 commit 将一个接一个地重放 pick（除非最终发生了合并冲突，在这种情况下 Git 会停止并在你修复它之后才能继续）。我们的完整存储库现在就像下边这样。

          +---+    +---+
rebased ->| D'+--->+ C'+
          +---+    +---+
                         
          +---+    +---+    +---+    +---+
branch -> | D +--+>+ C +--->+ B +--->+ A |
          +---+ /  +---+    +---+    +---+
               /     |
          +---+  master^
master -> | E |
          +---+

我希望上面的图会让你觉得熟悉。希望你也能明白为什么 Git 的 rebase 命令会创建所有新的 commit。Git 是一个函数式数据结构，它不允许更改现有的 commit。

由于 rebase 引入了一个新的提交链，所以我们一定希望能够对这个新链的外观进行必要的且任意的控制。我们可以用 rebase -i 来重新排序，压缩或删除提交，或者随意拉入新的提交，比如把一个 commit 分成几部分，或者从存储仓库中的其他位置开始（使用 --onto 参数）。

Git merge

现在我们来谈谈合并把。Git 允许我们将两个分支合并为一个

        +---+
      --+ X |
+---+/  +---+
| M |
+---+   +---+
      --+ Y |
        +---+

合并給我们的模型带来了更多的复杂性。它把我们的历史从一个树状图变成了一个非循环图。这并没有太大的改变，但请注意，虽然 rebase 听起来复杂，但只有 merge 命令带来了额外的概念复杂性。

可以通过在新方向上应用新提交来理解 Rebase 。合并是一种根本不同的操作。一个数据结构，一个你可以将两个部分像这样组合成数据结构一个特殊的名称：我们称它 confluently persistent。（函数式数据结构也叫 persistent。我避免使用
这个术语，所以你不要将它与像物理光盘这样的持久性媒体上的存储概念混淆。）

结论

Git可以看成是一个相当简单的函数式数据结构。与其把Git描述成一个版本控制系统，不如说版本控制是“不变性”数据结构的一个自然属性。。我认为以这种方式谈论 Git 能更准确地传达 Git 的简单性和威力，而不是与集中式版本控制系统相比能完成什么。

如果以这种方式来思考的话，Git 在概念上比 SVN, CVS 等要简单。 大家认为 Git 更加复杂可能是因为这种复杂性能支持更有趣的 workflow。

如果你曾经觉得 Git 令人生畏，那请记住它的简单结构，以及在函数式结构中，
插入其中的任何东西都不会真正丢失，并且可以被恢复。（检查你的 reflog）

目录