上个月底，2GIS开始显示门廊。 自2013年以来，我们一直在向组织展示入口，入口似乎是相同的入口。 那么，为什么现在呢？ 所有内部产品和流程均已准备就绪，您所要做的就是再添加一点并更正UI中的显示。
除了标准答案“还有其他优先事项”外，还有一个不太标准的答案：“这不是那么简单。” 本文介绍了什么是困难以及我们如何解决这些困难。
首先，入口不是入口。 因此，一个入口通常可以从建筑物的不同侧面引出多个入口。 “具有公共入口的（多层）公寓楼”的定义也不正确。 碰巧一个入口通向入口的第一层，而另一个入口通向第二层及随后的楼层。
其次，我想寻找入口。
这是一个非常抢手的机会，因为入口的位置并不总是很明显。
除了入口编号之外，还有名称（通常是单个字母）。
甚至就像
在加里宁格勒（Kaliningrad）一样 -一个单独的地址正好分配给楼梯。
第三，我们决定如果要搜索入口，那为什么不立即支持按公寓号搜索呢？ 他们决定-并收集了公寓的范围，但是到目前为止，还没有地板约束。 与入口一样，公寓不仅可以有数字名称（大多数情况下会有字母“ a”的变体），而且范围也不总是连续的。 在圣彼得堡的老房子里，编号有点奇怪：公寓1和3可以在同一入口，公寓2可以在建筑物的对面。
关于数据验证的抒情离题不要试图使收集到的数据变得非常聪明-在北部首都，有时您可以从多个入口进入一间公寓，在某些欧洲居住区中，地址除房屋外还包含入口名称和该入口的公寓号。 彼得还对带有两个第八个入口的建筑物感到满意。
第四，我想始终在地图上显示入口，而不仅仅是在研究特定房屋或入口的信息时。
最后，入口很多-根据目前的估计，仅在莫斯科就有大约十万个入口。 “手指上的”第一次评估确实给出了一些天文数字-我们每六个较大的方面犯了一次错误。
结论：- 我们需要一个具有自己名称的附加实体，其中包含一系列公寓范围，并且建筑物的入口可以附加到该列表中。
- 我们将搜索该实体，并为其显示单独的信息卡。
- 我们被迫要么再次增加移动应用程序下载的数据的大小，要么仅在存在网络连接时才显示此数据，或者提出某种格式的文件。
解决方案
前两点要求内部和外部产品都进行更改，但这是常规操作。 后者是完全不同的事情。 由于我们不喜欢让用户不满意，因此设置了一个限制：数据应可脱机使用，并且添加数据不应增加数据库的大小。
怎么了 一方面，您需要减小数据的当前大小，另一方面，您可以提出一种用于存储有关入口信息的格式，以使附加数据量最少。
减少数据量
有两种减少它的方法：
- 仔细查看存储的数据，并尝试找到我们所不能做的事情。
- 考虑是否可以以某种方式比我们现在更有效地存储数据。
门廊时代之前数据存储格式的演变第一个也是最简单的选择
保存复杂数据的传统方法是对其进行
规范化 ，将其放置在表数据库中并创建辅助
索引 。 曾经，2GIS只是这样做，除了减小大小外，还对每个表的内容进行了排序，以便单元格值尽可能与上一行的值一致。 我们独立存储列，并折叠相同值的序列。
优化建筑物的桌子存储的高度简化的示例：
规范化可以减少冗余，但是也有不利的一面-为了为某个对象形成UI元素，您必须进行多次查询以访问大量表。 但是，那时，这些表不仅用于获取显示数据，而且还用于几乎所有任务，包括文本搜索和各种旅行搜索。 对于所有这些任务，规范化数据仅使我们能够减少处理的信息量。
用于渲染地图的数据已经具有其自己的二进制格式，并存储在单独的块中。 逐渐地，我们制作了单独的二进制格式以加快方向和文本搜索的速度。 数据库中只保留了信息，该信息用于显示对象卡以及某些对象与其他对象的链接。
简化工作
您如何简化数据处理？ 通过对象的标识符立即接收所有用于抽卡的必要数据。 由于
在线版本已经针对一个请求以
JSON格式从
API接收了所有数据，因此您可以同时合并我们所有产品使用的格式。
用于显示卡的json和通讯都需要从有限的对象中接收，每次接收的能力只有几十个。 但是，在某些情况下，需要一次获取多达数十万个大样本的单个属性。 将此类属性分为具有单独存储格式（属性）的单独实体更为合乎逻辑。 属性可以是类型的，并且可以二进制格式更有效地存储。
一种简单的存储json的方法是使用键值数据库。 以莫斯科为例，这是我们最大的项目。 即使以最简单的形式-每个对象都存储json本身，8个字节的标识符和一个分隔符-该目录也将占用1.9 GiB。 生成的大小几乎是先前描述的选项的六倍，并且仍然没有联系和属性。
我们通过向对象填充有关显示其卡片所需的一切信息来故意使它们膨胀，但是您仍然需要存储字段名称，引号，逗号和括号。
压缩资料
标准化不是消除冗余的唯一方法。 第二种流行的方式是压缩。 我们难以置信的厚文件的lzma存档仅需55 MiB。
当然，我们不能直接使用这种格式，因为要访问任意对象，我们需要解压缩先前存储的所有数据，而lzma归档文件的解压缩速度不是很快。
一方面我们如何才能获得快速的随机访问，另一方面，如何通过压缩数据来减少所需空间的大小？ 答案是使用分页。
现在已经对数据进行了分页，我们可以分别压缩每个数据。 要访问任意位置，我们需要解压缩并扫描页面，但这比解压缩和扫描整个档案要快得多。
以这种格式存储所有数据-json'y，关系和属性。 仍然需要将此数据与对象的标识符相关联。 对于每个标识符，我们需要存储一对或多对
<存储号，存储中的数据号> 。
所有序列号，偏移量和大小均以类似于
UTF-8的压缩格式存储，其中较小的值仅占用一个字节。 这使我们可以通过简单地对二进制存储库的内容进行排序以减少出现的次数来减少链接的大小。
某些属性具有许多频率值，因此排序会带来很大的收益。 另一方面，由于这个原因，并非所有存储的数据序列号都一致。
同样，距离所有对象都不远的所有存储中都有数据，因此存储编号比引用空对象更有效。
加快数据检索
所描述的格式有一个问题。 为了找到存储指定标识符索引的对象的编号，我们需要在第一个对象的数据内进行二进制搜索。 为此，您需要将10.9 MiB加载到内存中，或再进行21次读数。 这两种解决方案都不适合我们，因此我们通过将数据存储在树中来减少读数的数量。
我们将数据分组到32个对象上，并且在中间级别中，我们存储128个嵌套节点的第一个标识符。 我们添加了三个树级别，并将其他读数的数量减少到四个（但实际上，考虑到先前读取的树节点的缓存，甚至是1-3）。 价格-不到400 KiB。
在此阶段，我们在存储关系和属性方面非常有效，但是json占用了大量空间。 这是可以理解的。 页面大小越大，到达的对象越多，并且压缩算法能够更好地确定哪些信息是冗余的。 但是，另一方面，读取单个对象需要做更多的工作。 Json的对象很大，因此一页中的对象很少。 因此，您需要帮助算法更好地完成其工作。
将json分成几部分
首先，许多对象具有匹配的数据方案；只有属性值不同。 其次，即使对于具有不同方案的对象，许多属性值也相同。 我们将方案和属性值分离到单独的存储中，并以以下形式存储json：方案的链接+属性值的链接。
在我们的数据模式中，属性名称的数量是有限的。 因此，我们可以将它们放在单独的文件中，然后存储数字。 考虑到json始终是对象，我们还将进行一些其他更改。
是的，我们实质上是自己压缩数据，从而缩小了算法的适用范围。 但另一方面，我们大大降低了对数据的访问速度，并且该算法仍然可以帮助您压缩附近存储的相似值。
我们将页面大小设置为1 KiB，结果是，尽管我们优化了格式，以便一方面读取速度不是很慢，另一方面，数据也尽可能地打包，我们...在大小和大小上都已经绕过了“优化表”为了易于使用。 但是这不是全部！ 最大增益应来自属性，属性和方案的值的压缩。 我们引用zlib并验证，在其余工作的背景下，从数据库读取数据花费的时间很少。 对结果满意后，我们切换到其他任务。
摆脱不必要的
我们开始通过搜索可以消除的数据来减少数据。 事实证明，在格式存在期间，我们已经学会了在没有最大联系的情况下进行操作。 这是尺寸的10％！
该数据的代码仍被束缚，但必要的更改却微不足道。 但是已经发布的应用程序不能轻易更改。 我们力求保持尽可能长的时间，不仅要向后兼容，而且还要保持直接兼容。 如果每个人都熟悉第一个，那么许多人可能会很乐意不考虑第二个。 我们之所以不得不支持它，是因为由于种种原因，用户关闭了自动更新，并且不急于切换到该应用程序的新版本，因此用户的尾巴很长。
按版本的用户分布最顶层是最新版本的Android应用程序的用户分布。 底部是iOS。
很容易注意到，iOS设备的用户更容易更新，但是即使在其中，也有很多旧版本的用户。
我们还仍在发布Windows Phone冻结版本的新数据。 尽管WP8用户只占我们听众的一小部分，但以绝对数字计算，每月大约有200,000。
长期以来，我们就有一种机制，可以使我们产生几种数据格式，并自动确定哪些版本应该得到什么。 机会不错，但是您仍然需要学习如何卸载这些格式。 第一项主要任务是实现一种服务，该服务将接收所有数据，并针对旧数据库格式过滤掉新数据，并针对新数据库格式过滤掉新数据。
完成的工作有一个不错的好处就是减少了每月更新的大小，因为远程连接每个月都发生了很大的变化，从而增加了差异的大小。
如果您查看其余数据，则总共可以挤出相同的10％，但是价格将无与伦比。 到目前为止，我们决定不碰。
优化当前的存储格式
如上所写，我们制作了1 KiB页，并且未打包所有二进制存储库。
我们要做的第一件事是尝试还打包带有链接的页面，并检查接收数据的速度差异是否在错误区域内。
下一项是选择最佳页面尺寸。 页面大小越大，压缩数据的效率越高，但是获取数据的速度越慢。 而且，如果随着页面大小的增加，时间和内存成本呈线性增长，那么收益将变得越来越不明显。 经过测试后，我们决定将大小增加到8 KiB。
页面大小对大量选择的影响如果预期页面扩大会减慢小选择的速度，那么甚至会加速数百个元素中的大选择。 这意味着您需要根据存储在其中的数据的使用情况，以很好的方式为存储选择不同的大小。
总共，只有这两个点才能使基数减少18％！
更改压缩格式
zlib当然是经典的，但是
zstd提供了更高的解压缩速度和更大的压缩比。 此外，zstd允许您首先为所有可用数据构建一个字典，然后将其保存一次并与所有页面一起压缩。 因此，我们确实减慢了使用数据库创建文件的速度，但是额外增加了8％。
添加门廊
简单的方法
最简单的方法是使每个入口成为一个单独的对象，分别对它们进行索引（根据粗略估计+索引大小的10％），并将它们的几何形状分别存储在用于绘制地图的数据中。
此方法将使基准总共增加3％。 在之前的阶段中，我们赢得了足够的收益，可以按照通常的方案使入口平静下来并使用入口，但是...在开始工作时，我们对此尚不确定，因此正在并行开发另一种形式。
详细评估，有兴趣者让我们尝试评估每个对象在数据库中软件包大小的增加：
8个字节-标识符，
6个字节-已用存储空间的数量（数据+五个属性；属性是从主数据中提取并以二进制形式存储的，因为它们通常一次需要大量对象使用），
3个字节-数据仓库中的索引，
2个字节-对象的偏移量数据，
5个字节-数据值-每个电路2个字节，用于公寓信息的平均3个字节（我们相信会有很多重复，并且数据本身只存储一次），
6个字节-偏移量数据坐标（其他属性具有很多重复值，并且会折叠），
8个字节-坐标值。
每个对象总共38个字节。 就莫斯科而言，这是4.5 MiB，代表着超过12.4万个收集的输入。
接下来，我们还需要存储房屋和入口之间的连接，每个公寓建筑物为2.5字节，每个入口为8字节。 还有1个MiB。
现在我们考虑一下这一切将在地图上显示多少。
首先，我们必须存储几何。 对于折线，第一个点始终占用8个字节，所有后续点都存储为所需精度的差异。 在这里，我们对精确度的满意程度是满意的。 大部分输入由彼此相隔不远的两个点组成，因此可以假定几何图形本身将占用10个字节。 总计1.2 MiB。
我们还需要将输入标识符和对象与其几何形状相关联。 索引与其他所有内容都是相同的二进制存储，仅存储通信目标（1个字节），层号（1个字节）和对象号（3个字节）。 每个标识符加上8个字节，以及一个快速搜索树。 总计另外1.5 MiB。
正如文章开头所说，我们要在地图上不断显示入口，最简单的方法是卸载带有点的另一层，但是...您还可以将具有几何形状的层重用，创建一个新的
符号来显示我们需要的图片在折线的最后一点。
搜索索引的10％为5.9 MiB。 总结所有内容，我们得到了14.2 MiB，仅比3％多一点。
当前选项
除了搜索入口索引和扩大搜索索引之外，我们搜索房屋，但还标记了查询词并从中选择地址（与在加里宁格勒搜索入口有关），入口和/或公寓。 因此，在出口处，我们有房屋标识符和键入的文本字段，通过这些字段我们必须找到所需的楼梯。
注意事项这是一个有争议的观点。 一方面，它使我们能够减小数据库的大小，另一方面，它对输入格式施加了限制-输入将不会出现在许多需要使用诚实搜索正确处理的请求上。
此外，我们不卸载单个对象，而是将有关入口的所有信息直接包含在建筑物数据中。
最后，我们将部分几何图形转移到目录中。
后者值得更详细地披露。
首先，我们注意到大多数输入是两个点，并且具有相同的长度。 这样的输入可以以点+方向的形式存储，即 每个输入节省1个字节。
其次，我们假设现代城市中的大多数房屋都是典型的，因此，其入口点相对于房屋中心点的位移将重合直至转弯。
我们已经有了建筑物的中心点。
如果我们为建筑物添加一个新属性-它的整数“方向”，又为每个输入添加两个新属性-沿着并垂直于方向线的以分米为单位的整数偏移量？考虑到我们如何存储带有信息的json，平均输入几何将仅占据两个字节以上。另一个好处是，由于几何位于目录中，因此我们不再需要在地图层中存储输入标识符和对象编号之间的对应关系。减号-代码变得更加复杂。之前我们只是告诉地图“显示这样的对象”，现在当显示输入时，我们从json提取数据并将动态对象添加到地图。这里的一切不是很可怕。在显示json输入的箭头键时，我们已经有了相应的对象，也就是说，无需另外转到数据库。使用显示的入口点，一切都会变得更糟-现在我们必须在后台确定哪些房屋可见，从数据库中提取这些房屋的数据，拆解json，并在有输入的情况下为其创建动态对象。由于我们已经编写了额外的代码来显示入口的入口，因此没有什么阻止我们开始在目录中的组织中存储两点输入。在这种情况下，增益将很小，但是是免费的。它给了我们多少？3％变为0.5％。我们可以做的甚至更少，但是我们在数据中保留了标识符（压缩效果很差），以简化有关不准确输入的用户消息的处理。结果
我们添加了大量入口，同时将带有地图数据的文件大小减小了0.5％，并将带有目录数据的文件大小减小了26.6％。后者仍然是我们文件中最大的文件，但它只是四个“繁重”文件中的一个，因此，总体变化较小，仅为10.1％。入口尚未收集。基地的规模将随着时间的推移而略有增长（根据目前的估计，同一莫斯科将增长0.4％），但是无论如何，目标是在不增加规模的情况下释放入口，而不是超过实现的规模。接下来是什么？
如果我们谈论杂货店的改进，我们将在搜索提示以及搜索路线的起点和终点中为入口和公寓提供支持。我们还考虑以与门廊相同的方式显示建筑物的重要入口（主要在购物中心）。在技术计划中，对几种想法进行了检查，这些想法可能导致带有参考数据的文件进一步减小，因此您需要仔细查看其他文件。而且，当然，我们将纠正迄今为止的错误。再想一想：明智地使用JSON
综上所述，结论本身表明您不能对二进制格式考虑太多，而仅使用JSON。 这并非完全正确。
这对我们有用，因为同时我们需要从力中接收数十个物体。另外，我们使用rapidjson，它非常聪明并且占用很少的内存。还有必要限制将JSON数据从C ++传输到用另一种语言编写的UI。首先，您必须将其转换为字符串。其次，UI部分可用的解析器将重新组合此行，并且速度会慢得多。最好自己从JSON中获取所有数据，然后将适合于显示特定元素的简单界面扔到UI端。