组合的概念

在以前的文章函数式编程中的 Functor 和 Applicative 中,我们探讨了函数式编程中几个经常使用的模式:Functor Applicative 和 Monad。 我们同时也经常看到或听到与之相关的另一个概念:Monoid (幺半群)。我以前不是很清楚为什么它被翻译作「幺半群」,不过现在想来大概和范畴论中的其他概念,如 Group(群)和 Semigroup(半群),有密切关联。Monoid 表示一个带有二元运算(记作 *: M x M -> M)的集合。成为 Monoid 需要满足三个条件,即,

  • 封闭性(Closure):对于任何 M 中的 a, ba * b 也在 M 内。
  • 结合律(Associativity):对于任何 M 内的 a, b, c(a * b) * c = a * (b * c) 均成立。
  • 单位元(Identity element):存在一个在 M 内的元素 e,使得任一在 M 内的 a 都符合 a * e = e * a = a

通常,我们也会说输入和输出类型相同的函数也是 Monoid。这样的函数也被称为是自同态(Endomorphisms)的函数。如果你理解了上述 Monoid 定义,你也就明白了为什么此概念会出现在函数式编程中——一切为了组合。

好的,现在我们总结一下这些模式如何帮助我们做程序设计,得到如下映射关系

  • 组合或聚合——Monoid
  • 有副作用和无副作用混合的场景——Functor
  • 并行地处理多个副作用——Applicative
  • 链式副作用——Monad

上述映射关系,本文在此不做展开讨论,诸位可参考文章 MonadFunctor Applicative 进一步理解。接下来,我们继续本文的主题:组合。前面两个链接中内容所涉及的组合概念,大都是函数的组合。但我们在应用上述不同的 patterns 解决实际业务问题时,常常会遇到另外一种组合。下面详细探讨。

考虑下面的例子(使用 Arrow 库实现)。我们首先构造了一个元素为 Option<Int> 类型的非空集合 typesComposition: Nel<Option<Int>>。可以看到,这个结构稍有别于函数组合,它是 Functor 和 Functor,Monad 和 Monad 的组合。为了验证这个 typesCompositionmap 功能能否通过 NelOptionmap 组合来实现,我们首先定义一个纯函数 pureFn: (Int) -> String,它转换 Int 类型成 String 类型。然后我们组合 mapOptionmap 应用该纯函数,转换它所包装的 Int 类型,Nelmap 应用一个 Option -> Option 的纯函数。运行下面的代码,发现执行结果确实如期望。因此我们实现了 Nel<Option<Int>>map 功能。

val typesComposition = Nel.of(1.some(), None, 2.some())

// 编译通过,且达到目的
val pureFn: (Int) -> String = { input -> input.toString() }
typesComposition.map { it.map(pureFn) }

继续我们的试验,为了使用 typesCompositionflatMap,需要先构造一个 effectful 函数 effectfulFn: (Int) -> Nel<Option<String>>。但在一番尝试和挣扎之后,我们发现,无论如何都无法通过 Monad 的诸多功能(包括 map apply 甚至 flatten),构造出一个可行方案。即便我们解决了可能的编译错误,最终得到的结果也是 Nel<Option<Nel<Option<String>>>> 的多层嵌套结构。

// effectful 函数
val effectfulFn: (Int) -> Nel<Option<String>> =
    { input -> input.toString().some().nel() }

// 这是什么操作???编译都无法通过。
typesComposition.flatMap { it.flatMap(effectfulFn) }

这个简单示例就是为了能让大家更直观地理解,为什么我们通常会说 Functor 彼此可组合,但是多个 Monad 却不可组合。我们当然不能在此推一及万,这个结论需要严格的数学证明。但限于篇幅,本文不介绍证明过程。问题是,即便 Monad 彼此不可组合,但这又有什么问题呢?当然有。我们不得不手动一层一层地展开类似于 Nel<Option<Nel<Option<String>>>> 的结构,获取最里层我们想要的结果。函数式编程中,我们希望自动化这种展开操作,去除重复的代码,使开发人员关注那些真正有业务价值的操作。因此,我们引入一个新的概念——Monad 转换器(Transformer),专门用于处理 Monad 多层嵌套时的问题。

Monad 转换器解决问题的思路是,使用一个 super Monad 将需要操作的多个 Monad 结合在一起,而这和 Monad 解决问题的思路一致。Monad 转换器应用返回类型为 MonadT(如 OptionTEitherT) 的函数,到 MonadT 类型。如 OptionT = OptionT<F, A>EitherT = EitherT<F, L, A>,分别表示 Option 转换器和 Either 转换器。

为了更加深入理解该概念,我们考虑场景:根据某一个人的 ID,最终找到她所归属国籍的代码。其中,findPersonfindCountry 是远程调用,且返回类型可能为空,因此定义返回类型为 ObservableK<Option<A>>。该场景就是一个非常典型的操作多个 Monad 的案例,适合使用转换器 OptionT 结合 ObservableKOption 简化操作。由于 OptionT 本身就是一个 Monad,因此我们可以使用它提供的便捷方式——Monad Comprehension,串行地执行它内部的语句。具体代码如下。

OptionT.fx(ObservableK.monad()) {
    val (person) = OptionT(findPerson(42))
    val (address) = OptionT(ObservableK.just(person.address))
    val (country) = OptionT(findCountry(address.id))
    val (code) = OptionT(ObservableK.just(country.code))
    code
}.value().fix()

上面代码的计算结果为 ObservableK<Option<String>> 类型。可以看到,OptionT 的引入使得包装和拆包装的过程对开发人员不可见,而只需在每一个步骤简单地使用 ObservableK<Option<String>> 构造 OptionT,保持计算地形态,直至最后一步。

本文至此就说清楚了当我们在函数式编程的上下文中讨论组合这个概念时,有可能会理解偏差的情况。希望能对大家学习有一些帮助。

 

 

 

抽象状态

状态(State)在编程中是一个十分重要而且自然的概念。称其「自然」,是因为状态是任意一个系统的内在性质。从常见的汽车发动机系统,到我们日常使用的软件系统,无不在其内部呈现状态迁移过程。汽油汽化和空气混合后在燃烧室内燃烧,发热而膨胀,进而下压活塞,最终带动活塞下的轴转动;网上购买的商品,其配送信息在某一时间段内持续变化……我们都能从中看到状态变化。

软件系统中,状态的变化有不同的表现方式。以伪随机数的生成为例。通常,需要一个 seed 用于初始化一个 Random 的实例。(在 Java 语言里面,Random 提供了无参构造函数,自动根据当前系统时间设置 seed 值)之后,通过调用 next 的方法获得生成的伪随机数。需注意的是,每次调用 next 的方法,seed 值都会更新。亦即,Random 实例维护了一个状态。在类似于 C# 和  Java 的面向对象语言中,状态变化表现为 Random 对象内部的属性 seed 的更新;在面向过程的语言如 C 中,我们定义全局变量 seed 表示状态,然后在必要处(模块方法 rand() 里)修改之……那么,在强调不可变的函数式编程中如何处理状态呢?接下来我们展开讨论。

