架构设计中的循环引用

引用计数是一种经典的内存管理垃圾回收机制，但它最明显的副作用就是循环引用，导致内存泄漏。循环引用其实是一个闭环。

闭环是什么

从图论的角度来说，闭环，其实就是一个有向有环图。图中的顶点表示一个对象，每一条边表示对象之间的关系。若图中的每条边都是有方向的，则称为有向图。
如果图中存在一个顶点，从该顶点出发经过若干条边可以回到该点，则这个图是一个有向有环图。这个环我们暂且称它为闭环。

除了引用计数内存管理，在工程应用中，很多地方都存在着闭环的影子：

• 死锁，是指多个进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。死锁的形成必然存在着资源的环形链，这也是一个闭环。

闭环的检测

判断一个有向图是否存在环，有多种算法。

• 算法1:环中的每个顶点的度都是>=2，基于此可以找到环：
  1. 求出图中所有顶点的度，
  2. 删除图中所有度<=1的顶点以及与该顶点相关的边，把与这些边相关的顶点的度减一
  3. 如果还有度<=1的顶点重复步骤2
  4. 最后如果还存在未被删除的顶点，则表示有环；否则没有环

• 算法2: 利用深度优先搜索遍历该图，如果在遍历的过程中，发现某个节点有一条边指向同一棵生成树上的祖先节点，则表示存在环：

  
  dfs.jpg

facebook最近刚开源的FBRetainCycleDetector就是使用深度优先搜索来检测iOS应用在运行时是否存在循环应用。它利用ivar layout 找出对象所引用的所有对象，并用有向图表示，节点就是对象，边就是对象之间的引用。然后使用深度优先搜索，检测出其中是否存在循环引用，精简过的核心代码如下：

[stack addObject:wrappedObject];
while ([stack count] > 0) {
  @autoreleasepool {
    FBNodeEnumerator *top = [stack lastObject];
    [objectsOnPath addObject:top];
    FBNodeEnumerator *firstAdjacent = [top nextObject];
    if (firstAdjacent) {
      BOOL shouldPushToStack = NO;
      if ([objectsOnPath containsObject:firstAdjacent]) {
       // 如果路径中存在访问过的点，说明存在环，表明有内存泄漏隐患
      } else {
        shouldPushToStack = YES;
      }
      if (shouldPushToStack) {
          [stack addObject:firstAdjacent];
      }
    } else {
      [stack removeLastObject];
      [objectsOnPath removeObject:top];      
    }
  }
}

架构设计应避免闭环

架构的设计当中，大部分场景下， 应当避免闭环。模块之间的关系应当是线性的，或者树状的，而不应该是存在闭环的复杂网络状。树状的结构意味着系统的层次清晰，模块职责明确。典型的在线服务三层架构图如下：

arch_3.jpg

这就是一个很简单的树状图，模块之间划分得非常清晰。流行的MVC和MVVP其实也是帮我们梳理这种层次结构。MVC三者的引用关系如下（Controller引用View和Model，View引用Model）：

mvc.jpg
这是一个无环图，假设在图中增加一条从Model到Controller的边，就形成了一个闭环。如果你的Model层或者View层代码中出现了类似这样的代码：import "Controller.h"，请再审视一遍你的代码设计。
模块之间相互引用，意味着模块之间耦合性高，设计的抽象还不够。在日常的实践开发，这种相互引用的引入往往是无心而隐蔽的。但是随着代码库的日益庞大，模块之间的联系日益增多，一旦这种循环引用多了，整个系统的结构将变得无比复杂，杂乱无章。最终系统的结构会变成这样：
messy_arch.jpg
这个系统一旦出现bug，将牵一发而动全身，改bug就是拆了东墙补西墙，久而久之，再也没有人改动这坨代码，项目华丽地走上了推倒重写之路。

那么如何找到模块之间是否存在闭环呢？我们可以将问题简化成为文件之间是否存在循环import。这样可以写一个检测脚本，协助定位和清理模块之间的关系。

1. 遍历项目中所有的文件，看每个文件import了哪些其他的文件。每个文件就是一个节点，每次import表示一次引用关系，从而建立一条有向边。
2. 建立好有向图之后，使用深度优先搜索算法检测图中是否存在环，若存在，将引用路径打印出来。

<b>让代码库变得庞大并不难，难的是在业务发展过程中，一直保持架构的简单。牢记KISS原则：Keep It Simple and Stupid.</b>