分类默认分类下的文章

GoFound核心源码浅析

作者: nbboy
时间: 2022-07-28
分类: 默认分类
评论

### 1.索引文档的过程

1）词典结构怎么表示 2）文档怎么存储 3）索引列表怎么存储

1）,3）首先对用户的查询进行分词，比如分词结果为S = {w1, w2, w3}，然后对w1进行分片计算Hash槽，分片算法为StringsToInt(w1) % Shard，目前分为10个Hash槽，这样做是为了把所有词典均匀分散开，类似分库的原理，而且这10个“库”的数据文件是分开存储的。根据w1从数据文件中能够获得索引列表，这些索引列表是由文档ID组成。在索引文档的时候，如果该文档ID不在这个索引列表中，就添加进去，值得一提的是ID的查找算法用的是二分查找算法。

![](https://chenxf.org/usr/uploads/2022/07/2175406851.png)

Figure1 倒排索引

2）文档存储也是采用分区存储，也同样存在leveldb中，分区ID计算方法为DocID % Shard。文档存储就以键为分区ID，值为文档内容进行存储，另外为了计算相关性，存储了键为分区ID，值为文档分词序列的正排索引。

![](https://chenxf.org/usr/uploads/2022/07/4240150671.png)

Figure2 文档存储

![](https://chenxf.org/usr/uploads/2022/07/247337852.png)

Figure3 分词存储，用来计算相关性

### 2.检索文档的过程

1）索引列表怎么合并和排序

读取词的倒排列表，合并后计算词的文档频率，并且根据这个值进行倒序，这个实现只考虑了文档频率，并没有考虑词的频率。计算分页的文档后，从库中获取文档内容返回给前端，整个实现过程还是非常简单。

![](https://chenxf.org/usr/uploads/2022/07/1497425236.png)

Figure4 比如检索"伟大人民",首先会对检索语句进行分词,分为“伟大”和“人民”，然后在倒排索引里获取这两个词的倒排列表。接下来第一步倒排列表会先放在一起，再进行排序，第二步会用一个散列表算出每个文档频率，第三步对这个散列表按照文档频率进行排序。

### 3.源码
[gofound](https://github.com/sea-team/gofound "gofound")

让我们一起构建全文搜索引擎(引用)

作者: nbboy
时间: 2022-07-28
分类: 默认分类
评论

> 在搜索资料的时候感觉这篇文章对入门《搜索引擎》还不错，所以翻译了一下，在此保留。

## 让我们一起构建全文搜索引擎

全文搜索引擎我们每天都会使用的一种工具，只不过我们没有意识到它。如果你以前在Google搜索过golang覆盖率报告，或者在购物网站搜索过室内摄像头，你就一定使用过某种类型的全文搜索引擎。

全文搜索引擎是一种在许多文档中搜索文本的技术。一个文档可以是网页，或者新闻文章，邮箱页面，或者任何结构化的信息。今天我们会构建自己的全文搜索引擎。在文末结束的时候，我们能够在少于毫秒的时间内搜索百万级别的文档。从像简单的“返回包含单词猫的所有文档”和扩展搜索引擎支持更加复杂的布尔查询。

### 为什么是全文搜索

在开始写代码之前，你可能会问“我们为什么不用Grep或者用循环检测每个文档是否包含某个词语？”，是的，我们能这样做，然而这个不是一个好主意。

### 本文的文档集

我们将搜索英文Wikipedia的部分文档。最后的转储在[dumps.wikimedia.org](https://dumps.wikimedia.org/enwiki/latest/enwiki-latest-abstract1.xml.gz)，大概到今天，解压缩后大小为913MB,所有的XML文件包含600K文档。

文档例子为：

```xml
<title>Wikipedia: Kit-Cat Klock</title>
<url>https://en.wikipedia.org/wiki/Kit-Cat_Klock</url>
<abstract>The Kit-Cat Klock is an art deco novelty wall clock shaped like a grinning cat with cartoon eyes that swivel in time with its pendulum tail.</abstract>
```

### 加载文档

首先从转储中加载所有的文档，在Golang中使用encoding/xml包可以很方便做到这点。

```go
import (
    "encoding/xml"
    "os"
)

type document struct {
    Title string `xml:"title"`
    URL   string `xml:"url"`
    Text  string `xml:"abstract"`
    ID    int
}

func loadDocuments(path string) ([]document, error) {
    f, err := os.Open(path)
    if err != nil {
        return nil, err
    }
    defer f.Close()

dec := xml.NewDecoder(f)
    dump := struct {
        Documents []document `xml:"doc"`
    }{}
    if err := dec.Decode(&dump); err != nil {
        return nil, err
    }

docs := dump.Documents
    for i := range docs {
        docs[i].ID = i
    }
    return docs, nil
}
```

每个加载的文档都被分配一个唯一的标识符,为简单起见，第一个加载的文档被分配 ID=0，第二个 ID=1，依此类推。

### 初体验

##### 搜索内容

现在我们已将所有文档加载到内存中，我们可以尝试查找有关猫的文档。首先，让我们遍历所有文档并检查它们是否包含子字符串 cat：

```go
func search(docs []document, term string) []document {
    var r []document
    for _, doc := range docs {
        if strings.Contains(doc.Text, term) {
            r = append(r, doc)
        }
    }
    return r
}
```

在我的笔记本电脑上，搜索需要 103 毫秒 - 还不错。但是如果我们检查搜索的结果，就发现有点问题，比如用该函数可能包含了*caterpillar*和*category*，但是不包含包含大写C的Cat，当然这个不是我们想要的。

所以，在继续之前，我们需要解决两件事：

- 搜索结果对大小写不敏感
- 匹配单词边界而不是子字符串（比如*caterpillar*和*communication*就不能被匹配）

##### 通过正则搜索

能够快速想到解决这个问题的办法就是正则表达式，在这个例子中就是(?i)\bcat\b：

- (?i)可以让大小写不敏感
- \b能够匹配单词的边界

```go
func search(docs []document, term string) []document {
    re := regexp.MustCompile(`(?i)\b` + term + `\b`) // Don't do this in production, it's a security risk. term needs to be sanitized.
    var r []document
    for _, doc := range docs {
        if re.MatchString(doc.Text) {
            r = append(r, doc)
        }
    }
    return r
}
```

有点惊讶，居然用了两秒才能够搜索完成。如您所见，即使有 600K 文档，事情也开始变得缓慢。虽然该方法挺方便，但它的扩展性并不好。随着数据集越来越大，我们需要扫描越来越多的文档。**该算法的时间复杂度是线性的**，需要扫描的文件数量等于文件总数。如果我们有 600 万个文档而不是 60 万个文档，那么搜索将需要 20 秒。我们需要寻找更加好的方法。

### 倒排索引

为了使搜索查询更快，我们将对文本进行预处理并提前建立索引。全文搜索的核心是一种称为倒排索引的数据结构。倒排索引将文档中的每个单词与包含该单词的文档相关联。

例子:

```go
documents = {
    1: "a donut on a glass plate",
    2: "only the donut",
    3: "listen to the drum machine",
}

index = {
    "a": [1],
    "donut": [1, 2],
    "on": [1],
    "glass": [1],
    "plate": [1],
    "only": [2],
    "the": [2, 3],
    "listen": [3],
    "to": [3],
    "drum": [3],
    "machine": [3],
}
```

以下是倒排索引的真实示例。书中的索引，其中术语引用页码：

![img](https://artem.krylysov.com/images/2020-fts/book-index.png)

### 文本分析

在开始构建索引之前，我们需要将原始文本分解为适合索引和搜索的单词标记。文本分析器由一个分词器和多个过滤器组成。

![img](https://artem.krylysov.com/images/2020-fts/text-analysis.png)

### 分词器

分词器是文本分析的第一步。它的工作是将文本转换为标记列表。我们的实现在单词边界上拆分文本并删除标点符号：

```go
func tokenize(text string) []string {
    return strings.FieldsFunc(text, func(r rune) bool {
        // Split on any character that is not a letter or a number.
        return !unicode.IsLetter(r) && !unicode.IsNumber(r)
    })
}
```

```shell
> tokenize("A donut on a glass plate. Only the donuts.")

["A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"]
```

### 过滤器

在大多数情况下，仅将文本转换为标记列表是不够的。为了使文本更易于索引和搜索，我们需要进行额外的规范化。

##### 小写

为了使搜索不区分大小写，小写过滤器将标记转换为小写。 cAt、Cat 和 catT 被归一化为 cat。稍后，当我们查询索引时，我们也会将搜索词小写。这将使搜索词 cAt 与文本 Cat 匹配。

```go
func lowercaseFilter(tokens []string) []string {
    r := make([]string, len(tokens))
    for i, token := range tokens {
        r[i] = strings.ToLower(token)
    }
    return r
}
```

```shell
> lowercaseFilter([]string{"A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"})

["a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"]
```

##### 删除常用词

几乎所有英文文本都包含常用词，如 a、I、the 或 be。这样的词称为停用词。我们将删除它们，因为几乎所有文档都会匹配停用词。

没有“官方”停用词列表。当然我们能够添加更多：

```go
var stopwords = map[string]struct{}{ // I wish Go had built-in sets.
    "a": {}, "and": {}, "be": {}, "have": {}, "i": {},
    "in": {}, "of": {}, "that": {}, "the": {}, "to": {},
}

func stopwordFilter(tokens []string) []string {
    r := make([]string, 0, len(tokens))
    for _, token := range tokens {
        if _, ok := stopwords[token]; !ok {
            r = append(r, token)
        }
    }
    return r
}
```

```shell
> stopwordFilter([]string{"a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"})

["donut", "on", "glass", "plate", "only", "donuts"]
```

##### 词干过滤

由于语法规则，文档可能包含同一个单词的不同形式。词干将单词简化为其基本形式。例如，fishing、fished 和fisher 可以简化fish。

实现一个词干分析器是一个非常重要的任务，这篇文章没有涉及,而是直接使用了一个模块:

```go
import snowballeng "github.com/kljensen/snowball/english"

func stemmerFilter(tokens []string) []string {
    r := make([]string, len(tokens))
    for i, token := range tokens {
        r[i] = snowballeng.Stem(token, false)
    }
    return r
}
```

```shell
> stemmerFilter([]string{"donut", "on", "glass", "plate", "only", "donuts"})

["donut", "on", "glass", "plate", "only", "donut"]
```

##### 将分析器放在一起

```go
func analyze(text string) []string {
    tokens := tokenize(text)
    tokens = lowercaseFilter(tokens)
    tokens = stopwordFilter(tokens)
    tokens = stemmerFilter(tokens)
    return tokens
}
```

标记器和过滤器将句子转换为标记列表:

```shell
> analyze("A donut on a glass plate. Only the donuts.")

["donut", "on", "glass", "plate", "only", "donut"]
```

标记已准备好进行索引。

##### 构建索引

回到倒排索引。它将文档中的每个单词映射到文档 ID。内置映射是存储这种映射的一个很好的方法。映射中的键是一个单词，值是一个文档 ID 列表:

```go
type index map[string][]int
```

构建索引包括分析文档并将其 ID 添加到映射中:

```go
func (idx index) add(docs []document) {
    for _, doc := range docs {
        for _, token := range analyze(doc.Text) {
            ids := idx[token]
            if ids != nil && ids[len(ids)-1] == doc.ID {
                // Don't add same ID twice.
                continue
            }
            idx[token] = append(ids, doc.ID)
        }
    }
}

func main() {
    idx := make(index)
    idx.add([]document{{ID: 1, Text: "A donut on a glass plate. Only the donuts."}})
    idx.add([]document{{ID: 2, Text: "donut is a donut"}})
    fmt.Println(idx)
}
```

OK! 映射中的每个标记都引用了包含该标记的文档的 ID:

```shell
map[donut:[1 2] glass:[1] is:[2] on:[1] only:[1] plate:[1]]
```

##### 查询

要查询索引，我们将应用与索引相同的标记器和过滤器:

```go
func (idx index) search(text string) [][]int {
    var r [][]int
    for _, token := range analyze(text) {
        if ids, ok := idx[token]; ok {
            r = append(r, ids)
        }
    }
    return r
}
```

```shell
> idx.search("Small wild cat")

[[24, 173, 303, ...], [98, 173, 765, ...], [[24, 51, 173, ...]]
```

最后，我们可以找到所有提到Cat的文件。搜索 600K 文档只需不到一毫秒 (18µs)！使用倒排索引，搜索查询的时间复杂度与搜索标记的数量成线性关系。在上面的示例查询中，除了分析输入文本之外，搜索只需要执行三个map查找。

##### 布尔查询

上一节中的查询为每个单词返回一个分离的文档列表。当我们在搜索框中输入Small wild cat时，我们通常期望找到的是一个同时包含Small,Wild和Cat的结果列表。下一步是计算列表之间的集合交集。这样，我们将获得匹配所有单词的文档列表。

![img](https://artem.krylysov.com/images/2020-fts/venn.png)

幸运的是，倒排索引中的 ID 是按升序插入的。由于 ID 已排序，因此可以在线性时间内计算两个列表之间的交集。交集函数同时迭代两个列表并收集两个列表中都存在的 ID：

```go
func intersection(a []int, b []int) []int {
    maxLen := len(a)
    if len(b) > maxLen {
        maxLen = len(b)
    }
    r := make([]int, 0, maxLen)
    var i, j int
    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            i++
        } else if a[i] > b[j] {
            j++
        } else {
            r = append(r, a[i])
            i++
            j++
        }
    }
    return r
}
```

更新的搜索分析给定的查询文本、查找单词并计算 ID 列表之间的集合交集

```go
func (idx index) search(text string) []int {
    var r []int
    for _, token := range analyze(text) {
        if ids, ok := idx[token]; ok {
            if r == nil {
                r = ids
            } else {
                r = intersection(r, ids)
            }
        } else {
            // Token doesn't exist.
            return nil
        }
    }
    return r
}
```

Wikipedia 转储只包含两个同时匹配 small、wild 和 cat 的文档：

```shell
> idx.search("Small wild cat")

130764  The wildcat is a species complex comprising two small wild cat species, the European wildcat (Felis silvestris) and the African wildcat (F. lybica).
131692  Catopuma is a genus containing two Asian small wild cat species, the Asian golden cat (C. temminckii) and the bay cat.
```

搜索按预期工作！

顺便说一句，这是我第一次听说 catopuma，这是其中之一：

![By Karen Stout - originally posted to Flickr as Asian Golden cat, CC BY-SA 2.0, https://commons.wikimedia.org/w/index.php?curid=11413240](https://artem.krylysov.com/images/2020-fts/asian-golden-cat-s.jpg)

### 总结

我们刚刚构建了一个全文搜索引擎。尽管它很简单，但它可以为更高级的项目奠定坚实的基础。我没有涉及很多可以显着提高性能并使引擎更加友好的内容。以下是一些进一步改进的想法：

- 扩展布尔查询以支持 OR 和 NOT。
- 将索引存储在磁盘上：
  - 在每次应用程序重新启动时重建索引可能需要一段时间。
  - 大量索引放在内存里也不合适
- 尝试使用内存和 CPU 高效的数据格式来存储文档 ID 集。看看[Roaring Bitmaps](https://roaringbitmap.org/)。
- 支持索引多个文档字段。
- 按相关性对结果进行排序。

所有代码都放在[GitHub](https://github.com/akrylysov/simplefts)

图片处理解决方案Gimg发布了

作者: nbboy
时间: 2022-06-21
分类: 默认分类
评论

基础知识

作者: nbboy
时间: 2022-06-06
分类: 默认分类
评论

Redis Hash原理

作者: nbboy
时间: 2022-02-27
分类: 默认分类,C
评论

> 分析的Redis版本基于6.0
## Redis Hash
#### 应用场景
哈希列表结构是一般在编程上非常重要的结构，因为它的查询性能接近O(1)，所以是一种非常高效的数据结构。我们平时用的字典（dict）往往都是通过哈希列表去实现的，而redis中自己实现的hash结构也非常重要。在redis中所有的键值都是通过hash结构去管理的，比如我们键入命令set a hello时，其实在redis server用结构redisDb->dict来进行维护，其键和值都是redisObject：
```c
typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
	...
} redisDb;
```

#### Hash结构
redis hash结构和普通的hash结构还是非常像的，但是因为它有一个渐进式hash过程（下面会讲），所以它其实有两个hash table。
```c
//字典采用链表处理冲突，而且在数据过多的时候会自动进行渐进式重新hash
typedef struct dict {
	//一些函数指针
    dictType *type;
	
    void *privdata;
	
	//rehash的oldhash和newhash
    dictht ht[2];
	
	//rehash的进度(hash槽索引), 如果是-1, 则表示没有进行rehash, 否则就是在rehash
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

typedef struct dictht {
	//指向hash槽的头部
    dictEntry **table;
	
	//分配的hash槽总数量
    unsigned long size;
	
	//计算hash槽的掩码值, 它等于size - 1
    unsigned long sizemask;
	
	//在用的hash槽数量
    unsigned long used;
} dictht;

//字典的每个元素
typedef struct dictEntry {
	//元素的健
    void *key;
	
	//指向的值,或是指向一个对象，或者数值...
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
	
	//采用链表的方式，next指向hash槽内的下个元素
    struct dictEntry *next;
} dictEntry;
```
比如size=6的hash表按照字母顺序进行编码（比如a:1,b:2,c:3,d:4,e:5,f:6,g:1...)，并且插入到hash列表中后的图示如下：
![](https://chenxf.org/usr/uploads/2022/02/3822166739.png)
#### 键冲突处理
我们知道所有的hash列表都会冲突，冲突是由于key被hash到一个bucket（有些资料里叫hash槽）里引起的。Redis采用如下的技术处理键的冲突：
- 选择好的Hash函数,尽量让键分布均匀
- 用拉链的方式处理冲突，即使键值过载，也会被分散到bucket内的链表里
- 设定一个阈值，如果元素过载，则会进行自动扩容

散列表的处理冲突方式一般有两种，开放定址和拉链法，而Redis采用的是拉链法，实现上用链表来管理冲突的键值对。Redis在Hash函数的选取上则用的是SipHash，这种算法有较强的安全性，可以用来防御“Hash-flooding”。

#### 扩容/缩容
当随着元素的增加，如果Hash列表不进行扩张，则必然会增加单个Bucket的元素数量，而这会导致命中该Bucket的检索操作退化到查询列表的操作，而这是不能被接受的，所以Redis设计了自动扩容的机制。
扩容是在添加操作完成的，当元素使用比例过了设定的阈值，则进行自动扩容：
```c
//超过阈值，开始进行hash扩展，扩展长度为两倍，里面会进行微调整
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
```
Redis扩容本身并不复杂，它会把散列的空间扩大到现有元素的2倍左右大小。相比扩容，缩容采用了更加主动的方式，采用定时器进行周期性的空间回收，具体操作在tryResizeHashTables函数，收缩的条件为空间利用率下降为10%，就会进行一次收缩，收缩过后的大小刚好大于原有键值对数量的2的n次。([dictResize](https://github.com/redis/redis/blob/6.0/src/dict.c#L135 "dictResize"))
```c
//低于10%的时候，会进行缩容
int htNeedsResize(dict *dict) {
    long long size, used;

size = dictSlots(dict);
    used = dictSize(dict);
	//use/size < 0.10
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}
```
#### 渐进式Rehash
作为hash列表，已有的功能都是完整的，但是作为高性能的Redis服务器如果只是容许暂停服务进行rehash，那将是不可承受的。Redis在设计上采用了渐进式的结构，也就是在rehash阶段，会有两个散列表存在，一个用来存目前用的健值对ht1，另外一个则是新扩张后的ht2。在这个阶段两个ht都需要去查找和更新，当完成这个阶段只需要考虑ht1。
可以用一个例子来图示一下，假设为了方便演示，resize比例为1的时候就进行扩张，初始化hash大小为2个Bucket，插入3个键值对后的hash状态如下：
![](https://chenxf.org/usr/uploads/2022/02/2878736334.png)
这时候，其实hash列表里的键值对已经达到扩容的零界点，当请求插入l=33的时候，根据used/size=4/2=2>1(dict_force_resize_ratio )，所以会分配一个2倍空间(2*used)大小给新的ht1，并且启动**渐进式hash迁移**。而在hash迁移期间，所有的插入请求的键值对都会放到新的ht1。
![](https://chenxf.org/usr/uploads/2022/02/4075936131.png)
当我们请求删除e为健的键值对时，其实它会进行两步操作(其实如果一旦进入hash迁移，则对于查找/添加/替换都会有下面的第一步)：
1. 依次获取ht0的一个bucket，并且迁移到ht1中
2. 在ht0和ht1中查找是否有健，如果找到的话进行删除
![](https://chenxf.org/usr/uploads/2022/02/3697740524.png)
*图画的不是很好，表达的是2个键值对迁移过来后，其中一个被删除（画叉的是被删除，画加号的是被正常迁移过来，顺序是先迁移，后删除）*

这时候如果来个检索操作，比如检索b为健的值是多少，同样检索操作也需要执行一次迁移操作，也即：
1. 依次获取ht0的一个bucket，并且迁移到ht1中
2. 在ht0和ht1中查找是否有健，如果找到的话返回
对于这里的例子，本次操作会迁移Bucket2，操作后会使ht0没有键值对（used==0）。而当ht0为空时候，ht1被作为新的ht0(ht1指针给ht0)，ht1清空作为下一次迁移用，本轮迁移标记rehashidx置空。
![](https://chenxf.org/usr/uploads/2022/02/3142013963.png)

需要说明的是如果在迁移阶段进行检索，并且第一步之后迁移也没有完成，则查找的时候会对h0和h1两个hash表都进行检索，因为键值有可能在h0也有可能在h1。
最后再补充一点，渐进式迁移不光光在查找/添加/替换等操作里有，而且在定时任务里也会给予一定的时间（1ms）进行迁移。

### 参考
《算法》散列表部分
《数据结构与算法之美》散列表部分