考虑场景:创建一个栈(Stack)类型,以便往它里面添加(压栈)和删除(出栈)内容。在函数式编程中,由于无法直接修改值,所以我们每次都返回一个新创建的值。首先定义 Stack 类型。我们考虑使用 Arrow 库的 NonEmptyList/Nel(有序非空列表)建模栈。为了简单,让列表元素类型为 String 。由于栈可能为空,于是我们使用 Option 包装该列表。最终我们有如下栈定义。

stack_definition
图一:Stack 类型定义

接下来,定义 Stack 的 pushpop 方法。我们使用 Option.fold 处理入参 stack 为空或不为空的情况。

pop_and_push
图二:pop 和 push 定义

如上文所说,因为不可变,所以每次 pop 或者 push 时都返回一个新的 Stack 。看上去不错,但是这里有个麻烦。当我们想对 Stack 做连续操作时,(如下图中例子)我们不得不手动处理和传递所有的中间状态。显而易见,越多暴露中间过程,越容易出现误操作。

stack_operation
图三:栈的操作

如果我们仔细观察上面这个对 Stack 连续操作的例子,就会非常容易联想到 Monad。Monad 是一种通过统一输入和输出类型,达到链式调用的设计模式。它的 flatMap 方法,接受返回类型为包装类型的函数,并应用该函数于其他包装值。而 poppush 正好都是这样的函数。于是,我们就可以构造 State Monad 来抽象状态。以 Arrow 库的 State 为例,使用了 State 的 poppush ,其定义变为,

pop_push_redefinition
图四:pop 和 push 重定义

。它们均将 S -> Tuple2<S, A> 类型的函数作为输入,构造出 State<Stack, Option<String>> 类型的返回。既然是 Monad,我们当然也就可以使用它的 binding 特性(参见 Monad 文章),简化针对 Stack 的连续操作——即操作的组合,如下例。

stack_operations
图五:State 的操作简化

接下来,我们就可以通过方法 StateT.runStateT.runAStateT.runS 分别获取初始 Stack ,以及操作结果中的 <A><S>。如下示例。

operations_output
图六:操作的结果示例

至此,State Monad  就解释清楚了。本质上, State<S, A> 代表一个 S -> Tuple2<S, A> 的函数。为了加深对 State Monad 的理解,我们再回到文章开始提到的伪随机数生成的例子。当使用 State 抽象其 seed 状态,我们就会得到如下表述,

random_example
图七:使用 State 抽象 Random 中 Seed 状态的示例

至此,本文完。

函数式编程中的 Functor 和 Applicative

在之前的文章中,我们讨论了函数式编程中的 Monad 模式。而通常只要涉及 Monad,我们会常常看到 Functor(函子)和 Applicative 也一起被拿出来比较讨论。因此,本篇文章中,我将使用不同场景的例子,进一步澄清这几个相关联的概念。

首先考虑场景:存在一个包装了 int 类型值的 Option。我们需要对它包装的值做一个 addOne 的操作,最终返回包装值加一的 Option。如下代码可能是第一个进入脑海的实现,

wrapped_value_addition_example
图一:Wrapped value addition

。这种方式先把操作值从包装器(wrapper/container)中取出(unwrap),然后进行操作,最后再重新包装为 Option。它带来的直接问题是,针对包装值的不同操作(如 addTwo),需要实现对应的 Option 操作(如 addOptionTwo)。当然,你可以选择把对数值的操作,以参数形式传入来解决此问题。另一个问题是,我们不断地手动对普通数值做拆包装和包装的操作,这种方式在封装性和抽象层次均有欠缺,破坏了函数式变成的原则:随时随地组合函数。分析问题发现,如果 addOne 的操作能在 Option 所处的域完成(下图二),而非通过与普通数值域(World of normal values)频繁沟通(下图三),就可以避免对函数组合的破坏。

wrap_unwrap
图二:Wrap/unwrap 方式
addition_in_option_world
图三:Options 世界的加操作

那么,如何实现上图右中所提出的构想呢?答案就是 lift。如下图四,我们区分普通类型和包装类型在两个 Categories,范畴(本文所有图片中提及的 World 均作为 Categories 理解)。函数式编程中,为了方便函数组合,我们希望任何操作都尽可能在包装类型的范畴内完成。而所谓 lift,即是通过定义一个新的方法 lift(g): (fb: F<B>) -> F<C>,达到组合函数 f: (a: A) -> F<B>  和 g: (b: B) -> C(即 f • g)的目的,即 f • lift(g)。其中,类似于 f 返回结果为 F<T> 的函数被称为 effectful function,它要组合的是一个纯函数。

lifting
图四:Lifting

在 Kotlin 的 Arrow 库中,Option.map 提供了 lifting 的能力。于是,addOne 的操作被放置在了包装类型的范畴里实现了,如下图。

functor
图五:Functor

可以看到,这种方式在使得对 OptionaddOne 操作变得简洁。而 Option 就是本文探讨的 Functor 的一个实现,它能够应用函数到包装类型(wrapped value)。以 Kotlin 的 Arrow 库中 Functor 的定义为例,

fun <A, B> Kind<F, A>.map(f: F<(A) -> B>): Kind<F, B>

。方法 map就代表了 lifting 能力。另一个典型就是我们常见的 List 类型,它的 map 方法,让我们能简单地通过操作达到类型转换的目的。

接下来切换场景:用户注册时需要收集用户 ID、用户名、Email 地址信息,用以生成创建用户的请求。为了保证数据的有效性, 我们通常会做验证:用户 ID 不少于 3 个字符;用户名长度不超过 50 个字符;email 地址格式的正确性。常见的处理方式是,简单地通过 if-else 语句或者 switch-case 等方式判断数据是否满足何种场景下并做相应处理。一般是按顺序一一验证,且一旦验证失败就返回。由于验证的结果可能成功可能失败,于是我们可能使用类似于 Arrow 库中的 Validated 类型,对验证结果进行包装。如下图。

validation_example
图六:注册数据验证示例

这种方式将带来问题:首先,就像前一个例子中提到的,这种代码不断地手动对普通数值做拆包装和包装的操作。另外,如果想要同时拿到所有验证错误的结果,上述代码无法做到。那么,有什么解决方案呢?让我们沿着上面提及的思路,考虑把生成请求的过程放在包装类型域(World of valueOrError),如下图。

applicative_lifting
图七:Applicative lifting

我们仍旧考虑使用 lifting 技术。现有函数 createRequest: (userId: String, name: String, email: String) -> Request,我们期望通过 lift 来实现函数 f: (a: A) -> F<B>createRequest 函数的组合。但是,函数 createRequest 并非前述的一元函数(unary function),因此我们不能直接使用 lift(g): (fb: F<B>) -> F<C>

