Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

常见分布式应用系统设计图解(五):Proximity 系统

Posted on 09/15/202008/14/2022 by 四火

今天是介绍 Proximity 系统,我不知道怎么翻译恰当,就保留英文原文。虽说词义上说的只是 “相似度”,但多数说的是 “地理” 上的相似度。因此,这一类系统多为基于地理上的邻近程度来提供服务的,核心功能就是要找到某人、物或地点地理位置附近的其它人、物或地点。比如像打车系统 Uber、滴滴的叫车功能,比如像大众点评、Yelp 或者百度地图、Google Map 中寻找附近餐馆的功能,或者是 “ 附近的人” 之类基于地理信息的 app 上的小功能。

从读写的角度看,基本上这类功能都要存储位置信息,基于位置的 “寻找” 是很核心的需求,因此读往往比较重。但是写的话差异就比较大了,像有一些应用,比如打车系统,需要司机和乘客双方匹配,而且双方又往往在地理位置上的移动中,因此每几秒钟就要汇报并记录一下位置,有非常重的写;但是像 “寻找附近餐馆” 这样功能,匹配双方至少有一方基本上地理位置是固定的,往往就不是这样了。

在这里我们选择其中相对较复杂的打车系统来讨论。

  • 大的功能上面,它包括两个部分。一个是单纯的位置汇报,比如每 10 秒钟,司机和乘客都要汇报自己的当前位置(经度和纬度),这也是图中最上面和最下面的两个横着的箭头,汇报给 Location Service。
  • 第二个是这个打车的流程。乘客发起一个打车请求,Ride Service 收到以后,去 Location Service 找一个范围内的 available 的车,然后按照根据距离的顺序,通过 Notification Service 向司机发送通知。为了提高效率,可以同时发送给几个司机,让司机抢单。司机收到并接受请求以后,Ride Service 让 Location Service 更新司机的状态为 unavailable, 再通过 Notification Service 告知用户正式匹配到的车。如果找不到司机,扩大搜索范围去 Location Service 继续寻找。
  • 这里司机也好,乘客也好,和 Notification Service 的连接,使用 push 模型,可以通过 long poll 或者 socket 连接实现。
  • 打车的信息存放在 Ride DB 里面,这个数据库可以是一个 RDB,也可以是一个 KV 的数据库。
  • Location Service 的实现是一个 Proximity 系统的核心。在这里它主要要做两件事,一个是接受司机和乘客位置的汇报并记录;一个是接受 Ride Service 的请求,返回一定范围内匹配到的 available 的司机。
  • 这个匹配机制有大致有这样两种实现方式(之前在这篇文章中都提到过):
    • 一种是使用 QuadTree,就是说把地图上任意一个区域都划分成四个子区域,每个区域如果节点超过一个阈值,就继续划分。
    • 第二种是使用 Geohash,本质上就是降维。降维的原因是,一维的数据管理和查找起来要容易得多,二维的数据要做到高效查找比较困难。我们的查找条件是基于经纬度的,而不是一个单值;我们存储的数据也都是一个个经纬度形成的点,因此,Geohash 的办法就是把查找条件和存储的数据全部都变成一个个单值,这样就可以利用我们熟悉的一维数组区域查找的技术来高效实现(比如把它索引化,而索引化其实是可以通过 B+树来实现的,因此 Geohash 的查询时间复杂度和 QuadTree 是可以在同一个数量级的,都是 log n)。
  • 由于写的频率太高,可能导致上面的树(无论哪一种)出现节点分裂和合并过于频繁,造成性能和资源竞争的压力,因此可以做两个优化:
    • 这个 location 数据的写入,可以不非常实时,比如对于没有处于接单状态的司机,可以合并几次写入到一次再写入。
    • 节点的分裂还是合并设置阈值,并且分裂阈值要大于合并阈值,阈值以内不发生节点变化。比如说,一个大节点的下一层,同样数量的司机,可能分布在 x 个子节点,也可能分布在 x+1 个子节点。

这是《常见分布式系统设计图解》系列文章中的一篇,如果你感兴趣,请参阅汇总(目录)寻找你其它感兴趣的内容。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

×Scan to share with WeChat

你可能也喜欢看:

  1. 常见分布式应用系统设计图解(一):即时消息系统
  2. 常见分布式应用系统设计图解(八):文件同步分享系统
  3. 常见分布式应用系统设计图解(十):电商秒杀系统
  4. 常见分布式应用系统设计图解(十四):日志系统
  5. 常见分布式应用系统设计图解(九):协同编辑系统

2 thoughts on “常见分布式应用系统设计图解(五):Proximity 系统”

  1. Anonymous says:
    09/13/2021 at 11:56 PM

    楼主的图是拿什么软件画的呀

    Reply
    1. 四火 says:
      07/31/2022 at 10:31 PM

      Balsamiq

      Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Spark 互联网 亚马逊 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 眼界 程序员 管理 系统设计 缓存 编程范型 美股 英语 西雅图 设计 问题 面向对象 面试

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Machine Learning and Artificial Intelligence (6)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 聊一聊分布式系统中的时间
  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • Ticket: TRANSACTION 1.922915 BTC. Go to withdrawal >> https://yandex.com/poll/enter/BXidu5Ewa8hnAFoFznqSi9?hs=20bd550f65c6e03103876b28cabc4da6& on 倔强的程序员
  • panshenlian.com on 初涉 ML Workflow 系统:Kubeflow Pipelines、Flyte 和 Metaflow
  • panzhixiang on 关于近期求职的近况和思考
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme