No final do mês passado, o 2GIS começou a exibir varandas. Mostramos as entradas para as organizações desde 2013, e as entradas parecem ser as mesmas. Então, por que agora? Todos os produtos e processos internos estão prontos, tudo o que você precisa fazer é adicionar um pouco mais e corrigir a exibição na interface do usuário.
Além da resposta padrão "Havia outras prioridades", há também uma não muito padrão: "Não é tão simples". Este artigo é sobre quais eram as dificuldades e como as resolvemos.
Em primeiro lugar, a entrada não é a entrada. Assim, em uma entrada pode levar várias entradas, geralmente de lados diferentes do edifício. A definição de "bloco de apartamentos (multinível) com uma entrada comum" também está incorreta. Acontece que uma entrada leva ao primeiro andar da entrada e a outra - ao segundo e subsequentes andares.
Em segundo lugar, quero procurar entradas.
Esta é uma oportunidade bastante procurada, pois as entradas nem sempre estão localizadas de maneira óbvia.
Além dos números de entrada, também existem nomes (geralmente de uma única letra).
Ou mesmo
em Kaliningrado - um endereço separado é atribuído exatamente à escada.
Em terceiro lugar, decidimos que, se fizéssemos uma busca por entradas, por que não apoiar imediatamente a busca pelo número do apartamento. Eles decidiram - e coletaram as séries de apartamentos, no entanto, até agora sem um encadernação no chão. Assim como nas entradas, os apartamentos podem ter não apenas nomes numéricos (na maioria das vezes existem variantes com a letra "a"), e os intervalos estão longe de ser sempre contínuos. Nas casas antigas de São Petersburgo, a numeração é bastante estranha: os apartamentos 1 e 3 podem estar na mesma entrada e o apartamento 2 pode estar na parte oposta do edifício.
Digressão lírica sobre validação de dadosNão tente fazer a validação dos dados coletados de maneira muito inteligente - na capital do norte, há casos em que você pode entrar em um apartamento de várias entradas e, em alguns assentamentos europeus, o endereço contém, além da casa, o nome da entrada e o número do apartamento nessa entrada. Peter também agrada com um edifício com duas oitavas entradas.
Quarto, quero mostrar sempre as entradas no mapa, e não apenas quando estudamos as informações de uma casa ou entrada em particular.
E, finalmente, existem muitas entradas - de acordo com a estimativa atual, existem cerca de cem mil delas somente em Moscou. A primeira avaliação "nos dedos" deu algumas figuras astronômicas - cometemos um erro uma vez a cada seis vezes para o lado maior.
Conclusões:- Precisamos de uma entidade adicional, com seu próprio nome, que contenha uma lista de faixas de apartamentos e às quais as entradas do edifício possam ser anexadas.
- Procuraremos essa entidade e mostraremos para ela um cartão de informações separado.
- Somos obrigados a aumentar mais uma vez o tamanho dos dados baixados pelo aplicativo móvel, ou mostrar esses dados apenas se houver uma conexão de rede, ou apresentar algo com o formato.
Chegando à solução
Os dois primeiros pontos exigem alterações nos produtos internos e externos, mas isso é uma rotina. O último é uma questão completamente diferente. Como não gostamos de incomodar os usuários, definimos uma restrição: os dados devem estar disponíveis offline e a adição deles não deve aumentar o tamanho dos bancos de dados.
Como Por um lado, você precisa reduzir o tamanho atual dos dados; por outro, pode criar um formato para armazenar informações sobre entradas, para que a quantidade de dados adicionais seja mínima.
Reduzir o volume de dados
Existem duas maneiras de reduzi-lo:
- Observe atentamente os dados armazenados e tente encontrar algo que não podemos fazer.
- Pense se é possível, de alguma forma, armazenar dados com mais eficiência do que estamos fazendo agora.
Evolução do formato de armazenamento de dados antes da era das varandasA primeira e mais fácil opção
A maneira tradicional de salvar dados complexos é
normalizá- los, colocá-los em um banco de dados de tabelas e criar
índices auxiliares. Uma vez, o 2GIS fez exatamente isso, exceto para reduzir o tamanho, o conteúdo de cada tabela foi classificado de modo que, sempre que possível, os valores das células coincidissem com os valores da linha anterior. Armazenamos as colunas independentemente e colapsamos sequências de valores idênticos.
Um exemplo altamente simplificado de otimização do armazenamento de uma tabela com edifícios:
A normalização permite reduzir a redundância, mas também existe um lado negativo - para formar um elemento de interface do usuário para algum objeto, é necessário fazer várias consultas que acessam um grande número de tabelas. No entanto, na época, essas tabelas eram usadas não apenas para obter dados para exibição, mas para quase todas as tarefas, incluindo pesquisa de texto e vários tipos de pesquisa de viagem. Para todas essas tarefas, os dados normalizados nos permitiram reduzir a quantidade de informações processadas.
Os dados para renderizar o mapa já tinham seu próprio formato binário e foram armazenados em um bloco separado. Gradualmente, criamos formatos binários separados para acelerar a pesquisa de direções e pesquisas de texto. Somente informações foram deixadas no banco de dados, que foi usado para exibir cartões de objetos, bem como para links de alguns objetos com outros.
Simplifique o trabalho
Como você pode simplificar o trabalho com dados? Receba todos os dados necessários para desenhar um cartão de uma só vez pelo identificador do objeto. Como a
versão online já recebe todos os dados da
API para uma solicitação no
formato JSON , você pode ao mesmo tempo combinar os formatos usados por todos os nossos produtos.
Os json's para exibição de cartões e as comunicações precisam ser recebidas para um número limitado de objetos, com o poder de várias dezenas de cada vez. Mas há cenários em que atributos individuais precisam ser obtidos de uma só vez para amostras grandes, até centenas de milhares. É mais lógico separar esses atributos em uma entidade separada com um formato de armazenamento separado - propriedades. As propriedades podem ser do tipo e armazenadas com mais eficiência em formato binário.
Uma abordagem ingênua para armazenar o json é usar um banco de dados de valores-chave. Tome Moscou como exemplo, como o maior de nossos projetos. Mesmo da forma mais simples possível - para cada objeto o json é armazenado, 8 bytes de identificador e um caractere delimitador - o diretório terá 1,9 GiB. O tamanho resultante é quase seis vezes maior que a opção descrita anteriormente, e isso ainda está sem vínculos e propriedades.
Nós inflamos objetos deliberadamente, enchendo-os de informações sobre tudo o que é necessário para exibir seus cartões, mas você ainda precisa armazenar nomes de campos, aspas, vírgulas e colchetes.
Compactar dados
A normalização não é a única maneira de eliminar a redundância. A segunda maneira popular é a compressão. O arquivo lzma do nosso arquivo incrivelmente espesso leva apenas 55 MiB.
Obviamente, não podemos usar esse formato diretamente, pois para acessar um objeto arbitrário, precisamos descompactar todos os dados armazenados anteriormente, e os arquivos lzma não são descomprimidos muito rapidamente.
Como podemos obter acesso aleatório rápido, por um lado, e por outro lado, compactando os dados, reduzindo o tamanho do espaço necessário? A resposta é usar paginação.
Agora que os dados estão paginados, podemos compactar cada um individualmente. Para acessar um local arbitrário, precisamos descompactar e digitalizar a página, mas isso é muito mais rápido do que descompactar e digitalizar o arquivo inteiro.
Nesse formato, todos os dados são armazenados - json'y, relacionamentos e propriedades. Resta associar esses dados aos identificadores dos objetos. Para cada identificador, precisamos armazenar um ou mais pares
<número de armazenamento, número de dados no armazenamento> .
Todos os números de série, compensações e tamanhos são armazenados em um formato compactado semelhante ao
UTF-8 , onde valores pequenos ocupam apenas um byte. Isso nos permite reduzir o tamanho dos links, simplesmente classificando o conteúdo dos repositórios binários para reduzir a frequência da ocorrência.
Algumas propriedades têm muitos valores de frequência e, portanto, a classificação fornece um grande ganho de tamanho. Por outro lado, por causa disso, o número de série dos dados não pode coincidir para todos os armazenamentos.
Além disso, longe de todos os objetos, há dados em todos os armazenamentos e, portanto, armazenar números de armazenamento é mais eficiente do que fazer referência a objetos vazios.
Acelere a recuperação de dados
O formato descrito tem um problema. Para encontrar o número do objeto que armazena os índices para o identificador especificado, precisamos executar uma pesquisa binária dentro dos dados do primeiro objeto. Para fazer isso, você precisa carregar 10,9 MiB na memória ou fazer 21 leituras adicionais. Ambas as soluções não são adequadas para nós e, portanto, reduzimos o número de leituras armazenando dados em uma árvore.
Agrupamos dados em 32 objetos e, nos níveis intermediários, armazenamos 128 dos primeiros identificadores de nós aninhados. Adicionamos três níveis da árvore e reduzimos o número de leituras adicionais para quatro (mas, de fato, levando em consideração o armazenamento em cache dos nós da árvore lidos anteriormente, mesmo para 1-3). Preço - um pouco menos de 400 KiB.
Nesse estágio, somos bastante eficientes em armazenar relacionamentos e propriedades, mas o json ocupa muito espaço. Isso é compreensível. Quanto maior o tamanho da página, mais objetos chegam lá e melhor o algoritmo de compactação é capaz de determinar quais informações são redundantes. Mas, por outro lado, mais trabalho precisamos fazer para ler um único objeto. Os objetos Json são muito grandes e, portanto, existem muito poucos em uma página. Portanto, você precisa ajudar o algoritmo a fazer seu trabalho melhor.
Quebrar json em partes
Em primeiro lugar, muitos objetos têm esquemas de dados correspondentes; apenas os valores dos atributos diferem. Em segundo lugar, muitos valores de atributo são os mesmos, mesmo para objetos com esquemas diferentes. Vamos separar os esquemas e atribuir valores em armazenamentos separados, e armazenaremos os json's na forma: um link para um esquema + links para atribuir valores.
Em nosso esquema de dados, o número de nomes de atributos é limitado. Assim, podemos colocá-los em um arquivo separado e armazenar o número. Também faremos mais algumas alterações, levando em consideração que os json são sempre objetos.
Sim, nós basicamente esprememos nossos dados, reduzindo o escopo para o algoritmo funcionar. Mas, por outro lado, diminuímos bastante o acesso aos dados, e o algoritmo ainda ajuda, comprimindo valores semelhantes armazenados nas proximidades.
Definimos o tamanho da página como 1 KiB e, apesar de otimizarmos o formato para que, por um lado, a leitura não fosse muito lenta e, por outro lado, os dados fossem compactados da melhor maneira possível, já ... ignoramos as “tabelas otimizadas” em tamanho e para facilidade de uso. Mas não é à toa que tudo isso foi! O ganho máximo deve ser da compressão dos valores de atributos, propriedades e esquemas. Incitamos o zlib e verificamos que, no contexto do restante do trabalho, a leitura dos dados do banco de dados leva pouco tempo. Satisfeitos com o resultado, mudamos para outras tarefas.
Livre-se do desnecessário
Começamos a reduzir pesquisando dados dos quais você pode se livrar. Acontece que, durante a existência do formato, aprendemos a ficar sem a maior conexão. Isso representa 10% do tamanho!
O código para esses dados ainda estava vinculado, mas as alterações necessárias são bastante triviais. Mas os aplicativos já lançados não podem ser facilmente alterados. Nós nos esforçamos para manter o maior tempo possível, não apenas para trás, mas também para compatibilidade direta. E se o primeiro é familiar a todos, muitos podem não pensar no segundo. Somos forçados a apoiá-lo devido à longa cauda de usuários que, por vários motivos, desativaram as atualizações automáticas e não têm pressa em mudar para uma nova versão do aplicativo.
Distribuição de usuários por versãoNo topo está a distribuição dos usuários pelas versões mais recentes do aplicativo Android. A parte inferior é o iOS.
É fácil perceber que os usuários de dispositivos iOS são atualizados com muito mais facilidade, mas mesmo entre eles existem muitos usuários de versões mais antigas.
Também estamos lançando novos dados para a versão congelada do Windows Phone. E embora os usuários do WP8 representem apenas uma pequena fração do nosso público, em números absolutos, isso é quase 200.000 por mês.
Há muito tempo possuímos um mecanismo que nos permite produzir vários formatos de dados e determina automaticamente quais versões devem receber o quê. A oportunidade é boa, mas você ainda precisa aprender como descarregar esses formatos. A primeira grande tarefa foi implementar um serviço que receba todos os dados e filtre os novos para o antigo formato de banco de dados e os antigos para o novo.
Um bom bônus do trabalho realizado é reduzir o tamanho das atualizações mensais, pois a conexão remota mudou bastante de mês para mês, aumentando o tamanho das diferenças.
Se você olhar para os dados restantes, no total, poderá espremer os mesmos 10%, no entanto, o preço será incomparavelmente mais alto. Até agora, decidimos não tocar.
Otimize o formato de armazenamento atual
Como foi escrito acima, criamos 1 página KiB e não empacotamos todos os repositórios binários.
A primeira coisa que fazemos é tentar compactar também páginas com links e verificar se a diferença na velocidade de recebimento de dados está na região do erro.
O próximo item é escolher o tamanho ideal da página. Quanto maior o tamanho da página, mais eficientemente os dados são compactados, mas mais lentamente os dados são buscados. E se, com o aumento do tamanho da página, os custos de tempo e memória aumentam linearmente, o ganho se torna cada vez menos perceptível. Após os testes, decidimos aumentar o tamanho para 8 KiB.
O efeito do tamanho da página em grandes seleçõesSe o aumento da página diminuir a velocidade das pequenas seleções, as grandes - de centenas de elementos - são aceleradas. Isso significa que, de uma maneira boa, você precisa escolher tamanhos diferentes para armazenamento, dependendo dos casos de uso dos dados armazenados neles.
No total, apenas esses dois pontos podem reduzir a base em 18%!
Alterar o formato de compactação
O zlib, é claro, é um clássico, mas o
zstd fornece uma velocidade de descompressão mais alta com uma taxa de compressão maior. Além disso, o zstd permite criar primeiro um único dicionário para todos os dados disponíveis, salvá-lo uma vez e compactá-lo com todas as páginas. Assim, desaceleramos decentemente o processo de criação de um arquivo com um banco de dados, mas reduzimos mais 8%.
Adicionar varandas
Maneira fácil
A maneira mais fácil é transformar cada entrada em um objeto separado, indexá-los separadamente (de acordo com estimativas aproximadas + 10% do tamanho do índice) e armazenar separadamente sua geometria nos dados para desenhar o mapa.
Este método inflará a base em um total de 3%. Nas etapas anteriores, ganhamos mais que o suficiente para nos acalmar e trabalhar com as entradas de acordo com o esquema usual, mas ... no início do trabalho, não tínhamos certeza disso, e o trabalho em um formato alternativo era paralelo.
Avaliação detalhada, para os interessadosVamos tentar avaliar o aumento no tamanho do pacote com o banco de dados para cada objeto:
8 bytes - identificador,
6 bytes - número de armazenamentos usados (dados + cinco propriedades; as propriedades são extraídas dos dados principais e armazenadas em formato binário, pois geralmente são necessárias para um grande número de objetos de uma só vez),
3 bytes - índice no data warehouse,
2 bytes - dados de deslocamento do objeto,
5 bytes - valores dos dados - 2 bytes por circuito, 3 bytes em média para informações do apartamento (acreditamos que haverá muitas duplicatas e os próprios dados serão armazenados uma vez),
6 bytes - coordenadas de dados de deslocamento (outras propriedades têm muitos valores duplicados e entram em colapso),
8 bytes - valores de coordenadas.
Total de 38 bytes por objeto. No caso de Moscou, são 4,5 MiB para mais de 124 mil insumos coletados.
Em seguida, precisamos armazenar também a conexão entre a casa e as entradas, são 2,5 bytes para cada prédio e 8 bytes para cada entrada. Mais 1 MiB.
Agora, consideramos quanto tudo isso levará no mapa.
Primeiro, devemos armazenar a geometria. Para polilinhas, o primeiro ponto sempre leva 8 bytes, e todos os subsequentes são armazenados como diferenças da precisão necessária. Aqui, estamos satisfeitos com a precisão dos decímetros. A maioria das entradas consiste em dois pontos que não estão muito longe um do outro e, portanto, pode-se supor que a própria geometria ocupará 10 bytes. Total 1,2 MiB.
Também precisamos associar o identificador de entrada e o objeto à sua geometria. Um índice é o mesmo armazenamento binário que tudo o resto, apenas o destino da comunicação (1 byte), o número da camada (1 byte) e o número do objeto (3 bytes) são armazenados. Mais 8 bytes por identificador, além de uma árvore de pesquisa rápida. Total outro 1,5 MiB.
Como foi dito no começo do artigo, queremos exibir constantemente as entradas no mapa, e a maneira mais fácil de fazer isso é descarregar outra camada com pontos, mas ... você também pode reutilizar a camada com geometrias, criando um novo
símbolo que exibirá a imagem de que precisamos no último ponto da polilinha.
10% do índice de pesquisa é de 5,9 MiB. Resumindo tudo, temos 14,2 MiB, que é um pouco mais de 3%.
Opção atual
Em vez de indexar as entradas e aumentar o índice de pesquisa, procuramos casas, mas adicionalmente marcamos as palavras da consulta e selecionamos endereços (relevantes para a pesquisa de entradas em Kaliningrado), entradas e / ou apartamentos. Assim, na saída, temos o identificador da casa e os campos de texto digitados, pelos quais devemos encontrar a escada de que precisamos.
NotaEste é um ponto controverso. Por um lado, nos permite reduzir o tamanho do banco de dados e, por outro, impõe restrições ao formato de entrada - as entradas não estarão em muitos pedidos que seriam processados corretamente usando uma pesquisa honesta.
Além disso, em vez de descarregar objetos individuais, incluímos todas as informações sobre as entradas diretamente nos dados da construção.
E, finalmente, transferimos parte das geometrias para o diretório
Vale a pena divulgar este último com mais detalhes.
Primeiramente, notamos que a maioria das entradas tem dois pontos e o mesmo comprimento. Tais entradas podem ser armazenadas na forma de um ponto + direção, ou seja, economize 1 byte por entrada.
Em segundo lugar, assumimos que a maioria das casas nas cidades modernas é típica; portanto, os deslocamentos dos pontos de suas entradas em relação ao ponto central da casa coincidirão até uma volta.
Já temos os pontos centrais dos edifícios.
E se adicionarmos uma nova propriedade ao edifício - sua "direção" inteira, e para cada entrada mais duas compensações - inteiras em decímetros ao longo e perpendiculares à linha de direção? Considerando como armazenamos json's com informações, a geometria de entrada, em média, ocupará pouco mais de dois bytes.Um bônus adicional é que, como a geometria está no diretório, não precisamos mais armazenar a correspondência entre o identificador de entrada e o número do objeto na camada do mapa.Menos - o código se tornou mais complicado. Anteriormente, acabamos de dizer ao mapa “mostrar tais e tais objetos” e agora, ao exibir as entradas, extraímos esses dados do json e adicionamos objetos dinâmicos ao mapa. Tudo não é muito assustador aqui. Na hora de exibir as teclas de seta das entradas json, já temos objetos correspondentes, ou seja, não há necessidade de ir adicionalmente ao banco de dados. Com os pontos de entrada exibidos, tudo fica um pouco pior - agora temos que determinar em segundo plano quais casas são visíveis, extrair os dados dessas casas do banco de dados, analisar o json e, se houver entradas, criar objetos dinâmicos para eles.Como já escrevemos código adicional para exibir as entradas, nada nos impede de começar a armazenar entradas de dois pontos na organização no diretório. O ganho neste caso será pequeno, mas gratuito.Quanto isso nos deu? 3% se transformaram em 0,5%. Poderíamos ter feito ainda menos, mas deixamos identificadores nos dados (que são compactados de maneira insuficiente) para simplificar o processamento de mensagens do usuário sobre entradas imprecisas.Resultado
Adicionamos um grande número de entradas, enquanto reduzíamos o tamanho do arquivo com dados do mapa em 0,5% e em 26,6% o tamanho do arquivo com os dados do diretório. O último ainda é o maior de nossos arquivos, mas é apenas um dos quatro arquivos "pesados"; portanto, a alteração geral acabou sendo mais modesta - 10,1%.As entradas ainda não foram coletadas. O tamanho das bases aumentará um pouco com o tempo (de acordo com as estimativas atuais, o mesmo Moscou aumentará 0,4%), mas, em qualquer caso, o objetivo é liberar as entradas sem aumentar o tamanho, mais do que o alcançado.O que vem a seguir?
Se falarmos sobre melhorias na mercearia, apoiaremos as entradas e os apartamentos nas dicas de pesquisa, bem como na pesquisa dos pontos de partida e de término da pesquisa de direções. Também pensamos em exibir entradas importantes para edifícios (principalmente em shopping centers) da mesma maneira que as varandas.Nos planos técnicos, há uma verificação de várias idéias que podem levar a uma redução adicional no tamanho do arquivo com dados de referência, e você precisa examinar cuidadosamente outros arquivos.E, é claro, corrigiremos os erros que temos até agora.Mais um pensamento: use JSON com sabedoria
Pelo exposto, a conclusão sugere que você não pode pensar muito em formatos binários e apenas usar JSON. Isto não é inteiramente verdade.
Isso funciona para nós, porque ao mesmo tempo precisamos receber várias dezenas de objetos da força. Além disso, usamos o rapidjson, que é muito inteligente e consome pouca memória.Também vale a pena restringir a transferência de dados JSON de C ++ para UI, escritos em outro idioma.Primeiro, você precisa transformá-lo em uma string.Em segundo lugar, os analisadores disponíveis na parte da interface do usuário remontam essa linha e o fazem muito mais devagar.É melhor obter todos os dados do JSON por conta própria e lançar interfaces simples adaptadas para exibir elementos específicos no lado da interface do usuário.