我们需要想其他办法——Currying,即一种转化多个参数的函数的计算为一系列单个参数的函数的计算的技术。记 g: (b: B, c: C) -> D,将它 Currying 之后变成 g: (b: B) -> (c: C) -> D。如果 lift 操作可以做到liftM(g): (fb: F<B>) -> (fc: F<C>) -> F<D> 就好了。可是如何做到呢?由于 Currying 后的函数 g 变成了一元函数,所以可以应用 Functor 的 lift 函数,有 lift(g): (fb: F<B>) -> F<(c: C) -> D>。由于无法拆解 F<(c: C) -> D>(fc: F<C>) -> F<D>,我们卡住了。现在不得不引出本文的另外一个概念——Applicative,它能应用包装函数(wrapped function)到包装类型(wrapped value),而这正好移除了刚才阻止我们继续推导的麻烦。以 Kotlin 的 Arrow 库中 Applicative 的定义为例,

fun <A> just(a: A): Kind<F, A>
fun <A, B> Kind<F, A>.ap(ff: Kind<F, (A) -> B>): Kind<F, B>
fun <A, B> Kind<F, A>.map(f: F<(A) -> B>): Kind<F, B> = ap(just(f))

。它包含了几个重要方法,一个是 just,负责包装普通类型。另一个是 ap,负责应用包装函数,最终完成类型转换,亦即拆解 F<(c: C) -> D>(fc: F<C>) -> F<D>。限于篇幅,我将略过具体拆解的过程。不过最终我们做到了 liftM(g): (fb: F<B>) -> (fc: F<C>) -> F<D>。还有一个是 map, 通过组合 apjust,实现 lifting 功能。

了解了整个推导过程,我们再回到前面的验证注册数据的例子。对函数 createRequest: (userId: String, name: String, email: String) -> RequestliftM(createRequest) 操作之后,便实现了 F<String> -> F<String> -> F<String> -> F<Request>,该过程被放置于包装类型域中。

至此,我们解决了频繁手动拆包装和包装的问题。如果仔细观察上图六,我们会发现,当要验证的值个数变多时,各种组合情况会让代码复杂度指数级上升。为了简化问题,我们常常会选择将所有的错误收集起来,并一起返回。以 Arrow 库为例,ApplicativeError 用于抽象可能成功可能失败的结果,我们将使用实现了该抽象的 ValidatedApplicativeError。为了收集所有的失败结果,我们需要一个集合,Nel<ValidationError>(Nel 等同于 NonEmptyList,表示至少有一个项的集合)。通过代理(Delegation),我们可以在自定义的 RegistrationRules 里访问 ValidatedApplicativeError(即 Applicative 的实现)的 justmap 方法。如下所示, RawRequest.validate 方法内部,使用了 map 方法,将有多个参数的纯函数 lift 到了包装类型域。ValidatedApplicativeError.handleErrorWith 则累积所有错误于一个集合中。

accumulated_errors
图八:错误累计示例

运行结果如下,

accumulated_errors_result

。由于用户 ID 和用户名都不是合法字段,因此在返回的错误集合 Nel<ValidationError> 中同时看到了 UserIdErrorNameError

至此,我们就介绍完了 Applicative 的概念。总结一下,Functor 解决了一元(单参数) effecful function 和纯函数的组合问题,Applicative 解决了多元(多参数)effectful function 和纯函数组合的问题。但如果两个函数都是 effectful function ,该如何组合呢?我们形式化表示,记 f: (a: A) => F<B>g: (b: B) => F<C>,于是问题就变成了如何让 f • g (f 和 g 的组合)可行。

为了解决这个问题,需要涉及到 Monad 的概念(参考介绍 Monad 的文章)。让我们沿着上面的逻辑,由于函数 g 是一元函数,我们可以参照 Functor 的 lifting 功能定义 Monad 自己的 lift 方法,记作 lift(g): (fb: F<B>) -> F<F<C>>。不妙!此处产生了 F<F<C>> 的类型,我们遇到了嵌套上下文(nested contexts)问题。思考片刻,我们想到可以通过引入一个 flatten: (ff: F<F<A>>) -> F<A> 方法,展开该层级嵌套,形式化为 flatten • lift(g)。如前所说,由于 Functor 的 lifting 能力通过 map 方法体现,而在诸多函数式编程语言或者库里,Monad 会合并 flattenmap 功能,一步到位地使用其 flatMap 方法(先 flatten 再 map)表示 flatten • lift(g)。至此,我们解决了多个 effectful function 的组合问题,即通过 f • flatMap(g)。对于 Monad 更多的介绍,可以详细查看该文章。

函数式编程中的 Monad

函数式编程作为一种不同的编程范式(programming paradigm),在编程语言发展的不同历史时期都体现出顽强的生命力。即便在当前面向对象语言主导的编程世界,函数式编程思想依然被广泛借鉴。例如 Kotlin 的函数式编程库 Arrow;C# 中引入的函数式编程;自 Java 8 起提供的 Stream 接口等……但同时我们也明显注意到,由于面向对象和面向过程语言的长期影响,程序开发人员接触的函数式编程概念极为有限——函数是一等公民;纯函数的好处;不可变性等。然而一旦去思考一个函数式语言实现的系统是什么样子的时候,就概念模糊了。而这就进一步限制了我们高效地使用混合型编程范式的语言,尤其是函数式特性的部分。大多数人不了解函数式编程的全貌,认为函数式只适用于处理集合的场景。因此,学习一门纯粹的函数式编程语言对程序开发人员来说,仍旧十分必要。而我也希望通过一系列的文章,来探讨函数式编程的设计原则和方法。

我们都知道,面向对象语言最重要的概念是:封装(encapsulation)、多态(polymorphism)和继承(inheritance)。著名的 SOLID 原则,对前面三个概念稍作展开讨论。为了帮助我们写出可扩展,易维护的程序,四人帮(GoF)又为我们提供了 23 种设计模式(design patterns),在更落地的层面指导我们的日常编程。对应地,在使用函数式语言开发软件时,我们也希望基于函数式的原则,寻找到更加广泛的模式,以解决软件设计中反复出现的问题,提升开发效率。

函数式编程设计原则,则涉及四个重要概念:借鉴数学、类型(type)、函数(function)和组合(composition)。纯函数在函数式编程中被推崇备至,它能带来诸多好处:延迟计算;缓存数据;无执行顺序依赖;并行计算。区别于面向对象中类(class)的概念,函数式编程中的类型,隔离了数据和行为(面向对象中使用类将数据和行为封装绑定在一起)。函数作为一等公民,不依赖于任何类似于面向对象中类的概念,独立存在。类型,既可以是函数的输入和输出类型,也可以是函数本身,如 f: Int -> Int。当有两个函数,function1: Int -> Stringfunction2: String -> Char 时,我们就能通过函数组合得到第三个函数:function3: Int -> Char。当然,函数式编程也提供了类型组合,在此不做赘述。

至此,我们对函数式编程的基本设计原则有了共识。接下来,我们通过案例来引出本文主角,也是我要探讨的第一个函数式设计模式。如下图一,我们在日常编程中常常会看到,由于不确定某个值是否为空,于是我们用大量的 if-else 语句来判断。这种代码一方面降低了我们编码的效率,同时让软件的可维护性大大降低——一定有人在此处添加更多的 if-else 语句。我们直觉性地会使用 Option 来代替并消除 null 这个代码坏味道,如下图二。

