算法

在这篇文章中，萌叔将介绍RAG技术。 将它与传统的搜索引擎进行对比，并介绍一个完整的RAG实现–lightRAG，详述其技术细节。 1. 传统搜索 传统搜索通常基于倒排索引来进行搜索 1.1 倒排索引 倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案， 是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。 倒排索引是Term到DocID的映射。 1.2 搜索语句示例 Lucene针对某个字段进行搜索样例 title:hello world 就意味着，搜索title为hello，或者包含title关键字的文档 伪代码形如 doc.title contains "hello" OR doc.title contains "world" 假定 “hello”-> [1, 5, 8] “world”-> [5, 8, 10, 12] 然后搜索引擎对2个doc ID集合的求并集，并对所有文档进行打分，选出分数最高的前N个文档。 2. RAG RAG (检索增强生成) 是一种人工智能技术，它结合了信息检索和生成式模型的功能， 以提高生成文本的准确性和相关性。 RAG 先从外部知识库中检索相关信息，然后结合这些信息，使用生成式模型， 生成更准确、更有上下文相关的文本。 提到RAG，需要先聊一聊Embedding models 2.1 Embedding models 2.1.1 高维向量表征文本 嵌入式模型，可以把一段文本转换为纯数值的高维向量 通过嵌入模型(如bge-m3)将文本转换为1024维的数值向量，这个向量包含了文本的语义特征 curl --location 'http://192.168.100.2:21434/api/embed' \ --header 'Content-Type: application/json' \ --data '{ "model": "bge-m3:latest", "input": "这个故事的主题是什么?" }' 2.1.2 向量距离反映语义相似度 当两个向量在向量空间中的距离越近（通常用余弦相似度或欧氏距离衡量） 说明它们对应的文本在语义上越相似 例如"猫"和"猫咪"的向量会比"猫"和"汽车"的向量更接近 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1.引言 topk问题是十分经典的算法问题，它的核心是从大量数据中找出前k个最大或者最小的元素。 它对于提高缓存的命中率，以及发现新增热点的发现有很大的帮助。 对于topk问题而言， 如果庞大的数据集本身是固定的，萌叔觉得topk问题本身还不算复杂， 顶多算是一个大数据计算的问题。 但如果这个庞大的数据集本身就处于变化中，不断在新增元素， topk问题就会变得非常复杂。 2023年萌叔看到一篇B站的文章，介绍了B站使用的heavykeeper算法来计算topk问题，取得了比较好的效果。 本文不是纯粹意义上的介绍heavykeeper算法的，萌叔想探讨一下里面的设计理念。 heavykeeper 对应的参考实现见参考资料4 B站给出的试验结果数据 2.数据结构 heavykeeper的设计目标是解决高流速情况下的topk问题且topk的元素出现的频率必须显著高于其它元素。 互联网数据大体满足二八定律，是符合要求的。 1）heavykeeper使用的d行w列的二维数组， 2）流体中的每个元素在 每一行上都有一个对应的位置，由哈希函数决定，哈希函数从h1()、h2() 到 hd() 这个数据结构与Count-Min Sketch算法是非常像的，唯一的区别是heavykeeper中二维数组的bucket，是一个结构体 type bucket struct { fingerprint uint64 // 比Count-Min Sketch算法多出来的字段 count uint64 } 3.处理逻辑 对应代码 heavy_keeper.go func (topk *TopK) jobAdder() { for item := range topk.items { itemFingerprint := xxhash.Checksum64S(item, uint64(topk.seed)) var maxCount uint64 itemHeapIdx, itemHeapExist := topk.minHeap.Find(item) heapMin := topk.minHeap.Min() // compute d hashes for i := uint32(0); i < topk.depth; i++ { bI := make([]byte, 4) binary.LittleEndian.PutUint32(bI, uint32(i)) bucketNumber := xxhash.Checksum64S(append([]byte(item), bI...), uint64(topk.seed)) % uint64(topk.width) topk.buckets[i][bucketNumber].mu.Lock() fingerprint := topk.buckets[i][bucketNumber].fingerprint count := topk.buckets[i][bucketNumber].count if count == 0 { // Case 1 topk.buckets[i][bucketNumber].fingerprint = itemFingerprint topk.buckets[i][bucketNumber].count = 1 maxCount = max(maxCount, 1) } else if fingerprint == itemFingerprint { // Case 2 if itemHeapExist || count <= heapMin { topk.buckets[i][bucketNumber].count++ maxCount = max(maxCount, topk.buckets[i][bucketNumber].count) } } else { // Case 3 decay := math.Pow(topk.decay, float64(count)) if rand.Float64() < decay { topk.buckets[i][bucketNumber].count-- if topk.buckets[i][bucketNumber].count == 0 { topk.buckets[i][bucketNumber].fingerprint = itemFingerprint topk.buckets[i][bucketNumber].count = 1 maxCount = max(maxCount, 1) } } } topk.buckets[i][bucketNumber].mu.Unlock() } // update heap if itemHeapExist { topk.minHeap.Fix(itemHeapIdx, maxCount) } else { topk.minHeap.Add(minheap.Node{ Count: maxCount, Item: item, }) } } } 3.1 众数问题 看到上面的处理逻辑，很多读者可能会感到懵，为什么这样做就可以找出topk的元素？ 为了解释heavykeeper的设计理念，我们先来看一个求众数问题 LeetCode 第169题 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 引言 我们的RCP系统中的每个客户端都会针对后端程序程序维持一个长连接发送请求。这些连接通常在客户端启动的时候就建立完成，并且保持活跃状态，不停地有请求通过它们，直到客户端终止。 每个连接都需要双方消耗一定数量的内存和CPU来维护。虽然这个消耗理论上很小，但是一旦数量多起来就可能变得很客观。 上面的两段话来自 在Golang中，每个连接除了接收和发送缓冲区，还会额外对应2个协程。在规模较大的服务中，浪费的资源是非常可观的。 在M个Client，N个Backend的场景中，一共需要建立M * N个连接。这种额外的负担不仅发生在Client端，同样影响会Backend。 一个很朴素的想法是让每个Client只请求所有Backend的一部分。那么划分子集之后，是否会引起其它问题呢？ 本文的重点是探讨使用Google给出的子集选择算法二：确定性算法，需要考虑的细节和注意事项。 2. 子集选择算法带来的思考 2.1 目标 当我们引入某个划分子集算法之后，我们担心的问题可能会有以下几个： Backend的负载是否均衡 当Backend集群发生变化(比如有实例宕机，或者进行滚动发布或者重启时，Client的连接池是否有大量的连接需要创建或者销毁 当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)) + geom_bar(stat = 'identity') subset/random/random.go 显然随机算法的效果不行 2.2.2 确定性算法 func Subset(backends []string, clientID, subsetSize int) []string { subsetCount := len(backends) / subsetSize // Group clients into rounds; each round uses the same shuffled list: round := clientID / subsetCount r := rand.New(rand.NewSource(int64(round))) r.Shuffle(len(backends), func(i, j int) { backends[i], backends[j] = backends[j], backends[i] }) // The subset id corresponding to the current client: subsetID := clientID % subsetCount start := subsetID * subsetSize return backends[start : start+subsetSize] } 只有短短几行，我们来下效果 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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 有限状态自动机 Leader Candidate Follower 2.2 各种存储 2.2.1 Write-Ahead Log（WAL） 存储:文件 4f raft:join">{"name":"2832bfa","connectionString":"http://localhost:4001"} e raft:nop 4f raft:join">{"name":"3320b68","connectionString":"http://localhost:4002"} 4f raft:join">{"name":"7bd5bdc","connectionString":"http://localhost:4003"} e raft:nop 29 write"{"key":"foo","value":"bar"} 29 write"{"key":"aaa","value":"bbb"} 29 write"{"key":"bbb","value":"ccc"} 29 write"{"key":"ddd","value":"eee"} e raft:nop e raft:nop 29 write"{"key":"foo","value":"bar"} 29 write"{"key":"foo","value":"bar"} 2.2.2 状态信息(状态信息) commitIndex、peer等 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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 ≤ 106, 0 < primes[i] < 1000 。 第 n 个超级丑数确保在 32 位有符整数范围内。 解题思路1 由于这是一道中等难度的题目，萌叔第一想到的是穷举，从1开始穷举，1、2 3、… N 判断每个数是否是超级丑数。这个思路肯定是没错的，结果提交后发现超时了。超时的原因是扫描了太多无用的数据。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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 which subdivides space into buckets of grid shape, which is one of the many applications of what is known as a Z-order curve, and generally space-filling curves. ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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 to one of the m array positions, generating a uniform random distribution. 布隆过滤器由一个m位的bitArray以及k个hash函数组成。m和k的具体值可以由布隆过滤器中预期存储的数据量n，以及可能出现假阳性概率p决定。 待存储的数据经过1个hash函数作用，并会将bitArray中的某一位置成1 k个hash函数最多会将bitArray中k位置成1 如上图所示,假定k=2 hash_func1将bitArray[3]=1 hash_func2将bitArray[8]=1 如果想判断数值1990是否在布隆过滤器中，只需要重新执行hash_func1和hash_func2，如果第3位和第8位都是1，那么1990可能在布隆过滤器中(存在假阳性的可能)，反之第3位和第8位有1位为0，则1990一定不在布隆过滤器中。 可以换一个角度来解释布隆过滤器，每个hash函数都在尝试提取数据值的一部分特征。存储数据的过程(置1)，实际是在标记，布隆过滤器中至少包含一个元素满足特定的特征。如果有一个特征不满足，那么该数据一定不在布隆过滤器中。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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 ... } 每个类型都有其对应的typeAlg // typeAlg is also copied/used in reflect/type.go. // keep them in sync. type typeAlg struct { // function for hashing objects of this type // (ptr to object, seed) -> hash hash func(unsafe.Pointer, uintptr) uintptr // function for comparing objects of this type // (ptr to object A, ptr to object B) -> ==? equal func(unsafe.Pointer, unsafe.Pointer) bool } var algarray = [alg_max]typeAlg{ ... alg_STRING: {strhash, strequal}, alg_INTER: {interhash, interequal}, alg_FLOAT32: {f32hash, f32equal}, alg_FLOAT64: {f64hash, f64equal}, alg_CPLX64: {c64hash, c64equal}, ... } func strhash(a unsafe.Pointer, h uintptr) uintptr { x := (*stringStruct)(a) return memhash(x.str, h, uintptr(x.len)) } 最终我们可以看到 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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 – 1 – 001 CBD – 2 – 010 CDB – 3 – 011 DBC – 4 – 100 DCB – 5 – 101 解被转换为数值以后，就可以使用2进制进行表示 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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引入了空命令NOPCommand Upon election: send initial empty AppendEntries RPCs (heartbeat) to each server; 一旦选举为leader, leader应该立马发送一个空命令给其它所有节点。 ...