馬蜂窩技術原創內容，更多干貨請關注公眾號：mfwtech
隨著智能手機存盤容量的增大，以及相冊備份技術的普及，我們可以隨時隨地用手機影像記錄生活，在手機中存盤幾千張甚至上萬張照片已經是很常見的事情，但另一方面，當我們想從這么多張照片中去找到一張，也是一件麻煩事，
馬蜂窩作為旅行玩樂平臺，希望實作「會玩的人」與「好玩的事」之間的連接，眾多旅行愛好者在這里記錄和分享他們的旅行記憶，使馬蜂窩在旅游 UGC 領域累積了大量內容，因此，不斷優化用戶在發布內容時的體驗是我們一直努力的主向，
用照片、視頻記錄旅行是最直接的方式，本文將介紹馬蜂窩如何通過 App 地理相冊空間索引的應用，為用戶提供直觀、好用的圖片分享服務，
Part.1 應用場景和需求
要想讓用戶快速地找到想要分享的照片/視頻，我們需要一個有效且合理的篩選手段，對用戶的相冊進行聚合、排序，提升用戶依托相冊去分享和記錄生活時易用性和便捷性，
首先要確定聚合排序的篩選維度，照片的地理位置就是最直觀的分類維度；同時，記錄最近發生的事情符合用戶的發布行為習慣，因此我們方案要滿足的需求是：
- 根據目的地和時間，對用戶相冊進行聚合、排序；
- 基于某個地理位置資訊和給定范圍，在用戶相冊中搜索給定范圍的照片/視頻，
本文提及的地理相冊服務在馬蜂窩 App 內主要有兩個落地場景，
1.1 筆記
「筆記」是以圖片、視頻為主要呈現形式的旅行短內容分享，用戶發布筆記的第一個環節就是從相冊中選擇需要發布的照片/視頻，在新版 App 中，基于地理相冊服務結合馬蜂窩自有目的地資料，對用戶相冊進行按照地點維度的聚合分類，并且按照片/視頻的創建時間由近及遠的排序，提升用戶選擇發布效率，
1.2 足跡
「足跡」這一產品的功能，旨在幫助馬蜂窩用戶以自動同步或手動點選去過的國家和地區這種更簡易的方式記錄旅行，在「我的足跡」中有一個場景，會鼓勵用戶對去過的但還沒有發布筆記的地點發布筆記，此時地理相冊服務可以幫助用戶發布相冊中以指定地點為圓心，給定半徑范圍內的所有照片，
Part.2 方案設計與演算法選型
2.1 初期方案
初期我們想到的方案比較直觀，也比較粗暴，就是對相冊進行遍歷后由服務端計算結果，具體來說，首先取出用戶所有攜帶地理資訊的照片/視頻，然后將地理資訊（經緯度）上傳服務端，由服務端進行聚合和篩選，回傳給客戶端結果，但是這個方案有很多缺點，
文章開始我們已經描述了目前用戶手機設備中的照片數量是成千上萬的，如果遍歷所有圖片，這上傳的資料體量是巨大的；同時，一般用戶照片的地理位置會有很多呈現出成簇聚集的狀態，因為一般我們會在一個地點范圍內拍攝許多照片，這就導致了大量的重復聚類的計算，
如果要優化這個方案，針對第一個需求我們可以采用快取+增量請求的方式，因為用戶分類資料是穩定的，但是針對給定范圍查詢的需求，我們無法做快取，這就需要每次都請求服務端做大量的計算，對于時間的消耗是不能容忍的，
可以看到，上述方案的挑戰主要在于用戶相冊中地理資訊的資料量和重復度、依賴服務端計算搜索結果導致的性能問題和用戶體驗，經過調研我們發現，基于地理空間點（經緯度）索引演算法可以很好地解決這些問題，
2.2 基于地理空間點索引演算法的實踐
結合我們的實際需求來理解地理空間點索引演算法，即找到合適的方法來對地理空間中海量的坐標點添加索引，從而對空間點進行快速查詢和排序的一種演算法，
我們對一些比較通用的地理空間點索引演算法進行了選型比較，下面主要介紹 GeoHash 演算法和 Google-S2 演算法，
2.2.1 演算法選型
（1）GeoHash
GeoHash 演算法即地理位置距離排序演算法，Geohash 是一種地理編碼，由 Gustavo Niemeyer 發明，它利用一種分級的資料結構，把空間劃分為網格，
GeoHash 屬于空間填充曲線中的 Z 階曲線的實際應用，GeoHash 有一個和 Z 階曲線相關的性質，那就是一個點附近的地方 Hash 字串總是有公共前綴，并且公共前綴的長度越長，這兩個點距離越近，由于這個特性，GeoHash 就常常被用來作為唯一識別符號，比如在資料庫里面可用 GeoHash 來唯一表示一個點，
GeoHash 這個公共前綴的特性就可以用來快速的進行鄰近點的搜索，越接近的點通常和目標點的 GeoHash 字串公共前綴越長，但是 Z 階曲線有一個比較嚴重的問題，就是它的突變性，在每個 Z 字母的拐角，都有可能出現順序的突變，導致搜索臨近點的精確度較差，不能滿足我們的業務場景對精確度的要求，
（2）S2 演算法
S2 其實是來自幾何數學中的一個數學符號 S²，它表示的是單位球，
S2 演算法采用正方體投影的方式將地球展開，然后利用希爾伯特分形曲線將展開后的二維地球進行填充，完成了對三位地球的降維和分形，從而得到空間坐標點與希爾伯特分形曲線的函式關系，即將球面經緯度坐標轉換成球面 xyz 坐標，再轉換成正方體投影面上的坐標，最后變換成修正后的坐標在坐標系變換，映射到 [0,2^30^-1] 區間，最后一步就是把坐標系上的點都映射到希爾伯特曲線上，最終，映射到希爾伯特曲線上的點成為 Cell ID，即是空間坐標點的索引，
S2 的最大的優勢在于精度高，Geohash 有 12 級，從 5000km 到 3.7cm，中間每一級的變化比較大，有時候可能選擇上一級會大很多，選擇下一級又會小一些，而 S2 有 30 級，從 0.7cm² 到 85,000,000km²，中間每一級的變化都比較平緩，接近于 4 次方的曲線，所以選擇精度時不會出現 Geohash 選擇困難的問題，
綜上，S2 演算法能夠滿足我們對于功能和精度上的要求，因此最終選擇 S2 演算法作為空間點索引演算法的實作方案，
Part.3 功能實作與性能優化
3.1 模塊設計
本文中的 App 地理相冊服務主要基于相冊索引資料操作、用戶相冊掃描、相冊索引服務和相冊地點分類計算四大模塊實作：
以下分別介紹，
3.1.1 相冊索引資料操作模塊
相冊位置資訊的索引采用資料庫作為存盤介質，將用戶照片資訊以及通過 S2 演算法計算出來的 Cell ID 存盤到資料庫當中，其中，考量存盤的數量和對搜索和聚合經度的要求，存盤了從 Level4~Level16 經度級別的 Cell ID，
相冊索引資料操作模塊，由資料庫（DB）和資料庫操作層（DAO）組成，資料表的設計見下圖:
資料庫操作層（DAO）封裝了資料插入、洗掉、查詢等基本操作的 API，
3.1.2 用戶相冊掃描模塊
用戶相冊掃描模塊基于 iOS 原生提供的相冊查詢的 API，將用戶相冊的資料與本地資料庫中存盤的照片資料進行對比，提取出新增照片資料和用戶已經洗掉的照片，
3.1.3 相冊索引服務模塊
相冊索引服務模塊，是基于 S2 演算法的相冊服務的核心模塊，模塊功能如下:
- 直接與資料模塊互動，向使用者屏蔽資料層的資料操作細節，提供滿足查詢、搜索等需求的 API
- 查詢指定 Cell ID 下的照片資源
- 查詢指定 Level 下，相冊照片索引后的 Cell ID
- 查詢以指定坐標點為圓心、指定半徑范圍內的照片
- 與用戶相冊掃描模塊互動，獲取新增照片和已經洗掉照片的資料，更新資料庫內容，同時支持查詢和通知更新狀態
3.1.4 相冊地點分類計算模塊
相冊地點分類計算模塊是計算用戶相冊的地點分類結果的核心模塊，該模塊的主體功能如下:
- 獲取 S2 相冊索引服務中的照片 Cell ID，作為引數上傳至服務端，服務端根據地圖服務提供的聚合介面，將 Cell ID 的聚合結果回傳給服務端
- 綜合考量精確度和 Cell ID 的資料量，選取 Level12 的 Cell ID 作為請求服務端的 Cell ID 等級
- 呼叫相冊索引服務模塊根據指定 Level 獲取 Cell ID 的方法得到去重后的 Cell ID
- 服務端回傳的資料結構是 mdd_id（目的地 ID） 與 Cell ID 的一對多的映射關系
- 利用本地 S2 相冊索引服務中的照片 Cell ID，根據上一步服務端回傳的分類資料進行分類
- 快取每次地點分類的計算結果
3.2 整體流程
相冊索引服務模塊會在 App 啟動時更新服務，將本地資料與相冊資料同步，當用戶觸發地點相冊功能時，相冊地點分類計算模塊會先取出快取在本地相冊地點分類計算結果展現給用戶，同時驅動相冊索引服務更新，
在收到更新服務更新完畢的通知后，首先向相冊請求 12Level 的全量去重的 Cell ID，然后將 Cell ID 上傳服務端由服務端計算分類，最后結合相冊索引服務的全量照片資料，計算照片的地點分類結果，快取結果并渲染展現給用戶，
3.3 性能優化
3.3.1 獲取相冊增量照片
相冊索引服務模塊需要同步服務和用戶相冊的照片資源資料，找到新增資料，加入到服務資料庫中，最初設計的獲取新增資料方案如下：
Step.1 獲取全量的用戶相冊的資料
Step.2 遍歷用戶照片，查詢是否存在本地服務資料庫中
但是這個方案應用到照片量較大的手機上時，獲取新增照片的時延很高，排查后我們發現原因在于全量遍歷用戶相冊時延很高，同時在遍歷中頻繁查詢資料庫也比較耗時，經過調研發現，iOS 的用戶相冊有「最近專案」的相冊分類，該相冊分類下的資源只按照添加順序的倒序排列，即越新的照片越靠前，故將方案優化如下：
Step.1：從串列頭部截取 100 條
Step.2：將該 100 條追加為新增照片
Step.3：判斷該 100 條中的最后一條，即新增時間最晚的一條，查詢是否存在于服務資料庫中
- 若不存在，繼續 Step.1
- 若存在，停止截取，從而得到新增照片
3.3.2 漸進計算相冊照片的地點分類
相冊地點分類計算模塊在獲得服務端回傳的分類結果（mdd_id 與 Cell ID 串列的映射關系）后，根據結果對本地服務資料庫中的照片進行分類，最初的方案如下:
Step.1：遍歷結果串列，獲得每個 mdd_id 映射的 Cell ID 串列
- A. 遍歷 Cell ID 串列，通過 Cell ID 向相冊索引服務模塊查詢屬于該 Cell ID 索引下的照片資源，從而獲得該 mdd_id 對應的照片資源
- B. 對該目的地下的照片按照創建時間倒序排序
Step.2：將所有目的地維度照片分類結果，按照每個結果集中照片最晚創建時間，即第一個照片的創建時間，進行倒序排序，獲得按照地點維度和創建時間維度排序的地點相冊的最終計算結果，
這樣的方案導致在地點相冊首次計算的時候，用戶需要等待所有目的地下的結果計算完畢后才能展現給用戶，同時需要多次按照創建時間排序，導致時延很高，冷啟動下用戶體驗很差，
為此，我們做出了方案優化，減少排序次數，同時通過漸進加載的方式優化用戶體驗，主要思路是相冊索引服務模塊的資料庫中，存盤照片的創建時間可以通過 SQL 查詢，按照創建時間倒序排列的所有照片資源，獲取倒序排列的照片資源集合：
Step.1：每次從照片資源集合頭部取 1000 條照片
- 遍歷每一張照片，根據照片的 Cell ID，從 mdd_id-Cell ID 映射表中查詢所屬的目的地, 判斷照片目的地分類結果集中是否存在該目的地的照片資源分類集合
- 存在，追加該照片
- 創建該目的地的結果集，追加到照片目的地分類結果集中，并追加該照片
Step.2：將該 1000 張照片的分類結果渲染展現給用戶
Step.3：計算完所有照片的分類，通知結束渲染，計算完畢，
以上方案，將全量的本地照片資源以 1000 張為一批次，進行漸進計算，同時漸進渲染，縮短了用戶的等待時間；同時，依托關系型資料庫的排序能力，減少排序次數，優化了性能，
Part.4 未來規劃和總結
目前，本文介紹的基于 Google-S2 演算法實作的地點相冊在馬蜂窩 APP iOS 客戶端已經上線一段時間，并且為筆記發布量帶來了正向增長，但是這套方案在資料庫資料處理中已經對于 Google-S2 演算法的使用上仍然有很大的優化和探索空間，后續我們團隊也會對其不斷優化和深挖，
Google-S2 演算法服務在馬蜂窩 App iOS 客戶端中的實作和落地，成果不僅僅是滿足了筆記發布場景的探索，更使得客戶端具備了對于用戶相冊照片百米級精確度的索引和搜索的能力，可以為后續更多、更復雜的業務場景服務，相信在不遠的未來能為用戶提供更便捷、更有趣的旅行記錄產品，
本文作者：王巖、王明友，馬蜂窩內容業務研發工程師，
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/5597.html
標籤：iOS