null_checks_example
图一:null check 示例
null_checks_with_option
图二:使用 Option 做 null check

我们仍旧不满足这样的代码。所以,我们继续,简单地将 if-else 抽取到单独的小方法里,如下图三。代码看上去确实整洁了一些,但是一定有人质疑这种做法并没解决根本问题—— if-else 语句仍旧是大量重复的,而我们只是将其挪了位置而已。

null_checks_simple_refactoring
图三:使用 Option 做 null check

那么我们继续观察重构过后的代码。if-else 这段模板代码一直在重复被执行—— 先是函数 refactoredNullCheckExample 使用 if-else 的语句调用 dealWithXdealWithX 使用 if-else 的语句调用 dealWithY,以此类推……我们发现一个模式(pattern)—— 函数 simpleChainablePattern!而重写后的 nullCheckExample,变成了 newNullCheckExample,如下图四。

refactored_example
图四:使用 pattern 重构

现在,我们看到代码变得十分简洁流畅。而且,我认为你一定也像我一样认可这个重构。

接下来我们总结一下该 pattern 的特征。如下图五所示。首先,我们有一个一般化的容器(Container,对类型的包装)包装 T 类型的实例,整体作为输入。为了达到链式函数调用的目的,我们期望 addStep 操作的返回值类型仍为该一般化容器包装另一种(或同一种)类型的实例。因此,作为 addStep 参数的函数,必须保证其返回值类型也是该一般化容器,而非靠 addStep 完成类型的转换——pattern 本身应尽量简单通用。由此我们看到,只要遵循这种操作,我们就可以在 addStep 之后继续 addStep,实现这种链式调用,保持流畅性。

图五:pattern 解析

以上这个模式,我们称它为 Monad。 这也就引出了我们本文所要讨论的主题。根据定义,Monad 在函数式编程中的一种设计模式,它通过自动抽离程序逻辑所需的模板代码,让程序结构一般化,通用化。这一类的模式,我们其实经常能够碰到。例如,Kotlin 的 Sequence(如下代码片段)和 Iterable 接口。在操作 Sequence 的实例时,能够非常方便地通过 flatMap 方法,对输入做连续的变换。

fun <T, R> Sequence<T>.flatMap(transform: (T) -> Sequence<R>): Sequence<R>

前面我们讲的都是按顺序调用时应用 Monad 的案例,而我们在日常工作中常常也会遇到非顺序工作流(Non-Sequential workflow)。考虑场景:帮助演讲者预订机票。机票的预订同时依赖 speaker 信息和根据 speaker 信息获取到的 city 信息。这个场景的不同之处在于,我们还必须保存 city 操作之前的计算步骤结果,即 speaker 的信息。于是,我们考虑如下实现(Kotlin 语言),

non_sequential_workflow
图六:non-sequential workflow 示例

我们仍旧应用了 Monad 模式——flatMap 帮助做类型转换。但是我们观察到,这种实现方式带来的问题就像本文最开始讨论的 if-else 示例,代码很快就会变得不可维护。那我们该如何改善这段代码呢?幸运的是,在诸如 C# 和 Kotlin (Arrow) 等编程语言中,为 Monad 提供了高可读性的 async/await 代码。以 Kotlin 的库 Arrow 提供的此类特性为例,

non-sequential_work_flow_monad
图七:Kotlin 中的 Monad 处理非顺序工作流

Arrow 中,任何 Monad 都有一个名为 binding 的方法(上图中的 Monad.fx.monad)。该方法的定义为,

fun <A> monad(c: suspend MonadSyntax<F>.() -> A): Kind<F, A>

,它的参数是一个 suspend 函数。也就是说,binding 方法接收的参数是一个 suspend 函数。Arrow 借助 suspend 函数在 coroutines 上执行的特性,保证了 binding 方法内部按顺序执行。需要强调的是,上图八中,变量名上加括弧,或是显式调用 bind() 方法,其作用等价于调用 Monad 的 flatMap 方法,传递的参数是类似于 { speaker -> speaker.nextTalk() } 的函数。虽然代码看上去仍旧不如按顺序工作流情景下 Monad 模式所带来的流畅度好,但是我们至少保证了单层调用,从而降低代码复杂度。

以上,就是关于函数式编程中 Monad 的一个基本探讨。最后,就像其他所有介绍 Monad 文章,需要提及一下 Monad Laws。记f: (a: A) => F<B>g: (b: B) => F<C>h: (b: C) => F<D>。 运算符 表示两个函数的组合。

  • Left Identify law。即 Monad 的构造是中立的。它不改变被用于构造的值,同时不影响函数(如上例中 flatMap 的参数)调用的结果。亦即 flatMap(just) • f = f
  • Right Identity law。即一个已存在的 Monad,记 M1,将它包装的值用于构造另一个 Monad,记 M2,对其做类型转换(如上例中的 flatMap)之后的结果仍 M1。亦即 flatMap(f) • just = f
  • Associativity law。也就是结合律,函数结合的先后顺序不会影响最终计算的结果。 亦即 flatMap(f) • (flatMap(g) h) = flatMap((flatMap(f) g)) h

对于初学者来说,只建议稍作了解,而不用深入研究。

编程中的「消息通信」

在之前的一篇关于「面向对象编程」讨论的文章中,我想着重强调「消息通信」这一概念在原初设计面向对象系统时的重要性。不过,在二零一九年 OO 大行其道的现状下,来理解「消息通信」和面向对象编程之间的关联,确实不容易。那么如何帮助大家在 2019 年理解这一概念呢?我希望在本文中尝试回答。

在编程的上下文讨论消息传递时,一般有两种定义。第一种定义是大众广泛理解的,在并发编程范式中,消息通信是异步分发的一种方法,用于在进程间的通信。不同的进程甚至可能存在于不同的机器上。通常,不同的并发模型可能会有不同角度的考量,如 receiver 需不需要和 sender 在某地汇合,亦或者,receiver 需不需要为 sender 命名以作区分等等。第二种定义则是 Smalltalk 系编程语言中涉及的,非常简单,即对象的方法调用。在 Smalltalk 中,消息是异步的。也就是说,调用者(caller)会等待被调用者(callee)返回结果。

Smalltalk 的消息通信

Smalltalk 使用「消息通信」可以追溯到它的起源。受 Actor 设计思想的启发和影响,最初被设计出来的 Smalltalk 系语言不是过程式的,它没有过程调用的概念,而是 Actor 式消息传送的变种。但这一设计在之后 Smalltalk 的版本演化中被移除了,原因之一是 Actor 式的计算模型在传统工作站下模拟出来的成本非常高。另外就是受当时 Lisp 研究实际在工作站上运行的结果影响。尽管后来彻底演变成了传统的过程式语言(更像是 Lisp 的变体),但是 Actor 模型下的术语被沿用了下来。再后来随着硬件性能的指数级增长,在过程式计算的硬件设备上模拟基于 Actor 模型的计算变得便宜,Alan Kay 开始后悔当初因性能问题而把 Smalltalk 改变为基于过程式计算模型的编程语言。也因此才有了那篇被激烈讨论的邮件

