分布式系统中的延续复杂性：回调地狱

### 分布式系统中的延续复杂性：回调地狱 #### 1. 引言 如今，对分布式系统进行建模、编程和验证是一个复杂的问题，需要高级技能。多线程编程、锁和并发控制会使中间件库的开发变得相当复杂。一般来说，使用回调来编写基于事件的系统是一项具有挑战性的任务，因为不同的代码片段需要操作相同的数据，而且执行顺序不可预测，这使得回调协调变得复杂。 在文献中，回调管理问题被称为“回调地狱”。对Adobe桌面应用程序的最新分析表明，事件处理逻辑几乎导致了近一半报告的错误。尽管这个问题通常与用户界面代码相关，但“回调地狱”在分布式系统的开发中也非常重要。许多分布式系统，如Actor库、基于事件的模拟器和基于事件的服务器库（如node.js）都采用异步编程风格。 分布式协议的异步事件性质意味着使用消息处理程序和回调的代码会变得混乱，难以理解和维护。当分布式算法依赖于远程过程调用（RPC）语义时，问题会变得更糟，因为这需要在消息之间进行复杂的状态维护。在这种情况下，用顺序代码和RPC编写的简洁算法必须拆分成多个单独的回调，回调就像为分布式系统重新设计的老式goto语句。 本文首先识别并形式化了所谓的延续复杂性问题，即当同步RPC代码必须转换为异步消息和处理程序时出现的问题。同时，为Actor库提出了解决延续复杂性问题的方案，即一种新颖的并行调用抽象，允许对其他Actor进行阻塞同步调用，而不会使当前Actor的控制线程停滞。最后，通过实现一个著名的分布式算法——基于环的结构化覆盖网络（Chord）来验证该方法的简单性。 #### 2. 延续复杂性问题 延续复杂性问题出现在分布式系统中，当同步RPC代码必须转换为异步消息和处理程序时就会产生。之所以称为延续复杂性，是因为它与编程语言中的延续概念直接相关。在分布式环境中，开发者在使用消息和处理程序（回调）将同步调用拆分成不同代码片段时，实际上是在隐式地实现自己的延续。通常，编程语言使用调用栈来存储函数使用的变量，但在这种情况下，开发者必须在不同消息之间显式地维护这些信息。 使用回调编程基于事件的系统的复杂性在交互式用户界面系统中也很重要。例如，最近解决“回调地狱”的一种方法是响应式编程范式。在.NET平台上，强大的async和await抽象也能简化异步编程，提高代码的清晰度，从而减少“回调地狱”问题，但这些抽象对开发者来说并非透明的，也不适用于单线程的Actor库。 在分布式系统中，有两种主要的编程模型可以帮助处理异步事件编程：分布式状态机和Actor库。分布式状态机是实现分布式系统的经典形式化模型，Macedon是一种简洁的领域特定语言（DSL），旨在涵盖分布式系统的整个生命周期。Actor模型为许多中间件解决方案提供了灵感，它提供了一种优雅的并发通信模型，将Actor视为并发计算的通用原语。 延续复杂性是基于RPC语义的分布式系统中的常见问题，如点对点（P2P）算法和覆盖网络（如Chord或Kademlia）、共识算法（如Paxos或2PC）和分布式应用程序（如键值存储或复制算法）。一个函数的延续复杂性直接取决于该函数内部的RPC数量以及包含RPC的迭代器数量。每个RPC会产生三个新的代码片段：两个用于延续，一个用于超时代码。此外，包含RPC的迭代器也会增加复杂性，因为响应处理程序必须在每次响应中控制迭代的状态。 延续复杂性与包含RPC的方法的圈复杂度直接相关。当方法的控制流非常复杂（高圈复杂度）时，延续复杂性也会很高，此时必须使用消息和消息处理程序重建原始的控制流。 ##### 2.1 一个简单的例子：Chord 许多分布式系统广泛使用RPC。使用面向对象的符号描述它们的算法很直接，因为在节点中调用方法意味着对该节点进行RPC。Chord分布式路由算法就是一个很好的例子。 Chord将节点组织成一个结构化的环形覆盖网络，每个节点都包含一个本地路由表，引用其他节点。Chord也被定义为分布式哈希表（DHT）或基于键的路由（KBR）层，因为通过一致性哈希，标识符空间在节点之间均匀分布。在Chord中，路由算法是顺时针的，每个节点负责环形覆盖网络中自己和其前一个节点之间的标识符。 以下是Chord路由机制的算法： ```plaintext Algorithm 1. Chord Routing Mechanism function find predecessor(id) n1 ← this node while id is not between (n1, n1.successor] do n1 ← n1.closest preceding finger(id) return n1 function closest preceding finger(id) for i ← N down to 1 do ```