寫在前面

對(duì)抗疫情的戰(zhàn)斗還在繼續(xù)。做好個(gè)人和家庭的防護(hù)，保持良好的心態(tài)，過好自己的生活，就是每個(gè)普通人抗擊疫情最好的武器。

在這樣的變化下，馬蜂窩充分發(fā)揮內(nèi)容與社區(qū)優(yōu)勢，讓大家在疫情期間每天在平臺(tái)上通過瀏覽其他網(wǎng)友發(fā)布的視頻和筆記找到正能量;宅在家的同時(shí)可以進(jìn)行“云旅行”，收藏和點(diǎn)贊自己想去的地方。

為了不斷優(yōu)化用戶在馬蜂窩分享內(nèi)容的體驗(yàn)，我們一直在努力。本文主要介紹馬蜂窩內(nèi)容業(yè)務(wù)研發(fā)團(tuán)隊(duì)在 App 地理相冊空間索引方面的探索和應(yīng)用實(shí)踐，希望為有類似問題的同學(xué)帶來一些思路。

疫情終將過去，那些被取消的旅行計(jì)劃，會(huì)在風(fēng)景更美的時(shí)候成行。

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

馬蜂窩作為旅行玩樂平臺(tái)，希望實(shí)現(xiàn)「會(huì)玩的人」與「好玩的事」之間的連接。眾多旅行愛好者在這里記錄和分享他們的旅行記憶，使馬蜂窩在旅游 UGC 領(lǐng)域累積了大量內(nèi)容。因此，不斷優(yōu)化用戶在發(fā)布內(nèi)容時(shí)的體驗(yàn)是我們一直努力的主向。

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

Part.1應(yīng)用場景和需求

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

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

1. 根據(jù)目的地和時(shí)間，對(duì)用戶相冊進(jìn)行聚合、排序;
2. 基于某個(gè)地理位置信息和給定范圍，在用戶相冊中搜索給定范圍的照片/視頻。

本文提及的地理相冊服務(wù)在馬蜂窩 App 內(nèi)主要有兩個(gè)落地場景。

1.1 筆記

「筆記」是以圖片、視頻為主要呈現(xiàn)形式的旅行短內(nèi)容分享。用戶發(fā)布筆記的第一個(gè)環(huán)節(jié)就是從相冊中選擇需要發(fā)布的照片/視頻，在新版 App 中，基于地理相冊服務(wù)結(jié)合馬蜂窩自有目的地?cái)?shù)據(jù)，對(duì)用戶相冊進(jìn)行按照地點(diǎn)維度的聚合分類，并且按照片/視頻的創(chuàng)建時(shí)間由近及遠(yuǎn)的排序，提升用戶選擇發(fā)布效率。

1.2 足跡

「足跡」這一產(chǎn)品的功能，旨在幫助馬蜂窩用戶以自動(dòng)同步或手動(dòng)點(diǎn)選去過的國家和地區(qū)這種更簡易的方式記錄旅行。在「我的足跡」中有一個(gè)場景，會(huì)鼓勵(lì)用戶對(duì)去過的但還沒有發(fā)布筆記的地點(diǎn)發(fā)布筆記。此時(shí)地理相冊服務(wù)可以幫助用戶發(fā)布相冊中以指定地點(diǎn)為圓心，給定半徑范圍內(nèi)的所有照片。

Part.2方案設(shè)計(jì)與算法選型

2.1 初期方案

初期我們想到的方案比較直觀，也比較粗暴，就是對(duì)相冊進(jìn)行遍歷后由服務(wù)端計(jì)算結(jié)果。具體來說，首先取出用戶所有攜帶地理信息的照片/視頻，然后將地理信息(經(jīng)緯度)上傳服務(wù)端，由服務(wù)端進(jìn)行聚合和篩選，返回給客戶端結(jié)果，但是這個(gè)方案有很多缺點(diǎn)。

