Dylan's Blog

增量处理引擎

上图是简化过的增量梳理引擎的拓扑，指向关系代表数据的依赖关系。总体逻辑是ovn-controller根据南向数据库和本机ovsdb中的数据生成ovs的物理流表。

lflow_output负责翻译南向数据库中的逻辑流表，pflow_output负责处理本机端口到逻辑端口的映射关系。具体地，lflow生成物理流表8-32、40-49、66-67，pflow生成物理流表0、37、38、39、64、65。每张物理流表的具体功能见「流表结构」。

记录Raft算法中的细节：

leader选举随机超时机制

大于两个candidate参与选举时可能导致选票分散，没有candidate获得大多数选票。condidate上会出现选举超时的情况，candidate会增加自己的term并开启新一轮选举。

如果每个candidate的超时时间一致，新一轮选举依旧会出现投票分散的情况，因此每个candidate的超时时间会在一个范围内随机选取。

日志匹配性

不同节点上的日志条目若拥有相同的term和index，那该条目及其之前的条目都是一致的。

首先给定的term和index的条目只会由唯一确定的leader下发，且leader不会覆盖或删除自己的条目，因此该条目在各节点上都一致。此外下发请求会包含leader中上一个条目的term和index，只有其与follower本地的上一个条目一致时才会被接收，因此之前的条目也都是一致的。

通过比较term和index，follower发现本地条目与下发请求不一致时会拒绝请求。leader会维护每个follower的nextIndex，下发请求被拒绝时会回退nextIndex，并下发上一个条目，重复此过程直到某个条目被follower接收。follower接收后会使用下发的条目覆盖本地条目，因此系统能够自动收敛。

日志提交方案

假设先前term中有一条目已在多数节点上被存储，若leader在得知此信息后将该条目提交，仍有可能出现该提交条目未来被覆盖的情况，导致不同节点的执行结果不一致。

为保证安全性，Raft只会提交当前term中被多数节点存储的term，并利用日志匹配性推断先前的条目均被多数节点存储。该策略牺牲了一定的实时性，推迟了先前term中条目的提交时间。

背景

使用 OSPF/ECMP 组织多个 DPVS 节点，不同节点上的 RS 创建顺序可能不一致，DPVS 一致性哈希在不同的节点能否将流量路由到相同的 RS？当有RS创建和删除时，流量的目的RS是否保持一致？

结论

假设已有 n 个 $RS$，$RS_1,…RS_n$，权重分别为 $w_1,…,w_n$。

1. 一致性哈希基于红黑树，根据地址+端口组织RS。虽然插入顺序不同会导致底层红黑树结构不同，但相同源IP的流量会路由到相同的RS。
2. $RSi$被选中的概率为$\frac{w_i}{\sum{i}^{n}wi}$。加入权重为$w{new}$的$RS{new}$时，会有$\frac{w{new}}{\sum{i}^{n}w_i+w{new}}$比例的流量目的$RS$会变为$RS_{new}$，其余流量目的$RS$不变；删除$RS_i$时，目的为$RS_i$的流量会根据权重比例分配到其他$RS$，其余流量目的$RS$不变；$RS$更新时，会先删除再加入。