# search-engine

**Repository Path**: kuixing233/search-engine

## Basic Information

- **Project Name**: search-engine
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-05-08
- **Last Updated**: 2025-05-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# search_engine
🔍基于RSS的全文搜索引擎

## 一些重要的算法

### 1. 网页去重Simhash算法（Google）
> 另一种网页去重是使用topK算法，比较两篇文章频率最高的K个词（去停用词）是否相同，但效率太差
Simhash算法可以将一个文章转换成一个64位的字节，称为特征字（指纹），根据两篇文章的特征字（指纹）的距离是否`<n`，判断是否相似
原理：
第一步：从文章中提取出前n（topN）个最重要的特征词，并计算他们的权重`<fi, wi>`
第二步：把特征值经过哈希得到的二进制序列，例如`100100`，根据`1`为正，`0`为负，分别乘以权重，得到权重序列
第三步：把所有特征词得到的权重序列竖着相加，得到的序列根据正为`1`，负为`0`，转换为**指纹**序列fingerprint，例如`110001`，两个文档越像，指纹越接近
第四步：计算两个文档的指纹的海明距离（异或之后1的个数），不超过`n`（自定义的，3或5）就认为两篇文档一致

### 2. TF-IDF算法

### 3. 余弦相似度算法


## 遇到的问题
### 1. vector在删除元素之后的迭代器失效
```c++
std::vector<std::string> wordList = SplitToolCppJieba::GetInstance()->cut(str);
for (auto it = wordList.begin(); it != wordList.end();)
{
    if (stopWordList.find(*it) != stopWordList.end())
    {
        wordList.erase(it);
    }
    else // 没有删除元素才让迭代器向后移动
    {
        ++it;
    }
}
```

### 2. 对两个数据结构求交集
```c++
std::vector<int> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2 = {3, 4, 5, 6, 7};
std::vector<int> intersection;

// 计算交集
std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(intersection));

// std::back_inserter 是一个标准库函数，它返回一个插入迭代器，该迭代器使用容器的 push_back 成员函数在容器的末尾插入元素。它通常用于算法函数中，以便将结果插入到容器的末尾，而不是覆盖现有的元素。
```

### 3. 对两个数据结构求并集
```c++
std::list<int> list1 = {1, 2, 3, 4};
std::list<int> list2 = {3, 4, 5, 6};

std::list<int> resultList;

// 需要先对两个列表进行排序
list1.sort();
list2.sort();

// 求并集
std::set_union(list1.begin(), list1.end(), list2.begin(), list2.end(), std::back_inserter(resultList));
```

## 缓存系统
### 1. 引入缓存的目的
引入缓存的目的：为了减少读取磁盘（查询数据库）的次数，根据局部性原理，在内存中创建一个数据结构，保存临时、热点查询词的结果

### 2. 缓存的数据结构
`unordered_map<string, string(json)>`：<查询词，查询结果>（淘汰）

### 3. 缓存的淘汰策略
假设缓存的上限只能有1000条，新的缓存数据到来就会发生缓存淘汰
三种淘汰策略：
1. FIFO：先进先出，但新的数据可能不是热点词，但它需要很久才被淘汰
2. LFU：根据频率
3. LRU：最近最少使用，LRU使用体验和LFU差不多，但性能好得多。
需要一个数据结构做存储，方便进行中间删除：`list<pair<key, json>>`，热点数据放头部，冷数据放尾部
一个数据结构做索引：方便进行查找，：`unordered_map<key, iterator>`，查得到key就根据迭代器去list中查找，查不到就去磁盘找

### 4. 缓存的并发问题
从业务上来说，缓存需要多用户共享，多用户就意味着多线程，多线程共享缓存就意味着竞争条件==》加锁，但如果缓存没有命中，就需要去读取磁盘，这样加锁的时间就会长
优化方向：
1. 每个线程一个缓存，各个缓存是独立的，工作线程只能看到自己的缓存，防止死锁。
2. 不应该让工作线程去处理缓存的更新：1. 设计上做解耦，不能让工作线程既要处理业务，又要管架构；2. 技术上避免死锁
3. 缓存管理线程：1. 更新保证缓存的一致性，2. 定时（一开始更新快一点，后面更新慢一点）

### 5. 缓存管理线程，怎样更新
1. 从所有的缓存中随机挑选一个主节点
2. 将所有从节点的修改发给主节点（取并集）
3. 主节点广播
4. 注意：主节点一直加锁，从节点发送时和接收广播时加锁

### 6. 增量更新策略
目的：减少锁从节点的时间，更新的速度快了一丢丢
做法：每个缓存另外开辟一个数据结构，记录自上次更新以后所有的修改，这样每个数据要保存两遍
数据结构：`list<string, string>`

### 7. 读写分离更新策略
每个线程管理两个缓存，一个读缓存，一个写缓存，读缓存负责读，写缓存负责进行同步
1. 这样在进行缓存同步的时候系统仍能进行服务
2. 注意分四步：
    1. ~~将读缓存中的内容更新到写缓存中，加锁~~，将读缓存中的内容swap到写缓存中，加锁但O(1)
    2. 将写缓存中的内容更新到主节点
    3. 将主节点广播回来的内容都更新到写缓存中
    4. 将写缓存中的内容swap到读缓存中，写缓存清空，加锁但O(1)
3. 减少锁的时间，写缓存和读缓存进行swap操作，是O(1)的
4. 存在的问题：本次新增的数据可能会到下一次同步时才能回来

### 8. 代码上要注意的事情
1. 不适合将Cache类作为Thread类的数据成员
2. 单独一个单例CahcheManage管理所有的缓存
3. 缓存使用vector<Chache>，比map通用性好

### 9. 线程局部存储 thread_local


1. 缓存同步问题
情境：
多线程环境下缓存同步存在性能瓶颈，直接加锁导致查询延迟增加。

解决过程：

尝试方案1：全局锁保护缓存 → 并发性能差（QPS<500）
尝试方案2：为每个线程分配独立缓存 → 数据不一致
最终方案：读写分离+双缓存swap（如README所述）
量化结果：
同步耗时从120ms降至8ms，QPS提升至3000+

2. 网页去重优化
情境：
初期使用TopK词频对比，误判率高且性能差。

解决过程：

实现SimHash算法（64位指纹）
引入汉明距离计算优化
添加二级缓存减少重复计算
量化结果：
去重准确率从72%提升至98%，处理速度提高5倍


### 4. 缓存系统设计挑战与优化
情境 ： 需要实现高并发缓存系统，原始设计使用全局锁导致：

- 查询延迟波动大（10ms~500ms）
- 缓存同步时服务不可用
解决过程 ：

1. 问题分析
   
   - 使用 perf 工具发现75%的CPU时间在锁竞争
   - 压力测试显示QPS在200时延迟陡增
2. 迭代优化
   
   ```cpp
   // 第一版：全局锁（失败）
   std::mutex globalCacheLock; 
   
   // 最终版：读写分离+双缓冲
   void periodicUpdateCaches2() {
       // 使用swap原子操作交换读写缓存
       _cacheList[idx].swapBack(_cacheList[i]); // O(1)操作
   }
    ```
   ```
3. 关键技术决策
   
   - 选择LRU而非LFU：因测试显示LRU的 std::list + unordered_map 实现比LFU的优先队列快3倍
   - 采用线程局部存储： thread_local 缓存副本减少锁竞争
量化结果 ：
 指标 优化前 优化后 最大QPS

320
12,000 99分位延迟
450ms
28ms CPU利用率
35%
68%


### 5. 优化：LSM，向量数据库faiss