梳理清楚了面向对象语言中「消息通信」这个名词的来源,让我们继续用该名词,详细看下 Smalltalk 中的消息通信。

Smalltalk 中,可以把消息理解成进行计算的请求。当一个对象接收到消息时,它负责响应消息——执行消息所表示的计算。具体来说,该对象根据消息名,在自己的方法命名空间(method namespace)中匹配并执行方法。方法在 Smalltalk 中亦为对象,它本身包含有算法过程(计算可能有副作用)。概念上,方法可类比于函数(function)或者子进程(subroutine),消息类比于函数或者子进程的调用。消息(或方法)的名字是它的选择器(selector),消息(或方法)选择器表达它本身的意图,同时用以区分不同的消息(或方法)。另外,消息可能含有零个或更多的参数。一般地,方法可能接收零个或者更多参数,所以最终这些消息中的参数也就作为方法所接收的参数。方法命名空间(method namespace)维护了一组方法选择器和方法的映射关系,使用选择器可查找对应要执行的方法。动态消息分发(dynamic message dispatch)代指使用方法命名空间找到对应方法的过程。应注意的是,Kay 博士(Alan Kay,Smalltalk 作者)使用方法(method)这一名词指代那些使用运行时动态消息分发方式,因响应消息而被调用的函数或者子线程。而这也是 Smalltalk 中方法和其他语言中函数的本质不同。也正是因为动态消息分发,发送消息给对象完全取决于接收消息的对象。同样的消息发送给不同的对象,可能会被解释为成完全不同的意义。这是因为,不同的对象可能使用不同的方法命名空间通过消息选择器查找方法,同样的消息选择器可能关联不同的方法。也正因此,消息可以被理解为抽象方法调用,即接收消息的对象来选择具体要执行的方法。此时,消息负责为逻辑计算过程命名,接收该消息的对象则负责实际的计算过程。

举个例子来理解下 Smalltalk 中消息传递的概念。假设我们已经有一个 Student 的类和变量 aPerson,Student 类包含一个 name 方法。让我们来看以下语句,

^Student new name: aPerson name

按照消息执行的顺序,以上的声明语句按照如下顺序执行,

  1. 发送消息 new 至 Student 类;
  2. 发送消息 name 至变量 aPerson 所指向的对象;
  3. 发送消息 name: (连同上一步的返回结果,作为参数)至消息 new 的结果,即实例化 Student 的对象;

由于消息 name: 没有重写默认返回值,因此上述声明语句会返回实例化 Student 的对象,也即消息 name: 消息的接收者。

Elixir 的消息通信

和 Erlang 一样,Elixir 基于 Erlang VM,致力于方便地构建可扩展易维护的应用程序。在借用了 Erlang 的优势的前提下,汲取了其他编程语言的精华,以此来提升 Erlang 中缺失的代码组织的能力——编写,分析和修改的能力。

Elixir 的代码运行在 process 中。不同的 process 彼此独立,它们并行运行的同时通过发送消息来互相沟通。需要注意的是,Elixir 中 process 的概念和我们平时所说的操作系统的进程(process) 完全不是一个层级的概念。Elixir 中的进程极其轻量,也因此,我们可以使用 Elixir 轻松启动数以百万计的进程。

我们通过 Elixir 中 send 和 receive 来进一步说明进程间消息传递的方式。send 用于从当前进程向另外某一进程发送消息,

iex> send self(), {:hello, "world"}
{:hello, "world"}

。以上代码中,当前进程给自己发送了一条消息 {:hello, “world”}。然后我们执行以下 receive 代码处理接受到的消息,

iex> receive do
...> {:hello, msg} -> msg
...> {:world, msg} -> "won't match"
...> end
"world"

。仍旧是当前进程,匹配接收的消息以决定如何处理。

Elixir 的每个进程都有属于自己的信箱(process mailbox),一旦有消息被发送至某个进程,该消息则会立即被存储在目标进程的信箱中。目标进程的 receive 块,会遍历信箱,查找匹配给定模式的消息。上例中如模式 :hello。如果信箱中的消息没有匹配到任何给定模式,则当前进程会一直等待,直到信箱中进来模式匹配成功的消息。(此时一个比较常见的处理方式是制定 timeout)另外,发送消息的进程本身不会产生阻塞,一旦它把消息投递到目标进程的信箱中之后,立即开始执行其他任务。

参考文章:

Smalltalk: Getting The Message

Message passing

 

面向对象编程中的「对称性」

The flexibility provided by Smalltalk’s high degree of symmetry and extreme late binding have proven to help programmer productivity and creativity more than any theoretical benefits that might be derived from the use of static type checking, symmetry-breaking primitive data types or symmetry-breaking syntactic sugar.
(译文:Smalltalk 高度的对称性和极致的延迟(动态)绑定特性所带来的灵活性,帮助提升程序开发人员的工作效率和创造力。这种收益已被证明高于任何静态类型检查,对称性破缺的基础数据类型或者对称性破缺的语法糖所可能带来的理论收益。)

对称性的概念

对称性在几何和代数中有不同的定义。几何中,对称性是指对几何形体施加某种操作使它的位置能完全复原。代数中,对称性被描述为给定的组合定律下闭合,关联和可逆的一组变换。不论哪种功能定义我们都可以得出,对称性的核心即是变换条件下的不变性

分类(classification)与对称性(symmetry)

从认知科学的角度讲,我们人类的思考基于对事物进行分类的能力,分类最终建立起类(class)和实例(instance)的关联。一些该领域的人甚至认为分类支撑了人类的认知,并帮助构建了人类记忆存储的组织结构。在编程领域,面向对象编程语言通常支持两个层次的分类,即对象归类构建类之间的结构关系。基于此,有人认为所有面向对象的概念都可被统一于某种理论模型,并由分类学作解释。这也就提出从一种新的视角,即从生物学(biology)和分类学(taxonomy)的角度,来理解面向对象编程。

面向对象语言中,类是对象的分类。这种分类直接构建起了类的不变性——类的描述适用于该类的所有对象。从这个角度进一步推导,类便拥有了对称性:类赋予了对象多变性,但这种多变性需要遵循该类所定义的结构和行为。类的对称性带来的好处是,它为对象的多变性划分界限,且强制性地保证了类的正确性。

类的概念在基于组件的软件开发中非常有价值。组件可以按照如接口或者行为的兼容性等共有特征,分组为不同的类。于是类就能够用于创建具有共同特征,但各自不同的组件。当应用的需求发生变化时,只要新的组件遵循该组件类的共有特性,那么它就可以用于替换旧的组件。这种可替换性对基于组件的软件开发很有意义。另外,软件维护和演进过程中,替换过时或问题频出的组件已然令人头大的情况下,组件的可替换性也就同样重要。

更为重要的是,对称性和分类之间的联结,为面向对象软件设计提供了理论研究的基础。通过应用对称性原则,软件设计的目的就变成了最大化地识别和保留设计上的不变,同时能良好地支持变化。

