Redis 实战 —— 10. 实现内容搜索、定向广告和职位搜索

使用 Redis 进行搜索 P153

通过改变程序搜索数据的方式，并使用 Redis 来减少绝大部分基于单词或者关键字进行的内容搜索操作的执行时间。 P154

基本搜索原理 P154

倒排索引 (inverted indexes) 是互联网上绝大部分搜索引擎使用的底层结构，它类似于书本末尾的索引。倒排索引从每个被索引的文档里面提取一些单词，并记录包含每个单词的文档集合。 P154

示例

假设有三个文档：

• R = "it is what it is"
• S = "what is it"
• T = "it is a banana"

我们就能得到下面的倒排索引集合：

{2}
{2}
{0, 1, 2}
{0, 1, 2}
{0, 1}

检索的条件 "what", "is" 和 "it" 将对应这个集合： {0,1} ∩ {0,1,2} ∩ {0,1,2} = {0,1}

可以发现 Redis 的集合和有序集合非常适合处理倒排索引。

基本索引操作

从文档里面提取单词的过程通常被成为语法分析 (parsing) 和标记化 (tokenization) ，这个过程可以产生一系列用于表示文档的标记 (token) ，有时又被成为单词 (word) 。 P155

标记化的一个常见的附加步骤就是移除非用词 (stop word) 。非用词就是那些在文档中频繁出现却没有提供相应信息量的单词，对这些单词进行搜索将返回大量无用的结果。 P155

本书中实现方向索引的逻辑非常简单：

1. 将文档划分为单词，并移除一个字符的单词
2. 对于每个单词获取或创建对应的集合，将当前文档的唯一标识放入集合中

如果需要支持中文等，就不能简单进行英文分词，需要分词器进行处理。第一次接触倒排索引是在 Elasticsearch 中，感兴趣的可以了解 Elasticsearch 中倒排索引的实现以及 IK 中文分词器。

基本搜索操作

在索引里面查找一个单词是非常容易的，只需要获取单词集合里面的所有文档即可。根据多个单词查找文档时，就需要根据条件处理对应的集合，再从最终集合中获取所有文档。 P156

可以使用 Redis 的集合操作完成对不同条件的处理：

• SINTER / SINTERSTORE : 找出同时包含所有指定单词的文档集合
• SUNION / SUNIONSTORE : 找出至少包含一个指定单词的文档集合
• SDIFF / SDIFFSTORE : 找出包含某个单词且包含其他某些单词的文档集合

通过以上三类命令，我们基本能实现条件大部分的与或非操作。

分析并执行搜索

我们使用的查询语句进行分词后具有以下特征：

• 以 + 开头的单词：表示这个单词是前一个单词的同义词，需要取并集
• 以 - 开头的单词：表示这个单词不希望包含在文档中，需要取差集
• 其他普通单词：表示用户需要查询这个单词，需要取交集

即： "connect +connection chat -proxy -proxies" 表示查询的文档需要包含 "connect" 或 "connection" ，同时也要包含 "chat" ，并且不能包含 "proxy" 和 "proxies" 。

实际处理时，先对同义词组分别取并集，然后与需要查询的单词一起取交集，最后与不希望包含的单词取差集，这样所得到的集合就是用户查询的结果集。

对搜索结果进行排序和分页 P160

上述搜索功能以及能够搜索出用户查询的所有文档唯一标识的集合，现在我们将根据这个文档唯一标识集合以及每个文档的具体信息进行排序分页。

• 文档唯一标识集合： 存储每个文档的唯一标识，例如： {1, 2, 276}
• 每个文档的具体信息： 数据结构为 HASH , 以 doc_{id} 为键，内部存储对应文档的相关信息，例如： "doc:276": {"id": 276, "created": 1324114412, "updated": 132562777, "title": "Troubleshooting...", ...}

对于这种情况我们可以使用 Redis 的 SORT 命令对文档唯一标识集合通过引用每个文档的具体信息进行排序分页。 （ 05. Redis 其他命令简介 ）

有序索引 P162

上面介绍了使用 Redis 进行搜索，并通过引用存储在 HASH 里面的数据对搜索结果进行排序分页。接下来将介绍利用集合和有序集合实现基于多个分值的复合排序操作，它能提供比 SORT 命令更高的灵活性。 P162

对多个数值字段进行排序 P162

假设我们目前需要根据文档对更新时间和得票数进行排序，为此我们需要用两个有序集合存储相关信息。这两个有序集合的成员都是文档唯一标识，成员的分值则分别是文档的更新时间和得票数。

