从分布式数据库看路由协议

最近在写Ruta的论文，突然想到从分布式数据库的视角来看待路由协议是一件非常有趣的事情。路由协议设计是一件非常有趣的事情，只是过去了30年了，互联网依旧还是OSPF、ISIS、BGP.. 最大的创新也无非是在BGP上扩展点字段支持EVPN、LS、FlowSpec或者ISIS扩展成OTV而已,昨天还看到个要在BGP里面传延迟信息的Performance Routing的RFC…

BGP导致的事故一起接一起,影响力越来越大,而这个影响着整个互联网的协议一开始只是一张餐巾纸上的作画,分布式数据库过去十年获得了突飞猛进的发展，是否到了可以重新设计路由协议的时候了呢？

回到过去那个年代,这种设计也无可厚非,可靠传输只有TCP可以选,所以把BGP状态机和TCP状态机耦合在了一起, 由于不想让路由协议在收敛过程中占用带宽,所有的协议都是尽量基于最小bits定义的紧耦合封装,最后在路由器控制面处理时也带来了大量消息串行化和解串行化的负担.而后面由于网络设备增多,又有了路由反射器的设计,一切的发展都是在特定的年代用最小的代价解决了特定的问题.

路由协议一致性的根源

计算机网络的书很多，但是却很少有人想路由协议为什么要这样设计的？回到30年前，带宽非常有限，而网络中的设备数量也非常有限。因此路由协议通常只是一些非常简单的同步操作即可。正是由于当年的网络芯片(NP or ASIC)和带宽的限制，所以IP网络路由选择了基于目的地址查表的方式(Dst based Routing),因此避免环路的最简单方法就是所有的转发表保持一致性。这便是很多路由协议需要保持一致性的根源。

在一致性的处理上, 当然有所不同. 知道CAP理论的人都清楚, 一致性(Consistency)、可用性(Availability)、分区容错性(Partition Tolerence)三者不可兼得的说法。而针对网络和路由协议，Partition Tolerence和Availability 本身就是一个非常让人纠结的问题。特别是到了SDN年代，例如Facebook一个简单的DNS故障就可以导致控制器失效进而整个网络瘫痪。接下来我们看看当年的一些路由协议的设计是如何取舍的。

分库(Sharding)

如果一个数据库要保证一致性同时提供足够的分区容错性, 并且还要完成快速收敛等一系列需求，那么最简单的办法就是把某些网络划分成一个区域，然后多个区域拼接。也就是您看到的OSPF、ISIS都提供的Area机制，或者BGP的AS、联盟机制。通过区域的划分还可以降低SPF计算的复杂度。

当然针对网络工程师对于分库的更直观解释是：隐藏子域的拓扑结构和隔离故障信息.这样就降低了数据库同步的通信量。

弱化一致性

事实上你们可以看到很多路由协议设计之初就是为了弱化一致性带来的影响，例如OSPF只需要满足LSDB的最终一致性(eventually consistency)，它通过Flooding机制来获得这样的最终一致性。

但是注意在SDN环境里，却由于控制器的中心化强化了一致性的要求，后面再单独讲

弱化可用性

如果从单体系统来看，每个路由器本身有一个路由信息数据库(RIB)，然后会根据本地算法来构建转发数据库(FIB)。因此网络设备必须要维持本地RIB可用性，并即时根据数据面状态变化而同步信息并即时进行计算。当然工程设计的时候对可用性也有了妥协，例如SPF计算时采用牺牲可用性的方式，在数据库同步完成后再触发SPF计算，当然后期还有一些ispf的算法避免非影响LSA链路的计算，本质上都是在弱化RIB的可用性要求。

提高分区容错性

