Dongxing's Wiki Dongxing's Wiki
首页
  • 剑指 Offer
  • LeetCode
  • 算法与数据结构
  • Python 语言
  • Web 开发
  • Hive
  • Elastic Search
  • 机器学习
  • NLP
  • 检索技术
  • 数据分析
  • 经验笔记
  • Linux 配置
  • 博客进化记
  • 杂谈
GitHub (opens new window)
首页
  • 剑指 Offer
  • LeetCode
  • 算法与数据结构
  • Python 语言
  • Web 开发
  • Hive
  • Elastic Search
  • 机器学习
  • NLP
  • 检索技术
  • 数据分析
  • 经验笔记
  • Linux 配置
  • 博客进化记
  • 杂谈
GitHub (opens new window)
  • 检索技术课程

    • 检索技术笔记(1)基础技术篇
    • 检索技术笔记(2)进阶实战篇
    • 检索技术笔记(3)系统案例篇
      • 1. 存储系统:LevelDB
      • 2. 搜索引擎
      • 3. 广告系统
      • 4. 推荐系统
  • 检索技术
  • 检索技术课程
anthony
2021-06-01
目录

检索技术笔记(3)系统案例篇

检索技术是更底层的通用技术,它研究的是如何讲我们所需要的数据高效地取出来。

  • 基础技术篇主要包括常见且核心的数据结构和检索算法
  • 进阶实战篇主要结合工业界的应用场景,深入介绍一些高级检索技术和架构设计思想
  • 系统案例篇对当前热门的应用方向进行分析


# 1. 存储系统:LevelDB

LevelDB是Google开源的存储系统,基于LSM树优化而来。

1) 读写分离,将内存数据高效存储到磁盘

使用跳表代替B+树,来实现内存中的C0树。

读写分离的设计,内存中的数据分为 MemTable 和 Immutable MemTable,当MemTable存储达到上限时,切为只读,并重新生成一个MemTable支持新数据的写入和查询。

合并时,采用延迟合并的设计,先将 Immutable MemTable 顺序快速写入磁盘,变成一个个 SSTable (Sorted String Table),然后再对这些 SSTable 文件进行合并。避免了C0和C1树合并的昂贵代价。

2)SSTable 的分层管理设计

SSTable 文件也要进行合并,采用多路归并的方式。合并后,需要保证文件之间的数据范围不重叠,这样查找时可以定位到某个文件完成查询。所以,当新增 SSTable 时,我们找出跟这个范围有重合的所有 SSTable,进行多路归并。同时,一个 SSTable 的大小是有限制的,所以多路归并的结果是多个 SSTable。

采用分层的方式,滚动合并,来避免大量数据的无效复制。从 Immutable MemTable 写进来的 SSTable 会被放在 Level 0 层,这一层满了之后,进行多路归并,放到 Level 1层,以此类推。每一层的容量有上限,满了之后就合并到下一层,而且容量上限逐层扩增。

为避免发生在下层的合并仍然产生大量开销,不仅会限制每个 SSTable 的大小,也会限制它跟下一层数据的重合度,如果重合超过了10个文件,则结束这个 SSTable 的生成,这样保证了每一个 SSTable 要和下层归并时,最多只涉及10个文件。

(为什么层的上限是容量而不是文件数量,也就是因为上面的限制可能会造成一层有很多个小的 SSTable 文件。所以用容量限制更好)

3)查找

Level 0 层是原始写入,因此这一层的每个文件都要查找。而之后的每一层,由于都经过了合并,保证覆盖范围是不重合的,所以可以先找到 SSTable 文件,再在文件中查找。找不到就继续沉入下一层。(如果找到了就没必要往下沉了,因为越往下是越旧的数据,即使存在相同key的,也只关心更新的数据)

4) SSTable 文件中的检索加速

SSTable 分为索引区和存储区,可以先将索引区读入内存,借助预先构建的布隆过滤器,快速判断这个文件中是否包含要找的数据,如果包含,则从索引中查找数据,然后读存储区,找到具体数据内容。

5)缓存机制

可以用 LRU 机制,将最近使用的数据和索引缓存到内存。

# 2. 搜索引擎

搜索引擎的核心系统包括爬虫系统、索引系统和检索系统。

  • 爬虫系统:完成持续的网页抓取
  • 索引系统:
    • 网页预处理:相似网页去重,网页质量分析,分词,反作弊分析
    • 生成索引:
      • 索引拆分:分离出高质量和普通质量的网页,分别做索引;也需要基于文档进行拆分
      • 索引构建:生成倒排
      • 索引更新:全量结合增量,也采用滚动合并
  • 检索系统:
    • 查询分析,找出用户真实意图
    • 拼写纠正或者相关查询推荐
    • 召回+打分排序 Top K