接下来我们看另一种对称性。继承(Inheritance),大多时候会和一般化(generalization)与特殊化(specialization)概念挂钩,较少有研究者将之与分类(classification)相关联。面向对象编程中,分类上下文里,继承的角色不如类那样清晰。这是因为继承机制本身的灵活性。继承可以用以扩展类,限制类,或者修改类。这就意味着,子类和其超类可能并非包含关系,并且超类的描述也可能不适用于所有其子类。因此继承并不总能将类做出分类。但是,当继承用于子类型(subtyping)时,它就可以被看作是类的分类,也就保持了子类和其超类行为的一致性,亦即行为的不变性。此处需要明确一下,子类型只是继承扮演的角色之一。例如基于原型编程中对象的继承。因此,只有在子类型的概念下,继承方才用于对类进行分类。子类型和对称性的内联表现为:所有通过子类型方式构建的类,彼此可能大不相同,但一定保持并符合某种相同行为,或者说,它们是相同类型。

当然,我们可以进一步在面向对象编程中找到其他对称性的案例。但是以上两个例子就足以说明对称性在编程中的重要性。接下来,我们换一个视角进一步来了解对称性。

对称性的威力

对应到大众熟知的「面向对象编程」语言,如 Java,C++ 和 Python,「类和继承」的确被放在了核心位置。相应带来的对称性,当然也就体现在这些编程语言中。

作为对比,观察 Smalltalk 这一面向对象编程语言会发现,类,本质上是对象。该对象本身也是另外某个类(这种类被称为类的元类,metaclass)的实例。类是一个元类的唯一实例。所有的元类都是类 Metaclass 的实例。Metaclass 类是「Metaclass class」的实例,而后者又是 Metaclass 的实例。如此递归。Smalltalk 中类的编程只是一些操作数据的程序(program),这些程序本身又是数据(data)——可被其他程序操作。这不同于 Lisp 哲学(Lisp 因使用符号表达式,而让程序即为数据),但殊途同归。

甚至可以更进一步地说,Smalltalk 的对象/类系统的真正威力,不是它的继承特性,而是它的反射(reflection)机制。Smalltalk 运行在它被编写创造出来的上下文中(runs in same context it’s written in)。具体来说,Smalltalk 的运行时系统的元对象(metaobject)可以被具象化为普通的对象,被用以查询甚至查看内部细节。在 Smalltalk 中,元对象可以是类、元类、方法字典、编译过的方法、运行时栈,等等。

 

reflection

 

我们看到,Smalltalk 中体现出了上文所没有涉及到的另一个层次的对称——程序和数据的对称,数据即程序,程序即数据。这种对称在诸如 Java、C++ 和 Python 等面向对象语言中并不存在。甚至,Smalltalk 中体现出的这种独有的对称性,让其「类和继承」特性带来的对称性黯然失色,以至于类的继承仅仅是代码重用的方式。这种数据即程序的对称性,意味着,所有的信息都封装在即时运行的活(living)对象中。它使得 Smalltalk 调试器在程序执行过程中能够暂停,剖析,修改和恢复。这也是为什么 Smalltalk IDE 不仅仅是使用 Smalltalk 编写的,它也是 Smalltalk 语言本身。

后记

在查阅「面向对象」概念相关的文章时,数次出现了「对称(symmetry)」 这个词。让我疑惑的是,编程语言和对称有什么关系?进一步地调查发现,对称性的概念远远超越了设计范围,广泛存在于多种理论中。归根结底,对称性表现出来的哲学意义极具普遍性和指导性。当「变换条件下的不变性」这一个理念,和软件设计结合时,显得恰如其分。我们行业的前辈们,已然做了很多尝试,从编程语言的设计和软件开发的过程两个层面,最终想让软件开发更加轻松地应对变化。当然,这种努力今天仍旧在持续。

最后,希望本篇文章能够对大家有所启发,就像对我有启发。

 

参考文章:

Lisp, Smalltalk, and the Power of Symmetry

Understand symmetry in object-oriented languages

Raft 共识算法

Raft 的设计初衷,就是要提供一个完整且实际可行的系统构建基础。因此,「易理解」是该协议最重要的目标。相较于 Paxos 的复杂性,Raft 为我们提供了一条更易实现的途径。本片文章是在通读原论文「In Search of an Understandable Consensus Algorithm (Extended Version)」之后按照自己的理解做了整理。希望对大家理解 Raft 有所帮助。

共识算法

共识算法常出现在「多副本状态机(replicated state machine)」这一概念里面。分布在一组服务器上的多个状态机,各自负责计算出状态一致的多个副本。即便在其中一些服务器宕机情况下,整个系统仍旧能够照常工作。多副本状态机用于解决分布式系统容错性问题。如下图所示,多副本状态机是由多副本日志系统实现的。各服务器上都维护了一个日志系统,该系统按顺序存储一系列的命令,状态机依据该顺序依次执行这些命令。由于各个服务器上的日志系统依同样的顺序存储同样的命令,因此状态机的执行结果可以保证是一致的。

replicated_state_machine_architecture

针对 Raft 算法过程的

共识算法的职责便是保证和维护所有服务器上日志系统的一致性。当某台服务器上的共识模块接收到来自客户端的命令,它先将该命令存储到日志系统,然后和其他服务器上的共识模块通信,以此保证所有的日志系统最终以同一顺序存储同样请求。一旦所有请求就绪,每台服务器的状态机开始按日志系统中命令的顺序执行,之后结果被返回给客户端。因此,这些配合起来工作的服务器集群,从外部看上去也就成为了「一台」可靠的状态机。

算法的实现细节

在具体展开算法细节之前,先解释下几个重要的概念。首先是服务器状态。分别为 leader,follower 以及 candidate。一般情况下,集群中只有一个 leader,其他均为 follower 。follower 比较被动,只负责回复来自 leader 或 candidate 的请求。candidate 则是服务器在竞选期间的状态。其次是任期(term)。任期被顺序编号,其时长是任意的。任期由选举期和施政期组成。服务器之间的通信方式为 RPCs(远程过程调用)。Raft 中只提供两种 RPC,一种是 RequestVote RPC,另一种是 AppendEntries RPC。前者用于投票竞选阶段,后者则用于 leader 向集群内其他服务器发送信息,如心跳。

leader 竞选

心跳机制是 Raft 推行竞选 leader 的核心。当服务器启动时,默认为 follower。leader 会定期地向所有 follower 发送心跳消息来保持自己的身份。如果某个 follower 在特定时间内没有收到 leader 的心跳消息,则竞选超时,该 follower 则会认为当前没有所有服务器一致同意的 leader,于是开始新一轮的 leader 竞选。

raft_leader_election

