算法

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 我在 聊聊raft的一个实现(2) 中的文末曾提到 只要client等到leader完成Commit动作。即使后续leader发生变更或部分节点崩溃，raft协议可以保证，client所提交的改动依然有效。 本文将举个例子，来说明一下。 2. 示例 如下图，假定cluster中有S1、S2、S3、S4、S5共5个节点，每个方格表示一条日志，方格中的数字是日志对应的term, 当前的leader是S1 commitIndex表示当前已经提交的日志，也就是成功同步到majority的日志位置(LogIndex)的最大值。 至少有3个node包含了LogIndex1、2、3，因此commitIndex的值是3 参看raft/server.go的processAppendEntriesResponse 函数了解commitIndex的计算方法 // Determine the committed index that a majority has. var indices []uint64 indices = append(indices, s.log.currentIndex()) for _, peer := range s.peers { indices = append(indices, peer.getPrevLogIndex()) } sort.Sort(sort.Reverse(uint64Slice(indices))) // We can commit up to the index which the majority of the members have appended. commitIndex := indices[s.QuorumSize()-1] committedIndex := s.log.commitIndex if commitIndex > committedIndex { // leader needs to do a fsync before committing log entries s.log.sync() s.log.setCommitIndex(commitIndex) s.debugln("commit index ", commitIndex) } 想象一个最糟糕的场景S1、S2，因为某种原因同时崩溃了。在goraft中，节点即使崩溃，也不会从peers中删除，也就是说cluster中节点的数目没有发生变化，要想保证剩下的节点能够正常选出leader，节点的数量不能少于3(集群节点总数/2 + 1)。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 在我的上一篇文章聊聊Raft的一个实现(1)，我简要的介绍了 goraft/raftd。这篇文章我将结合goraft的实现，来聊聊raft中的一些场景 2. 场景1-正常的执行1条WriteCommand命令 在上一篇文章，我们已经提到WriteCommand和NOPCommand、JoinCommand一样，对goraft而言都是LogEntry, 执行它时，这条命令会被分发到整个Cluster，让我们看看其中的详细过程 当前我们有3个node |节点|state|name|connectionString|term|lastLogIndex|commitIndex| |:—|:—|:—|:—|:—|:—| |node1|leader|2832bfa|localhost:4001|17|26|26| |node2|follower|3320b68|localhost:4002|17|26|26| |node3|follower|7bd5bdc|localhost:4003|17|26|26| 从上表可以看出整个集群处于完全一致的状态，我们开始执行WriteCommand step1 client:通过API提交WriteCommand命令 curl -XPOST http://localhost:4001/db/aaa -d 'bbb' step2 node1:收到指令后，生成LogEntry 写入logfile (磁盘文件) 2）添加到Log.entries (内存) step3 node1:等待Heartbeat(周期性由leader发往其它每个node1和node2), 把LogEntry带给其它node（这里的node1，node2状态相同，所以AppendEntriesRequest是一样的） AppendEntriesRequest { "Term": 17, "PrevLogIndex": 26, "PrevLogTerm": 17, "CommitIndex": 26, "LeaderName": "2832bfa", "Entries": [{ "Index": 27, "Term": 17, "CommandName": "write", "Command": "eyJrZXkiOiJhYWEiLCJ2YWx1ZSI6ImJiYiJ9Cg==" }] } 这里对PrevLogIndex做下简单的解释，PrevLogIndex表示的是leader所认为的follower与leader保持一致的最后一个日志index。PrevLogTerm是与PrevLogIndex对应的term。 Command做了base64编码解码后 { "key": "aaa", "value": "bbb" } 现在解释下上面的AppendEntriesRequest，node1(leader)告诉node2(follower) 如果LogIndex 26, 咱们是一致的, 那么Append LogIndex 27 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 最近花了不少时间来学习raft相关的知识，写这篇文章的目的 1）为了对raft中让我困惑的问题进行总结 为了对其它人的阅读便利，提供必要的帮助 网上raft的实现不少，但能够独立运行的样本工程实在不多。我选择的是 goraft/raftd raft的paper是为数不多的连实现都写的比较清楚的文档，因此在阅读本文前，请确保你已经大致了解过raft的协议 2. 概述 goraft/raftd 依赖 goraft/raft, goraft/raft是分布式一致性算法raft的实现，而goraft/raftd 已经可以称之最简单的分布式key-value数据库(服务)了 聊到一个服务，我们最常用的手法， 看它的接口。 看它的数据如何存储，包括内部的数据结构，数据如何落地 2.1 接口 接口大致可以分为2组 2.1.1 HTTP之上RPC协议 这其实goraft的作者对raft协议所要求的几个RPC的实现，包括 AppendEntries RPC RequestVote RPC Snapshot RPC （非raft协议要求的） SnapshotRecovery RPC （非raft协议要求的） 2.1.2 普通的HTTP API POST /db/{key} 写入key-value curl -XPOST localhost:4001/db/foo -d 'bar' GET /db/{key} 读取key对应的value curl localhost:4001/db/foo POST /join 把某个节点加入集群 curl http://localhost:4001/join -d '{"name":"5f2ac6d","connectionString":"http://localhost:4001"}' 这里有3个有趣的事情 1）这个节点可以是虚假的节点 2）由于JoinCommand 本身也是一条LogEntry, 所以当这条消息被发给Leader时，Cluster中的所有成员都会知道有一个新节点的加入(加入 raft.Server.peers) 3) 1个节点掉线后，它不会从raft.Server.peers移除 为了便于观察raft.Server的内部状态 我又扩充了3个接口 传送门vearne/raftd ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 前言 最近打算给我的博客做个性化推荐，初步选定使用关联规则算法来实现。 常见关联规则算法又有Apriori算法、FP-树频集算法、Eclat算法 3种。 请务必阅读参考资料1，了解Support(支持度), Confidence(置信度)， Lift（提升度） Association rules are usually required to satisfy a user-specified minimum support and a user-specified minimum confidence at the same time. Association rule generation is usually split up into two separate steps: A minimum support threshold is applied to find all frequent itemsets in a database. A minimum confidence constraint is applied to these frequent itemsets in order to form rules. While the second step is straightforward, the first step needs more attention. ...