设经过搜索后满足搜索条件的文档唯一标识集合为 filtered_doc_ids ，文档唯一标识及其更新时间对应的有序集合为 doc_ids_with_update ，文档唯一 标识及其得票数对应的有序集合为 doc_ids_with_votes 。那么可以通过 ZINTERSTORE 命令对这三个集合求交集，最后得出的满足搜索条件的文档唯一标识及其排序分值对应的有序集合，再使用 ZRANGE , ZREVRANGE 进行分页获取即可。 P162

示例： ZINTERSTORE filtered_doc_ids_with_sort_score 3 filtered_doc_ids doc_ids_with_update doc_ids_with_votes WEIGHTS 0 {update_weight} {vote_weight}

其中：

• filtered_doc_ids_with_sort_score 为结果有序集合
• filtered_doc_ids 的权重为 0 ，仅用做筛选结果，不用于排序
• doc_ids_with_update , doc_ids_with_votes 的权重可以进行设置，为 0 时表示不用于排序；为其他数时，表示对应字段对最终排序分所占的权重，正数相当于该字段需要正序排序，负数相当于该字段需要倒序排序。

所思

这种利用分值的方法很巧妙，基本可以实现多字段排序，但是优先级可能难以掌控，难以做到先按照某一字段排序，再按照另一字段排序的形式。因为每个字段对应的分值的数量级可能差别比较小，这个时候如果需要有排序字段的优先级，那么可能需要对每个权重进行精巧地设计才行。

对非数值字段进行排序 P164

上面介绍了使用有序集合对多个数值字段进行排序，由于有序集合的分值只能是浮点数，所以非数值字段不能直接用于排序，需要转换成对应的浮点数。但由于双精度浮点数只有 64 个二进制位，实际能使用 63 个二进制位，所以能表示的字符串并不多，只能使用字符串的前几个字符进行分值估计，不足指定字符数的需要补齐到指定字符数。当然如果字符集缩小的话，可以重新进行编码计算，进而可以对更长的字符串进行分值估计。 P165

当这个分值特别大的时候，可能会引发最终计算的分值溢出而出错的问题。

广告定向 P166

接下来将介绍使用集合和有序集合构建出一个几乎完整的广告服务平台 (ad-serving platform) 。 P166

对广告进行索引 P167

针对广告的索引操作和针对其他内容的索引操作并没有太大的不同，被索引的的广告通常都拥有像位置、年龄和性别这类必需的定向参数，并且往往只会返回单个广告。 P167

广告的价格 P167

• 按展示次数计费 (cost per view) ：这种广告又称 CPM 广告或按千次计费 (cost per mille) ，每展示 1000 次就需要收取固定的费用
• 按点击次数计费 (cost per click) ：这种广告又称 CPC 广告，根据被点击的次数收取固定费用
• 按动作执行次数计费 (cost per action) ：又称按购买次数计费 (cost per acquisition) ，这种广告又称 CPA 广告，根据用户在广告的目的地网站上执行的动作收取不同的费用

为了尽可能简化广告价格的计算方式，将对所有类型的广告进行转换，使得它们的价格可以基于每千次展示进行计算，产生出一个估算 CPM (estimated CPM, eCPM) 。 P168

• CPM 的 eCPM 价格可以直接使用 CPM 价格
• CPC 的 eCPM 价格可以通过将广告的每次点击价格乘以广告的点击通过率 (click-through rate, CTR) ，然后再乘以 1000 得到
• CPA 的 eCPM 价格可以将广告的点击通过率、用户在广告投放者的目标页面上执行动作的概率、被执行动作的价格这三者相乘起来，然后再乘以 1000 得到

将广告插入倒排索引 P169

我们基本可以复用上面提到的搜索功能，除了会将广告的关键词插入倒排索引，还会将广告的定向参数（位置、年龄和性别等）插入倒排索引中，并记录广告的类型、基本价格和 eCPM 价格。 P169

执行广告定向操作 P170

当系统收到广告定向请求的时候，它要做的就是在匹配用户定向参数的一系列广告里面，找出 eCPM 最高的那一个广告。同时，程序还会记录页面内容与广告内容的匹配程度，以及不同匹配程度对广告点击通过率的影响等统计数据。通过使用这些统计数据，广告中与页面相匹配的那些内容就会作为附加值被计入 CPC 和 CPA 的 eCPM 价格，使得那些包含了匹配内容的广告能够更多地被展示出来。 P170

