基于Google-S2的地理相册服务实现与应用做好个人和家庭防护，保持良好心态，过好生活，是每一个普通人抗击疫情的最佳武器。在这样的变化下，马蜂窝充分发挥内容和社区优势，让大家在疫情期间每天通过浏览平台内其他网友发布的视频和笔记，找到正能量；足不出户，即可进行“云旅行”，收藏并点赞想去的地方。为了不断优化用户在马蜂窝分享内容的体验，我们一直在努力。本文主要介绍马蜂窝内容业务研发团队在APP地理相册空间索引方面的探索和应用实践，希望能给有类似问题的同学带来一些思路。疫情终会过去，那些被取消的旅行计划，都会在风景更美的时候发生。随着智能手机存储容量的增加和相册备份技术的普及，我们可以随时随地用手机影像记录自己的生活，手机中存储几千甚至上万张照片已是家常便饭。但另一方面，当我们想要在这么多照片中找到一张时，也是一件比较麻烦的事情。作为一个旅游娱乐平台，马蜂窝希望实现“会玩的人”和“好玩的东西”的连接。许多旅行爱好者在这里记录和分享自己的旅行记忆，让马蜂窝在旅行UGC领域积累了大量内容。因此，不断优化发布内容时的用户体验是我们努力的主要方向。用照片和视频记录旅行是最直接的方式。本文将介绍马蜂窝如何通过APP地理相册空间索引的应用，为用户提供直观易用的图片分享服务。Part.1应用场景及需求为了让用户能够快速的找到自己想要分享的照片/视频，我们需要一种有效合理的筛选方法，对用户的相册进行聚合排序，提高用户依赖相册进行分享和分享的能力。记录他们的生活使用方便。首先确定聚合排序的过滤维度。照片的地理位置是最直观的分类维度；同时，记录近期事件也符合用户的发布习惯。因此，我们解决方案的需求是：根据目的地和时间对用户相册进行聚合和排序；根据一定的地理位置信息和给定的范围在用户相册中搜索给定范围的照片/视频。本文提到的地理相册服务在马蜂窝App中主要有两个落地场景。1.1笔记“笔记”是以图片和视频的形式分享的短途旅行内容。用户发布笔记的第一步是从相册中选择要发布的照片??/视频。在新版APP中，基于地理相册服务结合马蜂窝自身目的地数据，将用户的相册按照位置维度进行聚合分类，并按照片/视频的创建时间从近到远排序提高用户选择和发布的效率。1.2足迹“足迹”产品功能旨在通过自动同步或手动点击去过的国家和地区，帮助马蜂窝用户更便捷地记录旅行。“我的足迹”中有一个场景，鼓励用户对他们去过但还没有发表笔记的地方发表笔记。此时地理相册服务可以帮助用户发布以指定位置为中心的给定半径范围内的相册中的所有照片。Part.2方案设计与算法选择2.1初始方案我们想到的初始方案比较直观粗暴，即遍历相册后，服务器计算结果。具体来说，首先取出用户所有携带地理信息的照片/视频，然后将地理信息（经纬度）上传到服务器，服务器进行聚合过滤，返回结果给客户端。然而，这个解决方案有很多缺点。在文章的开头，我们已经描述了当前用户的移动设备中有几万张照片。如果遍历所有图片，上传的数据量巨大；同时，一般用户照片的地理位置会有很多结果。聚类状态，因为一般我们会在一个位置范围内拍摄很多张照片，导致大量的重复聚类计算。如果我们要优化这个方案，对于第一个需求，我们可以使用缓存+增量请求的方式，因为用户分类数据是稳定的。但是我们不能针对给定范围的查询需求做缓存，每次都需要请求服务器做大量的计算，时间消耗是无法忍受的。可以看出，上述方案的挑战主要在于用户相册中地理信息的数据量和重复性，依赖服务器计算搜索结果带来的性能问题和用户体验。经过考察，我们发现基于地理空间点（经纬度）的索引算法可以很好地解决这些问题。2.2地理空间点索引算法的实践根据我们的实际需要了解地理空间点索引算法，即找到合适的方法对地理空间中大量的坐标点添加索引，从而实现快速查询和排序空间点算法。我们选择并比较了一些常见的地理空间点索引算法。下面主要介绍GeoHash算法和Google-S2算法。2.2.1算法选择(1)GeoHashGeoHash算法是地理位置距离排序算法。Geohash是一种地理编码，由GustavoNiemeyer发明。它利用分层数据结构将空间划分为网格。GeoHash属于Z阶曲线在空间填充曲线中的实际应用。GeoHash有一个与Z序曲线相关的性质，即在一个点附近的Hash串总是有一个共同的前缀，并且共同前缀的长度越长，两点之间的距离就越近。由于这个特性，GeoHash经常被用作唯一标识符。例如，GeoHash可用于唯一表示数据库中的一个点。GeoHash的特性，一个公共前缀，可以用来快速搜索附近的点。较近的点通常与目标点的GeoHash字符串有较长的公共前缀。但是Z-order曲线有一个比较严重的问题，就是它的突兀性。在每个Z字母的转角处，可能会出现顺序突变，导致查找相邻点的准确率不高，无法满足我们业务场景的准确率要求。(2)S2算法S2实际上来源于几何数学中的一个数学符号S2，表示单位球体。S2算法利用立方体投影将地球展开，然后利用希尔伯特分形曲线对展开后的二维地球进行填充，完成三维地球的降维和分形，从而得到空间坐标点和希尔伯特曲线分形曲线的函数关系，即将球面经纬度坐标转换为球面xyz坐标，再转换为立方体投影面上的坐标，最后转换为坐标系中修正后的坐标，并映射到[0,2^30^-1]区间，最后一步是将坐标系上的点映射到希尔伯特曲线上。最后映射到希尔伯特曲线上的点就成为了CellID，也就是空间坐标点的索引。S2最大的优势就是精度高。Geohash有12个级别，从5000km到3.7cm，中间每一级别的变化都比较大。有时选择上层可能会大很多，选择下层可能会小一些。S2有30个等级，从0.7cm2到85,000,000km2，中间每个等级的变化比较平缓，接近4次方曲线。因此在选择精度时不会出现Geohash选择困难的问题。综上所述，S2算法能够满足我们对功能和精度的要求，因此最终选择S2算法作为空间点索引算法的实现。Part.3功能实现及性能优化3.1模块设计本文中的app地理相册服务主要基于四个模块实现：相册索引数据操作、用户相册扫描、相册索引服务、相册位置分类计算：下面分别介绍分别地。3.1.1相册索引数据操作模块相册位置信息索引以数据库为存储介质，将用户的照片信息和S2算法计算出的CellID存入数据库。其中，考虑到存储量和查找聚合经度的要求，存储Level4~Level16经度级别的CellID。相册索引数据操作模块由数据库（DB）和数据库操作层（DAO）组成。数据表的设计如下图所示：数据库操作层（DAO）封装了数据插入、删除、查询等基本操作的API。3.1.2用户相册扫描模块用户相册扫描模块根据iOS原生提供的相册查询API，将用户相册中的数据与本地数据库中存储的照片数据进行比对，提取出新的照片数据和用户删除的照片.3.1.3相册索引服务模块相册索引服务模块是基于S2算法的相册服务的核心模块。模块功能如下：直接与数据模块交互，屏蔽用户数据层的数据操作细节，提供满足查询、搜索等需求的API查询指定下的图片资源CellID查询指定Level下的相册照片索引后的CellID以指定坐标点为中心查询指定半径范围内的照片，与用户相册扫描模块交互，获取新照片和删除照片的数据，更新数据库内容，同时支持查询和通知更新状态。3.1.4相册位置分类计算模块相册位置分类计算模块是计算用户相册位置分类结果的核心模块。该模块主要功能如下：获取S2相册索引服务中的照片CellID，作为参数上传至服务器。服务器根据地图服务提供的聚合接口，将CellID的聚合结果返回给服务器。综合考虑准确性和CellID的数据量，选择Level12的CellID作为请求服务器的CellID级别。调用相册索引服务模块，根据指定的Level获取cellID，得到去重后的CellID。服务端返回的数据结构为mdd_id（目的地ID）和CellID一对多的映射关系使用本地S2相册索引服务中的照片CellID，根据分类缓存每个位置分类的计算结果上一步服务器返回的数据3.2整体流程相册索引服务模块会在App启动时更新服务，同步本地数据和相册数据。当用户触发位置相册功能时，相册位置分类计算模块会先取出缓存在本地相册中的位置分类计算结果展示给用户，同时驱动相册索引服务的更新。收到update服务更新通知后，先向相册请求12Level全去重CellID，然后将CellID上传到服务器，由服务器计算分类，最后合并相册全图数据索引服务来计算照片ID。定位分类结果，缓存结果并呈现给用户。3.3性能优化3.3.1获取增量相册相册索引服务模块需要同步服务和用户相册的照片资源数据，发现新的数据，添加到服务数据库中。原获取新数据的设计方案如下：Step.1获取用户相册全量数据。Step.2遍历用户照片，查看本地服务数据库中是否存在。但是，当这种方案应用到照片数量较多的手机上时，新添加照片的延迟很高。经过排查，原因是全遍历用户相册延迟高，遍历时频繁查询数据库也很耗时。经过排查，发现iOS用户相册有一个相册分类为“最近的项目”，该相册分类下的资源只是按照添加的倒序排列，即越新的照片越靠前。因此，方案优化如下：Step.1：从列表头部切出100个entryStep.2：将这100个entry添加为新照片Step.3：确定这100个entry中的最后一个entry，即最新添加时间一、查询服务数据库中是否存在，如果不存在，继续Step.1如果存在，则停止拦截，从而得到新的照片3.3.2逐步计算相册照片的位置分类结果后（mdd_id与CellID列表的映射关系），根据结果对本地服务数据库中的照片进行分类。初步计划如下：Step.1：遍历结果列表，得到每个mdd_id映射的CellID列表A.遍历CellID列表，通过CellID查询相册索引服务模块，获取CellID下的照片资源index,并得到mdd_id对应的照片资源B.将destination下的照片按创建时间倒序排序Step.2:对所有destination维度照片的结果进行分类，根据每条结果中照片的最新创建时间设置，即第一张照片的创建时间，逆序排序得到位置相册按地点维度和创建时间维度排序的最终计算结果。这样的方案导致用户在第一次计算位置相册时，需要等待所有目的地的计算结果显示给用户。同时需要多次按创建时间排序，导致延迟高，冷启动下用户体验差。.为此，我们对方案进行了优化，减少排序次数，同时通过渐进式加载优化用户体验。主要思路是在相册索引服务模块的数据库中，可以通过SQL查询存储照片的创建时间，获取所有按照创建时间倒序排列的照片资源，从而得到照片集资源倒序：Step.1：每次从照片资源集合的头部取全部1000张照片，遍历每张照片，根据照片的CellID从mdd_id-CellID映射表中查询目的地，并判断照片目的地分类结果集中是否有目的地的照片资源分类集，添加照片创建目的地的结果集，添加到照片目的地分类结果集中，添加照片Step.2：渲染显示1000张照片的分类结果给用户Step.3：计算所有照片的分类，通知渲染结束，计算完成。上述方案以1000张为批次全量使用本地图片资源进行渐进式计算和渐进式渲染，缩短了用户的等待时间；同时依托关系数据库的排序能力，减少排序次数，优化性能。Part.4未来规划与总结目前，本文介绍的基于Google-S2算法的位置相册已在马蜂窝APPiOS客户端上线一段时间，并为笔记发布数量带来了正增长.但该方案在数据库数据处理中使用Google-S2算法方面还有很大的优化和探索空间，后续我们团队会继续优化和深挖。Google-S2算法服务在马蜂窝AppiOS客户端的实现与落地，不仅满足了笔记发布场景的探索，还让客户端具备百米精度索引搜索用户相册照片的能力，可以未来服务于更多更复杂的业务场景，相信在不久的将来会为用户提供更方便、更有趣的旅行记录产品。