文章開始我們已經(jīng)描述了目前用戶手機(jī)設(shè)備中的照片數(shù)量是成千上萬的，如果遍歷所有圖片，這上傳的數(shù)據(jù)體量是巨大的;同時(shí)，一般用戶照片的地理位置會(huì)有很多呈現(xiàn)出成簇聚集的狀態(tài)，因?yàn)橐话阄覀儠?huì)在一個(gè)地點(diǎn)范圍內(nèi)拍攝許多照片，這就導(dǎo)致了大量的重復(fù)聚類的計(jì)算。

如果要優(yōu)化這個(gè)方案，針對(duì)第一個(gè)需求我們可以采用緩存+增量請(qǐng)求的方式，因?yàn)橛脩舴诸悢?shù)據(jù)是穩(wěn)定的。但是針對(duì)給定范圍查詢的需求，我們無法做緩存，這就需要每次都請(qǐng)求服務(wù)端做大量的計(jì)算，對(duì)于時(shí)間的消耗是不能容忍的。

可以看到，上述方案的挑戰(zhàn)主要在于用戶相冊中地理信息的數(shù)據(jù)量和重復(fù)度、依賴服務(wù)端計(jì)算搜索結(jié)果導(dǎo)致的性能問題和用戶體驗(yàn)。經(jīng)過調(diào)研我們發(fā)現(xiàn)，基于地理空間點(diǎn)(經(jīng)緯度)索引算法可以很好地解決這些問題。

2.2 基于地理空間點(diǎn)索引算法的實(shí)踐

結(jié)合我們的實(shí)際需求來理解地理空間點(diǎn)索引算法，即找到合適的方法來對(duì)地理空間中海量的坐標(biāo)點(diǎn)添加索引，從而對(duì)空間點(diǎn)進(jìn)行快速查詢和排序的一種算法。

我們對(duì)一些比較通用的地理空間點(diǎn)索引算法進(jìn)行了選型比較，下面主要介紹 GeoHash 算法和 Google-S2 算法。

2.2.1 算法選型

(1)GeoHash

GeoHash 算法即地理位置距離排序算法。Geohash 是一種地理編碼，由 Gustavo Niemeyer 發(fā)明。它利用一種分級(jí)的數(shù)據(jù)結(jié)構(gòu)，把空間劃分為網(wǎng)格。

GeoHash 屬于空間填充曲線中的 Z 階曲線的實(shí)際應(yīng)用。GeoHash 有一個(gè)和 Z 階曲線相關(guān)的性質(zhì)，那就是一個(gè)點(diǎn)附近的地方 Hash 字符串總是有公共前綴，并且公共前綴的長度越長，這兩個(gè)點(diǎn)距離越近。由于這個(gè)特性，GeoHash 就常常被用來作為唯一標(biāo)識(shí)符，比如在數(shù)據(jù)庫里面可用 GeoHash 來唯一表示一個(gè)點(diǎn)。

GeoHash 這個(gè)公共前綴的特性就可以用來快速的進(jìn)行鄰近點(diǎn)的搜索。越接近的點(diǎn)通常和目標(biāo)點(diǎn)的 GeoHash 字符串公共前綴越長。但是 Z 階曲線有一個(gè)比較嚴(yán)重的問題，就是它的突變性。在每個(gè) Z 字母的拐角，都有可能出現(xiàn)順序的突變，導(dǎo)致搜索臨近點(diǎn)的精確度較差，不能滿足我們的業(yè)務(wù)場景對(duì)精確度的要求。

(2)S2 算法

S2 其實(shí)是來自幾何數(shù)學(xué)中的一個(gè)數(shù)學(xué)符號(hào) S²，它表示的是單位球。

S2 算法采用正方體投影的方式將地球展開，然后利用希爾伯特分形曲線將展開后的二維地球進(jìn)行填充，完成了對(duì)三位地球的降維和分形，從而得到空間坐標(biāo)點(diǎn)與希爾伯特分形曲線的函數(shù)關(guān)系，即將球面經(jīng)緯度坐標(biāo)轉(zhuǎn)換成球面 xyz 坐標(biāo)，再轉(zhuǎn)換成正方體投影面上的坐標(biāo)，最后變換成修正后的坐標(biāo)在坐標(biāo)系變換，映射到 [0,2^30^-1] 區(qū)間，最后一步就是把坐標(biāo)系上的點(diǎn)都映射到希爾伯特曲線上。最終，映射到希爾伯特曲線上的點(diǎn)成為 Cell ID，即是空間坐標(biāo)點(diǎn)的索引。

