Git:纯函数式数据结构

Posted on | Edited on | In |

看到一篇有趣的文章《Git is a purely functional data structure》，作者：Philip Nilsson。它从函数式数据结构的角度讲解了Git的原理，把 Git 的 commit，branch 等操作和数据的不变性做了类比。本文将这篇文章搬过来，做个记录。

不变性

函数式数据层结构本质上是不可变的数据结构，也就是具有不变性（immutable），它的值不会发生变化。然而函数式数据结构又支持比如插入、删除等操作，这些操作会创建一个全新的更新过的数据结构，而原始数据保持不变。

比如有个list 是 [3,2,1]，如果它是可变的，那我们就可以向头部插入一个元素4, 从而让这个列表变成 [4,3,2,1]。之前的 list 对我们来说丢失了，我们只能看到新的列表。在函数式编程中，这是不应该发生的，当我们插入一个元素4的时候， 并不会修改老的列表，相反，我们会创建一个全新的列表：
[4,3,2,1]， 老的列表 [3,2,1] 依然存在。

那这种“不变性”有什么好处呢？很重要的一点就是线程安全，一个线程对数据的修改不会影响到另外一个线程，这样就不需要加锁的操作了。但是每次添加/删除一个元素就要创建一个新的列表出来，这样做是很低效和浪费内存的。那就做点优化，对原列表进行复用，比如：

老的列表和新的列表复用了内存中的元素，但是从外界的使用者看来，这是两个不同的列表。此时，如果线程再次在老列表 [3,2,1] 之前插入新的元素 9 ，怎么处理？ 同样，还是可以复用：

如果我想把 new list 1 中的元素 3 更新成元素 5， 这就有点难办了，因为它会影响到两个新的列表，new list 1 和 new list 2。 没办法，只有把元素 copy 一下了：

经过以上若干次操作，形成了四个列表：

  • 老的列表： [3,2,1]
  • new list 1: [4,3,2,1]
  • new list 2: [9,3,2,1]
  • new list 3: [4,5,2,1]

这四个列表对外界而言是完全独立的，只不过内部的数据是复用的。

Git 与 不变性

函数式结构的不变性和 Git 有什么关系？对比下函数式数据结构不变性和版本控制：

版本控制的目的：

  1. 用新版本的文件来更老版本文件，老版本文件还要保留。
  2. 大家在同一个仓库中同时操作的时候，需要互不干涉。

不可变的数据结构能让我们：

  1. 保持老的数据结构不变的情况下，更新数据结构
  2. 一个线程对数据结构的更改不会影响另外一个线程

两者是不是很像？所以可以确切的说，Git 是一个纯函数式的数据结构，允许你在命令行使用命令进行各种”不变性”操作。

为了更好的进行类比，需要将上面例子中的数字换成 commit。Git 中的一个 commit 是对某个历史时间点完整的工作状态的一次拷贝；是你当前工作路径的一个完整“快照”。

比如一个仓库的 master 分支按时间先后顺序有 A、B、C 三次 commit，所以 Git 对我们工作路径下的全部状态进行存储了三次。看下图：

Git commit

如果我们再执行一次 commit，就变成下图这样：

Git 将master指针指向 [D,C,B,A]，老的 history 指针（即 master^）还在，仍然指向 [C,B,A]。我的这次提交不会影响其他人，因为老的 mater^ 依然不变。

Git amend

如果你用过Git的话，你也许知道可以使用 commit –amend 来更新最近一次的 Commit (图 D), 但是你真的把那个 Commit (图 D) 给更新了吗？ 实际上并没有，Git只是创建了一个新的 Commit（下图中的E），并且让 master 指针指向 E 而已。 通过git reflog 命令，你依然能看到修改前的那个 Commit （图 D）（假设它的hash value 是 33b90b7）。

Git branch

正如你在上面看到的，每次你使用 commit –amend ， 你实际上创建了一个新的分支！分支实际上就是给一个我们想引用的 commit 起了个名字而已。我们甚至可以使用那个“被替换掉的”，“废弃的” Commit (33b90b7)来创建一个分支，比如起个名字叫 “dev”：

1
git checkout -b mybranch 33b90b7

所以，只要你理解了Git 是函数式数据结构的本质，你就可以从任何 commit 上来创建分支了。原文还讲了Rebase/Merge和不变性的比较，我觉得就不是很贴切了，这里不再展开，感兴趣的同学可以看下原文。

与其把Git描述成一个版本控制系统，不如说版本控制是“不变性”数据结构的一个自然属性。如果以这种方式来思考的话，Git在概念上比SVN, CVS等要简单。 大家认为Git更加复杂可能是因为这种复杂性能支持更有趣的workflow。