Segment Routing发明本质上是开始于一个路由协议的研究， 如何在OSPF上提高分区容错性。当然针对LAN的广播链路类型采用DR/BDR这种Leader选举的功能是一方面。而在SR以前出现过一个IP-FRR的东西，即链路或节点发生失效时，如何通过本地计算备用路径绕开故障点，这种技术当时被称为Loop-Free-Alternative(LFA). 但是基于目的地址的一致性转发过程中，它是不完备的，因此只能覆盖到90%以上的场景。通过嵌入一部分节点ID进行转发，才能最终实现Topology Independent LFA，也就是最终Segment Routing的样子。

另一个方式是增加新的心跳线，例如思科的在nexus上实现VPC时， 为了防止Brain-Split的操作就是在对分区容错性影响较大的链路上增加备份来防止它发生Active-Active的情况。

SDN之殇

渣一直以来对很多SDN的设计都在吐槽，中心化的控制平面看上去易于管理了，但是带来的问题就更多了。很简单的一句话就是：你永远无法设计一个良好的具有分区容错性的SDN控制器 因为这是一个先有鸡还是先有蛋的问题。更学术的说法是”Controller Placement problem,CPP), 而SDN搞了那么多年了，却发现网络设备的控制面处理器从MIPS换成了Xeon，内存加到了几十个G，还跑着完全的Linux操作系统和各种容器，和当初设备不需要控制面的SDN设计完全背道而驰了…

回到SDN之初，OpenFlow本身就是一个强化一致性要求的设计，规模一大就出事了，同步本身带来的故障使得人们不得不放弃它。

然后利用控制器计算路径并下发路径的中心化视角，当年思科自己做IWAN也吃雷了。记得那段时间研发团队一起商量在失效情况下的防环机制搞了一大堆专利出来，但是最终还是收购了Viptela采用分布式算路的机制解决了这个问题。而这个问题的价值是6亿美金。你不得不在整个工业界做一件事情的时候，跳出来想想这又有什么不对。

另一个问题是配置，网络工程师在开发Yang Model的时候最大的问题就是没有了解MVCC的原理，而是简单的照搬以往的配置方式抽象。而配置本身要求是Sequential Consistency，Yang Model又没有定义相应的Reverse操作，只是简单的做了一些基本的类似于TCC的操作但做的不彻底，经常网络出现故障是在commit以后观测到的，要回退配置就成了一个非常难的操作了。而路由器无论是控制面和转发面都是基于命令式的操作，回退并不是重新刷一个配置那么简单的事情。

还有就是IPAM这类的操作到了控制器上，无形的要求了整个控制器需要实现Strictly Consistency，因为一个IP地址无法分配给两个主机。

当然在我们谈到微分段时还有Group-Policy，这些Group-Policy的同步和多设备处理上也会带来强一致性的需求。

而针对SDWAN这个问题更加明显，在数据中心内部Network Partition的问题并不是太严重，基本上通过ECMP都可以实现控制器可达。而SDWAN动不动就是一个数据中心掉线，然后控制器掉了如何HA的问题，分布式控制器又面临着数据同步如何防止脑裂的问题…

解决问题之道

解决这个问题本身不能单纯的说控制面协议选什么、转发面协议选什么。并不是你选择了SegmentRouting就能解决很多问题，它也需要控制面的配合，而控制面本身的很多路由协议也到了不改不行的时候。

而这些问题的解法在于巧妙的组合随路信息(In-band)和带外信息(Out-of-band).在一些要求强一致性的地方解耦，也就是说对于数据库操作的transaction进行巧妙的拆分使得整个系统提高可用性，例如思科Viptela采用的分布式路径计算方式。所以我看到集中式路径计算这事就头皮发麻，特别是某运营商提的SRv6 SDWAN白皮书….

解耦的方式则是来自于范畴论，通过对路由协议所携带的信息进行分析，你会发现承载的路由和nexthop和linkstate之间会有巧妙的组合。通过范畴论的方法把他们之间的对象关系搞清楚后，抽像成对象之间的态射，并映射到相应的K-V pair上就很好的解决了问题。而BGP最大的失误就在这里，耦合了TCP状态机，又耦合了Linkstate(AS-PATH)，还耦合了Nexthop，自然整个收敛就变得非常缓慢了。