À la fin du mois dernier, 2GIS a commencé à afficher des porches. Nous montrons les entrées aux organisations depuis 2013, et les entrées semblent être les mêmes entrées. Alors pourquoi maintenant? Tous les produits et processus internes sont prêts, il vous suffit d'ajouter un peu plus et de corriger l'affichage dans l'interface utilisateur.
En plus de la réponse standard «Il y avait d'autres priorités», il y en a aussi une qui n'est pas tout à fait standard: «Ce n'est pas si simple.» Cet article explique quelles étaient les difficultés et comment nous les avons résolues.
Premièrement, l'entrée n'est pas l'entrée. Ainsi, une seule entrée peut conduire à plusieurs entrées, généralement de différents côtés du bâtiment. La définition de «bloc d'appartements (à plusieurs niveaux) avec une entrée commune» est également incorrecte. Il arrive qu'une entrée mène au premier étage de l'entrée, et l'autre - au deuxième étage et aux suivants.
Deuxièmement, je veux chercher des entrées.
C'est une opportunité assez recherchée, car les entrées sont loin d'être toujours situées de manière évidente.
En plus des numéros d'entrée, il existe également des noms (généralement à partir d'une seule lettre).
Ou même comme
à Kaliningrad - une adresse distincte est affectée exactement à l'escalier.
Troisièmement, nous avons décidé que si nous cherchions des entrées, pourquoi ne pas soutenir immédiatement la recherche par numéro d'appartement. Ils ont décidé - et collecté les gammes d'appartements, cependant, jusqu'à présent sans reliure au sol. Comme pour les entrées, les appartements peuvent avoir non seulement des noms numériques (le plus souvent, il existe des variantes avec la lettre «a»), et les plages sont loin d'être toujours continues. Dans les vieilles maisons de Saint-Pétersbourg, la numérotation est assez étrange: les appartements 1 et 3 peuvent être dans la même entrée, et l'appartement 2 peut être dans la partie opposée du bâtiment.
Digression lyrique sur la validation des donnéesN'essayez pas de rendre la validation des données collectées très intelligente - dans la capitale du nord, il y a des cas où vous pouvez entrer dans un appartement à partir de plusieurs entrées, et dans certaines colonies européennes, l'adresse contient en plus de la maison le nom de l'entrée et le numéro de l'appartement dans cette entrée. Peter plaît également avec un bâtiment avec deux huitièmes entrées.
Quatrièmement, je veux toujours montrer les entrées sur la carte, et pas seulement lorsque nous étudions les informations d'une maison ou d'une entrée particulière.
Et enfin, il y a de nombreuses entrées - selon les estimations actuelles, il y en a environ cent mille à Moscou seulement. La première évaluation «sur les doigts» a donné quelques chiffres astronomiques - nous avons fait une erreur une fois toutes les six fois sur le plus grand côté.
Conclusions:- Nous avons besoin d'une entité supplémentaire, qui a son propre nom, contient une liste de gammes d'appartements et auxquelles les entrées du bâtiment peuvent être attachées.
- Nous rechercherons cette entité et lui montrerons une fiche d'information distincte.
- Nous sommes obligés soit d'augmenter à nouveau la taille des données téléchargées par l'application mobile, soit d'afficher ces données uniquement s'il y a une connexion réseau, soit de proposer quelque chose avec le format.
Accéder à la solution
Les deux premiers points nécessitent des changements dans les produits internes et externes, mais c'est une routine. Ce dernier est une question complètement différente. Comme nous n'aimons pas déranger les utilisateurs, nous fixons une restriction: les données doivent être disponibles hors ligne et leur ajout ne doit pas augmenter la taille des bases de données.
Comment? D'une part, vous devez réduire la taille actuelle des données, d'autre part, vous pouvez penser à un tel format de stockage des informations sur les entrées que la quantité de données supplémentaires est minimale.
Réduisez le volume de données
Il existe deux façons de le réduire:
- Examinez attentivement les données stockées et essayez de trouver quelque chose dont nous pouvons nous passer.
- Réfléchissez à la possibilité de stocker les données de manière plus efficace que nous ne le faisons actuellement.
Evolution du format de stockage des données avant l'ère des porchesLa toute première option et la plus simple
La méthode traditionnelle pour enregistrer des données complexes consiste à les
normaliser , à les placer dans une base de données de table et à créer des
index auxiliaires. Une fois, 2GIS a fait exactement cela, sauf pour réduire la taille, le contenu de chaque tableau a été trié de sorte que le plus souvent possible, les valeurs des cellules coïncident avec les valeurs de la ligne précédente. Nous avons stocké les colonnes indépendamment et réduit les séquences de valeurs identiques.
Un exemple très simplifié d'optimisation du stockage d'une table avec des bâtiments:
La normalisation vous permet de réduire la redondance, mais il y a aussi un côté négatif - pour former un élément d'interface utilisateur pour un objet, vous devez effectuer plusieurs requêtes qui accèdent à un grand nombre de tables. Cependant, à cette époque, ces tableaux étaient utilisés non seulement pour obtenir des données à afficher, mais pour presque toutes les tâches, y compris la recherche de texte et divers types de recherche de voyage. Pour toutes ces tâches, les données normalisées nous ont juste permis de réduire la quantité d'informations traitées.
Les données pour le rendu de la carte avaient déjà leur propre format binaire et étaient stockées dans un bloc séparé. Progressivement, nous avons créé des formats binaires distincts pour accélérer la recherche d'itinéraires et les recherches de texte. Seules les informations sont restées dans la base de données, qui a été utilisée pour afficher les fiches d'objets, ainsi que pour les liens de certains objets avec d'autres.
Simplifiez le travail
Comment pouvez-vous simplifier le travail avec les données? Recevez toutes les données nécessaires pour dessiner une carte à la fois par l'identifiant de l'objet. Étant donné que la
version en ligne reçoit déjà toutes les données de l'
API pour une demande au
format JSON , vous pouvez en même temps combiner les formats utilisés par tous nos produits.
Les deux json pour l'affichage des cartes et les communications doivent être reçues pour un nombre limité d'objets, de la puissance de plusieurs dizaines à la fois. Mais il existe des scénarios où des attributs individuels doivent être obtenus à la fois pour des échantillons de grande taille, jusqu'à des centaines de milliers. Il est plus logique de séparer ces attributs dans une entité distincte avec un format de stockage distinct - propriétés. Les propriétés peuvent être de type et stockées plus efficacement au format binaire.
Une approche naïve pour stocker json consiste à utiliser une base de données de valeurs-clés. Prenons Moscou comme exemple, comme le plus grand de nos projets. Même sous la forme la plus simple possible - pour chaque objet json lui-même est stocké, 8 octets d'identifiant et un caractère délimiteur - le répertoire prendra 1,9 Gio. La taille résultante est presque six fois plus grande que l'option décrite précédemment, et cela est toujours sans liens ni propriétés.
Nous avons délibérément gonflé les objets en les remplissant d'informations sur tout ce qui pourrait être nécessaire pour afficher leurs cartes, mais vous devez toujours stocker les noms de champ, les guillemets, les virgules et les crochets.
Compresser les données
La normalisation n'est pas le seul moyen d'éliminer la redondance. La deuxième méthode populaire est la compression. L'archive lzma de notre fichier incroyablement épais ne prend que 55 Mo.
Bien sûr, nous ne pouvons pas utiliser ce format directement, car pour accéder à un objet arbitraire, nous devons décompresser toutes les données stockées précédemment et les archives lzma ne sont pas décompressées très rapidement.
Comment obtenir un accès aléatoire rapide d'une part, et d'autre part, en compressant les données, réduire la taille de l'espace requis? La réponse est d'utiliser la pagination.
Maintenant que les données sont paginées, nous pouvons compresser chacune individuellement. Pour accéder à un endroit arbitraire, nous devons décompresser et numériser la page, mais c'est beaucoup plus rapide que de décompresser et de numériser l'archive entière.
Dans ce format, toutes les données sont stockées - json'y, relations et propriétés. Reste à associer ces données aux identifiants des objets. Pour chaque identifiant, nous devons stocker une ou plusieurs paires
<numéro de stockage, numéro de données dans le stockage> .
Tous les numéros de série, décalages et tailles sont stockés dans un format compressé similaire à
UTF-8 , où les petites valeurs ne prennent qu'un octet. Cela nous permet de réduire la taille des liens en triant simplement le contenu des référentiels binaires pour réduire la fréquence d'occurrence.
Certaines propriétés ont de nombreuses valeurs de fréquence, et donc le tri donne un gros gain de taille. En revanche, à cause de cela, le numéro de série des données ne peut pas coïncider pour tous les stockages.
De plus, loin de tous les objets, des données sont présentes dans tous les stockages, et donc stocker des numéros de stockage est plus efficace que de référencer des objets vides.
Accélérez la récupération des données
Le format décrit présente un problème. Pour trouver le numéro de l'objet qui stocke les indices pour l'identifiant spécifié, nous devons exécuter une recherche binaire à l'intérieur des données du premier objet. Pour ce faire, vous devez soit charger 10,9 Mio en mémoire, soit effectuer 21 lectures supplémentaires. Les deux solutions ne nous conviennent pas et nous réduisons donc le nombre de lectures en stockant les données dans un arbre.
Nous regroupons les données sur 32 objets, et aux niveaux intermédiaires, nous stockons 128 des premiers identifiants des nœuds imbriqués. Nous avons ajouté trois niveaux de l'arborescence et réduit le nombre de lectures supplémentaires à quatre (mais en fait, en tenant compte de la mise en cache des nœuds d'arbre précédemment lus, même à 1-3). Prix - un peu moins de 400 Ko.
À ce stade, nous sommes assez efficaces pour stocker les relations et les propriétés, mais les json occupent beaucoup d'espace. C'est compréhensible. Plus la taille de la page est grande, plus il y a d'objets et plus l'algorithme de compression est en mesure de déterminer quelles informations sont redondantes. Mais, d'un autre côté, plus nous devons travailler pour lire un seul objet. Les Json sont des objets assez gros, et donc il y en a très peu sur une seule page. Par conséquent, vous devez aider l'algorithme à mieux faire son travail.
Diviser JSON en plusieurs parties
Premièrement, de nombreux objets ont des schémas de données correspondants; seules les valeurs d'attribut diffèrent. Deuxièmement, de nombreuses valeurs d'attribut sont les mêmes, même pour des objets avec des schémas différents. Nous séparerons les schémas et les valeurs d'attribut dans des stockages séparés, et nous stockerons les json sous la forme: un lien vers un schéma + des liens vers des valeurs d'attribut.
Dans notre schéma de données, le nombre de noms d'attribut est limité. Nous pouvons donc les mettre dans un fichier séparé et stocker le numéro à la place. Nous apporterons également quelques modifications supplémentaires, en tenant compte du fait que les json sont toujours des objets.
Oui, nous avons essentiellement compressé nos données nous-mêmes, réduisant la portée du fonctionnement de l'algorithme. Mais d'un autre côté, nous avons considérablement ralenti l'accès aux données, et l'algorithme aide toujours, en compressant des valeurs similaires stockées à proximité.
Nous avons fixé la taille de la page à 1 Ko et il se trouve que si nous avons optimisé le format afin que, d'une part, la lecture ne soit pas très lente, et d'autre part, les données aient été emballées le mieux possible, nous ... avons déjà contourné les «tables optimisées» à la fois en taille et pour une facilité d'utilisation. Mais ce n'est pas pour rien que tout cela était! Le gain maximal doit provenir de la compression des valeurs des attributs, des propriétés et des schémas. Nous incitons zlib et vérifions que, dans le contexte du reste du travail, la lecture des données de la base de données prend peu de temps. Satisfait du résultat, nous passons à d'autres tâches.
Débarrassez-vous de l'inutile
Nous commençons à réduire en recherchant des données dont vous pouvez vous débarrasser. Il s'avère que pendant l'existence du format, nous avons appris à nous passer de la plus grande connexion. C'est 10% de la taille!
Le code de ces données était toujours lié, mais les modifications nécessaires sont assez triviales. Mais les applications déjà publiées ne peuvent pas être facilement modifiées. Nous nous efforçons de maintenir aussi longtemps que possible non seulement la rétrocompatibilité, mais aussi la compatibilité directe. Et si le premier est familier à tout le monde, alors beaucoup peuvent ne pas penser au second avec bonheur. Nous sommes obligés de le supporter en raison de la queue assez longue d'utilisateurs qui, pour diverses raisons, ont désactivé les mises à jour automatiques et ne sont pas pressés de passer à une nouvelle version de l'application.
Répartition des utilisateurs par versionTout en haut se trouve la répartition des utilisateurs par les dernières versions de l'application Android. Le fond est iOS.
Il est facile de remarquer que les utilisateurs d'appareils iOS sont mis à jour beaucoup plus facilement, mais même parmi eux, il y a beaucoup d'utilisateurs d'anciennes versions.
Nous publions également de nouvelles données pour la version figée pour Windows Phone. Et bien que les utilisateurs de WP8 ne représentent qu'une petite fraction de notre audience, en chiffres absolus, c'est presque 200 000 par mois.
Nous avons depuis longtemps un mécanisme qui nous permet de produire plusieurs formats de données et détermine automatiquement quelles versions doivent obtenir quoi. L'opportunité est bonne, mais vous devez toujours apprendre à décharger ces formats. La première grande tâche a été d'implémenter un service qui recevra toutes les données et filtrera le nouveau pour l'ancien format de base de données et l'ancien pour le nouveau.
Un bon bonus du travail effectué est de réduire la taille des mises à jour mensuelles, car la connexion à distance a considérablement changé d'un mois à l'autre, gonflant la taille des différences.
Si vous regardez les données restantes, au total, vous pouvez obtenir les mêmes 10%, cependant, le prix sera incomparablement plus élevé. Jusqu'à présent, nous avons décidé de ne pas toucher.
Optimiser le format de stockage actuel
Comme il a été écrit ci-dessus, nous avons créé des pages de 1 Ko et emballé pas tous les référentiels binaires.
La première chose que nous faisons est d'essayer de compresser également les pages avec des liens et de vérifier que la différence de vitesse de réception des données se situe dans la région de l'erreur.
L'élément suivant consiste à choisir la taille de page optimale. Plus la taille de la page est grande, plus les données sont compressées efficacement, mais plus les données sont lues lentement. Et si, avec l'augmentation de la taille des pages, les coûts de temps et de mémoire augmentent linéairement, le gain devient de moins en moins perceptible. Après les tests, nous décidons d'augmenter la taille à 8 Ko.
L'effet de la taille de la page sur les grandes sélectionsSi l'agrandissement de la page devrait ralentir les petites sélections, les grandes - à partir de centaines d'éléments - sont même accélérées. Cela signifie que dans le bon sens, vous devez choisir différentes tailles pour les stockages en fonction des cas d'utilisation des données qui y sont stockées.
Au total, seuls ces deux points peuvent réduire la base de 18%!
Changer le format de compression
zlib, bien sûr, est un classique, mais
zstd fournit une vitesse de décompression plus élevée avec un taux de compression plus élevé. De plus, zstd vous permet de créer d'abord un dictionnaire unique pour toutes les données disponibles, puis de l'enregistrer une fois et de le compresser avec toutes les pages. Ainsi, nous ralentissons décemment le processus de création d'un fichier avec une base de données, mais nous pressons 8% supplémentaires.
Ajouter des porches
Moyen facile
Le moyen le plus simple est de faire de chaque entrée un objet distinct, de les indexer séparément (selon des estimations approximatives + 10% de la taille de l'indice) et de stocker séparément leur géométrie dans les données pour dessiner la carte.
Cette méthode gonflera la base de 3% au total. Lors des étapes précédentes, nous avons gagné plus qu'assez pour nous calmer et travailler avec les entrées selon le schéma habituel, mais ... au moment du début des travaux, nous n'étions pas sûrs de cela, et travailler sur un format alternatif était en parallèle.
Évaluation détaillée, pour les personnes intéresséesEssayons d'évaluer l'augmentation de la taille du package avec la base de données pour chaque objet:
8 octets - identifiant,
6 octets - nombre de stockages utilisés (données + cinq propriétés; les propriétés sont extraites des données principales et stockées sous forme binaire, car elles sont souvent nécessaires pour un grand nombre d'objets à la fois),
3 octets - index dans l'entrepôt de données,
2 octets - décalage des données de l'objet,
5 octets - valeurs de données - 2 octets par circuit, 3 octets en moyenne pour les informations d'appartement (nous pensons qu'il y aura de nombreux doublons et que les données elles-mêmes sont stockées une fois),
6 octets - coordonnées de données décalées (d'autres propriétés ont de nombreuses valeurs en double et s'effondreront),
8 octets - valeurs de coordonnées.
Total 38 octets par objet. Dans le cas de Moscou, cela représente 4,5 Mio pour plus de 124 000 intrants collectés.
Ensuite, nous devons stocker également la connexion entre la maison et les entrées, c'est 2,5 octets pour chaque immeuble et 8 octets pour chaque entrée. 1 MiB de plus.
Maintenant, nous considérons combien tout cela prendra sur la carte.
Tout d'abord, nous devons stocker la géométrie. Pour les polylignes, le premier point prend toujours 8 octets et tous les suivants sont stockés sous forme de différences de la précision requise. Ici, nous sommes satisfaits de la précision en décimètres. La plupart des entrées se composent de deux points qui ne sont pas très éloignés l'un de l'autre, et donc on peut supposer que la géométrie elle-même occupera 10 octets. Total 1,2 Mio.
Nous devons également associer l'identifiant d'entrée et l'objet à sa géométrie. Un index est le même stockage binaire que tout le reste, seules la destination de communication (1 octet), le numéro de couche (1 octet) et le numéro d'objet (3 octets) sont stockés. Plus 8 octets par identifiant, ainsi qu'un arbre de recherche rapide. Total de 1,5 Mio.
Comme cela a été dit au tout début de l'article, nous voulons afficher en permanence les entrées sur la carte, et la façon la plus simple de le faire est de décharger une autre couche avec des points, mais ... vous pouvez également réutiliser la couche avec des géométries, créant un nouveau
symbole qui affichera l'image dont nous avons besoin au dernier point de la polyligne.
10% de l'index de recherche est de 5,9 MiB. Pour résumer tout, nous obtenons 14,2 MiB, ce qui est juste un peu plus de 3%.
Option actuelle
Au lieu d'indexer les entrées et de gonfler l'index de recherche, nous recherchons des maisons, mais balisons en outre les mots de la requête et en extrayons des adresses (pertinentes pour la recherche d'entrées à Kaliningrad), des entrées et / ou des appartements. Ainsi, à la sortie, nous avons l'identifiant de la maison et les champs de texte tapés, par lesquels nous devons trouver l'escalier dont nous avons besoin.
RemarqueC'est un point controversé. D'une part, cela nous permet de réduire la taille de la base de données, et d'autre part, il impose des restrictions sur le format d'entrée - les entrées ne seront pas sur de nombreuses demandes qui seraient correctement traitées en utilisant une recherche honnête.
De plus, au lieu de décharger des objets individuels, nous incluons toutes les informations sur les entrées directement dans les données du bâtiment.
Et enfin, nous transférons une partie des géométries dans le répertoire.
Ce dernier mérite d'être divulgué plus en détail.
Tout d'abord, nous remarquons que la plupart des entrées sont deux points et ont la même longueur. Ces entrées peuvent être stockées sous la forme d'un point + direction, c'est-à-dire économisez 1 octet par entrée.
Deuxièmement, nous supposons que la plupart des maisons dans les villes modernes sont typiques, par conséquent, les déplacements des points de leurs entrées par rapport au point central de la maison coïncideront jusqu'à un tour.
Nous avons déjà les points centraux des bâtiments.
Que se passe-t-il si nous ajoutons une nouvelle propriété pour le bâtiment - sa "direction" entière, et pour chaque entrée deux autres - décalages entiers en décimètres le long et perpendiculaire à la ligne de direction? Compte tenu de la façon dont nous stockons les json avec des informations, la géométrie d'entrée occupera en moyenne un peu plus de deux octets.Un bonus supplémentaire est que puisque la géométrie est dans le répertoire, nous n'avons plus besoin de stocker la correspondance entre l'identifiant d'entrée et le numéro d'objet dans la couche de carte.Moins - le code est devenu plus compliqué. Auparavant, nous venions de dire à la carte de "montrer tel ou tel objet", et maintenant lors de l'affichage des entrées, nous extrayons ces données de json et ajoutons des objets dynamiques à la carte. Tout n'est pas très effrayant ici. Au moment d'afficher les touches fléchées des entrées json, nous avons déjà les objets correspondants, c'est-à-dire qu'il n'est pas nécessaire d'aller en plus dans la base de données. Avec les points d'entrée affichés, tout est légèrement pire - maintenant, nous devons déterminer en arrière-plan quelles maisons sont visibles, extraire les données de ces maisons de la base de données, analyser json et, s'il y a des entrées, créer des objets dynamiques pour elles.Remarque. , , 0,2% (972 ).
Comme nous avons déjà écrit du code supplémentaire pour afficher les entrées aux entrées, rien ne nous empêche de commencer à stocker des entrées à deux points dans l'organisation dans l'annuaire. Le gain dans ce cas sera faible, mais gratuit.Combien cela nous a-t-il donné? 3% sont devenus 0,5%. Nous aurions pu faire encore moins, mais nous avons laissé des identifiants dans les données (qui sont assez mal compressés) pour simplifier le traitement des messages utilisateur sur les entrées inexactes.Résultat
Nous avons ajouté un grand nombre d'entrées, tout en réduisant la taille du fichier avec les données cartographiques de 0,5% et en réduisant de 26,6% la taille du fichier avec les données du répertoire. Ce dernier est toujours le plus gros de nos fichiers, mais il ne s'agit que d'un des quatre fichiers «lourds», de sorte que le changement global s'est avéré plus modeste - 10,1%.Les entrées ne sont pas encore collectées. La taille des bases augmentera légèrement au fil du temps (selon les estimations actuelles, le même Moscou augmentera de 0,4%), mais en tout cas, l'objectif est de libérer les entrées sans augmenter la taille, plus qu'atteint.Et ensuite?
Si nous parlons d'améliorations d'épicerie, nous allons soutenir les entrées et les appartements dans les conseils de recherche, ainsi que dans la recherche des points de début et de fin de la recherche d'itinéraires. Nous pensons également à afficher les entrées importantes des bâtiments (principalement dans les centres commerciaux) de la même manière que les porches.Dans les plans techniques, il existe une vérification de plusieurs idées qui peuvent conduire à une réduction supplémentaire de la taille du fichier avec des données de référence, et vous devez examiner attentivement les autres fichiers.Et, bien sûr, nous corrigerons les erreurs que nous avons jusqu'à présent.Une dernière pensée: utilisez JSON judicieusement
D'après ce qui précède, la conclusion suggère que vous ne pouvez pas trop penser aux formats binaires et simplement utiliser JSON. Ce n'est pas tout à fait vrai.
Cela fonctionne pour nous, car en même temps, nous devons recevoir plusieurs dizaines d'objets de la force. De plus, nous utilisons rapidjson, et il est très intelligent et consomme peu de mémoire.Il convient également de restreindre le transfert de données JSON de C ++ vers l'interface utilisateur, écrites dans un autre langage.Tout d'abord, vous devez le transformer en chaîne.Deuxièmement, les analyseurs disponibles à partir de la partie interface utilisateur remonteront cette ligne, et le feront beaucoup plus lentement.Il est préférable d'obtenir toutes les données de JSON par vous-même et de lancer des interfaces simples adaptées pour afficher des éléments spécifiques du côté de l'interface utilisateur.