馬蜂窩技術原創內容，更多乾貨請關註公眾號：mfwtech

隨著智能手機存儲容量的增大，以及相冊備份技術的普及，我們可以隨時隨地用手機影像記錄生活，在手機中存儲幾千張甚至上萬張照片已經是很常見的事情。但另一方面，當我們想從這麼多張照片中去找到一張，也是一件麻煩事。

馬蜂窩作為旅行玩樂平臺，希望實現「會玩的人」與「好玩的事」之間的連接。眾多旅行愛好者在這裡記錄和分享他們的旅行記憶，使馬蜂窩在旅游 UGC 領域累積了大量內容。因此，不斷優化用戶在發佈內容時的體驗是我們一直努力的主向。

用照片、視頻記錄旅行是最直接的方式。本文將介紹馬蜂窩如何通過 App 地理相冊空間索引的應用，為用戶提供直觀、好用的圖片分享服務。

Part.1 應用場景和需求

要想讓用戶快速地找到想要分享的照片/視頻，我們需要一個有效且合理的篩選手段，對用戶的相冊進行聚合、排序，提升用戶依托相冊去分享和記錄生活時易用性和便捷性。

首先要確定聚合排序的篩選維度。照片的地理位置就是最直觀的分類維度；同時，記錄最近發生的事情符合用戶的發佈行為習慣。因此我們方案要滿足的需求是：

1. 根據目的地和時間，對用戶相冊進行聚合、排序；
2. 基於某個地理位置信息和給定範圍，在用戶相冊中搜索給定範圍的照片/視頻。

本文提及的地理相冊服務在馬蜂窩 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 客戶端中的實現和落地，成果不僅僅是滿足了筆記發佈場景的探索，更使得客戶端具備了對於用戶相冊照片百米級精確度的索引和搜索的能力，可以為後續更多、更複雜的業務場景服務，相信在不遠的未來能為用戶提供更便捷、更有趣的旅行記錄產品。

本文作者：王岩、王明友，馬蜂窩內容業務研發工程師。