計：為對話機器人打造地理編碼與POI檢索能力)
lingbot-map這個項目說起來起因特別樸素我們內(nèi)部那套叫l(wèi)ingbot的對話機器人框架被業(yè)務(wù)方追著要一個能認路、能找店、能算距離的地圖能力。一開始我滿腦子想的都是接第三方地圖SDK結(jié)果一調(diào)研就僵住了——商業(yè)地圖服務(wù)的配額費、流量費在演示環(huán)境很友好一上生產(chǎn)就是另一套價碼而且底圖樣式、POI數(shù)據(jù)、路線引擎全都綁在別人生態(tài)里想換底圖或者混入企業(yè)私有點位幾乎沒有操作空間。于是我們決定自己寫一個輕量的、自托管的、可以嵌進lingbot框架的地圖模塊也就是lingbot-map。lingbot-map做的事不復(fù)雜瓦片渲染、地理編碼、逆地理編碼、POI檢索、距離和路線估算外加一套適合對話場景的查詢接口。它不打算跟商業(yè)地圖App比豐富度目標只有一個——讓機器人在對話里說到位置的時候不至于一問三不知。這篇文章把整個模塊從需求拆解、核心原理、工程決策到實測優(yōu)化的完整過程都捋一遍適合正在做機器人或助手類產(chǎn)品、想給自家應(yīng)用加一個自托管輕量地圖能力的同學參考。1. 為什么會有l(wèi)ingbot-map商業(yè)地圖API之外的現(xiàn)實選擇1.1 最初的需求機器人先得知道自己在哪很多對話場景一旦涉及位置問題就立刻復(fù)雜起來。用戶報修時說2號樓東側(cè)門禁壞了會議紀要里寫在園區(qū)B棟集合外賣場景說送到樓下前臺這些句子里的2號樓B棟樓下都是位置可機器人拿到的是一段文本如果不知道園區(qū)的經(jīng)緯度范圍根本沒法把這些話變成可計算的坐標。我們最初梳理出的需求很明確機器人需要把自然語言里的方位表達解析成結(jié)構(gòu)化坐標再基于坐標完成兩個動作——查找附近的POI興趣點以及告訴用戶大概要跑多遠。除此之外的需求比如實時交通、導(dǎo)航語音播報當時沒有一個人提。這也是lingbot-map最后能被控制在一個合理規(guī)模里的前提所有功能都由真實對話需求驅(qū)動而不是為了做一個地圖而做。1.2 商業(yè)地圖服務(wù)的三道隱形門檻不接商業(yè)SDK不是因為它不好而是因為三道門檻在對話機器人這個場景里太難受了。第一是費用結(jié)構(gòu)。演示環(huán)境和個人測試通常有免費額度但生產(chǎn)環(huán)境的調(diào)用成本跟業(yè)務(wù)量強相關(guān)對話機器人是高頻交互用戶每問一次附近有什么就是一次地理編碼加一次POI檢索。日活上去之后費用是線性增長的而且這部分成本很難轉(zhuǎn)嫁給用戶。第二是數(shù)據(jù)鎖定。商業(yè)平臺的底圖、POI、路線規(guī)則是一套封閉體系企業(yè)內(nèi)部的位置數(shù)據(jù)——比如自有園區(qū)、合作門店、敏感點位——要么沒有入口錄入要么受平臺審核規(guī)則限制。我們要的是一個公用數(shù)據(jù)私有數(shù)據(jù)混排的地圖商業(yè)平臺給不了。第三是數(shù)據(jù)出域風險。企業(yè)內(nèi)部位置信息屬于業(yè)務(wù)數(shù)據(jù)讓這類數(shù)據(jù)在每次查詢時都經(jīng)過外部服務(wù)對很多團隊來說是不可接受的數(shù)據(jù)安全紅線。自托管方案把數(shù)據(jù)留在自己手里日志、緩存、訪問鏈路都能完全管控。1.3 主動砍掉的功能地圖模塊的邊界自研最大的陷阱是功能蔓延。我們開工時立了幾條規(guī)矩不做實時路況不做衛(wèi)星影像不做室內(nèi)地圖不做導(dǎo)航語音。所有這些在對話場景里要么數(shù)據(jù)源貴得離譜要么用戶根本用不上。最終的功能范圍很明確能力是否實現(xiàn)說明柵格瓦片底圖渲染是縮放級別覆蓋10到17滿足城市級到街區(qū)級地理編碼是文本地址轉(zhuǎn)坐標返回候選列表逆地理編碼是坐標反查行政區(qū)與最近POI關(guān)鍵詞POI檢索是按關(guān)鍵詞和半徑篩選支持排序距離估算是球面距離為主可選道路距離路線規(guī)劃部分輕量路網(wǎng)的預(yù)估方案不承諾實時路況實時路況否數(shù)據(jù)獲取和維護成本太高衛(wèi)星影像否瓦片體量大交互場景收益低砍功能的同時我們反反復(fù)復(fù)跟使用者確認了一點所有查詢接口必須能在100毫秒內(nèi)返回因為對話系統(tǒng)對延遲的敏感度遠超Web頁面。這句話后來成了整個模塊設(shè)計的最高優(yōu)先級。2. 瓦片渲染與坐標先把地圖畫出來2.1 瓦片金字塔一張大地圖怎么切成小方塊地圖繪制的核心不是畫而是切。一張完整的世界地圖在屏幕上一次性渲染是不可能的業(yè)界通行做法是瓦片金字塔把某一縮放級別下的地圖切成固定大小的正方形小圖瀏覽器或客戶端只加載當前視野內(nèi)需要的那些塊。瓦片編號有一套全球統(tǒng)一的計算方式俗稱slippy map規(guī)則在第z級縮放級別整個地球被分成2^z × 2^z個瓦片x從西到東遞增y從北到南遞增。給定經(jīng)緯度換算成瓦片坐標的公式很固定function lonLatToTile(lon, lat, zoom) { const x Math.floor((lon 180) / 360 * Math.pow(2, zoom)); const latRad lat * Math.PI / 180; const y Math.floor( (1 - Math.log(Math.tan(latRad) 1 / Math.cos(latRad)) / Math.PI) / 2 * Math.pow(2, zoom) ); return { x, y, z: zoom }; }這個公式我建議直接背下來或者存到工具庫最顯眼的位置。整個模塊里幾乎所有功能——定位、搜索、路線——最終都要落到給定坐標知道它在哪個瓦片上這一步。忘了括號或者把y方向取反地圖就會出現(xiàn)南北顛倒或者錯位一整行這種看著特別詭異的毛病。2.2 Web Mercator投影為什么地圖上高緯度地區(qū)會變形瓦片系統(tǒng)建立在Web Mercator投影EPSG:3857上。它把地球近似成一個球體然后展開成正方形平面。好處是計算簡單、方向恒定壞處是越靠近極地變形越嚴重所以Web Mercator的實際覆蓋范圍被限制在南北緯85.05113度以內(nèi)超出這個范圍沒有瓦片。這套投影對工程實現(xiàn)的影響在邊界上體現(xiàn)得最明顯。瓦片y坐標在緯度為85.05113度時正好是0緯度往后再高就是負值。我們早期的代碼沒做截斷在高緯度測試點出現(xiàn)了一批坐標異常排查了半天才發(fā)現(xiàn)是投影邊界問題。所以無論你用哪個地圖庫第一課都是經(jīng)緯度進瓦片計算之前先在緯度上做一次clamp(-85.05113, 85.05113)。瓦片尺寸方面主流有兩種規(guī)格256×256和512×512。256的兼容性好512在Retina屏幕上更清晰。我建議先在256規(guī)格上把整個鏈路跑通確認渲染無誤之后再考慮是否切512因為瓦片體量會隨著邊長平方增長。2.3 坐標偏移混用底圖與坐標源時最隱蔽的坑國內(nèi)做地圖繞不開一個概念坐標偏移。GPS拿到的原始坐標是WGS-84橢球體系而國內(nèi)合規(guī)發(fā)布的地圖產(chǎn)品通常使用經(jīng)過偏移加密的坐標體系。這兩種坐標系之間的偏移不是一個固定常數(shù)而是隨位置變化的非線性變換。換句話說你不能靠統(tǒng)一減掉0.001度來校正那樣在部分地區(qū)誤差會到幾百米。lingbot-map的定位是自托管輕量模塊我們用的策略是整個系統(tǒng)內(nèi)部統(tǒng)一使用WGS-84作為基準坐標所有外部來源的坐標在入口處經(jīng)過一個可插拔的CoordinateTransformer轉(zhuǎn)換器底圖瓦片源則按照它實際采用的坐標體系選擇對應(yīng)的請求參數(shù)。核心經(jīng)驗是坐標轉(zhuǎn)換必須在數(shù)據(jù)進入系統(tǒng)的第一道關(guān)口完成絕不能散落在各個業(yè)務(wù)接口里各轉(zhuǎn)各的否則維護成本會失控。另外一個很容易忽略的點公共網(wǎng)絡(luò)上流傳的糾偏算法公式大多是通過采樣點擬合出來的近似解在某些地區(qū)精度可以在個別區(qū)域會出現(xiàn)突變。線上環(huán)境如果對精度有硬要求建議在關(guān)鍵區(qū)域布設(shè)本地控制點做二次修正這個話題后面的踩坑章節(jié)還會詳細講。3. 地名解析自建地理編碼服務(wù)的輕量實現(xiàn)3.1 詞庫與索引十萬條POI要怎么塞進內(nèi)存地理編碼就是把文本地址翻譯成坐標。商業(yè)服務(wù)做這件事靠海量地址庫和復(fù)雜的解析模型我們自托管顯然不能那么奢侈路徑是公開地名數(shù)據(jù) 企業(yè)私有POI合并成一個精簡詞庫再用內(nèi)存索引加速檢索。詞庫的索引結(jié)構(gòu)我最終選擇了前綴樹 拼音前綴 編輯距離三層組合。首先是基于漢字的前綴樹保證科技園區(qū)能快速命中所有以這四個字開頭的記錄其次是把地名轉(zhuǎn)成拼音后建立拼音前綴索引解決用戶輸入拼音的場景最后是編輯距離兜底用來處理用戶輸入少個字、多個字或順序顛倒的情況。這個方案每增加一條POI記錄內(nèi)存開銷大概在幾百字節(jié)量級十萬條POI僅索引部分占用約50MB左右在現(xiàn)在的服務(wù)器配置下完全不是問題。真正要控制的是數(shù)據(jù)質(zhì)量詞庫里同名地點太多會讓候選列表變得不可用所以每條記錄都帶行政區(qū)劃和類型標簽檢索時先按行政區(qū)過濾再按文本相似度排序。3.2 解析流程從附近咖啡館到坐標候選一次完整的地理編碼查詢走四步。第一步是標準化把大約附近大概那個這類修飾詞剝掉再把東門西門這樣的相對方位詞解析成更明確的方位描述。第二步是候選召回用前面建的索引去找所有可能的匹配項這一步要求快寧多勿漏。第三步是評分排序綜合文本相似度、行政層級匹配度和距離權(quán)重給每個候選算出置信度。第四步是輸出返回Top N個候選而不是強行只給一個。這么做非常重要。對話場景的地址往往殘缺不全去上次那家店公司樓下老地方見——這些表達缺乏結(jié)構(gòu)化信息硬解析成單一坐標必然出錯。返回候選列表讓上層機器人把選擇權(quán)交給用戶或者結(jié)合會話上下文判斷才是符合對話語義的做法。{ status: 0, query: 園區(qū)B棟咖啡店, candidates: [ {name: 園區(qū)B棟咖啡店, lat: 30.2501, lng: 120.2012, score: 0.95, type: poi}, {name: B棟咖啡工坊, lat: 30.2510, lng: 120.1998, score: 0.71, type: poi} ] }3.3 逆地理編碼從坐標反查這是哪兒逆地理編碼比正向解析簡單但坑也不少。我們給出的坐標點要先判斷落在哪個行政區(qū)劃內(nèi)再找距離最近的POI。行政區(qū)劃判斷本質(zhì)是點是否在多邊形內(nèi)的問題經(jīng)典算法是射線法從目標點引一條水平射線統(tǒng)計它與多邊形邊的交點數(shù)奇數(shù)在內(nèi)偶數(shù)在外。這個算法本身很快真正的問題是行政邊界數(shù)據(jù)往往是幾萬個頂點的大多邊形逐點判斷性能上不去。我的優(yōu)化方案是把每個行政區(qū)的外包矩形作為粗篩網(wǎng)格一個坐標點先通過外包矩形快速過濾掉絕大多數(shù)不可能的多邊形剩下的再走射線法精判。實測下來這個兩級判斷能讓逆地理編碼的單次延遲控制在幾十毫秒量級。逆地理編碼還有一個業(yè)務(wù)層面的細節(jié)也是踩坑章節(jié)的重點行政區(qū)劃邊界存在飛地和重疊歸屬的情況一個點落在兩個區(qū)劃的邊界附近時返回哪個區(qū)劃必須要有明確的業(yè)務(wù)規(guī)則不能靠算法隨機。4. 距離與路線對話場景夠用即可4.1 三種距離別拿直線距離騙用戶距離計算是地圖模塊里用戶感知最強的部分。同樣是3公里遠直線距離和實際駕車距離差別很大在道路繞行嚴重的城區(qū)可以差到一倍以上。最基礎(chǔ)的是球面距離用Haversine公式實現(xiàn)import math def haversine_km(lat1, lon1, lat2, lon2): r 6371.0 p1, p2 math.radians(lat1), math.radians(lat2) dp math.radians(lat2 - lat1) dl math.radians(lon2 - lon1) a math.sin(dp / 2) ** 2 math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2 return 2 * r * math.asin(math.sqrt(a))但對話機器人直接跟用戶說1.8公里直線距離是會被罵的。我們對距離估算做了一個道路系數(shù)修正先按城市類型和區(qū)域特征給直線距離乘一個繞路系數(shù)——城市密集區(qū)取值1.4到1.6郊區(qū)取值1.7到2.0。這個方案的準確度在大多數(shù)場景下足夠而且?guī)缀醪辉黾佑嬎懔俊Ｈ绻阈枰呔仍倏紤]引入真實路網(wǎng)。4.2 輕量路網(wǎng)加A星路線規(guī)劃的壓縮版要實現(xiàn)真正的道路距離就得有路網(wǎng)數(shù)據(jù)。我們做的不是全量精細路網(wǎng)而是只保留主干道和次干道的輕量拓撲然后基于A星算法計算最短路徑。A星的啟發(fā)函數(shù)直接用Haversine距離加上一個當前邊權(quán)重的估計。輕量路網(wǎng)因為節(jié)點少搜索空間有限單次路線規(guī)劃在幾十毫秒內(nèi)可以完成。這套方案的局限也很明顯它不區(qū)分車道、匝道和紅綠燈算出來的是一條理論上可行的路線不能當導(dǎo)航用。但在對話場景里用戶要的答案是打車大概20分鐘還是騎車15分鐘輕量路網(wǎng)恰好夠用。路線數(shù)據(jù)和路網(wǎng)拓撲的維護是成本大頭。我們的策略是只對業(yè)務(wù)覆蓋的高頻區(qū)域生成路網(wǎng)全國范圍內(nèi)的完整路網(wǎng)規(guī)劃優(yōu)先級往后排。每次新增區(qū)域時跑一遍離線路網(wǎng)生成任務(wù)產(chǎn)出結(jié)果提交到瓦片包一起發(fā)布。4.3 為對話設(shè)計的查詢協(xié)議地圖模塊最后提供服務(wù)的方式是一組REST接口但設(shè)計這批接口時我們想的不是地圖怎么暴露能力而是機器人對話時最需要什么。接口被設(shè)計成三類/v1/geocode用于文本轉(zhuǎn)坐標/v1/search用于POI檢索/v1/route用于路線和距離。每個接口都支持在請求體里帶一個session_id模塊會把當前會話最近的錨點位置緩存起來。這樣多輪對話里用戶先說我在C棟樓下機器人記住這個位置下一句說附近有打印店嗎就不需要用戶再重復(fù)一遍位置信息。異步和限流也是必須的。地理編碼批量導(dǎo)入任務(wù)會占用較多CPU如果跟線上查詢搶資源會導(dǎo)致對話延遲飆高。我們在服務(wù)里給查詢設(shè)置了獨立的線程池重任務(wù)走消息隊列保證線上查詢通道始終有冗余資源。這個設(shè)計在后來的壓測里證明非常值——有一版我們把導(dǎo)入任務(wù)直接放在主進程跑結(jié)果查詢p95延遲從60毫秒被拉到900毫秒回滾之后立刻恢復(fù)。5. 性能實測從零散請求到穩(wěn)定低延遲5.1 瓦片訪問優(yōu)化首屏從4.8秒壓到780毫秒地圖模塊被接入機器人之后第一個性能瓶頸出現(xiàn)在瓦片加載。對話端的歷史消息里嵌入了地圖卡片用戶每次翻開詳情都要重新加載瓦片冷啟動狀態(tài)下首屏要4.8秒體驗完全不能接受。我們對癥下藥做了三件事。第一是兩級LRU緩存內(nèi)存緩存最近訪問的瓦片磁盤緩存做持久化內(nèi)存不夠時逐出到磁盤。第二是熱門區(qū)域預(yù)取根據(jù)歷史查詢熱度提前把常用區(qū)域的低級別瓦片生成好放進緩存用戶一來就是熱的。第三是靜態(tài)資源走對象存儲并掛內(nèi)容分發(fā)網(wǎng)絡(luò)把重復(fù)請求的壓力從應(yīng)用服務(wù)上卸掉。優(yōu)化后的首屏加載從4.8秒降到780毫秒這個結(jié)果說明了一個道理在自托管地圖模塊里瓶頸通常不是計算能力而是數(shù)據(jù)組織方式。5.2 地名索引預(yù)熱與查詢優(yōu)化地理編碼服務(wù)的性能取決于索引是否在內(nèi)存里常駐。我們采用的方式是啟動時一次性加載全部索引到內(nèi)存用內(nèi)存映射方式訪問索引文件查詢時不落盤。優(yōu)化前單次地理編碼平均320毫秒排查發(fā)現(xiàn)大部分時間耗在冷啟動后的首次磁盤讀取上。索引預(yù)熱之后單查降到38毫秒p95也穩(wěn)定在60毫秒以內(nèi)。附近POI檢索5公里半徑從900毫秒降到60毫秒靠的是在檢索前先用geohash網(wǎng)格做粗篩命中候選后再計算精確距離排序。這里有個計算細節(jié)值得強調(diào)全量POI兩兩算Haversine的距離排序非常昂貴但如果你先按geohash定位到同一網(wǎng)格把候選集縮到十幾條再對這十幾條算精確距離成本就完全可以忽略。粗篩用索引精算用公式這套組合拳在空間檢索里通用。5.3 低配環(huán)境下的資源核算很多讀者關(guān)心自托管地圖到底要什么配置。我們做了一組基準測試部署環(huán)境數(shù)據(jù)規(guī)模實測表現(xiàn)2核4G單城市POI 局部瓦片緩存支撐內(nèi)部演示與低流量驗證穩(wěn)態(tài)QPS約304核8G省級POI 多級瓦片緩存支撐正式對話流量穩(wěn)態(tài)QPS約120p95 100ms8核16G多點區(qū)域POI 大尺寸瓦片包可支撐多業(yè)務(wù)線并發(fā)主要瓶頸在帶寬瓦片包體量也需要提前算清楚只做單城市的常用縮放級別柵格瓦片大概1到3GB如果覆蓋到一個省且包含高縮放級別體量會漲到幾十GB。我們的經(jīng)驗是瓦片包體積直接決定了部署成本和更新頻率所以默認只在業(yè)務(wù)熱點區(qū)域生成高縮放級別瓦片低級別全局鋪底把總包控制在5GB以內(nèi)。6. 踩坑記錄文檔里查不到的五個細節(jié)6.1 瓦片索引的邊界取整錯誤第一個坑在瓦片坐標計算。x和y必須用向下取整這個大多數(shù)人都知道但y方向在北半球高緯度地區(qū)有個隱藏問題當緯度超過Web Mercator的85.05113度上限時y值變成負的數(shù)組下標越界瓦片渲染直接崩潰。我們在一次高緯度測試點的聯(lián)調(diào)里遇到了整個地圖區(qū)域灰屏的現(xiàn)象查了一下午發(fā)現(xiàn)是測試數(shù)據(jù)里混入了一個緯度85.5度的異常坐標點。修復(fù)方式就是在進入瓦片計算前對緯度做clamp。后來我把這行clamp寫成了公共函數(shù)的一個固定步驟所有調(diào)用方都從這里走一勞永逸。6.2 坐標偏移在邊緣區(qū)域的突變坐標轉(zhuǎn)換是另一個反復(fù)出問題的地方。我們一開始直接采用網(wǎng)上流傳的公開糾偏算法在大多數(shù)區(qū)域表現(xiàn)正常但在某些地區(qū)誤差突然放大到幾百米。地圖上一開始幾百米的偏移很難肉眼發(fā)現(xiàn)直到用戶反饋機器人說的位置永遠偏了一條街我們才意識到是轉(zhuǎn)換精度在這些區(qū)域失效了。解決方案是用本地控制點做校正收集一批在該區(qū)域已知真實坐標與展示坐標對應(yīng)的樣本點對偏差建一個區(qū)域修正表轉(zhuǎn)換時先查表再套用通用算法。這個方案比單純調(diào)參可靠得多也讓我徹底明白了一個道理坐標偏移問題是空間相關(guān)的任何一勞永逸的近似公式都要在目標區(qū)域做局部驗證。6.3 瓦片預(yù)取把帶寬打滿了瓦片預(yù)取功能上線的第一天我們就把自己給打掛了。預(yù)取程序用20個并發(fā)線程去熱門區(qū)域抓瓦片結(jié)果應(yīng)用服務(wù)的連接池和帶寬瞬間被打滿在線查詢?nèi)砍瑫r。修復(fù)方式是給預(yù)取任務(wù)加信號量限流把并發(fā)控制在2到3個線程并且對失敗請求做指數(shù)退避。實際上瓦片服務(wù)的穩(wěn)定性從來不由總帶寬決定而由瞬時并發(fā)尖峰決定。后來我們給所有內(nèi)部批處理任務(wù)都立了規(guī)矩批處理不得與線上查詢共享同一資源池。6.4 逆地理編碼的飛地與邊界重疊逆地理編碼返回錯誤行政區(qū)是線上反饋里最難排查的一類問題。現(xiàn)象是用戶在地圖上定位機器人報出的行政區(qū)劃和他實際所在的位置對不上。最終定位到兩類原因一是行政邊界存在飛地即某行政區(qū)的一塊區(qū)域完全被另一個行政區(qū)包圍二是多邊形邊界重疊一個點同時落在多個區(qū)劃內(nèi)。單靠多邊形包含算法沒法處理這類問題。我們的做法是對重疊區(qū)域建立網(wǎng)格歸屬表以固定間隔把有沖突的區(qū)域切成網(wǎng)格每個網(wǎng)格預(yù)先指定一個業(yè)務(wù)歸屬同時把這種歸屬結(jié)果緩存起來避免每次查詢都跑一遍多邊形判斷。這套機制上線后逆地理編碼的實際錯誤率降了一個數(shù)量級。6.5 日志里不能出現(xiàn)一根坐標最后這個坑不是技術(shù)問題而是意識問題。地圖模塊的日志里天然會記錄經(jīng)緯度、查詢關(guān)鍵詞、逆地理編碼結(jié)果這些信息與具體用戶關(guān)聯(lián)后就是敏感數(shù)據(jù)。早期排查問題時我們直接把查詢參數(shù)打到了日志里后來安全評審被一票否決。改造方式是在日志輸出層做統(tǒng)一脫敏坐標只保留到小數(shù)點后一位POI名稱做模糊化會話ID替換成不可逆散列。日志脫敏這件事不能靠每個開發(fā)者自覺必須做成框架層強制執(zhí)行的過濾器。我在實際維護lingbot-map的過程中最大的體會是地圖模塊是一個很容易把自己做成無底洞的東西。如果你一開始就想著覆蓋全國數(shù)據(jù)、做完整導(dǎo)航、接實時路況那這項目一年都交付不了。反過來先圈定一個城市或者一個園區(qū)把對話場景里的閉環(huán)跑通——能定位、能找店、能算距離——然后再往下一個區(qū)域擴展才是自托管地圖的正確打開方式。最后再分享一個小技巧附近POI檢索的排序永遠先做geohash網(wǎng)格粗篩再做Haversine精算千萬別讓全量候選集都走一遍球面距離計算否則接口延遲會隨著POI數(shù)量線性膨脹。這是我被壓測數(shù)據(jù)教育出來的經(jīng)驗照著做能省掉你后面大半的優(yōu)化時間。 自托管輕量地圖模塊設(shè)計：為對話機器人打造地理編碼與POI檢索能力
lingbot-map這個項目說起來起因特別樸素我們內(nèi)部那套叫l(wèi)ingbot的對話機器人框架被業(yè)務(wù)方追著要一個能認路、能找店、能算距離的地圖能力。一開始我滿腦子想的都是接第三方地圖SDK結(jié)果一調(diào)研就僵住了——商業(yè)地圖服務(wù)的配額費、流量費在演示環(huán)境很友好一上生產(chǎn)就是另一套價碼而且底圖樣式、POI數(shù)據(jù)、路線引擎全都綁在別人生態(tài)里想換底圖或者混入企業(yè)私有點位幾乎沒有操作空間。于是我們決定自己寫一個輕量的、自托管的、可以嵌進lingbot框架的地圖模塊也就是lingbot-map。lingbot-map做的事不復(fù)雜瓦片渲染、地理編碼、逆地理編碼、POI檢索、距離和路線估算外加一套適合對話場景的查詢接口。它不打算跟商業(yè)地圖App比豐富度目標只有一個——讓機器人在對話里說到位置的時候不至于一問三不知。這篇文章把整個模塊從需求拆解、核心原理、工程決策到實測優(yōu)化的完整過程都捋一遍適合正在做機器人或助手類產(chǎn)品、想給自家應(yīng)用加一個自托管輕量地圖能力的同學參考。1. 為什么會有l(wèi)ingbot-map商業(yè)地圖API之外的現(xiàn)實選擇1.1 最初的需求機器人先得知道自己在哪很多對話場景一旦涉及位置問題就立刻復(fù)雜起來。用戶報修時說2號樓東側(cè)門禁壞了會議紀要里寫在園區(qū)B棟集合外賣場景說送到樓下前臺這些句子里的2號樓B棟樓下都是位置可機器人拿到的是一段文本如果不知道園區(qū)的經(jīng)緯度范圍根本沒法把這些話變成可計算的坐標。我們最初梳理出的需求很明確機器人需要把自然語言里的方位表達解析成結(jié)構(gòu)化坐標再基于坐標完成兩個動作——查找附近的POI興趣點以及告訴用戶大概要跑多遠。除此之外的需求比如實時交通、導(dǎo)航語音播報當時沒有一個人提。這也是lingbot-map最后能被控制在一個合理規(guī)模里的前提所有功能都由真實對話需求驅(qū)動而不是為了做一個地圖而做。1.2 商業(yè)地圖服務(wù)的三道隱形門檻不接商業(yè)SDK不是因為它不好而是因為三道門檻在對話機器人這個場景里太難受了。第一是費用結(jié)構(gòu)。演示環(huán)境和個人測試通常有免費額度但生產(chǎn)環(huán)境的調(diào)用成本跟業(yè)務(wù)量強相關(guān)對話機器人是高頻交互用戶每問一次附近有什么就是一次地理編碼加一次POI檢索。日活上去之后費用是線性增長的而且這部分成本很難轉(zhuǎn)嫁給用戶。第二是數(shù)據(jù)鎖定。商業(yè)平臺的底圖、POI、路線規(guī)則是一套封閉體系企業(yè)內(nèi)部的位置數(shù)據(jù)——比如自有園區(qū)、合作門店、敏感點位——要么沒有入口錄入要么受平臺審核規(guī)則限制。我們要的是一個公用數(shù)據(jù)私有數(shù)據(jù)混排的地圖商業(yè)平臺給不了。第三是數(shù)據(jù)出域風險。企業(yè)內(nèi)部位置信息屬于業(yè)務(wù)數(shù)據(jù)讓這類數(shù)據(jù)在每次查詢時都經(jīng)過外部服務(wù)對很多團隊來說是不可接受的數(shù)據(jù)安全紅線。自托管方案把數(shù)據(jù)留在自己手里日志、緩存、訪問鏈路都能完全管控。1.3 主動砍掉的功能地圖模塊的邊界自研最大的陷阱是功能蔓延。我們開工時立了幾條規(guī)矩不做實時路況不做衛(wèi)星影像不做室內(nèi)地圖不做導(dǎo)航語音。所有這些在對話場景里要么數(shù)據(jù)源貴得離譜要么用戶根本用不上。最終的功能范圍很明確能力是否實現(xiàn)說明柵格瓦片底圖渲染是縮放級別覆蓋10到17滿足城市級到街區(qū)級地理編碼是文本地址轉(zhuǎn)坐標返回候選列表逆地理編碼是坐標反查行政區(qū)與最近POI關(guān)鍵詞POI檢索是按關(guān)鍵詞和半徑篩選支持排序距離估算是球面距離為主可選道路距離路線規(guī)劃部分輕量路網(wǎng)的預(yù)估方案不承諾實時路況實時路況否數(shù)據(jù)獲取和維護成本太高衛(wèi)星影像否瓦片體量大交互場景收益低砍功能的同時我們反反復(fù)復(fù)跟使用者確認了一點所有查詢接口必須能在100毫秒內(nèi)返回因為對話系統(tǒng)對延遲的敏感度遠超Web頁面。這句話后來成了整個模塊設(shè)計的最高優(yōu)先級。2. 瓦片渲染與坐標先把地圖畫出來2.1 瓦片金字塔一張大地圖怎么切成小方塊地圖繪制的核心不是畫而是切。一張完整的世界地圖在屏幕上一次性渲染是不可能的業(yè)界通行做法是瓦片金字塔把某一縮放級別下的地圖切成固定大小的正方形小圖瀏覽器或客戶端只加載當前視野內(nèi)需要的那些塊。瓦片編號有一套全球統(tǒng)一的計算方式俗稱slippy map規(guī)則在第z級縮放級別整個地球被分成2^z × 2^z個瓦片x從西到東遞增y從北到南遞增。給定經(jīng)緯度換算成瓦片坐標的公式很固定function lonLatToTile(lon, lat, zoom) { const x Math.floor((lon 180) / 360 * Math.pow(2, zoom)); const latRad lat * Math.PI / 180; const y Math.floor( (1 - Math.log(Math.tan(latRad) 1 / Math.cos(latRad)) / Math.PI) / 2 * Math.pow(2, zoom) ); return { x, y, z: zoom }; }這個公式我建議直接背下來或者存到工具庫最顯眼的位置。整個模塊里幾乎所有功能——定位、搜索、路線——最終都要落到給定坐標知道它在哪個瓦片上這一步。忘了括號或者把y方向取反地圖就會出現(xiàn)南北顛倒或者錯位一整行這種看著特別詭異的毛病。2.2 Web Mercator投影為什么地圖上高緯度地區(qū)會變形瓦片系統(tǒng)建立在Web Mercator投影EPSG:3857上。它把地球近似成一個球體然后展開成正方形平面。好處是計算簡單、方向恒定壞處是越靠近極地變形越嚴重所以Web Mercator的實際覆蓋范圍被限制在南北緯85.05113度以內(nèi)超出這個范圍沒有瓦片。這套投影對工程實現(xiàn)的影響在邊界上體現(xiàn)得最明顯。瓦片y坐標在緯度為85.05113度時正好是0緯度往后再高就是負值。我們早期的代碼沒做截斷在高緯度測試點出現(xiàn)了一批坐標異常排查了半天才發(fā)現(xiàn)是投影邊界問題。所以無論你用哪個地圖庫第一課都是經(jīng)緯度進瓦片計算之前先在緯度上做一次clamp(-85.05113, 85.05113)。瓦片尺寸方面主流有兩種規(guī)格256×256和512×512。256的兼容性好512在Retina屏幕上更清晰。我建議先在256規(guī)格上把整個鏈路跑通確認渲染無誤之后再考慮是否切512因為瓦片體量會隨著邊長平方增長。2.3 坐標偏移混用底圖與坐標源時最隱蔽的坑國內(nèi)做地圖繞不開一個概念坐標偏移。GPS拿到的原始坐標是WGS-84橢球體系而國內(nèi)合規(guī)發(fā)布的地圖產(chǎn)品通常使用經(jīng)過偏移加密的坐標體系。這兩種坐標系之間的偏移不是一個固定常數(shù)而是隨位置變化的非線性變換。換句話說你不能靠統(tǒng)一減掉0.001度來校正那樣在部分地區(qū)誤差會到幾百米。lingbot-map的定位是自托管輕量模塊我們用的策略是整個系統(tǒng)內(nèi)部統(tǒng)一使用WGS-84作為基準坐標所有外部來源的坐標在入口處經(jīng)過一個可插拔的CoordinateTransformer轉(zhuǎn)換器底圖瓦片源則按照它實際采用的坐標體系選擇對應(yīng)的請求參數(shù)。核心經(jīng)驗是坐標轉(zhuǎn)換必須在數(shù)據(jù)進入系統(tǒng)的第一道關(guān)口完成絕不能散落在各個業(yè)務(wù)接口里各轉(zhuǎn)各的否則維護成本會失控。另外一個很容易忽略的點公共網(wǎng)絡(luò)上流傳的糾偏算法公式大多是通過采樣點擬合出來的近似解在某些地區(qū)精度可以在個別區(qū)域會出現(xiàn)突變。線上環(huán)境如果對精度有硬要求建議在關(guān)鍵區(qū)域布設(shè)本地控制點做二次修正這個話題后面的踩坑章節(jié)還會詳細講。3. 地名解析自建地理編碼服務(wù)的輕量實現(xiàn)3.1 詞庫與索引十萬條POI要怎么塞進內(nèi)存地理編碼就是把文本地址翻譯成坐標。商業(yè)服務(wù)做這件事靠海量地址庫和復(fù)雜的解析模型我們自托管顯然不能那么奢侈路徑是公開地名數(shù)據(jù) 企業(yè)私有POI合并成一個精簡詞庫再用內(nèi)存索引加速檢索。詞庫的索引結(jié)構(gòu)我最終選擇了前綴樹 拼音前綴 編輯距離三層組合。首先是基于漢字的前綴樹保證科技園區(qū)能快速命中所有以這四個字開頭的記錄其次是把地名轉(zhuǎn)成拼音后建立拼音前綴索引解決用戶輸入拼音的場景最后是編輯距離兜底用來處理用戶輸入少個字、多個字或順序顛倒的情況。這個方案每增加一條POI記錄內(nèi)存開銷大概在幾百字節(jié)量級十萬條POI僅索引部分占用約50MB左右在現(xiàn)在的服務(wù)器配置下完全不是問題。真正要控制的是數(shù)據(jù)質(zhì)量詞庫里同名地點太多會讓候選列表變得不可用所以每條記錄都帶行政區(qū)劃和類型標簽檢索時先按行政區(qū)過濾再按文本相似度排序。3.2 解析流程從附近咖啡館到坐標候選一次完整的地理編碼查詢走四步。第一步是標準化把大約附近大概那個這類修飾詞剝掉再把東門西門這樣的相對方位詞解析成更明確的方位描述。第二步是候選召回用前面建的索引去找所有可能的匹配項這一步要求快寧多勿漏。第三步是評分排序綜合文本相似度、行政層級匹配度和距離權(quán)重給每個候選算出置信度。第四步是輸出返回Top N個候選而不是強行只給一個。這么做非常重要。對話場景的地址往往殘缺不全去上次那家店公司樓下老地方見——這些表達缺乏結(jié)構(gòu)化信息硬解析成單一坐標必然出錯。返回候選列表讓上層機器人把選擇權(quán)交給用戶或者結(jié)合會話上下文判斷才是符合對話語義的做法。{ status: 0, query: 園區(qū)B棟咖啡店, candidates: [ {name: 園區(qū)B棟咖啡店, lat: 30.2501, lng: 120.2012, score: 0.95, type: poi}, {name: B棟咖啡工坊, lat: 30.2510, lng: 120.1998, score: 0.71, type: poi} ] }3.3 逆地理編碼從坐標反查這是哪兒逆地理編碼比正向解析簡單但坑也不少。我們給出的坐標點要先判斷落在哪個行政區(qū)劃內(nèi)再找距離最近的POI。行政區(qū)劃判斷本質(zhì)是點是否在多邊形內(nèi)的問題經(jīng)典算法是射線法從目標點引一條水平射線統(tǒng)計它與多邊形邊的交點數(shù)奇數(shù)在內(nèi)偶數(shù)在外。這個算法本身很快真正的問題是行政邊界數(shù)據(jù)往往是幾萬個頂點的大多邊形逐點判斷性能上不去。我的優(yōu)化方案是把每個行政區(qū)的外包矩形作為粗篩網(wǎng)格一個坐標點先通過外包矩形快速過濾掉絕大多數(shù)不可能的多邊形剩下的再走射線法精判。實測下來這個兩級判斷能讓逆地理編碼的單次延遲控制在幾十毫秒量級。逆地理編碼還有一個業(yè)務(wù)層面的細節(jié)也是踩坑章節(jié)的重點行政區(qū)劃邊界存在飛地和重疊歸屬的情況一個點落在兩個區(qū)劃的邊界附近時返回哪個區(qū)劃必須要有明確的業(yè)務(wù)規(guī)則不能靠算法隨機。4. 距離與路線對話場景夠用即可4.1 三種距離別拿直線距離騙用戶距離計算是地圖模塊里用戶感知最強的部分。同樣是3公里遠直線距離和實際駕車距離差別很大在道路繞行嚴重的城區(qū)可以差到一倍以上。最基礎(chǔ)的是球面距離用Haversine公式實現(xiàn)import math def haversine_km(lat1, lon1, lat2, lon2): r 6371.0 p1, p2 math.radians(lat1), math.radians(lat2) dp math.radians(lat2 - lat1) dl math.radians(lon2 - lon1) a math.sin(dp / 2) ** 2 math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2 return 2 * r * math.asin(math.sqrt(a))但對話機器人直接跟用戶說1.8公里直線距離是會被罵的。我們對距離估算做了一個道路系數(shù)修正先按城市類型和區(qū)域特征給直線距離乘一個繞路系數(shù)——城市密集區(qū)取值1.4到1.6郊區(qū)取值1.7到2.0。這個方案的準確度在大多數(shù)場景下足夠而且?guī)缀醪辉黾佑嬎懔俊Ｈ绻阈枰呔仍倏紤]引入真實路網(wǎng)。4.2 輕量路網(wǎng)加A星路線規(guī)劃的壓縮版要實現(xiàn)真正的道路距離就得有路網(wǎng)數(shù)據(jù)。我們做的不是全量精細路網(wǎng)而是只保留主干道和次干道的輕量拓撲然后基于A星算法計算最短路徑。A星的啟發(fā)函數(shù)直接用Haversine距離加上一個當前邊權(quán)重的估計。輕量路網(wǎng)因為節(jié)點少搜索空間有限單次路線規(guī)劃在幾十毫秒內(nèi)可以完成。這套方案的局限也很明顯它不區(qū)分車道、匝道和紅綠燈算出來的是一條理論上可行的路線不能當導(dǎo)航用。但在對話場景里用戶要的答案是打車大概20分鐘還是騎車15分鐘輕量路網(wǎng)恰好夠用。路線數(shù)據(jù)和路網(wǎng)拓撲的維護是成本大頭。我們的策略是只對業(yè)務(wù)覆蓋的高頻區(qū)域生成路網(wǎng)全國范圍內(nèi)的完整路網(wǎng)規(guī)劃優(yōu)先級往后排。每次新增區(qū)域時跑一遍離線路網(wǎng)生成任務(wù)產(chǎn)出結(jié)果提交到瓦片包一起發(fā)布。4.3 為對話設(shè)計的查詢協(xié)議地圖模塊最后提供服務(wù)的方式是一組REST接口但設(shè)計這批接口時我們想的不是地圖怎么暴露能力而是機器人對話時最需要什么。接口被設(shè)計成三類/v1/geocode用于文本轉(zhuǎn)坐標/v1/search用于POI檢索/v1/route用于路線和距離。每個接口都支持在請求體里帶一個session_id模塊會把當前會話最近的錨點位置緩存起來。這樣多輪對話里用戶先說我在C棟樓下機器人記住這個位置下一句說附近有打印店嗎就不需要用戶再重復(fù)一遍位置信息。異步和限流也是必須的。地理編碼批量導(dǎo)入任務(wù)會占用較多CPU如果跟線上查詢搶資源會導(dǎo)致對話延遲飆高。我們在服務(wù)里給查詢設(shè)置了獨立的線程池重任務(wù)走消息隊列保證線上查詢通道始終有冗余資源。這個設(shè)計在后來的壓測里證明非常值——有一版我們把導(dǎo)入任務(wù)直接放在主進程跑結(jié)果查詢p95延遲從60毫秒被拉到900毫秒回滾之后立刻恢復(fù)。5. 性能實測從零散請求到穩(wěn)定低延遲5.1 瓦片訪問優(yōu)化首屏從4.8秒壓到780毫秒地圖模塊被接入機器人之后第一個性能瓶頸出現(xiàn)在瓦片加載。對話端的歷史消息里嵌入了地圖卡片用戶每次翻開詳情都要重新加載瓦片冷啟動狀態(tài)下首屏要4.8秒體驗完全不能接受。我們對癥下藥做了三件事。第一是兩級LRU緩存內(nèi)存緩存最近訪問的瓦片磁盤緩存做持久化內(nèi)存不夠時逐出到磁盤。第二是熱門區(qū)域預(yù)取根據(jù)歷史查詢熱度提前把常用區(qū)域的低級別瓦片生成好放進緩存用戶一來就是熱的。第三是靜態(tài)資源走對象存儲并掛內(nèi)容分發(fā)網(wǎng)絡(luò)把重復(fù)請求的壓力從應(yīng)用服務(wù)上卸掉。優(yōu)化后的首屏加載從4.8秒降到780毫秒這個結(jié)果說明了一個道理在自托管地圖模塊里瓶頸通常不是計算能力而是數(shù)據(jù)組織方式。5.2 地名索引預(yù)熱與查詢優(yōu)化地理編碼服務(wù)的性能取決于索引是否在內(nèi)存里常駐。我們采用的方式是啟動時一次性加載全部索引到內(nèi)存用內(nèi)存映射方式訪問索引文件查詢時不落盤。優(yōu)化前單次地理編碼平均320毫秒排查發(fā)現(xiàn)大部分時間耗在冷啟動后的首次磁盤讀取上。索引預(yù)熱之后單查降到38毫秒p95也穩(wěn)定在60毫秒以內(nèi)。附近POI檢索5公里半徑從900毫秒降到60毫秒靠的是在檢索前先用geohash網(wǎng)格做粗篩命中候選后再計算精確距離排序。這里有個計算細節(jié)值得強調(diào)全量POI兩兩算Haversine的距離排序非常昂貴但如果你先按geohash定位到同一網(wǎng)格把候選集縮到十幾條再對這十幾條算精確距離成本就完全可以忽略。粗篩用索引精算用公式這套組合拳在空間檢索里通用。5.3 低配環(huán)境下的資源核算很多讀者關(guān)心自托管地圖到底要什么配置。我們做了一組基準測試部署環(huán)境數(shù)據(jù)規(guī)模實測表現(xiàn)2核4G單城市POI 局部瓦片緩存支撐內(nèi)部演示與低流量驗證穩(wěn)態(tài)QPS約304核8G省級POI 多級瓦片緩存支撐正式對話流量穩(wěn)態(tài)QPS約120p95 100ms8核16G多點區(qū)域POI 大尺寸瓦片包可支撐多業(yè)務(wù)線并發(fā)主要瓶頸在帶寬瓦片包體量也需要提前算清楚只做單城市的常用縮放級別柵格瓦片大概1到3GB如果覆蓋到一個省且包含高縮放級別體量會漲到幾十GB。我們的經(jīng)驗是瓦片包體積直接決定了部署成本和更新頻率所以默認只在業(yè)務(wù)熱點區(qū)域生成高縮放級別瓦片低級別全局鋪底把總包控制在5GB以內(nèi)。6. 踩坑記錄文檔里查不到的五個細節(jié)6.1 瓦片索引的邊界取整錯誤第一個坑在瓦片坐標計算。x和y必須用向下取整這個大多數(shù)人都知道但y方向在北半球高緯度地區(qū)有個隱藏問題當緯度超過Web Mercator的85.05113度上限時y值變成負的數(shù)組下標越界瓦片渲染直接崩潰。我們在一次高緯度測試點的聯(lián)調(diào)里遇到了整個地圖區(qū)域灰屏的現(xiàn)象查了一下午發(fā)現(xiàn)是測試數(shù)據(jù)里混入了一個緯度85.5度的異常坐標點。修復(fù)方式就是在進入瓦片計算前對緯度做clamp。后來我把這行clamp寫成了公共函數(shù)的一個固定步驟所有調(diào)用方都從這里走一勞永逸。6.2 坐標偏移在邊緣區(qū)域的突變坐標轉(zhuǎn)換是另一個反復(fù)出問題的地方。我們一開始直接采用網(wǎng)上流傳的公開糾偏算法在大多數(shù)區(qū)域表現(xiàn)正常但在某些地區(qū)誤差突然放大到幾百米。地圖上一開始幾百米的偏移很難肉眼發(fā)現(xiàn)直到用戶反饋機器人說的位置永遠偏了一條街我們才意識到是轉(zhuǎn)換精度在這些區(qū)域失效了。解決方案是用本地控制點做校正收集一批在該區(qū)域已知真實坐標與展示坐標對應(yīng)的樣本點對偏差建一個區(qū)域修正表轉(zhuǎn)換時先查表再套用通用算法。這個方案比單純調(diào)參可靠得多也讓我徹底明白了一個道理坐標偏移問題是空間相關(guān)的任何一勞永逸的近似公式都要在目標區(qū)域做局部驗證。6.3 瓦片預(yù)取把帶寬打滿了瓦片預(yù)取功能上線的第一天我們就把自己給打掛了。預(yù)取程序用20個并發(fā)線程去熱門區(qū)域抓瓦片結(jié)果應(yīng)用服務(wù)的連接池和帶寬瞬間被打滿在線查詢?nèi)砍瑫r。修復(fù)方式是給預(yù)取任務(wù)加信號量限流把并發(fā)控制在2到3個線程并且對失敗請求做指數(shù)退避。實際上瓦片服務(wù)的穩(wěn)定性從來不由總帶寬決定而由瞬時并發(fā)尖峰決定。后來我們給所有內(nèi)部批處理任務(wù)都立了規(guī)矩批處理不得與線上查詢共享同一資源池。6.4 逆地理編碼的飛地與邊界重疊逆地理編碼返回錯誤行政區(qū)是線上反饋里最難排查的一類問題。現(xiàn)象是用戶在地圖上定位機器人報出的行政區(qū)劃和他實際所在的位置對不上。最終定位到兩類原因一是行政邊界存在飛地即某行政區(qū)的一塊區(qū)域完全被另一個行政區(qū)包圍二是多邊形邊界重疊一個點同時落在多個區(qū)劃內(nèi)。單靠多邊形包含算法沒法處理這類問題。我們的做法是對重疊區(qū)域建立網(wǎng)格歸屬表以固定間隔把有沖突的區(qū)域切成網(wǎng)格每個網(wǎng)格預(yù)先指定一個業(yè)務(wù)歸屬同時把這種歸屬結(jié)果緩存起來避免每次查詢都跑一遍多邊形判斷。這套機制上線后逆地理編碼的實際錯誤率降了一個數(shù)量級。6.5 日志里不能出現(xiàn)一根坐標最后這個坑不是技術(shù)問題而是意識問題。地圖模塊的日志里天然會記錄經(jīng)緯度、查詢關(guān)鍵詞、逆地理編碼結(jié)果這些信息與具體用戶關(guān)聯(lián)后就是敏感數(shù)據(jù)。早期排查問題時我們直接把查詢參數(shù)打到了日志里后來安全評審被一票否決。改造方式是在日志輸出層做統(tǒng)一脫敏坐標只保留到小數(shù)點后一位POI名稱做模糊化會話ID替換成不可逆散列。日志脫敏這件事不能靠每個開發(fā)者自覺必須做成框架層強制執(zhí)行的過濾器。我在實際維護lingbot-map的過程中最大的體會是地圖模塊是一個很容易把自己做成無底洞的東西。如果你一開始就想著覆蓋全國數(shù)據(jù)、做完整導(dǎo)航、接實時路況那這項目一年都交付不了。反過來先圈定一個城市或者一個園區(qū)把對話場景里的閉環(huán)跑通——能定位、能找店、能算距離——然后再往下一個區(qū)域擴展才是自托管地圖的正確打開方式。最后再分享一個小技巧附近POI檢索的排序永遠先做geohash網(wǎng)格粗篩再做Haversine精算千萬別讓全量候選集都走一遍球面距離計算否則接口延遲會隨著POI數(shù)量線性膨脹。這是我被壓測數(shù)據(jù)教育出來的經(jīng)驗照著做能省掉你后面大半的優(yōu)化時間。