Design Yelp

1. 理解需求

1.1 商业目的

帮助用户找到餐馆。

1.2 功能性需求

• 根据地图范围 + 餐厅名称/类型/特征/菜品查询餐厅。

• 用户可以上传或者浏览餐厅评论以及打分。

• 用户可以上传或者浏览菜品照片。

1.3 非功能性需求

• 高可用性 (Availability)

• 高可靠性 (Reliability)

• 扩展性 (Scalability) - 支持百万级别的餐厅和亿级的用户

2. 资源估算

2.1 假设

• 100M 日活跃用户

• 每个用户每天向服务器发送 10 次请求

• 总共 1M 商户

• 每个商户平均存储 1000 条文字评论，500 张图片

2.2 估算

• 商户使用的存储 - 1M * (1000 * 1KB + 500 * 2 MB) ~= 1 PB

• QPS - 100M * 10 / (24 * 3600) ~= 10000 QPS

3. High-level Diagram

4. 核心子服务设计

4.1 商户搜索

Yelp 使得商户和用户能够更方便地找到彼此。下面我们会主要从用户的视角来解析 Yelp 最常用过的功能 - 商户搜索。从技术栈角度上说，Yelp 目前对于搜索的实现主要使用 ElasticSearch，但是下面的小节会假设我们没有这样的工具，而直接使用 SQL 数据库作为 Building Block，讨论如何设计数据库的列，如何索引， 如何检索，从而从更底层的视角来做细致的分析。

4.1.1 商户搜索特点

商户可以在 Yelp 平台上为自己的商户创建一个账号，用来上传商户相关的各种资料，比如店名，地址，电话，营业时间，类别，菜单，价格区间，网站等等。这些信息一旦被平台审核通过，商户就在 Yelp 上拥有了自己的主页。

Yelp 搜索由于它被限制于商户，与传统搜索相比，会有一些特殊的要求：

• 所有的搜索都是根据地图区域或是地区名称搜索

• 可以在搜索框中进行模糊搜索 - 比如 “cheap chicken wings in downtown”

• 可以额外加入限制条件 - 商户类别 (餐馆或是理发店)，餐馆类型（中餐或是日餐），食物类型，价格

4.1.2 位置索引

在用户进行搜索时，Yelp 可以根据位置信息先缩小范围，然后再根据其他限制条件选出相关的商户。这里的位置优先的搜索模式就使得 Yelp 的索引会跟传统索引有很大的区别。

如果按照传统索引的思路，根据经纬度分别进行索引，搜索效率会相对低。我们可以采用 Google S2。简单来说，S2 将地球分隔成越来越小的方块，并使用 Hilbert Curve 对这些方块进行编码。每个方块称为一个 Cell，S2 的 Cell 级别从 0 到 30，最小的 30 级 Cell 可以很精准到1平方厘米，已经超过了 Yelp 需要的精度。由于 Hilbert Curve 的特性，编号相近的 Cell 在位置上也是相近的，这样可以进一步方便我们进行分片 (Sharding)。 Hilbert Curve - s2geometry.io. S2 Cells

实现上我们可以简单地在 Business Profile DB 中为 S2 Cell ID 这一列添加 Index，利用数据库自带的索引就能很好地完成对于位置的索引。

在分片 (Sharding) 的时候，我们可以根据每个地区的一些特征，比如

• 商户总数

• 用户总数

• 用户访问量

• 跟其他地区的相对位置（一个 Shard 存储的 S2 Cell 最好是相邻的）

来选择一个或者多个 S2 Cell 存储到单一 Shard 中，注意这里的需要挑选合适的 Cell 级别来做 Shard 中 Cell 的最小单位。分片完成后会产生类似下图的 Shard 分布 - 商户和用户多的地方每个 Shard 覆盖的面积小，反之则大。Tinder Geoshard - Frank Ren. (2019). Geosharded Recommendations Part 1: Sharding Approach