S2 的最大的優(yōu)勢在于精度高。Geohash 有 12 級(jí)，從 5000km 到 3.7cm，中間每一級(jí)的變化比較大。有時(shí)候可能選擇上一級(jí)會(huì)大很多，選擇下一級(jí)又會(huì)小一些。而 S2 有 30 級(jí)，從 0.7cm² 到 85,000,000km²，中間每一級(jí)的變化都比較平緩，接近于 4 次方的曲線。所以選擇精度時(shí)不會(huì)出現(xiàn) Geohash 選擇困難的問題。

綜上，S2 算法能夠滿足我們對(duì)于功能和精度上的要求，因此最終選擇 S2 算法作為空間點(diǎn)索引算法的實(shí)現(xiàn)方案。

Part.3功能實(shí)現(xiàn)與性能優(yōu)化

3.1 模塊設(shè)計(jì)

本文中的 App 地理相冊服務(wù)主要基于相冊索引數(shù)據(jù)操作、用戶相冊掃描、相冊索引服務(wù)和相冊地點(diǎn)分類計(jì)算四大模塊實(shí)現(xiàn)：

以下分別介紹。

3.1.1 相冊索引數(shù)據(jù)操作模塊

相冊位置信息的索引采用數(shù)據(jù)庫作為存儲(chǔ)介質(zhì)，將用戶照片信息以及通過 S2 算法計(jì)算出來的 Cell ID 存儲(chǔ)到數(shù)據(jù)庫當(dāng)中。其中，考量存儲(chǔ)的數(shù)量和對(duì)搜索和聚合經(jīng)度的要求，存儲(chǔ)了從 Level4~Level16 經(jīng)度級(jí)別的 Cell ID。

相冊索引數(shù)據(jù)操作模塊，由數(shù)據(jù)庫(DB)和數(shù)據(jù)庫操作層(DAO)組成。數(shù)據(jù)表的設(shè)計(jì)見下圖:

數(shù)據(jù)庫操作層(DAO)封裝了數(shù)據(jù)插入、刪除、查詢等基本操作的 API。

3.1.2 用戶相冊掃描模塊

用戶相冊掃描模塊基于 iOS 原生提供的相冊查詢的 API，將用戶相冊的數(shù)據(jù)與本地?cái)?shù)據(jù)庫中存儲(chǔ)的照片數(shù)據(jù)進(jìn)行對(duì)比，提取出新增照片數(shù)據(jù)和用戶已經(jīng)刪除的照片。

3.1.3 相冊索引服務(wù)模塊

相冊索引服務(wù)模塊，是基于 S2 算法的相冊服務(wù)的核心模塊。模塊功能如下:

• 直接與數(shù)據(jù)模塊交互，向使用者屏蔽數(shù)據(jù)層的數(shù)據(jù)操作細(xì)節(jié)，提供滿足查詢、搜索等需求的 API
• 查詢指定 Cell ID 下的照片資源
• 查詢指定 Level 下，相冊照片索引后的 Cell ID
• 查詢以指定坐標(biāo)點(diǎn)為圓心、指定半徑范圍內(nèi)的照片
• 與用戶相冊掃描模塊交互，獲取新增照片和已經(jīng)刪除照片的數(shù)據(jù)，更新數(shù)據(jù)庫內(nèi)容，同時(shí)支持查詢和通知更新狀態(tài)

3.1.4 相冊地點(diǎn)分類計(jì)算模塊

相冊地點(diǎn)分類計(jì)算模塊是計(jì)算用戶相冊的地點(diǎn)分類結(jié)果的核心模塊。該模塊的主體功能如下:

• 獲取 S2 相冊索引服務(wù)中的照片 Cell ID，作為參數(shù)上傳至服務(wù)端，服務(wù)端根據(jù)地圖服務(wù)提供的聚合接口，將 Cell ID 的聚合結(jié)果返回給服務(wù)端
• 綜合考量精確度和 Cell ID 的數(shù)據(jù)量，選取 Level12 的 Cell ID 作為請(qǐng)求服務(wù)端的 Cell ID 等級(jí)
• 調(diào)用相冊索引服務(wù)模塊根據(jù)指定 Level 獲取 Cell ID 的方法得到去重后的 Cell ID
• 服務(wù)端返回的數(shù)據(jù)結(jié)構(gòu)是 mdd_id(目的地 ID) 與 Cell ID 的一對(duì)多的映射關(guān)系
• 利用本地 S2 相冊索引服務(wù)中的照片 Cell ID，根據(jù)上一步服務(wù)端返回的分類數(shù)據(jù)進(jìn)行分類
• 緩存每次地點(diǎn)分類的計(jì)算結(jié)果

3.2 整體流程

相冊索引服務(wù)模塊會(huì)在 App 啟動(dòng)時(shí)更新服務(wù)，將本地?cái)?shù)據(jù)與相冊數(shù)據(jù)同步。當(dāng)用戶觸發(fā)地點(diǎn)相冊功能時(shí)，相冊地點(diǎn)分類計(jì)算模塊會(huì)先取出緩存在本地相冊地點(diǎn)分類計(jì)算結(jié)果展現(xiàn)給用戶，同時(shí)驅(qū)動(dòng)相冊索引服務(wù)更新。

在收到更新服務(wù)更新完畢的通知后，首先向相冊請(qǐng)求 12Level 的全量去重的 Cell ID，然后將 Cell ID 上傳服務(wù)端由服務(wù)端計(jì)算分類，最后結(jié)合相冊索引服務(wù)的全量照片數(shù)據(jù)，計(jì)算照片的地點(diǎn)分類結(jié)果，緩存結(jié)果并渲染展現(xiàn)給用戶。

3.3 性能優(yōu)化

3.3.1 獲取相冊增量照片

相冊索引服務(wù)模塊需要同步服務(wù)和用戶相冊的照片資源數(shù)據(jù)，找到新增數(shù)據(jù)，加入到服務(wù)數(shù)據(jù)庫中。最初設(shè)計(jì)的獲取新增數(shù)據(jù)方案如下：

Step.1 獲取全量的用戶相冊的數(shù)據(jù)

Step.2 遍歷用戶照片，查詢是否存在本地服務(wù)數(shù)據(jù)庫中

但是這個(gè)方案應(yīng)用到照片量較大的手機(jī)上時(shí)，獲取新增照片的時(shí)延很高。排查后我們發(fā)現(xiàn)原因在于全量遍歷用戶相冊時(shí)延很高，同時(shí)在遍歷中頻繁查詢數(shù)據(jù)庫也比較耗時(shí)。經(jīng)過調(diào)研發(fā)現(xiàn)，iOS 的用戶相冊有「最近項(xiàng)目」的相冊分類，該相冊分類下的資源只按照添加順序的倒序排列，即越新的照片越靠前。故將方案優(yōu)化如下：

Step.1：從列表頭部截取 100 條

Step.2：將該 100 條追加為新增照片

Step.3：判斷該 100 條中的最后一條，即新增時(shí)間最晚的一條，查詢是否存在于服務(wù)數(shù)據(jù)庫中

• 若不存在，繼續(xù) Step.1
• 若存在，停止截取，從而得到新增照片

3.3.2 漸進(jìn)計(jì)算相冊照片的地點(diǎn)分類

相冊地點(diǎn)分類計(jì)算模塊在獲得服務(wù)端返回的分類結(jié)果(mdd_id 與 Cell ID 列表的映射關(guān)系)后，根據(jù)結(jié)果對(duì)本地服務(wù)數(shù)據(jù)庫中的照片進(jìn)行分類。最初的方案如下:

