Distributed-Systems

序本文主要研究一下Election Algorithms Election AlgorithmsElection Algorithms大致有两类，一类是Garcia-Molina提出的Bully Election，一类是Chang & Roberts's Token Ring Election algorithm；对于大多数的election algorithms通常有如下几个假定： 完整的topology，信息可以在topology的nodes之间传递每个node有唯一的id，而且对整个topology其他node可见所有的通信网络是可靠的，只允许node fail，要求消息不丢失，不重复，不损坏要求已经有fail detector机制来处理node fail的情况Bully Election当有node检测到leader fail之后，就发送election request给其他node，election request中带上自己的id当node接收到election request时判断如果自己的id大于request中的id，则可以"bully"覆盖request中的id，如果小于则不改动，然后发送election request给其他node；当有node接收到election request的id是自己的node id时，则表明自己是leader，于是给其他node发送leader request当node接收到leader request时设置本地leader id，同时判断如果leader id不是自己的node id时则转发该leader request给其他nodeToken Ring Election当有node检测到leader fail之后，就发送election request给其他node，election request中带上自己的id当node接收到election request时，则判断自己的node id是否在里面，不在的话则追加自己的node id到election request中；如果自己的node id已经在该election request中时则提取这些node id，取出id最大的作为leader，然后给其他node发送leader request当node接收到leader request时设置本地leader id，同时判断如果leader id不是自己的node id时则转发该leader request给其他node实例这里采用distributedLeaderElection的实现Bully Election public void onMessage(String message) { String messageHeader = message.split(":")[0]; String messageBody = message.split(":")[1]; if (messageHeader.equals("Election")){ if (Integer.parseInt(messageBody.trim()) < Node.getMyID() // If we are a better candidate && !participant){ System.out.println("I " + Node.getMyID() + " am a better candidate than "+messageBody); Node.sendMsgToNextNode("Election" + ":" + Node.getMyID()); // Suggest us for election } else if (Integer.parseInt(messageBody.trim()) == Node.getMyID()) { // If this is our ID System.out.println("I " + Node.getMyID() + " received my own pebble, so I am the new leader"); Node.sendMsgToNextNode("Leader" + ":" + Node.getMyID()); // Announce us as the new leader } else { // The current candidate is better System.out.println("I " + Node.getMyID() + " am a worse candidate than "+messageBody); Node.sendMsgToNextNode(message); // Forward his candidancy } participant = true; } else if (messageHeader.equals("Leader")){ System.out.println(messageBody + " is the new leader"); leaderID = messageBody; if (Integer.parseInt(messageBody.trim()) != Node.getMyID()) Node.sendMsgToNextNode(message); } }可以看到bully算法在看到election request中node id小于自己node id时，直接bully覆盖该node id；当走了一圈发现请求中node id是自己的node id时，则选举自己为leaderToken Ring Election public void onMessage(String message) { String messageHeader = message.split(":")[0]; List<String> messageBody = Arrays.asList(message.replace(messageHeader+":", "").split(":")); if (messageHeader.equals("Election")){ if (!messageBody.contains(Node.getMyID()+"")){ // If we are not contained in the list System.out.println("I " + Node.getMyID() + " am not contained in this message "+message); Node.sendMsgToNextNode(message + ":" + Node.getMyID()); // Suggest us for election } else { // If we are in the list System.out.println("I " + Node.getMyID() + " am contained in this message"); String newLeader = findLeaderInBody(messageBody); Node.sendMsgToNextNode("Leader" + ":" + newLeader); // Announce the new leader } } else if (messageHeader.equals("Leader")){ String leaderBody = message.split(":")[1]; System.out.println(leaderBody + " is the new leader"); leaderID = leaderBody; if (Integer.parseInt(leaderBody.trim()) != Node.getMyID()) Node.sendMsgToNextNode(message); } } private String findLeaderInBody(List<String> messageBody) { int maxID = 0; if (messageBody.size() > 0){ for (String leaderCandidate : messageBody){ if (Integer.parseInt(leaderCandidate.trim()) > maxID) { maxID = Integer.parseInt(leaderCandidate.trim()); } } } return maxID+""; }可以看到ring算法是在请求中追加自己的node id；当走了一圈发现自己的node id已经在其中时，通过findLeaderInBody从这些node id中取出最大的那个，选举该node为leader小结Election Algorithms大致有两类，一类是Garcia-Molina提出的Bully Election，一类是Chang & Roberts's Token Ring Election algorithm对于大多数的election algorithms通常有如下几个假定： ...