关于分片的更多内容，建议阅读 Tinder 的 Geoshard 实现，它与 Yelp 同样有强地域性，所以这套 Sharding 方案很适合迁移来给 Yelp 使用。

• Frank Ren. (2019). Geosharded Recommendations Part 1: Sharding Approach

• Xiaohu Li. (2019). Geosharded Recommendations Part 2: Architecture

• Devin Thomson. (2019). Geosharded Recommendations Part 3: Consistency

4.1.3 按其他限制条件索引

Yelp Filters

对于每个餐厅的结构化信息（如商户类型，营业时间，店名），可以分别进行索引。

这些结构化信息可以分成三类 - 类型索引，范围索引和关键词索引。

• 类型索引 - 如商户类型，餐馆类型。用户会根据这些类型进行筛选。这些类型的总量相对少 (Low Cardinality)，比如餐馆的类型大致是按国别分，按地域分，按口味分，按价格分等等。这些类型可以认为餐馆的属性。一个餐馆可以有多个属性。实现上我们可以使用逆向排序，即每个属性对应一组商户。

• 范围索引 - 如营业时间，用户可以搜索餐厅是否现在开门。实现上我们可以利用数据库的两列 A, B 来表达一天内的时间区间，一列 C 表达周几。这样使用数据库的多条记录就可以对以周为单位的开关们情况进行建模，在这个基础上辅助上节假日的特别开门时间就更完善了。可以用 (C, A asc, B desc) 来编制索引，来优化检索速度。

• 关键词索引 - 如店名，菜名，可以将这些信息做类似传统搜索引擎的逆向排序。传统索引和逆向排序的细节实现在 Google 搜索引擎系统设计题解一文里有具体讲解，供大家做印证。

Google 搜索引擎系统设计题解Google 作为搜索引擎的标杆，帮助用户发现了互联网上无数的精彩。这道系统面试题着重考察同学对信息索引 (Index) 和查询 (Query) 的理解。这篇6000字题解就来帮你深挖小小的搜索框是如何帮我们从茫茫互联网上找到内容的。罗辑爱思系统设计

4.1.4 执行搜索

前两小节中，我们讨论了如何将餐厅的信息编制成索引。这一小节，我们就来讨论如何利用这些索引执行搜索。回顾一下 Yelp 搜索的输入 - 用户可以在搜索框中填写关键词 + 位置信息 + 勾选餐厅类型。

位置信息和餐厅类型的匹配相对简单固定，我们着重讨论关键词搜索。下面我们考虑关键词 “cheap chicken wings in downtown”。Query Understanding. Heath V. (2015). Reading Between the Lines: How We Make Sense of Users' Searches

可以看到，其中 “Cheap” 对应一个类型标签 (“$”)，“Chicken Wing” 可以对应菜名或者店名，”downtown” 对应位置或者店名。要准确理解用户的搜索意图，我们需要将其中每个部分拆开并找到可能的对应。Query Processing. Heath V. (2015). Reading Between the Lines: How We Make Sense of Users' Searches

在对搜索关键词进行语义分析后，搜索流程如下：

1. 根据用户输入的城市，地区或是地图范围找到相关的一个或者多个分片 (Shard)。

2. 在每个分片中:

   • 找到所有范围内 Business ID。

   • 根据搜索关键词中提到的类型，店名，菜名，位置等进行筛选

   • 根据勾选的类型标签进行筛选

3. 将各分片中的 Business ID 汇总

4. 将 Business ID 排序 - 根据一定的规则或者模型按照以下几点因素计算一个分数，并以此为依据排序:

   • 和用户之间的距离 (Distance)

   • 商户的质量 (Quality) - 比如餐厅的评分

   • 用户搜索的匹配程度 (Relevance) - 搜索时 Relevance Score 可以与 Business ID 一起返回。

5. 产品层逻辑根据 Business ID 找到商户具体信息返回给移动端