Step.1：遍歷結(jié)果列表，獲得每個(gè) mdd_id 映射的 Cell ID 列表

• A. 遍歷 Cell ID 列表，通過 Cell ID 向相冊索引服務(wù)模塊查詢屬于該 Cell ID 索引下的照片資源，從而獲得該 mdd_id 對(duì)應(yīng)的照片資源
• B. 對(duì)該目的地下的照片按照創(chuàng)建時(shí)間倒序排序

Step.2：將所有目的地維度照片分類結(jié)果，按照每個(gè)結(jié)果集中照片最晚創(chuàng)建時(shí)間，即第一個(gè)照片的創(chuàng)建時(shí)間，進(jìn)行倒序排序，獲得按照地點(diǎn)維度和創(chuàng)建時(shí)間維度排序的地點(diǎn)相冊的最終計(jì)算結(jié)果。

這樣的方案導(dǎo)致在地點(diǎn)相冊首次計(jì)算的時(shí)候，用戶需要等待所有目的地下的結(jié)果計(jì)算完畢后才能展現(xiàn)給用戶，同時(shí)需要多次按照創(chuàng)建時(shí)間排序，導(dǎo)致時(shí)延很高，冷啟動(dòng)下用戶體驗(yàn)很差。

為此，我們做出了方案優(yōu)化，減少排序次數(shù)，同時(shí)通過漸進(jìn)加載的方式優(yōu)化用戶體驗(yàn)。主要思路是相冊索引服務(wù)模塊的數(shù)據(jù)庫中，存儲(chǔ)照片的創(chuàng)建時(shí)間可以通過 SQL 查詢，按照創(chuàng)建時(shí)間倒序排列的所有照片資源，獲取倒序排列的照片資源集合：

Step.1：每次從照片資源集合頭部取 1000 條照片

• 遍歷每一張照片，根據(jù)照片的 Cell ID，從 mdd_id-Cell ID 映射表中查詢所屬的目的地, 判斷照片目的地分類結(jié)果集中是否存在該目的地的照片資源分類集合
• 存在，追加該照片
• 創(chuàng)建該目的地的結(jié)果集，追加到照片目的地分類結(jié)果集中，并追加該照片

Step.2：將該 1000 張照片的分類結(jié)果渲染展現(xiàn)給用戶

Step.3：計(jì)算完所有照片的分類，通知結(jié)束渲染，計(jì)算完畢。

以上方案，將全量的本地照片資源以 1000 張為一批次，進(jìn)行漸進(jìn)計(jì)算，同時(shí)漸進(jìn)渲染，縮短了用戶的等待時(shí)間;同時(shí)，依托關(guān)系型數(shù)據(jù)庫的排序能力，減少排序次數(shù)，優(yōu)化了性能。

Part.4未來規(guī)劃和總結(jié)

目前，本文介紹的基于 Google-S2 算法實(shí)現(xiàn)的地點(diǎn)相冊在馬蜂窩 APP iOS 客戶端已經(jīng)上線一段時(shí)間，并且為筆記發(fā)布量帶來了正向增長。但是這套方案在數(shù)據(jù)庫數(shù)據(jù)處理中已經(jīng)對(duì)于 Google-S2 算法的使用上仍然有很大的優(yōu)化和探索空間，后續(xù)我們團(tuán)隊(duì)也會(huì)對(duì)其不斷優(yōu)化和深挖。

Google-S2 算法服務(wù)在馬蜂窩 App iOS 客戶端中的實(shí)現(xiàn)和落地，成果不僅僅是滿足了筆記發(fā)布場景的探索，更使得客戶端具備了對(duì)于用戶相冊照片百米級(jí)精確度的索引和搜索的能力，可以為后續(xù)更多、更復(fù)雜的業(yè)務(wù)場景服務(wù)，相信在不遠(yuǎn)的未來能為用戶提供更便捷、更有趣的旅行記錄產(chǎn)品。