为了启动新一轮竞选,follower 需将当前任期值加一,并身份转变为 candidate。然后该服务器在给自己投上一票的同时,发送 RequestVote RPCs 到集群中所有其他服务器。随之会产生三种不同的结果。其一,该 candidate 赢得了竞选。集群中的每个服务器最多只能投一票,该服务器遵循「先到先服务」的原则来自处理 candidate 的投票请求。当 candidate 获得大多数的选票时则胜出,成为新的 leader。(这种大多数选票规则可以保证最终只有一个 candidate 能够成为 leader。)之后它会发送心跳信息到其他所有的服务器来确立自己的 leader 身份。其二,该 candidate 接收到了来自其他服务器的声明其为 leader 的 AppendEntries RPC 。如果请求中包含的任期值(即 leader 的任期值)不小于该 candidate 的当前任期值,该 candidate 则承认 leader 的合法性,自己转变回 follower 身份。否则,该 candidate 不处理请求,继续保持其 candidate 身份。其三,既没有胜出,也没有败选。也就是存在太多 candidate,导致选票分裂(split votes)的情况。此时任何 candidate 都不再可能获得大多数选票。一旦此种情况出现,则最终 candidate 竞选超时,然后它们增加各自当前任期值,发送 RequestVote RPCs 以开始新一轮的竞选。当然这会引发新的问题,即选票分裂的情况无限循环下去。Raft 为了解决这个问题,使用随机竞选超时(randomized election timeouts)来确保尽可能少出现选票分裂的情况,即使出现也能被快速处理。

日志副本

leader 在接受到来自客户端的请求之后,先把请求中的命令顺利添加到所在服务器的日志系统中以供状态机之后执行,然后一并将 AppendEntries RPCs 发送至其他服务器以生成副本。如下图所示,多个条目在日志系统被编号存储。每个条目包含有任期值和具体的命令。任期值表明在哪一任期内该条目被写入进日志系统,命令是状态机需要执行的具体操作。

 

raft_log_replication

leader 会决定何时让状态机执行条目中的命令,该条目被叫做已提交(committed)条目。当 leader 将日志条目成功存储在集群中大多数服务器上时,该日志条目状态即为已提交。之后, Raft 会保证所有已提交状态的日志条目持久化,且最终被所有可用的状态机执行。此处注意,在提交新的条目时,该条目之前的所有其他条目,包括过往 leader 创建的,也一并被提交。

Raft 日志系统拥有两个匹配特性(Log Matching Property),即,

  • 如果不同日志系统中的两个条目拥有相同的索引和任期值,那么它们存储相同的命令。
  • 如果不同日志系统中的两个条目拥有相同的索引和任期值,那么位于该条目之前的所有条目完全相同。

leader 在特定任期内,给定日志索引的情况下,最多只能创建一个条目。并且这些日志条目在日志系统中的位置永远不会发生改变。这也就证明了第一个特性。而第二个特性则通过使用 AppendEntries 所做的一种简单一致性检查来保证。当 leader 发送 AppendEntries RPCs 时,它会将紧靠新条目的前一个条目的索引和任期值一并发送出去。如果 follower 之后接收请求后,在自己的日志系统中没有匹配到同样索引同样任期值的条目时,新的条目则被拒绝录入。因此,只要 AppendEntries 成功返回,leader 就可以推论得出,follower 的日志系统和它自己的日志系统从头到尾完全一致。

但是现在有个问题,如果 leader 崩溃了呢?这会直接导致 leader 和 follower 日志不一致。如, follower 日志缺失了一些存在于 leader 日志中的条目;又如,follower 日志中存在额外 leader 日志中不存在的条目;或者二者兼备。为了解决这个问题,Raft 采用了这一方法,即:leader 上台之后,它分别针对每个 follower 保存维护一个 nextIndex,并设置值为紧接 leader 日志末尾索引的下一索引值。nextIndex 代表了下一个 leader 发送给给相应 follower 的日志条目索引。因此,当出现 leader 和 follower 日志不一致情况时, AppendEntries RPCs 所做的一致性检查会失败,follower 拒绝条目录入。接着 leader 会修改 nextIndex 值,将其减一,然后重试一致性检查。重复此操作,最终会在某个条目点,leader 和 follower 的日志匹配成功,AppendEntries 一致性检查通过,这时,它删除冲突的条目,并将存在于 leader 日志中 follower 所缺失的条目,添加至 follower 日志中,最终日志达成一致。

安全性

竞选的限定条件

上述 leader 竞选和日志副本的方式其实并不能保证每个状态机按同样顺序运行同样的命令。例如,有可能在 leader 在复制某些日志条目到其他服务器时,其中某个服务器处于不可用状态,随后该服务器在竞选中胜出成为 leader,于是它将这些日志条目用新条目覆盖。最终结果是, 不同的状态机可能执行的是不同的命令序列。

为了解决以上这个问题,Raft 在竞选阶段就阻止了那些不包含完整已提交状态条目的 candidate 参与 leader 竞选。RequestVote RPCs 会包含该 candidate 的日志信息,一旦投票者发现自己的日志相比该 candidate 的日志更新一些,它就投反对票。这个新旧的比较是 Raft 来做的,通过对比日志的最末尾条目的索引和任期值。如果不一致,则认为末尾条目任期值更大的较新。如果一致,则认为日志条目数更多的较新。

往期条目的提交

raft_safety

前面我们说到了,leader 在收到大多数服务器已录入条目的回复消息,即将改变该条目状态为已提交时,可能崩溃。下一任 leader 会尝试完成该条目的副本创建,但麻烦在于,leader 不能通过一个条目被复制到了大多数的服务器中,来立刻断定该条目状态是已提交的。因为,以上图为例,(a) 中 S1 是第二任的 leader,并在索引 2 下添加新条目,但是在自身和 S2 中完成之后挂掉了。(b) 中 S5 获得 S3 和 S4 选票之后胜选,成为 leader。开始在索引 2 下添加新的条目。(c) 中 S5 崩溃,S1 重启完成并被推举为新的 leader。它继续完成副本的添加。此时,第二任期的条目已经完成在大多数服务器上的复制,但还未被提交。不幸的是,如(d)中情景,此时 S1 在它修改条目为已提交状态之前再次挂掉,S5 有可能再次当选成为 leader,接着用它自己的第三任期的条目,覆盖了其他服务器日志索引 2 下的条目。以有次可知,即便当往任的 leader 在大多数服务器日志中添加新条目成功,仍旧有可能发生未来的 leader 覆盖这些新条目的情况。

为了解决这一问题,Raft 通过计算副本数量,不提交以往任期的日志条目,相反,只提交当前任期内的日志条目的。如此,在上例(c)中,如果 S1 在崩溃前,只将当前任期内的条目(不处理往任条目)复制到了大多数的服务器上,如(e)所示,那么该条目便成为已提交状态。根据 Log Matching Property,该条目之前的所有条目都被间接提交。

安全性证明

