## Detailed walkthrough
### [00:00](https://www.youtube.com/watch?v=v2_hv4qIEPc&t=0s) 面试开场与背景铺垫：从微软 Teams 到高精地图行业内幕
面试伊始，面试官邀请候选人 Leo 简短介绍自己的工作经历与技术专长。Leo 表示自己在微软负责一款名为 Microsoft Teams 的软件版本发布（release），主要技术栈集中在后端服务（backend service），但过去较少深入接触大规模分布式系统，因此希望通过自学和模拟面试来提升。面试官风趣地称赞道，Teams 最近势头非常迅猛，短短几个月的用户增长甚至超过了 Slack 一年多的积累，很大程度上归功于微软高超的商业捆绑策略，将 Teams 直接整合打包进 Office 365 矩阵销售。随后，面试官将共享文档（Google Doc）发送给 Leo，宣布当天的系统设计主题是“设计 Google Maps”。
在正式进入设计前，面试官向在线观众询问是否有在 Google Maps、Apple Maps、Uber 甚至 OpenStreetMap 团队工作过的同学，希望能邀请有经验的人举手交流。由于现场没有地图业务背景的听众，面试官便分享了自己早年与地图组合作、调研自动驾驶（Autonomous Driving）以及高精地图（HD Map）时积累的第一手经验。他指出，理解地图系统必须先了解两项关键背景：
面试官重点揭秘了 Google Maps 数据之所以能保持极高新鲜度的底层逻辑——背后依赖着极其庞大的外包人工标注流水线。以旧金山（San Francisco）为例，工程团队会将城市地图切分成例如 1,000 个长方形或正方形网格（Rectangles / Blocks），根据人口密集度或特定权重每天随机抽取（Sample）若干网格。随后，系统调取该区域昨天或今天最新的高清卫星云图，连同现有矢量地图数据一同推送给身处印度、马尼拉等低人工成本地区的专职操作员（Human Operators）。操作员负责对比两张图：如果现状一致则予以确认；如果不一致，则需要人工绘制出新修的道路，或者标出正在施工封闭的道路（Closed for construction）。假若每天采样 100 个网格，大约 20 天就能将全城轮训刷新一遍。
```mermaid
flowchart LR
accTitle: Map Data Pipeline and Maintenance
accDescr: Diagram showing how satellite imagery and ground fleet data are processed by human operators into mapping layers.
subgraph DataCollection["Data Ingestion"]
A["Satellite Imagery"]
B["Street View 360 Cars"]
C["Municipal Notices"]
end
subgraph Verification["Sampling & Human Curation"]
D["Grid Partitioning"]
E["Human Operators"]
D --> E
end
subgraph Services["Core Map Layers"]
F["Vector Map Tiles"]
G["Road Network & Restrictions"]
end
A --> D
B --> E
C --> E
E --> F
E --> G
```
[05:00](https://www.youtube.com/watch?v=v2_hv4qIEPc&t=300s) 地图数据的“烧钱”本质与 Google 地图演进史
地图的新鲜度直接取决于资本投入规模（"Depends on your budget"）。如果每月砸下数百万美元预算，完全可以做到两三天或一个月全量更新一次。作为行业龙头的 Google Maps 投入巨大；而像 Uber 这样的厂商由于预算相对受限，地图底图往往长达数月才刷新一次。除采集外，团队还会监控各市政府的行政公告，以便快速同步街道重命名、法定限速由 30 降为 20 等硬性变更。虽然初期尝试过引入计算机视觉（CV）或机器学习自动化生成，但迭代到最终，绝大多数核心道路修补与修正工作依然是“人画出来的”。自动驾驶领域使用的厘米级 HD Map 容错率极低，无法容忍一个月才更新的周期，因而催生了一批专注于特定少数城市、提供日级（Daily Update）超高频更新的初创公司。总结来说，高精度地图业务本质上是“烧钱烧出来的”。
交代完宏观背景后，面试官将设计主题正式推向白板环节：“今天的问题是尝试设计一个 Google Maps 服务。”由于完整体系过于庞大，面试官将本次系统的核心需求（Functional Requirements）聚焦于以下几个主要方面：
1. **地图图层展示（Render Map / Graphic pattern）**：向客户端呈现基础地图瓦片与图形图像。
2. **移动轨迹追踪（User Movement Tracking）**：通过客户端上传的 GPS 数据及 Telematics 传感器数据持续追踪用户位移与行驶状态。
3. **路线规划（Routing from Place A to Place B）**：支持两点间路线规划，例如寻找从用户公寓到心仪餐馆的最佳行驶路径。
4. **地点信息检索（Place Lookup Service）**：支持地标、大学、商铺等 POI（Point of Interest）的搜索查询。
5. **范围界定**：本场面试暂不深入探讨高难度的实时耗时预测与动态路况重估（Real-time ETA Estimation）。
Leo 询问是否需要在 Google Doc 上直接绘制架构图，面试官鼓励他按照最舒服习惯的节奏进行，无论直接用画图工具、Google 图形组件，还是先用文字拆解都可以。Leo 随即在文档上起草，将整体系统初步拆分成几大核心服务：
- **Tracking / User Movement Service**：负责采集并追踪用户位置与行进动态。
- **Navigation Service（导航服务）**：负责计算用户当前位置与目的地之间的路径指引。
- **Graph Processing Service / Map Service（图处理/地图底图服务）**：支撑底层路网图数据存储与结构化计算。
- **Lookup Service（地点检索服务）**：承载大学、地标等实体的基本元数据查询。
```mermaid
flowchart TD
accTitle: High-Level Google Maps Functional Architecture
accDescr: High-level architectural components showing client interaction with lookup, navigation, tracking, and graph processing services.
User["Client App"]
Leo 确立了系统的非功能性需求（Non-Functional Requirements）：地图渲染与交互对延迟极为敏感，系统必须具备低延迟（Low Latency）、高可用与高可靠性（High Reliability），同时地点与路线信息的准确性（Accuracy）至关重要，面对全球海量并发，系统吞吐需具备极高扩展性（Scalability）。
面试官要求按照 Google Maps 的真实体量进行容量估算：
- **月活跃用户（MAU）**：设定为 10 亿（1 Billion）。
- **用户平均在线时长**：Leo 假设用户平均每天在 Google Maps 上花费约 30 分钟，面试官认可这一粗略假设。
面试官引导 Leo 深入思考整个系统的读写特性：“首先第一点，你认为这个系统是读密集型（Read-heavy）还是写密集型（Write-heavy）？”
Leo 第一反应认为系统是 Read-heavy 的，因为用户绝大多数时候都在看地图；随后他意识到客户端必须周期性地上报自身经纬度位置信息。面试官随即点拨道：系统整体不能一概而论，读写倾斜度完全取决于具体的子服务（"Read heavy and write heavy depends on service"）：
- **Location / Tracking Service**：客户端以几秒一次的高频频率持续写入经纬度与 Telematics 数据，显著偏向写密集型（Write-heavy）。
- **Map / Graph Processing Service**：底层路网和瓦片绝大多数由内部系统或少数内部审核员录入，终端普通用户全量发起读取，属于极端的读密集型（Read-heavy）。
在深入探讨导航服务（Navigation Service）时，两人发生了一段有趣的认知对齐：Leo 最初认为导航也是写密集的，理由是客户端在导航过程中必须不断往服务端 API 发送 POST 请求上传最新当前位置，而查询路线结果（Get 请求）由于可以缓存在本地设备，请求频次相对较低。面试官解释了概念边界：导航中频繁发送的“当前位置”本质上应划归 Location/Tracking Service 的范畴；真正负责算路、提供底层地图拓扑（Cartograph Processing）与导航图层的服务，只接受带有起点和终点的读取请求，其底层数据的写入者仅是那几万名 Google 地图数据维护员工（Map Monitors/Employees）。因此，如果把位置上报解耦至独立服务，地图与导航核心服务面对的就是数十万乃至数百万比一的极端读密集场景。双方就数据职责划分与各服务的读写比重达成了一致。
```mermaid
flowchart TD
accTitle: System Data Ingestion and Query Architecture
accDescr: High-level overview of offline graph processing into databases and client query path.
GPS -->|"Ingests & Generates Grid Data"| M
M -.->|"Caches Hot Grid Data"| R
R -->|"Low-latency Reads"| LS
Client["Client (Mobile / Web App)"] <-->|"API Requests / Rendered Tiles"| LS
```
理解了底图是以多边形和微小路段为基础单位之后，面试官把话题引向核心算法与业务逻辑：如果用户想要搜索从地点 A 到地点 B 的路线，系统在底层究竟该如何查询数据、如何做路径规划（Routing）？候选人提出，用户只需在手机客户端输入目标地点或城市名称并调用 API，服务端便会根据实时交通数据和路况推荐数条候选路线（例如提供 3 到 5 条路线选项）。面试官随即指出关键挑战：系统如何知道哪些路段（Shots/Segments）在物理上是彼此相邻（Adjacent）的？又如何确保路径搜索算法是在朝着正确的方向推进，并处理好从 A 到 B 沿途所经过的中间节点？
---
[40:00](https://www.youtube.com/watch?v=v2_hv4qIEPc&t=2400s) 具体场景下的路径拓扑瓶颈：从 King Street 到 Market Street
为了让设计更加落地，面试官给出了一个极具现实感的具体场景：假设用户在旧金山（San Francisco）的国王街（100 King Street，邮编 94007），现在想要前往位于市场街（1435 Market Street）的最近一家麦当劳。系统面临两个阶段的问题：首先是如何在海量地点中检索到最近的目标，其次是如何在起点与终点之间规划出一条真正的行驶路径。
这种层级设计的巨大优势在于模糊地理定位解析。例如用户导航直接指定“旧金山（SF）”，系统在词义解析后只能向下定位到 City Level，无法对应单一具体邮编，此时系统会直接定位到旧金山市的物理几何中心，再由该中心关联的对应邮编和路网继续向下展开。面试官对此表示赞同，指出这与四叉树的空间分级思想异曲同工，区别在于四叉树是严格按照物理经纬度网格切分，而 Bing 采用的是现实中的行政/虚拟地理层级关系，两者都是工业级地图系统中行之有效的高阶架构。
- 空间缩放性能瓶颈：Zoom-out 时加载的数据量通常远高于 Zoom-in，容易出现明显的加载延迟（Loading lag），多层级预计算与缓存是优化的关键手段。
- 实体分层引用模型：通过 `Entity (Lat-Long) -> Postal Code -> City -> State -> Country` 的向上引用链，实现不同尺度地理抽象的精准解耦与降级寻址。
```mermaid
flowchart TD
accTitle: Map Database Selection Architecture
accDescr: Comparison of different database engines for map graph data and spatial queries.
subgraph MapGraph["地图图拓扑与大数据存储"]
A["地图数据服务 (Map Data Service)"] --> B{"存储引擎评估"}
B -->|"海量数据规模 / 超大单记录"| C["Apache Cassandra<br/>(Uber 地图服务选型)"]
B -->|"原生图查询遍历"| D["Neo4j / 专用图数据库"]
B -->|"文档存储模型"| E["MongoDB<br/>(尺寸受限 / 扩展性欠佳)"]
end
subgraph SpatialQueries["地理空间查询 (GeoSpatial)"]
B -->|"关系型 + 空间索引扩展"| F["PostgreSQL (PostGIS) / MySQL"]
F --> G["原生支持 GeoQuery"]
E -.->|"效率较低且难支撑高扩展"| G
end
```
系统设计面试告一段落后，面试者感慨这个课题的技术跨度极大，坦言“自己知道太少了，好像很多地方展开之后都能谈挺久”，暴露出地图系统在底层图算法、路由搜索和空间索引等维度的深度与广度。面试官对此深表认同，强调设计 Google Maps 这类题目确实属于系统设计中难度最高的一档，对前置背景知识（pre-knowledge）要求极高。面试官分享了自己的切身经历打趣道：他自己虽然未曾在 Uber 的 Maps 组直接任职，但他“经常跑去用他们的 server，偷他们的 server 用”，因此对地图底层的运行机制和依赖链路有较多直观体会。
针对求职面试的定位，面试官给出了一颗“定心丸”：在北美工业界的技术面试中，除非候选人明确面试与地图、出行或强位置服务相关的团队（例如 Google Maps、Lyft、Uber Maps 等），否则普通业务后端岗位极少会抛出如此硬核且依赖专业背景的系统设计题。若工作内容与地图完全无关，通常不会在这类专用架构上过分深挖。
[5:00] 面试官: Depends on your budget
[20:00] 面试官: Read heavy and write heavy depends on service
[40:00] 面试官: 这中间是有算法智能（smartness）的，到底是由哪个模块来负责这部分计算？
[70:00] 面试官: 我个人对 Mongo 有很大的意见，这都是个人 preference 嘛，因为我知道至少有三个例子，Mongo 是不 scale 的。
[72:45] Leo: 自己知道太少了，好像很多地方展开之后都能谈挺久
[72:45] 面试官: 这个确实比较难，并且确实需要一点这个 Maps 的 pre-knowledge……我其实没有在 Maps 组直接接触过，但我经常跑去用他们的 server，偷他们的 server 用……你如果工作和 Maps 不相关的话，是不太会被问到这个问题的。
Original transcript
[0:00] 我会让你来的博弱需要介绍什么好,Leo,您简单说一下自己的工作经验,然后之前focus上什么方面什么的?简单的工作是在微软有款软件叫做Teams 负责release的一些发布然后嗯怎么讲呢 写的话主要是写一些后台的backend service然后也没怎么接触过这种分布式系统然后觉得就不想靠自己自学一下嗯Teams还是最近停货的,我看它Teams好像几个月增长,超过了slack一年多的增长,还是挺快的游戏。Viron的战略还是很强,他把Teams绑到O365人们一块去卖。好的好的,那我把Dog发给你了,我们就开始好了。今天讲的是那个Design Google Map。我自己没有在Map组工作过,但是我知道点Map的事情,我不知道今天有没有在Map组工作的人今天同学有在Maps工作,不管是UberMap, AppleMap, GoogleMap,甚至你那个有个open map,我记得有个open map,你在多少工作过点的话你可以提一下,然后可以举一下手,然后我们看一下能不能就是解惠一下你在之前在Maps组工作的经验,然后我们看能不能把这个Design Mocking Interview 做得更好一点就在Maps 做工作的谢谢大家好像没有啊,那我只能靠我自己的Maps的经验来,我之前是和Maps有合作吧,然后我大概知道他怎么做的然后包括怎么样做Map Quality啊然后我自己调查了点,就是我自己做了点那个autonomous driving 的 research,我也知道那个high definition map 大概是怎么做的。也是那块做了点调查我们先看,Liang你可以share这个screen了Map这块,我先给大家两个背景吧一个背景就是,其实那个现在不管是手机,还是有一个嵌入式的一个device,都有个GPS,一般来说那个GPS是分辨率大概是几米之内,mobile是几米之内,我记得我上次同学跟我聊是可能3到4米之内还是可以的,但是有时候信号比较差的时候,GPS定位有时候有十几米,就是和你的实际位置差了十几米,误差可能有十几米,但一般来说一米到三米之间,我觉得是他说是比较合理的,然后这是一点。但是那个autonomous driving 的那个 map 就是它那个定位特别准。基本上是到厘米级的,就是你误差不会超过一厘米的。就是它那个是比较精准的一个high precession 的一个 GPS 的。然后就是一个GPS,然后Maps,就是Mobile里面还有一个feature,是Telematic,Telematic data主要是测你的速度加速度方向的,就是你可以认为是一个速度加速度和方向是有个Telematic data,然后它可以通过你的Telematic data来判断这个现在行驶的速度啊,你的速度怎么样,加速度怎么样,这个是可以判断出来的然后可以根据这个来判断出推测出你到底是在步行还是开车是吧?一个是GPS data,一个是Telematic data然后我们这块再额外说一下这个Maps,这个Maps就是补充一点背景信息。Maps的数据,你像比如说你看Google Maps,它为什么能那么新呢?就是它那个Data为什么能更新的很快呢?他的data更新其实是雇佣了大量的人的他实际上怎么做呢?他就是把这个任务包装到印度比如说呢就是说他比如说比如说我举个例子就是San Francisco的Map它根据San Francisco Map 然后把数落的San Francisco 画成那种正方形或者是其他形状,一般是正方形,就是正方形或者长方形,化成成这个 rectangle 是吧?然后它每次呢,它会就是把这个 San Francisco 比如假设把 San Francisco 化成了 1000 个 rectangle 了,然后呢,它每天呢会随机 sample 几个 rectangle 了,这个随机可能是 equal weight 随机,是吧?就是比如说你这块 population 比较多,那你被随机的概率也比较大,根据你的 population 来,或者根据那个,这个其他的那个,然后你随机到这个Rectangle了呢它给你个卫星云图就是最新的昨天的或者今天的卫星云图然后呢给你一个现在的Map是怎么样画的然后你来判断说这个卫星领图和现在Map是否符合如果符合
[5:00] 那你就说这个是OK的,这个Map没有变化然后不符合的话,你要画出这个Map多了一条路呢?还是这个Map是Close for construction呢?还是什么?所以它其实是一个概率,就是你想吧,假设一天sample100个的话,你可能过个20天左右这1000个block就全部被refresh过一遍了。然后他会找很多这种Maps operator在比如在印度,或者是在那个曼尼拉比较便宜的地方,然后他认为比较简单,左手是MAP的卫星图,右面是MAPS现在的数据,然后你把它修正一下然后最原始的数据也是这样画出来的,它会给你一个Maps,卫星图,然后你开始就是画出来,然后它会有一些metadata,比如说就是什么什么路啊,线数是什么,线数的话可能从卫星图上看不到,你可能需要结合一些其他data,比如说像Google的Maps,有很多那种车,它走过的时候,它会不停的360度在拍摄,那也是一种额外的data,除了微信图以外,还有另一种数据,就是你车在这个城市里面随机漫步,什么Random work,然后你这个做完了以后,它也可以把这些街道更新但是即使是这样子的话,它这个Maps其实更新速度有时候也会有各种误差吧就是我记得我12年用Google Map的时候,去加拿大一个城市然后结果就它指的是那块有个车站,然后过去后发现还没有建好这种还是出现过的,但是近几年可能建的少一点然后其次的话,自动驾驶的,一般来说这个Map的更新速度, depends on your budget 了,你要是 budget 很多,几个 million 投下去的话,你可能三天就更新一次,是吧?一个月就更新一次,但一般来说 Google Map我不知道Google Map怎么样,Google Map是业绩老大,但是Uber的话,我记得Map可能是好几个月才更新一次。你这块已经更新了很久了,但是因为budget有限的话,可能几个月后才更新到,你有一定时机概率吗?然后其次的话是他们也会看一些市政府的通知啊,就是市政府通知,比如说把限数30变成20了这个也是可以直接更新的这个target就比较高了嘛,就是你知道哪个loop变成什么名字了,更新率就比较高一点但是这些都是人做出来的我不知道一开始版本有没有做了什么Machine Learning,用什么Computer Vision给你画一下,但是后面的这个版本基本上几个Iteration过去后都是人画出来的。然后这是Maps,然后这个AutoNomous Driving是不可以用一个月更新的Maps,是吧?你本来迷密集的计算的时候,你本来就是需要最快的计算出你这个附近有没有障碍物啊,有没有在修路啊。所以AutoMustreaming用的那个high definition map,是很多这种小公司在做,就是有一些创业公司在做。它那个update是dailyupdate,它可能支持的cd比较少,但是它那个update是dailyupdate。所以Maps基本上是烧钱烧出来的,就是你所看到的Maps基本上都是烧钱烧出来的,就是你左Mail 右面找一个Human Operator,然后给你画出来所以你有这个Maps data所以这块是比较所以这个Maps其实我们看的话最早的Google Map也是05年06年收购了几家公司啊他当时是先收购了一个就是这个用微信图画Maps 的公司然后又收购了一家先是收购了一家用微信用画Maps的公司,然后Google又收购了一家测量Traffic的公司然后又收购了一家专门给MAP提供DATA的公司,就是说白了GoogleMAP车360度角Camera那个车的公司,然后2007年,08年推出的吧然后09年退出了Developer API嘛我记得刚退出的时候我还试验了一下我还试了一下,就是做了一个简单的APP我觉得还挺好用的,后来开始charge钱了是吧?所以现在这个Google Map差不多有1 billion 的用户,就是Monthly Active User大概1 billion 左右。所以是这样子的好,我们今天这个讨论的就是,各位,然后大家有什么额外问题的话可以问一下,包括Leon,这句话对这个context有什么问题的话我们可以讨论一下,将给你补充点context,因为这个确实需要点context才能接着说起。谢谢大家啊我第一次参加这个活动我也不知道这个形式是怎么样的因为其他的设计其实比较好,简单嘛,上周设计的Facebook feed的话其实相对比较简单嘛他那个Facebook feed的话不是就是大家都用过吗?
[10:00] 你知道怎么产生了data,但是这个Maps确实有点Maps这个data其实怎么样采生的对于很多人都不知道就是你除非跟Maps合作过或者见过Maps怎么做的很多人都不知道嘛就是我给你提供了一下这个Maps data是怎么采生的感谢感谢对就是人画出来的说白了就是烧钱画出来的所以现在的话只有现在只有三家在做Map,就是四家嘛,加一个OpenSource的叫OpenMap我忘了叫open map还是什么了,它是免费的,就是公益的Map。然后除了那个open map,就是google map,apple map和uber map。只有四家在做MAP,好像我听说特斯拉也在做MAP,我不知道是不是真的,但我觉得特斯拉现金流应该是不够烧MAP的。但是你就知道这个MAP是很烧钱的一个东西。好, so today's problem, let's try to design a Google Maps service.它是很难的问题,而且是很难的问题,所以我们要Google Maps Service 支持功能在下面的部分首先,你需要展示了一些图案的图案。在这个地方,你需要展示了一些图案的图案。and also we want to be able to support tracking the user movement so user movement can be tracked bythe gps data or telematics data additionally we want to routing from place a to place b so forexample you can see we are we are to get my favorite restaurant from my apartment and alsowe want to make sure we can support place lookup service so if you're looking up like a university但是我认为我们不想要有时间的时间来到它。第一是,我们要去看 calculated real-time estimationOK,so how am I supposed to draw or just, you know, discuss about it? Sure, sure. Just, you know, use whatever the most familiar way you're comfortable with. That's fine. You know, start with whichever order you'd like to proceed with.OK 等会儿谢谢大家oh do i need to draw the diagram for not know如果你想要跟 architecture 打开,你可以找到的地方了OK 啊谢谢大家这是在Google Doc上直接撞吗 直接画吗?你可以直接画 这画不是有一个Google picture还是什么你可以直接画 或者是你描述一下也可以 都可以看你怎么样comfortableOK 啊我说好谢谢大家谢谢大家谢谢大家谢谢大家谢谢大家好谢谢大家嗯backuser所以,我认为,有一个人的用户,所以我认为,有一个人的用户谢谢大家and then there are a few services covering the requirement the required services like谢谢大家我说 Graph Processing ServicesI'll say是有所措置的?是有的谢谢大家优优优优独播剧场——谢谢大家OK好Malai about tricking user
[15:00] The trap user Thank you. moment to Thank you. Yeah, to trap users movement. Navigation services. Thank you. to provide rust between the two. user. User's kernel cushion. This destination. Um, Thank you. So, uh, co-graph processing services. I would say, kind of like a map service, including All right. including I'm back right, right. Bye. Mm-hmm. Thank you. Thank you. Thank you. Bye. Thank you. Okay, sounds good. Also, I'll say lookup services. Thank you. including basic information. That's it. places like that. Thank you. Okay, so it's like if you want to look up for university or place, right? Yeah. Okay, sounds good. Yeah. So since for this system, the latency should be low. Thank you. and reliability. It's high. The information should be accurate. Scalability also is high. Yeah, let's assume that you're designed for Google Maps. So you have one billion active user, monthly active user. OK. One doing. Yeah. Yeah. So, assuming that for -- for -- Average lay people will spend about 30 minutes on Google Map today, every day. Yeah, I think it's a fair estimation. Yeah, let's assume that. Okay, cool. And so, So I would say people will, in the 30 minutes, people will average, come like a, a, a, a, 10 cities lookup. And we all have five rods lookup. or three ROTS navigation. Thank you. Thank you. YOH KAWANO: That's a monthly user, but that's fine. Let's estimate. Roughly estimate. Yeah, that's fine. That's rough. Okay. In that case, I would say for 30 minutes the query is about for 30 minutes. The query is about Thank you. Ah. For 30 minutes, the query is about 15 lookup. And, you know, it's for navigation, so I would guess, - Yeah. Estimated 20 minutes per day. So the the rust navigation is required. the whole service to be connected all the time. Kind of like a I will say, I will say a socket connection or tunnel connection. Which means that it has to be on, has to be on at all time. Thank you. Yeah, so you definitely want to have a socket connection. Yeah, yeah. So about the QPS, I'll say 1 billion. I buy 15. in about 30, 30 minutes. Uh... Yeah, per day. So, yeah, that's about the QPS for lookups. Thank you. Thank you. And for
[20:00] for tunnel connections, or socket connections, I would say, hmm. 20 minutes per day. Okay. So first thing first, do you think it's a read-heavy or read-heavy? OK. I think-- Thank you. In this case, I believe it's really heavy. Terrific. Okay. Yeah. So user, so I would say the one client should send It's locations information periodically, but we see all the information based on location service and uh, So yeah, I think read heavy and write heavy depends on service, right? If you if it's a location service is probably right heavy as well, right? You're constantly right to your location. If it's a graph processing service or map, you know, map service, you look up map, there's probably really heavy, right? It's dependent on service here. Okay. Yeah. Yeah. Like navigation services for a read heavy because you only have limited number of employees to update the map majority of people just look up. Right. Thank you. Yeah, so Yeah. Can we spend 30 seconds to calculate your read/write ratio here? Let's briefly, you know, what do you think of read/write ratio for the Thank you. No, no, read/write ratio. Read/write ratio. Yeah, let's spend one minute to calculate what's the read/write ratio for different service. For different services? Okay, so location services. I would say a read/write would be one One to one. So one read based on where we're right. okay far enough yeah and navigation services I would say one read, probably 10, sorry, one write. Terry. the sensitive destinations are kind of like Oh, okay. So, I mean, Thank you. Thank you. uh with navigation service would be Thank you. Because I think as a user, one needs to constantly send its location information to the API. While The information query from API, you know, can be saved on the local, on the local device, for example, the exact raw, so things like that. So I believe it's in terms of it, to API is a right heavy service. like this. Yeah, so I think this number could be much bigger because, you know, the only right user writing this is a maps monitor and which is employee of Google. So that's going to be, you know, comparing to the user of Google, that's probably 10 to the power of five or six. to our six like this. Yeah, that's probably accurate, I think. All right. Yeah, so, you know, assume that you have 10,000 user employee to update map. you have a billion user. to actually use a map, right? So it's probably this number, yeah. Thank you. Well, in my opinion, the read-write ratio, because in my opinion, the write is the post request sent by the user to the API, while the read is more like a get request, the user sent to the API. Am I correct? Oh, so here navigation depends on what data you want to write, because you may not--so your location may be writing location service, and the navigation part, maybe you'll just assign your location. to request read from maps data, right? Or we can see them if there is a cost on map service, you know, map service. There is a map service right graph your cartograph processing services. It's probably yeah that's probably Yeah, I really have a really heavy one like this. The opposite of a location service. Yeah. Okay. Yeah. Navigation series. It's really depends on if you want to write anything when you actually request something. um But yeah, you'll get it.
[25:00] Good idea. So, okay, let's start at rest. Yeah. Look at the services. I would say, So, the local service will be, I think, a really heavy watch. Uh, Also, I think it's even more heavy than the graph processing services. because the information in the cities remains relatively the same. while people might query those informations. Okay, I think we understand it's a little bit different here. So basically, graph processing service and lookup service are two service or one database. It's like a graph processing service is like the right for the location data, like service, like city data and lookup services rate for the city data, right. It's like a graph processing is provide data for lookup. So yeah, so this number should be same, right? It's, you know, yeah. Am I on the center right? Yeah, I want to say graph processing service to me is more like the map service. I'm rendering the map. on the phone or on the web page. All right. Oh, you mentioned it's a-- do you mean it's like more like a front-end rendering service or something? I'll say yes. Oh, front-end rendering service. I want to say that Uber has a few maps and UI entries that are coming out. We have a Capter. Kepler's open source fountain tool, I'll just look at it. It's Kepler.ai. It's a tool that is doing this UI tool. You can give it location data and render it. They have several engineers, several staff engineers, who started to create a front-end library. But this is what I think. Graph processing service is still only backhand. Because fronthand is actually This is a separate issue. Graph processing is going to be a specific location to be a grid. Yes, it is a grid data. Okay, I think that's the reason. Let's actually skip to QPS. This part QPS is not done. QPS is a lot of people who are talking about. I think this is not the main point. It's a fun point. Okay, I think this constraints and architecture looks good. How do you want to install the data and what's the data model, database, etc.? Okay, data storage. So in order to guarantee the load latency, I'm going to store the data He's got the real data in a redis, sorry, redis. kind of like a cache, which is a kind of key value store. And also the information of the cities, they remain working the same beyond the time. So this can be saved as a I'll say MongoDB. That's back in. Thank you. So. Um, So, yeah, so I have a few questions here. I think what's the reason to select Redis, and what's the reason to select MongoDB here? Yeah, the reason Redis is that it's it is very quick to respond so the radius is in memory while the mongol TV so it's So since it's a NoSQL database, it's very flexible, and the cost is low. And it doesn't have to be that quick in terms of response for the information of the cities. OK, so I want to understand how you want to design the MongoDB data. Like, how do you want to, you know, what's a document in a MongoDB here and how you're going to link different document together? Okay. And also, yeah, and also people asking what's the key value in Redis? Thank you. Maybe we can start with data model first because then you can see, you know, this is data model. This is how we're going to start. - Gotcha. So, um... I would say, first of all, the user, user ID. So location, car.
[30:00] Okay, sure. I'll find out here. - On the two. Thank you. - Okay. um So, uh, uh, Thank you. Thank you. - Oh, yeah. off. Thank you. Thank you. Thank you. Thank you. So I'll put another class collocation right here. Thank you. Thank you. Thank you. Thank you. Thank you. Mm-hmm. Thank you. Thank you. Okay, so let's actually yeah, so you have two table here. I saw it when I use user table and And the other location table. Well, for location, it's more like a, okay. All right. Okay. Thank you. Thank you. Thank you. - Yeah. Thank you. Thank you. Let me just say the time. We should just put maps data in the future. I think it's better. Because user data is quite simple. You can map there. This part still needs a lot of professional knowledge. Like Uber Maps is used a six-fold. Polygon has a lot of polygons geometry data. Let's make the maps data set up a bit more simple. Thank you. OK, addresses. I'll say... Thank you. There's some coding. Street. city, state, country, code. route of his starter. And so, Thank you. Thank you. Thank you. Probably a few parentheses. Thank you. Thank you. Thank you. Thank you. So, uh, Thank you. I also believe that's called location, too, including latitude and magnitude. Thank you. Thank you. Sorry. Ready? Thank you. Also, for my computer traffic. Yeah. Yeah. Thank you. Thank you. Thank you. Hmm. Thank you. - Yes, this is for models for city and route. Thank you. Okay, so I just found some maps data I used to work with. I'll give you a little bit of this one. This one is quite interesting. There's a polygon, and polygon is a six-fold. Then we have four-fold and long-fold. If you have four-fold, That's how you can write four points. I'll just look at it. Because this is a domain knowledge. In the case, you have city ID and city name. Then he set up this polygon, this polygon is a four-sided shape. So, if you're 4-sit, 4-sit, four points of latitude and longitude. Then we set a square kilometer square, which is how much the area is.
[35:00] 然后练了一下肉的长度是什么然后呢这个然后因为这个就是Quality Data,就是说白了是检测这个路有没有这个问题的所以它这块是没有这个,它会有一些job name 什么的,但是咱们这个System Design是没有帮助的。然后它有一些就是area property,就比如说这个area是在这个里面是在哪一个就是这个ZipCodeLocale啊,然后这个,然后有一个嗯对 有一些这些data 说白了是这样子就是你要把这个数据里面你要把这个数据里面就是你的Latitude的Langitude列起来,然后你要把这个里面另一点的话你要把这个里面这个肉的然后用这个road 然后用这个就是这个visualize的就是你看到这个road然后把它变成那个就是data来存下来是吧然后你可能比如说用几颗图形存下来然后设计一个这样的一个transform然后把它存下来然后这个到时候你可能说这个就相当有个坐标系嘛然后你计算一下你比如说我给大家举个简单例子不一定是这么算的但我觉得这个还是比较make sense 的你可以认为是当你移动屏幕的时候,你屏幕最左下的角你的Lattitude,Long Titude是多少,比如说Lattitude是110度,北纬110度那里做的是嗯我忘了就Lantitude可能比如说北纳110度是吧,然后那个Lantitude什么东京什么37度什么的,然后那个是点是吧,然后根据你其他的这个形状的这个四边形的这个形状,然后再根据你这个当前的这个Room的scope,然后你把整个这个Map在当前这个屏幕上画出来它是这样画出来的但是你这个data里面其实是其实是你就存了一个当前这个四边形然后这个四边形,然后把那个latitude,lentitude以及它里面有的路的形状,路的起点终点是这么写出来的我不知道有没有解释到,说白了它是一小段一小段一小段画出来的,然后它那个所有的一小段,它所有的不管是,不管是,no matter it's a street,然后 it's a block,然后都是一小段一小段画出来的。谢谢大家就是它有一大堆polygon然后画出来的 OKOK, so I think some maps here make sense, and we have start and end of the road, and also we have parcel road.谢谢大家我有一些不同的路程, 可能有三十五的路程,recommended depending on the uh the some uh the traffic of real data or the conditions of the uhof the road所以好 makes sense okay so in that case how are you going to search a data for example if I want to search from place A to place B how do you actually want to search a data and how do you want to rotateso if i want to let's say at the current location that i have right now is a and i want to you know reach city bI simply put the destination, the city, where I want to go, the name of it into the phone and send it to the API.And the data I received from it would be a few options.谢谢大家好 Yeah, so how do you know which shots is adjacent to each other? And basically you want to make sure, you know, you want to make sure you want to do two things, right? You want to be able to, you are on the right direction, so you want to reach from A to B.它是在中间的部分,在A2B,所以你也要能够把那部分的部分所以,我可以把我所在的地方的情报和我,的用者而且我可以的地位可以在可以
[40:00] in by the user as well. So there will be two location service location data sent to the API and a third city the city side CDC which is in the middle of the the past year. can be tapped again. you know, as an intermediate-- to set up as an intermediate intermediate spot. So, Okay, so what data model do you need here? I think we, so I saw it. So basically here, I saw data model for maps data, which including the address for individual building an address for individual unit, right? And I saw I wrote data and start and end, but I don't see how we can connect them And for example, if I want to go from my home and, you know, go to most recent restaurants, how do I look up? Yeah, let's actually give a concrete example in this part. So assume that you have two city here, right? So let's say we have two city. I want to go to the you know, the nearest McDonald's, let's say San Francisco, you know, and we want to go to the nearest McDonald's. Thank you. And, you know, we know its zip code is 9407, and it's in... I don't know, Market Street. And then I want to go from my home and I'm on King Street and see if we can see city is also San Francisco. They're on King Street. Okay. Yeah, so Let's say we are 100 kings, really. We want to go 1435 Market Street. And you have lots of roads here connecting, but this road here started and, you know, don't contain this data directly. because, you know, those start and don't contain the data directly. So it is suggesting that I'll say in this case, restaurant object. Yeah, so we do have a restaurant. We do have my current location. We want to see how do I get to a restaurant. Let's see how we store the data, but how do I find a road to a restaurant? How do I find the restaurant? So I think as a user, I can provide my current location to the API. And as the response, the surroundings, a restaurant, stuff like that. can be sent back to my device. All right. So once I decided to go to a restaurant or somewhere nearby, I can select that. and place and That's where the destination... how the destination is defined. Yeah, so I think you'll answer one question, you'll answer lookup service, right? You'll have a lookup service for the SQL time, we assume that, you know, lookup service is an elastic search, because you're an elastic search, it's not a lot of talk, but you can think of Google search, localize Google search, but lookup service can be a restaurant. Now, if I find a restaurant, how do I direct from my current location? to restaurant. You're in my required location. So, you know, I can, so the device will send the mass selection to the API and the API will send back the broadcast information. Right, but how do the API know which goals should take? There is some smartness there, right? Which part do the smart part? Which part do the... Okay, so yeah, so how how navigation service going to use this data to navigate? Thank you. um Thank you. You said that the "suit" is how to do this? Yes. Yes.
[45:00] 先从Alqa怎么从来想,你想一下,之前肯定有些个算法,用什么算法算比较好是吧?OK什么测漫比较糙的话我能想到的就是简单的讲的是BFS是吧然后稍微复杂一点就是这个SLA是这是纳达了你可以先写一个你认为最对的算法是吧我们先写一个I say samudinist which is bfs okay uh always return it returns the uh you know a path with the nearest uh我说 或是 最新的时间 应该好谢谢大家好OK,所以我看到BFS,你会说这一句话,但你可能不是,但这BellmanFoldy是其实是一个标志的看法。and the other is probably the director right let's express yeah i believe these two are for a directed weight graph yeah bfs for it's similar than that uh谢谢大家我记得我上学还有个叫A*,不过A*好像需要一点Domain,你需要知道一些Vate然后有一个A4大2规则我意思就是说简单体验的话就未来都相等然后就返回最近的实际情况之中的时候可能考虑到很多的很多的这个这个影响因素吧所以说这个味道都不会想到的OkOK,我们这话就不cover这个算法细节了,其实相对来说读一遍的话不是太复杂。I assume that we're going to have this trajectory A* rate on, you know, the BFS and Bellman for the algorithm.你懂得要做什么?所以我需要知道OK,所以你需要... 要是,你需要的,你需要的,你需要的, right?谢谢大家We areOK,你需要有位置的位置, 和位置的位置, 和位置的位置?I believe the vertex are the cities and the edges are the rowsAge as roads, okay. So,Age as a weighted roads with weighted roads.位置路上的路上的路上的路上,所以它是在距离和速度上的一种OK, yeah, still limit. Yeah, OK. And also, you know, traffic conditions. Vertex. So, the vertex here, you need to be careful, right? Because I think vertex here,可以 refer toA location?可以 refer to a particle location,可以 refer to a road interactionOK. 如果有路的,你要要划算,你要划算,你要划算,然后其实它真的真的可以说,它是通过的通过程。intersection, so intersection, intersection, it's always your taking section.OK,so assume that you have two GPS, then you can basically, in this case, you can basicallyPingPoint and pinpoint your location, and restaurant locationlocation to ageA H all vertex of the graph谢谢大家谢谢大家你的名字是因为你的位置 may not be a vertex, right?对,对在这个时候,你需要做两个事件。首先,我们先把一个组织的组织Mapping to our intersection first, and then add the time ETA to that vertex, nearest vertex.所以你先要先要先找到最好的路线,在100米的距离然后它是100米多从那路由的路由
[50:00] to the restaurant, right? and maybe the other intersection because it's a age so you have two vertex right you can go to the other vertex if it's closer to your destination then then from that part you can you can do a director or you know bfs to find the road. Yeah, thanks. OK, so this part is going to be a bit complicated. This part is quite complicated. Can you think this part is a bit complicated? This part is quite complicated. Because you can't put storage and Google Maps together. And then you can use location, you can use location It will be You are on edge of the area, right? And you are on edge of the vertex. And you are on location and location. You map the location of the vertex. And from the lookup, it's from vertex to vertex to lookup. is it? So, the intersection lookup But you can choose vertex, you can choose the right, right? Mm-hmm. Okay, guys, guys. OK, so now we have Alright, I'm going to say that the location of the map is the vertex. For example, we have location data, right? And you can say that nearest vertex is what? Near East of WebEx, is it right? Vertex is "g" and the other one is "g" Okay, let's go. There are some things that the vertex is not 0, the road is closed, the road is closed. What is this situation? The road is closed, the graph is closed. The road is closed, the vertex is removed. Okay, so you need to know. Right, so you can see an operator for the new星. And the road is closed, and he will say, The path is closed, and the vertex is closed. Then the nearest vertex is closed. It's not visible, after修好了, we can bring it back to the app. But according to GPS, You can see it on GPS. And then this part is edge and vertex. So you can see it on GPS. If it's a line, it's a line, you can make a small line. You can use the "Cow-Won-D" to see the distance between the distance and the distance. You just want to write the location of the vertex, latitude and longitude, and you say you have two vertices and two vertices. You just want to know the distance. Shabbat shalom. Thank you. Great. This is the direction. If you have a direction, you can add a direction model. Road type is the direction? It's the direction of the direction. It's the direction of the direction. And then, you can go from vertex, you can't go from every location, right? You can go from the vertex, and from the vertex, and from the restaurant, and from the vertex, and from the vertex, and from the vertex, Cool. I think that's more make sense. It's about to use the graph lookup series, shortest distance lookup series. algorithm in Google Maps All right. And this is a category of customer events. It's not a category of customer events. For example, if you want to go to New York, you can go to New York. It's not that complicated. You can set up every room level. You can use the grid for example from the New York City, you can use the grid This room scope becomes 100 km grade. And this level This scope, you may have only state roads, only the road, and the road.
[55:00] 其实你判断你怎么样就是你怎么样define你这个A这个Vertex了嗯一般来说你其实思考一下的话我们思考一下,哪一个city来讲的话,比如说纽约的话,比如说从第一街到一百街然后纽约曼哈顿是比较好算的因为它就是个曼哈顿 distance不是很有名的一个算法问题你其实就是一接到一百接,一接到一百接,整个曼哈顿可能就一百个segment 是吧100个 低仓100个 1万个Segom是吧就一万个左右,其实它数量也不是很多嘛去吧但是你要知道很快的知道你的最近的location就是你肉的A连到哪个肉的然后你肉的必连到哪个肉的其实是需要点计算OK OK OK, so here基本上,我们需要做两个东西,我们首先要做的东西,我们需要先做的东西,我们需要先做的东西。 into our graph data. And so then we need to look up in this graph data and find the nearest road from A to B.然后我认为是一个问题的, right?如果我们也认为最大的地方是在 Manhattan你认为你课的 马产举 它是可能的 几个人的路上是可能的 几个人的路上你呢所以它是最大的市场,so even if you have one million real segment in one city是仍然能够, right?and so here can we actually spend可以 其实你呢 这些 data model可以 其实 说我们可以 说what database do you want to start this model and how you do how do you want to make a quick lookup for the for thefor a road to the destination.to the destinationOK谢谢大家如果是发出图像的信息,我发出什么就算比较好,我只用Mongo和Redis。这边的话,用Mongo感觉也行,这块的话我们还是回到最早讲过的一块,就是DataModel这块了。Graph Database 是可以的Graph Database 你比如用 Neo4G这种是专门为这个设计的然后你设计的话有一个好处就是graph database search 有个好处是它支持那个Recursal Search,比如说你可以recursively with recursively search 这个是比较好的他的 Recursive ResearchCost 比较低,我记得它是说是 index free 还是叫什么来着,它Cost 比较低,它是就是O.n或者O.1的这个index数量,说白了是我现在有一个age,或者我现在有个vertex,我找见它相邻的age,我这个cost非常非常低,就是O.1的,所以它可以不停的找它那个age,不停的找相邻的age,然后直接找见你,直到找见你那个离你最近的地儿,你用A*search的话,你的cost很低,因为A*是有pre-knowledge,你这个cost,其实你额外读取的数据量是很低的,然后如果你Graph Database不用Graph Database,我记得Google Map应该是有自己设计的Database,我还真没调查过,我记得我两天,就是之前读过Google Map是专门自己设计的Graph Database,然后如果不用Graph Database的话,这块的话应该用一个Relational Database,就是relational database也可以的,就是你对两端,对这个vertex的话,对age的话,对两边的vertex的进行,就是start vertex和end vertex的index如果是这个Age的话,你要对Vertex所有连着的Age你要进行index 并且这个age应该是个directed graph 吗?因为你可能比如说有单向路啊什么的,应该是Directed Graph所以你这个是可以的,就是说一般来说我觉得大家可能都没有graph database 的工作经验的话,你就直接用MySQL就行,这个SQL database就可以了。SQL database是一个非常 reasonable choice特别是你没有这种专门为你这个Graph Use Case进行optimize的话,Sycle是非常reasonable的一个choice那用,那不是用MySQL的话,把这些存下来该怎么查呢?对,你怎么查呢?就是你查的时候是这么查嘛,就是说你查的时候可以说你可以把它index 啊,比如说这个是
[60:00] Polygon 15是吧或者是Polygon你可以记了一个起脏点 起脂点吗?比如说Polygon,Latitude,Latitude都是多少?然后你就把这个这个Polygon的这个Data全部读出来,然后visualize出来,如果你是Route的话,比如说这个Route的话,可能是从A到B这个Route比较远的话,你查的时候,像 Postgres 支持很多这个locationPostgres 首先有个叫 Post GIS 的一个 data format 的支持Post GIS是直接支持它存Location,Latitude,Lontitude,它专门是对这个经济优化的,就是Post.js然后这个 Postgres 呢我记得还有一个,我想Postgres还支持recursive research,我不知道MySQL支持不支持,我这块没有查,就是你其实是可以recursive search,比如说你这个,你说白了就是你search一下这个的 edge 的这个的Age的,跟这个Age相邻的Age,然后再search,跟刚才你search过的Age再相邻的Age,然后一直往下设置,是可以支持这个的,就是recursever search然后你是可以支持这个的所以这块的话你如果用Dijectra的话你比如说像我们如果细分的很细的话你就说你这个A值数量其实指数型增长了所以你可能需要A*这种有点pre-knowledge有点像A*我记得是AI的一个algorithm但是其实没有什么AI的层次比较简单的一个AI就是你需要一种pre-knowledge你知道这个你要往北走往南走就远了那就不色彻往南走的路了你就只 search 往北走的路,然后这样会越涉及越近越色日境直到你最后很快地达到你要到的那个地方叫 A* algorithm我记得我和林世尔还讨论过很多次这个A*L贵总,上研究生的时候。谢谢大家好好,我看看我们之前问的问题还有什么没有回答的。Display maps for the certain city,然后Tracking user movementTracking user movement的话,你可能就是不停地把你的Lattitude和Lantitude打包上传然后routing from A to B 的话,你可能要有个 A star algorithm,或者是similar,需要一些pray knowledge,否则你用dijecter的话,你search范围太大了,就是你的adjacent,adjacent edge,就是指数性增长了,所以你就有一些a*algorithm去search然后你需要PlaceLookup的话是要用那个PlaceLookup用Elasticsearch来search的然后 tracking or traffic 的话其实是你可能说可能是结合一些我这块也没有调查过,我只能想的话,可能你可以根据一下你自己当前的使用用户的速度啊然后用户的行驶速度或者是卫星云土啊或者是其他的那个来实施卫星云土啊其他出来我觉得但是根据速度来说应该够了,然后 tracking or traffic light 的话,可能就是根据这个就需要人为的operator去update了需要 operator,然后结合那个 tool 来去 update 了这个问题还是很难的,就是你需要对这个graph algorithm 比如说知道一个degetra 是吧然后然后要graph database 啊,要稍微了解一下,就是知道然后Graph Data Model啊,最后的话我觉得这个设计的是把那个Individual的Road和这个Location其实这部分Data还是设计出来的,但是其实没有把那个Map联系起来是吧,没有把它联系成一个Graph,然后就是你必须把它联系成一个Graph才能Lookup嘛。谢谢大家OK然后这块的话还是有些细节,就是当你比如说room in,room out的时候那是不是有新的request database?你要是读新的data的话,肯定是有新的request,比如特别是room mount的时候,肯定有新的request你看你那个实际上你注意到的话你实际上如果注意到的话,当你入Mod的时候,它Loading其实会慢很多,特别是在那个,你比如说在XXX的时候,这块的话有一个地方就是有一个algorithm叫那个cordra tree,quatray其实也是比较适合这种Geo-spirtual data的Quartray是什么呢quatray就是说白了是包括Quattray和KT-Train呢是Search这个是一个什么呢?就是说白来是,你可以认为是,比如说我们当前这个屏幕是一个parent node的话,你把屏幕四等分,就是四分,就是横切一刀,竖切一刀,那最上面左上角这个四分之一的这个屏幕呢,就是它这个quatray的第一个node,然后其次的话就是右上边
[65:00] 就是第二个node左下角是第三个node,右下角是第四个node,就是quatria然后这个quatrait也是可以帮你列出它这个嗯也是可以帮你列出它的location的这个reference就是location之间关系的你其实是可以把整个一个世界地图呢,然后quattray分的,虽然它这个Map的时候,它其实有点圆形,Map不到正方形了,所以这个Map是有点问题的。但是你一个City的话是可以按quattray来分的。那当你入in入mout的话我觉得你可以用quatray来优化也可以如果你不用quatray来优化的话假设你不用quattray来优化的话因为quattray的话Quatray这块有个好处就是你可以存不同granularity 的 data 是吧?就是你可以存...你如果 rule mode 特别多的话你可以存那个 data 就相对颗粒度比较大一点是吧当你room mode 特别,rooming特别多的话,你的那个你的那个 cost 程度就更低一点,是吧?就是Granulatory 的那个就更更更 fine 一点,是吧?就是你的那个粗糙度就更更低一点,是吧?所以这个又可以用 Quattray 来实验,当你这个不同的时候它这个可能也不一样是吧,读的可能是不同的这个data当你data进行更新的时候你可能多个level 多个Granularity的这个data都要同时被更新像我们这块说过这个更新和阅读比可能是十万比一甚至是百万比一是吧你实际上更新的很少大部分时候你这个肉的都在就是被lookup,但是你肉的发生construction的概率很低所以这个也是可以的,就是这样的话去支持你不同的Granularity去lookup 是吧这样的话也是可以的,虽然它是同一个Data单查写了不同的Granulatary写了好几份,就是写了好几份,这也是一种做法吧。所以当你入命的入冒的时候你就是实际上就是从quatrait的parent到child或者从child到返回parent嘛我觉得是一种比较合理的优化吧这个其实就是还是比较有趣的我们这块链,你有没有什么? 上罗,我这边有个问题,就是我们刚才谈到那个location上面的那个存的那个location的时候,我不知道咱们这边是怎么存的,但是我今天做过一个binggeomigration,就是微软那个bing他们的geomigration的时候,我们存的其实并不是把一个record就是像这样子存成Light Lounge 存成City State Postal Code的呀我们是有点类似于像竖状那样存的 就比如说如果一个东西就是一个object 比如像你写的麦当劳如果它可以存在的话 它会先把它就是看它有没有一个最底层的一个结构 一个那种granularity那种最底层的结构 比如说Led-Lung然后它来浪市场会有一个像像找它的Parentanode一样它会找到它上一级的结构比如说Postcode,然后再找到它上一集的结构比如说City,再找到上一集结构比如State再找上一节目,比如说 country,所以这样的话,它其实就是,它就是拿不来说它只存一个ID,然后这个ID里面只有只有Led-Long的Information然后Led-Long后面可能会有个FrancReading from Key就是像一个Flatfrager 取向一个Parent Anola这样有一个好处就是比如说我如果放的是SF这样的话我就不会去考虑SF会在哪里我就直接能把SF解析到OK我只能到City Level 我再往下下不去了我没有Postcode Level所以我如果要比如说从西卡古要走到SF的话,我就直接去定位到SF的物理上的中心,然后物理上的中心它会有个自己的Postcode,然后再解析到这个小的Postcode上的一些情况。我觉得这个设计可能既然微软这么用了肯定是更好的设计啊因为我毕竟没有直接接触过这个production就是他们到底怎么设计的我觉得这个设计可能更好设计的我觉得用quatray的其实这个设计和Quartrait的概念比较像Quartrate 存在是按 Geolocation 来进行分这个 relation 是吧Quartrate 就是根据 Geolocation 来分的这个实际上是跟一个虚拟的一个关系嘛,就是你比如说把那个 city 画成 zip code 然后 zip code 上面然后这个location到zipcode的link起来这个更就是一个虚拟的一个关系啊,就有点像Time Stamp和这个Reference 的感觉,就在Database 里面你这个timestamp 根据这个版本号来决定谁后,还是根据timestamp来决定谁后,这种感觉很嚣入存在肯定合理,我觉得这个设计肯定是更好的那你们这块怎么样 visualize 这个 map 啊? 怎么样 visualize 这个 road 啊? 这样的话哦这个不是我们说的
[70:00] 我们只是把我们的Data Service迁移到BingGL上就是说这个road怎么样visualize其实不在这个里面是吧?因为我们只是考虑每一个object,比如说1455 Market Street这边我们如何把这个东西surnalize到一个具体的一个地址上嗯那如果是这样子的话那其实你那个肉的应该有单独存的方式了应该还是有一个其他的Apps在录存的是吧好,我这边说一下,我知道的几个Graph database都是用Cassandra圈的,database选的是Cassandra,就是就是这个Maps Service是用Cassandra圈的,像Uber是用Cassandra圈的,然后我看到几个其他做法也是用Cassandra寸的就是database选择是Cassandra这块的话可能有多种原因吧,最重要的原因可能还是,Single Record 的数量可能很大,就是你有一个 Single Record 的数量可能会很大,你像 DynamoDB每个 record 可以相对来说比较大一点我记得DynamoDB好像是一个 megabytes吧但是我记得那个我记得那个,像我们Uber Cassandra当时新建的Cluster就说可能有些recker的数量,它的datasize可能多达250个gb所以它这个,因为数据量,单个数据的数据量很大,所以它就用这个Cassandra来存的。然后,像这个Mongo的话,它其实是一个,我记得Mongo最大的那个Document Size是8MB,就是你如果存的话,你得把它细分一下。比如说你的Granial Nile腿怎么分的,这个其实还是,但是总体来说Mongo不太适合做graph database,Mongo做graph database的效率比较低,不适合这个,用graph database 一般来说就是优先考虑比如说专门为设计的Neo4G这种Graph Database然后其次的话是考一个relational database比较多一点我个人就是用过MongolDB的JL/Query这一个功能然后成年仅限于此。对,他那个Geo,Special,Cory好多都支持,像那个Postgres也是支持的。有一些Diabetes也支持的Mongo,其实我个人觉得Mongo应用的case比较少并且现在Mongo支持的说实话 MySinkhole和Postgres基本也支持我个人对Mongol不是很喜欢,Mongol skill, scalability 还挺有问题的就是不过我个人对Mongo有很大的意见,这都是个人preference嘛,因为我知道它很多,我知道至少有三个例子,Mongo是不skill的,就是本来说当时13年的时候说被忽悠上Mongo了,然后之后不得不migrate到其他地方都是因为Mongo的Skillability有问题谢谢大家谢谢大家谢谢大家好,那利昂,你还有什么就是额外的就是我们在想讨论的这个这个关于这个这个是想知道的就是关于这个课题是吗?关于这个topic对,自己知道太少了,好像很多地方展开之后都能谈挺久。这个确实比较难,并且确实需要一点这个Maps的pre-knowledge,我对Maps,因为我其实没有在Maps组直接接触过,但我经常跑去用他们的server,偷他们的server用。看了也可以联系我指正一下,我到时候更改一下这块需要点Maps knowledge,然后大概知道这个到底怎么work的,确实pre-knowledge需要多一点,然后你一般面试的话,你可能会面试跟Maps相关的可能会面试到这个问题,我觉得不太会说你工作跟Maps不相关,然后问你这个问题,我觉得可能性不大。谢谢大家你比如说Google Map, EF,这种跟location相关的,Uber的话,如果你去面试Uber Map的话也有可能相对来说好,那这样的话,对这个考量的话题有没有什么额外的问题?谢谢大家对,你如果工作和Maps不相关的话,是不太会被问到这个问题的。谢谢大家谢谢谢谢好,今天我们还有,我们再演个十分钟好了,我想就是简单的跟大家聊一下,就是看一下就是,就闲聊一下呗 就是嗯 简单介绍一下然后我也知道一下这个我们不建议的话可以把这个摄像头打开,我们简单聊一下,就是这样的话大家 其实我也希望知道大家
[75:00] it. I was just like, 27th century I don't know a lot, but I just want to talk a few minutes. And then uh, Yes, we can briefly introduce ourselves and meet each other. It's an aside cost High definition, it's accurate to 0.5. Because the GPS is accurate to 0.5. If you look at the Apollo project, the navigation is the main part. It's the main part of the GPS and navigation. So the BDU's structure is more like Cheers, Carl. Yeah. Thank you. or just simple, I'll just take the recording.
![[Chinese] Mock Interview: Design google map — Scott Shi](https://reducer.xgoose.org/media/thumbnail/3891.jpg)