查询分析

查询分析包括分词粒度(中文特有,比如按词,短语,字)、属性分析(权重分析、紧密度分析)和 需求分析(意图分析、时效性分析)

查询纠错

  • 错误判断:人工和日志挖掘,得到常见字典和混淆字典;或者基于语言模型和机器学习;
  • 候选召回:预估出每种出错的可能性,召回一些正确结果(比如发音相近,字形相近等)
  • 打分排序

查询纠错和查询推荐不同。查询推荐更多是分析搜索日志的结果,分析哪些检索词之间有相关性。

短语检索

首先可以拿完整短语查询,如果结果足够多,就满足要求。否则,可以把短语拆分,然后对结果求交集。但是需要注意,需记录每个词在文档出现的位置,短语拆出来的几个词位置要相近,不能太远,可以按照这个信息来对结果进行排序。

# 3. 广告系统

整体架构

广告可以分为搜索广告和展示广告。搜索广告是关键词输入后,在结果中返回;展示广告则是在搜索引擎之外,比如打开某些app时出现的广告。搜索广告中,广告和搜索词有很强的相关性,类似于搜索;而展示广告,没有搜索词的约束条件,更加灵活。

通过系统对用户的长期行为收集和分析,可以知道用户的喜好,打上标签;各种网页和广告位,也可以有网页分类等标签信息。另一方面,广告主在投放时,也会加上一些定向投放的条件。所以,广告引擎处理一个广告请求的过程,是根据用户的广告请求信息,找出匹配的广告,并进行排序返回的过程。还需要采集广告的后续监测数据,比如是否展现,是否点击等。

标签检索

以标签为key来对广告做倒排索引。比如“地域:北京”,前一半表示定向类型,后一半表示该类型下的具体标签取值。

有一些区分度很低的标签,比如“媒体类型:APP”,会包含大量广告,这类可以用tf-idf值的方式找出这种标签,不建倒排。但是在召回广告之后,需要用这些标签信息进行过滤,要满足广告主定向投放的要求。

对于区分度很低的标签,也可以作为树的结构,每一层是一个类型,不同取值代表不同分支,这样来建立分片索引,比如媒体类型、性别、操作系统这种,属于区分度很低的标签,但可以将索引划分成不同的片,进行分流。

向量检索

广告引擎自动召回,可以将广告和用户兴趣都表示为向量,做最近邻检索。

打分排序 分为召回、粗排、精排等阶段。不过广告最后通常只返回第一个结果。

索引精简 广告的生命周期变化非常快,比如预算用光了就不能再投出去了。而且由于广告总量小(相比推荐和搜索的候选池非常大),可以较快更新索引,因此也可以在索引中直接将不符合条件的广告过滤掉,而不是召回之后再过滤,节省索引空间。

# 4. 推荐系统

整体架构 搜索引擎中的强约束条件是用户输入的搜索词,广告系统中的强约束条件是广告主设置的定向要求,但在推荐引擎中,外界输入的检索约束条件非常少,推荐引擎有更灵活的检索能力。

在离线缓解,通过数据挖掘每个用户的星球,对用户分类,生成用户画像。在用户画像中,有着不同的标签,标签权重会随着时间变化衰减。同时,也会给文章打上标签。

召回 召回可以是基于统计的静态召回,比如离线统计好哪些点击量高、收藏多的热门文档等。也可以是个性化召回。

  • 基于内容的召回:文章内容有标签,用户有兴趣标签,匹配。优点是不需要其他用户数据,也可以给出小众用户的推荐,新的文章加入后可以推荐;缺点是依赖用户和文章画像,难以挖掘用户的潜在兴趣,同时对一个冷启动新用户没有兴趣标签,无法给出推荐。

  • 基于协同过滤的召回:又可以分为基于用户的协同过滤和基于物品的协同过滤。也可以将一部分计算放在离线环节。基于物品的协同过滤更注重兴趣传承,基于用户的协同过滤则更注重社会化的推荐,因此前者更倾向于商品电商,后者更适合于新闻资讯。

混合推荐 召回阶段有多路召回,混合使用各种方案;然后经过粗排、精排打分排序。

上次更新: 2022/11/11, 2:11:00
检索技术笔记(2)进阶实战篇

← 检索技术笔记(2)进阶实战篇

Theme by Vdoing | Copyright © 2017-2023 anthony 京ICP备17072417-3
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式