根据上述完整的 Raft 算法,我们可以推断出 Leader Completeness Property 的存在。证明过程可以使用反证法。假设, T 任期的 leader leaderT 在该任期提交了一条条目,但是该条目没有被未来任期 U (U > T)的 leader leaderU 存储于其日志中。

  1. leaderU 在当选时,它的日志中缺失了 T 任期提交的条目 entryT。
  2. leaderT 将条目 entryT 复制到了集群中大多数的服务器中,leaderU 获得了大多数服务器的投票。由此,至少存在一个服务器 voter,既接受了 leaderT 的条目 entryT 写入,又投票给了 leaderU。
  3. voter 必须在投票给 leaderU 之前,接受 leaderT 提交的条目 entryT 写入。否则,它会拒绝 leaderT 的 AppendEntries 请求。
  4. voter 在投票给 leaderU 时,entryT 仍旧存在于其日志中,因为任何介入的 leader 都包含条目 entryT,而 leader 任何时候都不会移除条目,同时 followers 仅在自己的日志条目和 leader 的冲突时,才会移除。
  5. voter 投票给了 leaderU,说明 leaderU 的日志至少和 voter 的日志是同样新的。而这与假设矛盾。
  6. 首先,如果 leaderU 和 voter 的末尾条目相同,那么 leaderU 的日志至少要和 voter 的日志长度相同,这样 leaderU 的日志包含了所有 voter 的日志条目。而这和我们的假设矛盾。
  7. 或者,如果 leaderU 的末尾条目任期值大于 voter 的末尾条目任期值,且该值大于 T。写入 leaderU 末尾条目,位于 leaderU 之前的 leader,一定也包含了已提交条目 entryT。那么根据 Log Matching Property,leaderU 的日志也一定包含了已提交条目 etnryT。而这也与假设矛盾。
  8. 因此,T 任期之后的所有 leader 一定包含 T 任期内提交的所有条目。
  9. Log Matching Property 确保未来的 leader 也包含有那些间接被提交的条目。

通过 Leader Completeness Property 可以证明 State Machine Safety Property,即,如果某个服务器将某一索引下的日志条目应用于其状态机,那么一定不会出现任何其他服务器,应用于其状态机的相同索引下条目不一样。服务器应用某条目到它的状态机时,该条目之前的日志和 leader 的完全一致,并且该条目是已提交状态。

follower 和 candidate 崩溃

前面大量讨论了 leader 崩溃时如何保证系统的可用性和安全性。相比来看,follower 和 candidate 崩溃的处理就简单多了,且处理方式一样。当某个 follower 或者 candidate 奔溃时,发送来的 AppendEntries RPCs 或者 RequestVote RPCs 随之失败。Raft 处理此类失败的方式为,无限重试。当挂掉的服务器完成重启,RPC 也随之成功完成。如果服务器在 RPC 完成之后,尚未回复之前挂掉,则重启之后的服务器会重新收到新的同样的 RPC。Raft 的 RPC 是幂等的,因此多次发送并无副作用。

时间和可用性

Raft 在设计之初就尽量避免依赖于时间。某个事件发生早于或晚于期望时间而导致结果错误,这是系统不能接受的。但同时,可用性(系统及时响应客户端请求的能力)又不可避免地要依赖于时间。以 Raft 中竞选过程为例,candidate 发送投票消息到其他服务器,然后其他服务器响应并回复,这个过程用时如果超过服务器通常崩溃的时间频率,那么 candidate 就会因为在线时长太短而无法胜选。同理,如果没有一个稳定的 leader,Raft 的可用性会大打折扣。

一个稳定的 leader 需要满足以下不等式,

broadcastTimeelectionTimeoutMTBF

,其中,broadcaseTime 代表 candidate 一并发送投票请求至其他服务器且被接收到所花时间。electionTimeout 如前文说提及,是 follower 等待 leader 消息到达的最大时长。MTBF 则是单个服务器的平均崩溃时间周期。broadcaseTime 和 electionTimeout 值属于同一量级,前者小于后者时,能够保证 leader 发送心跳类型的 RPC 到 follower,来确保自己的身份,当然也就避免了 follower 因为超时而发起新一轮的竞选。electionTimeout 和 MTBF 值相差几个量级,当 leader 崩溃时,大约有 electionTimeout 时间内整个系统是不可用的。

集群的配置更新

在日常使用场景中,一个动态可配置的集群必要的。例如,当集群中的某个服务器崩溃时,我们不想等待它恢复,而是选择向其中添加一台新的服务器。Raft 共识算法也囊括了功能, 以达到自动配置且平滑过度的目的。

为了保证安全性,配置更新必须使用两阶段方案。两阶段方案有很多不同的实现。Raft 中,集群首先切换使用过渡期配置(transitional configuration),也称之为协同共识(joint consensus)。当协同共识被提交,系统则切换使用新的配置。协同共识整合了新旧配置,

  • 日志条目会被复制到所有不论新旧配置中的服务器上
  • 不论新旧配置中,任何服务器都有可能成为 leader
  • 选举和日志条目提交的共识,同时需要来自新旧配置中大多数服务器的确认

raft_configuration_update

集群配置作为特殊的条目被存储在多副本日志系统中。上图展示了配置变更生效的过程。当 leader 收到请求,更改配置从 C.old 到 C.new,它会把协同共识的配置 C.old,new 先存储到自己的日志为一个条目,然后以文章前面提及的方式将配置复制到集群中其他服务器上。一旦服务器添加新的配置条目成功,它便使用该配置。因此,leader 按照条目 C.old,new 描述的配置规则工作,并决定该条目是否为已提交状态。总之不论何种情况下,在该期间内 C.new 都无法做任何单方面的决定。

一旦配置条目被提交,C.new 和 C.old 如果没有彼此的同意,他们都无法做决定。而且,Leader Completeness Property 确保了只有日志中包含 C.old,new 条目的服务器才可能被推举为 leader。此时对 leader 来说,为新的配置 C.new 创建并复制日志条目到集群服务器是安全的。当新的配置被提交,新的配置也随之开始生效,旧的配置失效,不在新配置中的服务器也会离线。

当然,还有三个问题尚需解决。第一个是,新加入的服务器可能不包含任何日志条目。这种情况下,需要一定时间才能保持和集群中的大多数服务器同步。Raft 在配置变更前引入新的阶段,该阶段中的新加入的服务器没有投票权,但是它们仍旧可以复制日志条目。第二个问题,leader 有可能不在新的配置中。此时,leader 在提交 C.new 之后立即退位(成为 follower)。此时,leader 在提交 C.new 这段时间内,leader 管理的集群却不包含它自身。它确实在复制日志条目,确不把它自己计算在大多数里面。因此 Raft 中,leader 的身份转变发生在 C.new 被提交后。因为这一时间点是新配置可以独立运行的起始点。而在此之前,可能只有 C.old 中的服务器才能被推举为 leader。第三个问题则是,移除掉的服务器可能破坏集群。移除掉的服务器因为接收不到心跳,他们开始发起新一轮的 leader 竞选,而当前 leader 也被迫转变为 follower 身份,最终新的 leader 被推举出来。但是那些被移除的服务器会再次超时,循环整个上述过程。为了解决这个问题,如果某个服务器在当前 leader 响应的最小竞选超时时段内,收到一条 ReqeustVote RPC,它将不会更新任期值或者投票支持。这个规则不会影响到正常的竞选,因为正常的竞选下,各服务器在启动新一轮竞选前,会等待至少最小竞选超时的时间。

结语

Raft 已然在现实世界中有了广泛的应用,例如 TiDB 的 TiKV 和 etcd 中。当然,这些不同的案例都有它们各自的具体实现,甚至改进。但是核心的算法过程仍旧保持一致,如上所述。