算法类别

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 引言 我们的RCP系统中的每个客户端都会针对后端程序程序维持一个长连接发送请求。这些连接通常在客户端启动的时候就建立完成，并且保持活跃状态，不停地有请求通过它们，直到客户端终止。 每个连接都需要双方消耗一定数量的内存和CPU来维护。虽然这个消耗理论上很小，但是一旦数量多起来就可能变得很客观。 上面的两段话来自 在Golang中，每个连接除了接收和发送缓冲区，还会额外对应2个协程。在规模较大的服务中，浪费的资源是非常可观的。 在M个Client，N个Backend的场景中，一共需要建立M * N个连接。这种额外的负担不仅发生在Client端，同样影响会Backend。 一个很朴素的想法是让每个Client只请求所有Backend的一部分。那么划分子集之后，是否会引起其它问题呢？ 本文的重点是探讨使用Google给出的子集选择算法二：确定性算法，需要考虑的细节和注意事项。 2. 子集选择算法带来的思考 2.1 目标 当我们引入某个划分子集算法之后，我们担心的问题可能会有以下几个： 1) Backend的负载是否均衡 2) 当Backend集群发生变化(比如有实例宕机，或者进行滚动发布或者重启时，Client的连接池是否有大量的连接需要创建或者销毁 3) 当Backend集群发生变化(比如有实例宕机，或者进行滚动发布或者重启时，Client的请求时的错误率相比没有划分子集时，是否会变大 2.2 子集选择算法 2.2.1 随机选择 先来看看随机算法是否可行, 假定 clientSize=50 backendSize=100 subsetSize=50 生成图片用ggplot2 library(ggplot2) data <- read.table(“/tmp/datafile.csv”,header=TRUE, sep=”,”) ggplot(data, aes(X, Y)) +… 继续阅读 利用划分子集限制连接池的大小(1)

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 参考资料 1.1 In Search of an Understandable Consensus Algorithm 1.2 寻找一种易于理解的一致性算法 1.3 Raft协议精解 1.4 Raft协议动画演示 1.5 goraft/raftd The original project authors have created new raft implementations now used in etcd and InfluxDB. goraft/raftd的作者参与了etcd项目的实现，所以goraft/raftd是有参考价值的 。另外goraft/raftd的实现不完整，没有实现Log擦除等功能，因此不能用于生产环境。 2. Node的简单介绍 2.1 node的三种状态(state) 图1 有限状态自动机… 继续阅读 聊聊Raft协议

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 题目 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/super-ugly-number 编写一段程序来查找第 n 个超级丑数。超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例 输入: n = 12, primes = [2,7,13,19] 输出: 32 解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32]。 说明: 1 是任何给定 primes 的超级丑数。  给定 primes 中的数字以升序排列。 0 < k ≤ 100, 0 < n ≤… 继续阅读 算法题 LEECODE 313. 超级丑数

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 本文基于 Redis 3.2.0 前言 鲁班门前弄大斧，笔者今天要聊一下geohash。 redis/elasticsearch/mongoDB 中地理位置的搜索，比如某个位置，附近1公里内的POI点，类似这样的功能都是基于geohash算法实现的。 首先看看维基百科的定义 Geohash is a public domain geocode system invented in 2008 by Gustavo Niemeyer[1], which encodes a geographic location into a short string of letters and digits. It is a hierarchical spatial data structure… 继续阅读 聊聊GeoHash

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 笔者早几年的工作经历和爬虫相关，为防止重复抓取URL, 要对每个需要抓取的URL进行判重，由于每天待抓取的URL数量都在好几亿条。因此去重服务的压力很大，当时相关的小伙伴就曾经调研过布隆过滤器。 本文笔者将结合Google Guava的BloomFilter(com.google.common.hash.BloomFilter)，谈谈布隆过滤器的实现，以及它的一些特点。 2. 布隆过滤器简介 An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element… 继续阅读 聊聊布隆过滤器

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1.引子 哈希表的原理是用数组来保存键值对，键值对存放的位置（下标）由键的哈希值决定，键的哈希值可以在参数时间内计算出来，这样哈希表插入、查找和删除的时间复杂度为O(1)，但是这是理想的情况下，真实的情况是，键的哈希值存在冲突碰撞，也就是不同的键的哈希值可能相等，一个好的哈希函数应该是尽可能的减少碰撞。解决冲突碰撞的方法有分为两种：开放地址法和 链接法，这里不具体展开。哈希表一般都采用链接法来解决冲突碰撞，也就是用一个链表来将分配到同一个桶（键的哈希值一样）的键值对保存起来。 所谓的哈希碰撞攻击就是，针对哈希函数的特性，精心构造数据，使所有数据的哈希值相同，当这些数据保存到哈希表中，哈希表就会退化为单链表，哈希表的各种操作的时间复杂度提升一个数量级，因此会消耗大量CPU资源，导致系统无法快速响应请求，从而达到拒绝服务攻击（Dos）的目的。 绝大多数语言中map的默认实现都是HashMap，比如Golang、Python，Java有2种HashMap和TreeMap 2.攻击方法与防范机制 通过构造哈希值完全相同的字符串 比如 hash(str1) == hash(str2) 找到大量的哈希值相同的str1、str2、str3 … 这种攻击方法依赖的前提是hash函数本身是不变的。 那么如果hash函数是变化的，那么就会大大增加构造哈希值完全相同的字符串的难度。 由此衍生出方案1。 2.1 方案1 加salt 哈希值的计算变为 hash(salt + str) salt为特殊的字符串，一般都是固定值 由于salt是不对外暴露的，所以黑客构造哈希值完全相同的字符串的难度就增大了 2.2 方案2 可变的hash函数 如果hash函数本身就是可变的，那么黑客几乎无法构造哈希值完全相同的字符串。 我们来看Golang是怎么做的 type _type struct { … kind uint8 alg *typeAlg … }… 继续阅读 哈希碰撞攻击与防范机制

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 一直对遗传算法非常好奇，它是对自然界生物进化机制的计算机模拟。可以用于对NP问题的最优化求解。 在生活中，可以被用于排班、排课、路径优化，甚至可以被用于歌曲自动编写。 2. 问题分析 遗传算法的一个典型案例是针对旅行商问题。 旅行商问题，一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 我们从一个最简单的情况来说明这个问题。 例1：假定有A、B、C、D四个地点，坐标如上图 假定出发点是A点，那么所有的可能的路径是 ABCDA ABDCA ACBDA ACDBA ADBCA ADCBA 由于起点和终点都是A，是完全确定的；所以所有可能的路径就是B、C、D的全排列 共有n!中情况，此处n为3，共有6种情况 我们实际是在解空间中寻找最优解。 当n=20时 20！= 2,432,902,008,176,640,000 当n=21时，解空间的大小已经溢出了int64所能存储的空间 解空间相当大，以至于遍历一遍几乎是不大可能的 3. 遗传算法如何寻找最优解 事实上，遗传算法得到有可能得到最优解，也有可能得到次优解。 下面是遗传算法的完整过程 3.1 编码 让我们再回到例1，由于只有6种情况，那么解空间的取值范围就是 [0, 5] 假定如下的对应关系 BCD — 0 — 000 BDC… 继续阅读 使用遗传算法来解决旅行商问题

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 在我的文章聊聊RAFT的一个实现(3) 我曾经提到NOPCommand也是一种LogEntry，它会在集群中被分发。那么它有什么作用呢？ 2. NOPCommand 我们依然使用raft paper 5.4 Safety 图8来说明这个问题 2.1 场景1 如图所示，集群中有S1 ~ S5，5个节点，在时间点(A)，S1是leader, 它接收到外部的指令，生成logIndex 2的日志，并复制到S2。在时间点(B)S1奔溃了，S5在term 3通过S3、S4和自己的选票赢得选举，称为leader。它从客户端接收到一条不一样的日志条目放在logIndex 2。然后到时间点(C1), S5又崩溃了；S1重新启动，被选举为leader, 开始复制日志LogEntry{Term:2, Index:2} 到S3, 此时已经达到了提交点。LogEntry{Term:2, Index:2} 已经被复制到majority，可以向状态机中写入数据了。但是接下来时间点(D1) S1可能再次崩溃，S5重新启动，S5可以重新被选举成功(通过S3、S4以及它自己的选票)。然后复制日志LogEntry{Term:3, Index:2}到S2、S3、S4。 如果事情进展按上面的情况发生, 那么显然违反了raft论文所要求 Leader Completeness和State Machine Safety 领导人完全特性–如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中（5.4 节） 状态机安全特性–如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志（5.4.3 节） 2.2 场景2… 继续阅读 聊聊RAFT的一个实现(4)–NOPCommand

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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,… 继续阅读 聊聊raft的一个实现(3)–commit

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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… 继续阅读 聊聊Raft的一个实现(2)-日志提交