序本文主要研究一下scalecube-cluster的MembershipProtocol MembershipProtocolscalecube-cluster-2.2.5/cluster/src/main/java/io/scalecube/cluster/membership/MembershipProtocol.java /** * Cluster Membership Protocol component responsible for managing information about existing members * of the cluster. */public interface MembershipProtocol { /** * Starts running cluster membership protocol. After started it begins to receive and send cluster * membership messages */ Mono<Void> start(); /** Stops running cluster membership protocol and releases occupied resources. */ void stop(); /** Listen changes in cluster membership. */ Flux<MembershipEvent> listen(); /** * Returns list of all members of the joined cluster. This will include all cluster members * including local member. * * @return all members in the cluster (including local one) */ Collection<Member> members(); /** * Returns list of all cluster members of the joined cluster excluding local member. * * @return all members in the cluster (excluding local one) */ Collection<Member> otherMembers(); /** * Returns local cluster member which corresponds to this cluster instance. * * @return local member */ Member member(); /** * Returns cluster member with given id or null if no member with such id exists at joined * cluster. * * @return member by id */ Optional<Member> member(String id); /** * Returns cluster member by given address or null if no member with such address exists at joined * cluster. * * @return member by address */ Optional<Member> member(Address address);}MembershipProtocol接口定义了start、stop、listen、members、otherMembers、member方法MembershipProtocolImplscalecube-cluster-2.2.5/cluster/src/main/java/io/scalecube/cluster/membership/MembershipProtocolImpl.java ...

序本文主要研究一下scalecube-cluster的FailureDetector FailureDetectorscalecube-cluster-2.2.5/cluster/src/main/java/io/scalecube/cluster/fdetector/FailureDetector.java /** * Failure Detector component responsible for monitoring availability of other members in the * cluster. This interface is supposed to be used internally as part cluster membership protocol. It * doesn't specify that particular node is failed, but just provide information that either it is * suspected or trusted at current moment of time. So it is up to cluster membership or other top * level component to define when suspected member is actually failed. */public interface FailureDetector { /** * Starts running failure detection algorithm. After started it begins to receive and send ping * messages. */ void start(); /** Stops running failure detection algorithm and releases occupied resources. */ void stop(); /** Listens for results of ping checks (ALIVE/SUSPECT) done periodically by failure detector. */ Flux<FailureDetectorEvent> listen();}FailureDetector定义了start、stop、listen方法FailureDetectorImplscalecube-cluster-2.2.5/cluster/src/main/java/io/scalecube/cluster/fdetector/FailureDetectorImpl.java ...

序本文主要研究一下SWIM Protocol SWIM ProtocolSWIM的全称是Scalable, Weakly-Consistent, Infection-Style, Processes Group Membership Protocol heartbeats传统的诸如heartbeats这种membership protocols，每个node周期性地向网络中的所有其他节点发送heartbeat来表示自己是alive的，如果peer超过指定interval没有收到node的heartbeart则该node被认定为dead。这种方式适用于小型网络，其发送的heartbeart数量为O(n^2)，当网络中有成千上万的node时则会造成巨大的网络负担；SWIM采用Infection-Style dissemination来解决这个问题tasks与传统的heartbeats相比，SWIM将整个过程分为Failure Detection及Membership update Dissemination两个task Completeness与Accuracy对于failure detection来，有几个衡量标准： Completeness是否每个failed node最终都会被检测到Speed of failure detection一个node从failed到被检测到failed的平均耗时Accuracyfalse positive rate，即一个node被误判为failed的概率Message Load在检测中每个node的network load是多少，是否均匀分布Unreliable Failure Detectors for Reliable Distributed Systems一文中指出对于异步的网络来说，100%的Completeness与Accuracy无法同时保证，因而SWIM权衡之下选择了Completeness，同时尽可能减少false positive rate以提升Accuracy Failure DetectionSWIM的failure detection过程分为两个部分，一个是direct ping，一个是indirect ping direct pinglocal node从alive nodes中随机选择N个node来进行detect；如果direct ping中有的node没有在timeout时间内返回ack则会进行indirect pingindirect pinglocal node从alive nodes中随机选择K个node来对direct ping目标node进行indetect ping，这K个node会把结果forwards给这个local node，最后local node检查如果这个K个node没有一个返回ack，则将该目标node标记为failed，然后通过Membership update Dissemination将该node的FAILED信息传播到网络中的其他nodeMembership update DisseminationMembership update Dissemination可以将messages分为JOINED、FAILED两类： JOINED当一个node加入到该网络时，需要通知其他node更新local membership新增该nodeFAILED当一个node被检测为failed时，需要通知其他node更新local membership移除该node这个过程可以使用multicast来实现 改进Infection-Style Disseminationmulticast实现的Dissemination是不可靠的而且低效的，一个更加robust版本的SWIM采用Infection-Style的方式进行dissemination，即利用Failure Detection的ping机制，将需要dissemination的消息piggyback在ping/ack上，来实现类似gossip的消息传播，从而减少额外的单独信息传递开销 Suspicion Mechanism为了更好地减少false positive rate以提升Accuracy，可以引入Suspicion Mechanism，即当local node检测到该node failed时将其标记为suspected；被标记为suspected的node在最终被确认为failed之前被当做是alive；其他node如果检测到该node是alive则对该node取消suspected，恢复alive；如果在指定时间该node没有被恢复为alive则被标记为failed ...