计算附加值

计算附加值就是基于页面内容和广告内容两者之间匹配的单词，计算出应该给广告的 eCPM 价格加上多少增量。每个单词都有一个有序集合，成员为广告 id ，成员的分值为当前单词对这则广告的 eCPM 的附加值。 P171

在寻找合适的广告时，我们首先会过滤出匹配定位位置且至少包含一个页面单词的广告，然后通过计算附加值的方法替代搜索，以便实现每次投放价值最高的广告，并能够根据用户的行为学习。同时由于每个广告匹配的内容不同，最优方式应该是使用加权平均值来计算单词部分的附加值，但限于 Redis 本身的命令，我们最终采取 (max + min) / 2 的形式计算单词部分的附加值（max 表示所有匹配单词的最大附加值， min 表示所有匹配单词的最小附加值），采用如下命令即可： ZUNIONSTORE final_score 3 base max min WEIGHTS 1 0.5 0.5 。

从用户行为中学习 P175

首先需要存储用户的浏览记录，包括三部分：（每 100 次就主动更新一次 eCPM ） P175

• 被定向至给定广告的单词（即：内容中单词和给定广告单词的交集）
• 给定广告被定向的次数
• 广告中的某个单词被用于计算附加值的次数

其次需要存储用户的点击和动作记录，用于计算 点击通过率 = 点击量或动作次数 / 广告展示次数。（每次都更新 eCPM） P176

最后就是更新 eCPM ，包括两部分：

• 广告的 eCPM ：根据广告的实际价格和当前广告的点击通过率，计算出最新的 eCPM
• 广告单词的 eCPM 附加值：根据广告的基本价格和每个单词的点击通过率，计算出每个单词最新的 eCPM 附加值

改进方案 P179

• 随时间流逝：可以仿照 03. Redis 简单实践 - Web应用 文章的 RescaleItemViewedNum 函数进行定期降低广告的展示次数和点击次数（或者动作执行次数）
• 增加计数值：可以考虑前一天、前一星期或者其他时间段的点击技术，并基于时间段的长短给予不同的权重
• 使用第二价格拍卖 (second-price auction) 的方式来决定广告位的费用
• 给予低价广告一定曝光量：部分时间内，获取收益排名前 100 的广告，基于它们的 eCPM 的相对值来挑选广告，而不是挑选 eCPM 最高的广告
• 优化新广告初始 eCPM ：
  • 初期使用同类型广告的平均点击数据
  • 在同类型广告的平均点击通过率和当前实际点击通过率之间，构建一种简单的反线性关系 (inverse linear relationship) 或者反 S 关系 (inverse sigmoid relationship) ，直到广告有足够的展示次数为止
  • 人为提高点击通过率，保证有足够多的流量学习真正 eCPM
• 考虑使用真正的贝叶斯统计、神经网络、关联规则学习、聚类计算或者其他技术来计算附加值
• 将记录信息的逻辑变为异步（可以利用 09. 实现任务队列、消息拉取和文件分发 中的任务队列实现），提高响应效率

职位搜索 P180

接下来将使用集合和有序集合实现职位搜索功能，并根据求职者拥有技能来为他们寻找合适的职位。 P180

遍历合适的职位 P180

第一反应肯定是直接对每一个求职者搜索所有的岗位，从而找到求职者合适的岗位。但这种方法效率极低（大部分岗位肯定是技能对不上的），而且无法进行性能扩展。 P181

搜索合适的岗位 P181

使用类似上面提到的附加值形式，每次添加一个岗位时，在对应的技能集合中添加这个岗位的 id ( SADD idx:skill:{skill} {job_id} )，再在岗位有序集合中进行添加，成员为岗位 id ，成员的分值为所需的技能数量 ( ZADD job_required_skill_count {job_id} {required_skill_count} )。搜索的时候就先对求职者所有技能对应的集合使用 ZUNIONSTORE 操作计算每个公司匹配的技能数量 ( ZUNIONSTORE matched {n} idx:skill:{skill} ... WEIGHTS 1 ... )，然后再与岗位有序集合求交集，并让公司有序集合的权重为 -1 ( ZINTERSTORE result 2 job_required_skill_count matched WEIGHTS -1 1 )，最后获取分值为 0 的所有岗位即可完成搜索。 P181

所思

书上的这个方法比较麻烦，其实可以使用文章最开始的无序倒排索引，岗位相当于要搜索的文档，岗位所需的技能相当于单词。