4.2 评价打分服务

用户在找到想去的餐厅之后，往往会参考餐厅的评论和打分，来决定是否会去以及点什么菜品。

评论打分系统是一个 Read-heavy 的服务，因为读评论打分的人数远大于写评论打分的。在设计数据库的时候，我们就要考虑把评论数据库和打分数据库按照餐厅来分区 (Shard)，而不是按照用户。我们进一步考虑，往往相邻的地区的数据会容易出现同一次访问中，所以分区方案可以跟搜索一样，使用 Google S2 根据区域来划分。

评论和打分数据库都可以加上缓存来加速。尤其需要缓存的是餐厅的平均分 - 可以想象，这个平均分会在搜索结果中出现，在搜索排序中作为一个因素以及在餐厅主页上显示。因为它具有多种用途，每次遍历每个食客对餐厅的打分并重新计算平均分就不够优化了。可以考虑对于每个餐厅在缓存中维持总分和打分人数，每次有新的打分之后更新缓存中的这两个值；在读平均分的时候可以做一个简单的除法。为了更高的可用性，此应用场景下可以考虑牺牲一定的一致性，将读写机器分开。

评论打分系统在向用户呈现评论时也会需要排序，可以根据用户的评论长短，是否有图片，以及用户在所有餐馆的总评论数来决定优先显示哪条评论。

4.3 多媒体服务

用户可以上传餐厅的图片或者视频到餐厅的主页或是其中一条评论中，这些图片和视频的完整数据会存在 Object Store (e.g. S3)，而 S3 链接会存入 Business Media DB，如果该图片或视频是属于某一条评论的，那么可以额外加一列给出评论 ID。这样可以方便我们在检索餐厅所有图片和视频的时候找到那些属于评论的图片或视频。

本地热门的多媒体可以通过部署到就近的 CDN 来提高访问速度。

当用户查询多媒体服务希望获取餐厅的所有照片和视频的时候，

5. 数据结构与存储

5.1 Business Profile DB

Cache & DB

Business ID | Business name | S2 Cell ID (Sharding Key) | Address | Menu Link | Website Link | Description

5.2 Business Media DB

Media ID | Business ID (Sharding Key) | Media URL | Review ID (Index)

5.3 Review DB

Cache & DB

Review ID | Business ID (Sharding Key) | Content | Author ID

6. 接口设计

6.1 搜索

HTTP GET api/v1/search?query=cheap%20chicken%20wings%20in%20downtown&map_area=San%20Francisco&filter=open_now

Response - List of Rendered Businesses

6.2 评论打分

HTTP POST api/v1/business/{business_id}/reviews
HTTP POST api/v1/business/{business_id}/ratings
HTTP GET api/v1/business/{business_id}/reviews?last_review_id=123&page_size=5 (同时返回一组评论和打分信息并提供 Pagniation 支持)
HTTP GET api/v1/business/{business_id}/reviews/{review_id} (同时返回该评论的内容和打分信息)
HTTP GET api/v1/business/{business_id}/average_rating (返回平均分)

7. 扩展性

• S2-based Sharding

• 服务不存储状态，支持横向扩展

• Cache & DB 可扩展

8. 监控和警报

• 单一分片访问量占总访问量比例（防止分片访问量过大）

• CDN 命中率

• 缓存命中率

• 数据库使用比例

• 文件系统使用比例

9. 参考资料

• Heath V. (2015). Reading Between the Lines: How We Make Sense of Users' Searches

• Umesh Dangat. (2017). Moving Yelp's Core Business Search to Elasticsearch

• Elasticsearch Reference. Query and filter context

• Frank Ren. (2019). Geosharded Recommendations Part 1: Sharding Approach

• Xiaohu Li. (2019). Geosharded Recommendations Part 2: Architecture

• Devin Thomson. (2019). Geosharded Recommendations Part 3: Consistency

• s2geometry.io. S2 Cells