过去几年容器逐渐成为了打包和部署代码的流行的方式。容器镜像解决很多现有的打包和部署工具所带来的问题，初次以外，还为我们提供了构建分布式应用的全新的思路。就如SOA提倡将应用拆分为模块化的内聚的服务，容器应当进一步提倡将这些服务拆分为紧密协作的模块化容器。通过构建应用边界，容器使用户能够使用模块化，可重用的组件构建其服务，从而使得服务比单机容器构建的应用程序更可靠，更具可扩展性并且构建速度更快。从VM向容器的演变从各种角度来说就如同当年从单机应用转化为模块化的面向对象的应用程序。容器镜像提供的抽象层与面向对象编程中类的抽象边界有很大的共同点，而且也提高了开发者的效率和程序的质量。就像正确的编码方式是将关注点分离为模块化对象一样，在容器中打包应用程序的正确方法是将关注点分离为模块化容器。根本上来说，这意味着不仅要将整个应用程序分解，而且要将任何一个服务器中的各个部分分解为多个模块化容器，这些容器易于参数化和重复使用。这就像现代语言中的标准语言库，大多数应用程序开发人员可以将由其他人编写的模块化容器组合在一起，并使用更高质量的组件更快地构建应用程序。从模块化容器方面进行思考的好处很多，特别是模块化容器提供以下内容：加快应用的开发，因为容器可以在团队甚至是大型社区之间进行复用支持敏捷团队，因为容器边界是一个天然的边界，划分给各个团队。支持关注点分离，并专注于开发特定功能从而减少复杂的依赖和不可测试组件。从模块化容器构建应用程序意味着考虑协作提供服务容器的共生组，而不是一个容器提供一个服务。在Kubernetes中，这种模块化容器服务的实施者是Pod。一个Pod是指一组共享文件系统，内核命名空间和IP地址的一组容器。Pod在K8s集群中是调度的基本单位，正是因为Pod中容器的共生特性要求它们共同安排在同一台机器上，而可靠地实现这一点的唯一方法是将容器组作为原子调度单元。当你从Pod的角度思考时，自然会出现一些模块化应用程序开发的通用模式，这些模式会多次重复出现。我相信，随着我们在Kubernetes的开发中向前发展，将会发现更多这些模式，但这里有三个我们常见的模式：例子1：Sidecar容器Sidecar容器拓展并且加强主容器，他们融合当前已有的容器并且将它们完善。举个例子，假设有一个运行这Nginx web应用的容器。添加另一个容器将文件系统与git仓库同步，在容器间共享文件系统，从而实现git的提交并部署。但是这种模块化实现使得git同步器可以交给另一个容器开发，并且跨不同的web服务器复用。因为这种模块化，你只需要编写并测试单个git同步应用并且提供给多个应用使用。而如果有别的团队开发了这个工具，你甚至不需要重复开发。例子2：Ambassador容器Ambassador容器代理外界至本地的连接。比如，现在有一个Redis集群，包含多个读者和单个写者。 你可以创建一个Pod，包含主应用和Redis ambassador容器。ambassador容器作为代理分离读写请求分别交给对应的服务器。因为这两个容器共享一个网络命名空间，即他们共享一个IP地址，因此主应用可以用localhost访问ambassador服务，无需通过服务发现。从主应用的视角来看，就仿佛在localhost上连接了redis集群。这种方式非常方便，不仅因为不同的团队可以管理自己的组件，而且因为在开发环境中，你可以跳过代理，直接连接到Redis集群上。例子3：Adapter容器Adapter容器标准化输入输出。假设现在需要监控N个应用，每个应用可能使用了不同的方法来输出监控数据（比如JMX, StatsD等）。但是每个监控系统都希望用一个一致的数据模型来管理收集的数据。通过使用Adapter模式来组合容器，你可以创建一个pod将应用容器和适配器容器组合起来，从而将同质的监控数据转化为单个同一个的表现形式。同样的，因为这些Pod共享命名空间和文件系统，这两个容器间的协作简单明。RefrenceSidecar PatternAmbassador Pattern