A finales del mes pasado, 2GIS comenzó a mostrar porches. Hemos estado mostrando las entradas a las organizaciones desde 2013, y las entradas parecen ser las mismas entradas. Entonces, ¿por qué justo ahora? Todos los productos y procesos internos están listos, todo lo que necesita hacer es agregar un poco más y corregir la pantalla en la interfaz de usuario.
Además de la respuesta estándar "Hubo otras prioridades", también hay una no bastante estándar: "No es tan simple". Este artículo trata sobre las dificultades y cómo las resolvimos.
En primer lugar, la entrada no es la entrada. Por lo tanto, en una entrada puede conducir varias entradas, generalmente desde diferentes lados del edificio. La definición de "bloque (de varios niveles) de apartamentos con una entrada común" también es incorrecta. Sucede que una entrada conduce al primer piso de la entrada, y la otra, al segundo y subsiguientes pisos.
En segundo lugar, quiero buscar entradas.
Esta es una oportunidad muy buscada, ya que las entradas están lejos de estar siempre ubicadas de manera obvia.
Además de los números de entrada, también hay nombres (generalmente de una sola letra).
O incluso como
en Kaliningrado : se asigna una dirección separada exactamente a la escalera.
En tercer lugar, decidimos que si íbamos a buscar entradas, ¿por qué no apoyar inmediatamente la búsqueda por número de apartamento? Decidieron, y recogieron las gamas de apartamentos, sin embargo, hasta ahora sin una fijación al piso. Al igual que con las entradas, los apartamentos pueden tener no solo nombres numéricos (la mayoría de las veces hay variantes con la letra "a"), y los rangos están lejos de ser siempre continuos. En las antiguas casas de San Petersburgo, la numeración es bastante extraña: los apartamentos 1 y 3 pueden estar en la misma entrada, y el apartamento 2 puede estar en la parte opuesta del edificio.
Digresión de letras sobre la validación de datosNo intente hacer que la validación de los datos recopilados sea muy inteligente: en la capital del norte hay casos en los que puede ingresar a un apartamento desde varias entradas, y en algunos asentamientos europeos la dirección contiene, además de la casa, el nombre de la entrada y el número de apartamento en esta entrada. Peter también agrada con un edificio con dos octavas entradas.
Cuarto, quiero mostrar siempre las entradas en el mapa, y no solo cuando estudiamos la información de una casa o entrada en particular.
Y, finalmente, hay muchas entradas: según la estimación actual, hay alrededor de cien mil de ellas solo en Moscú. La primera evaluación "en los dedos" dio algunas cifras astronómicas: cometimos un error una vez cada seis veces en el lado más grande.
Conclusiones:- Necesitamos una entidad adicional, que tenga su propio nombre, que contenga una lista de rangos de apartamentos y a la que se puedan adjuntar las entradas al edificio.
- Buscaremos esta entidad y le mostraremos una tarjeta de información separada.
- Nos vemos obligados una vez más a aumentar el tamaño de los datos descargados por la aplicación móvil, o mostrar estos datos solo si hay una conexión de red, o encontrar algo con el formato.
Llegando a la solución
Los primeros dos puntos requieren cambios en los productos internos y externos, pero esta es una rutina. Este último es un asunto completamente diferente. Como no nos gusta molestar a los usuarios, establecemos una restricción: los datos deben estar disponibles sin conexión, y agregarlos no debe aumentar el tamaño de las bases de datos.
Como? Por un lado, debe reducir el tamaño actual de los datos, por otro lado, puede encontrar un formato para almacenar información sobre las entradas, de modo que la cantidad de datos adicionales sea mínima.
Reduce el volumen de datos
Hay dos formas de reducirlo:
- Mire cuidadosamente los datos almacenados e intente encontrar algo de lo que podamos prescindir.
- Piense si es posible almacenar datos de manera más eficiente de lo que lo estamos haciendo ahora.
Evolución del formato de almacenamiento de datos antes de la era de los porchesLa primera y más fácil opción
La forma tradicional de guardar datos complejos es
normalizarlos , colocarlos en una base de datos de tablas y crear
índices auxiliares. Una vez, 2GIS hizo exactamente eso, excepto para reducir el tamaño, los contenidos de cada tabla se ordenaron de manera que con la mayor frecuencia posible los valores de las celdas coincidieran con los valores de la fila anterior. Almacenamos las columnas de forma independiente y colapsamos secuencias de valores idénticos.
Un ejemplo muy simplificado de optimizar el almacenamiento de una mesa con edificios:
La normalización le permite reducir la redundancia, pero también hay un lado negativo: para formar un elemento de la interfaz de usuario para algún objeto, debe realizar varias consultas para acceder a una gran cantidad de tablas. Sin embargo, en ese momento, estas tablas se usaron no solo para obtener datos para mostrar, sino para casi todas las tareas, incluida la búsqueda de texto y varios tipos de búsqueda de viajes. Para todas estas tareas, los datos normalizados simplemente nos permitieron reducir la cantidad de información procesada.
Los datos para representar el mapa ya tenían su propio formato binario y se almacenaban en un bloque separado. Gradualmente, creamos formatos binarios separados para acelerar la búsqueda de direcciones y búsquedas de texto. Solo quedaba información en la base de datos, que se usaba para mostrar tarjetas de objetos, así como para enlaces de algunos objetos con otros.
Simplifica el trabajo
¿Cómo puede simplificar el trabajo con datos? Reciba todos los datos necesarios para dibujar una tarjeta de una vez por el identificador del objeto. Dado que la
versión en línea ya recibe todos los datos de la
API para una solicitud en
formato JSON , al mismo tiempo puede combinar los formatos utilizados por todos nuestros productos.
Tanto los json para mostrar tarjetas como las comunicaciones deben recibirse para un número limitado de objetos, desde el poder de varias decenas a la vez. Pero hay escenarios en los que los atributos individuales deben obtenerse a la vez para muestras grandes, hasta cientos de miles. Es más lógico separar tales atributos en una entidad separada con un formato de almacenamiento separado: propiedades. Las propiedades pueden ser de tipo y almacenarse de manera más eficiente en formato binario.
Un enfoque ingenuo para almacenar json es usar una base de datos clave-valor. Tomemos a Moscú como ejemplo, como el mayor de nuestros proyectos. Incluso en la forma más simple posible: para cada objeto que se almacena json, 8 bytes de identificador y un carácter delimitador, el directorio tomará 1.9 GiB. El tamaño resultante es casi seis veces mayor que la opción descrita anteriormente, y esto aún no tiene vínculos ni propiedades.
Inflamos deliberadamente objetos llenándolos con información sobre todo lo que podría ser necesario para mostrar sus tarjetas, pero aún debe almacenar nombres de campos, comillas, comas y corchetes.
Comprimir datos
La normalización no es la única forma de eliminar la redundancia. La segunda forma popular es la compresión. El archivo lzma de nuestro archivo increíblemente grueso toma solo 55 MiB.
Por supuesto, no podemos usar este formato directamente, porque para acceder a un objeto arbitrario necesitamos desempaquetar todos los datos almacenados anteriormente, y los archivos lzma no se desempaquetan muy rápidamente.
¿Cómo podemos obtener acceso aleatorio rápido, por un lado, y por otro lado, al comprimir los datos, reducir el tamaño del espacio requerido? La respuesta es usar paginación.
Ahora que los datos están paginados, podemos comprimir cada uno individualmente. Para acceder a un lugar arbitrario, necesitamos descomprimir y escanear la página, pero esto es mucho más rápido que desempacar y escanear todo el archivo.
En este formato, todos los datos se almacenan: json'y, relaciones y propiedades. Queda por asociar estos datos con los identificadores de los objetos. Para cada identificador, necesitamos almacenar uno o más pares
<número de almacenamiento, número de datos en el almacenamiento> .
Todos los números de serie, desplazamientos y tamaños se almacenan en un formato comprimido similar al
UTF-8 , donde los valores pequeños ocupan solo un byte. Esto nos permite reducir el tamaño de los enlaces simplemente ordenando el contenido de los repositorios binarios para reducir la frecuencia de ocurrencia.
Algunas propiedades tienen muchos valores de frecuencia y, por lo tanto, la clasificación proporciona una gran ganancia de tamaño. Por otro lado, debido a ello, el número de serie de los datos no puede coincidir para todos los almacenamientos.
Además, lejos de todos los objetos tienen datos en todos los almacenamientos y, por lo tanto, almacenar números de almacenamiento es más eficiente que hacer referencia a objetos vacíos.
Acelerar la recuperación de datos
El formato descrito tiene un problema. Para encontrar el número del objeto que almacena los índices para el identificador especificado, necesitamos ejecutar una búsqueda binaria dentro de los datos del primer objeto. Para hacer esto, necesita cargar 10.9 MiB en la memoria o hacer 21 lecturas adicionales. Ambas soluciones no son adecuadas para nosotros y, por lo tanto, reducimos el número de lecturas almacenando datos en un árbol.
Agrupamos datos en 32 objetos, y en los niveles intermedios almacenamos 128 de los primeros identificadores de nodos anidados. Agregamos tres niveles del árbol y redujimos el número de lecturas adicionales a cuatro (pero, de hecho, teniendo en cuenta el almacenamiento en caché de los nodos del árbol previamente leídos, incluso a 1-3). Precio: un poco menos de 400 KiB.
En esta etapa, somos bastante eficientes para almacenar relaciones y propiedades, pero Json ocupa mucho espacio. Esto es entendible. Cuanto mayor sea el tamaño de la página, más objetos llegarán allí y mejor será el algoritmo de compresión capaz de determinar qué información es redundante. Pero, por otro lado, cuanto más trabajo tenemos que hacer para leer un solo objeto. Json son objetos bastante grandes y, por lo tanto, hay muy pocos en una página. Por lo tanto, debe ayudar al algoritmo a hacer su trabajo mejor.
Romper json en partes
En primer lugar, muchos objetos tienen esquemas de datos coincidentes; solo difieren los valores de los atributos. En segundo lugar, muchos valores de atributos son iguales incluso para objetos con diferentes esquemas. Separaremos los esquemas y los valores de los atributos en almacenamientos separados, y almacenaremos json en la forma: un enlace a un esquema + enlaces a valores de atributos.
En nuestro esquema de datos, el número de nombres de atributos es limitado. Entonces podemos ponerlos en un archivo separado y almacenar el número en su lugar. También haremos algunos cambios más, teniendo en cuenta que los json siempre son objetos.
Sí, esencialmente exprimimos nuestros datos nosotros mismos, reduciendo el alcance para que el algoritmo funcione. Pero, por otro lado, ralentizamos bastante el acceso a los datos, y el algoritmo todavía ayuda, comprimiendo valores similares almacenados cerca.
Establecimos el tamaño de la página en 1 KiB y resulta que mientras optimizamos el formato para que, por un lado, la lectura no fuera muy lenta y, por otro, los datos se empaquetaran lo mejor posible, nosotros ... ya pasamos por alto las "tablas optimizadas" tanto en tamaño como en tamaño. para facilitar su uso. ¡Pero no por nada que todo esto fue! La ganancia máxima debe ser de la compresión de los valores de atributos, propiedades y esquemas. Incitamos a zlib y verificamos que, en el contexto del resto del trabajo, leer datos de la base de datos lleva poco tiempo. Satisfechos con el resultado, cambiamos a otras tareas.
Deshazte de lo innecesario
Comenzamos a reducir buscando datos de los que pueda deshacerse. Resulta que durante la existencia del formato, hemos aprendido a prescindir de la conexión más grande. ¡Esto es el 10% del tamaño!
El código para estos datos todavía estaba vinculado, pero los cambios necesarios son bastante triviales. Pero las aplicaciones ya lanzadas no se pueden cambiar fácilmente. Nos esforzamos por mantener el mayor tiempo posible no solo hacia atrás, sino también la compatibilidad directa. Y si el primero es familiar para todos, entonces muchos felizmente no pensarán en el segundo. Nos vemos obligados a admitirlo debido a la larga cola de usuarios que, por diversas razones, han desactivado las actualizaciones automáticas y no tienen prisa por cambiar a una nueva versión de la aplicación.
Distribución de usuarios por versiónEn la parte superior está la distribución de usuarios por las últimas versiones de la aplicación de Android. La parte inferior es iOS.
Es fácil notar que los usuarios de dispositivos iOS se actualizan mucho más fácilmente, pero incluso entre ellos hay muchos usuarios de versiones anteriores.
También estamos lanzando nuevos datos para la versión congelada para Windows Phone. Y aunque los usuarios de WP8 representan solo una pequeña fracción de nuestra audiencia, en números absolutos esto es casi 200,000 por mes.
Hace tiempo que tenemos un mecanismo que nos permite producir varios formatos de datos y determina automáticamente qué versiones deberían obtener qué. La oportunidad es buena, pero aún necesita aprender a descargar estos formatos. La primera gran tarea fue implementar un servicio que reciba todos los datos y filtre el nuevo para el antiguo formato de base de datos y el viejo para el nuevo.
Una buena ventaja del trabajo realizado es la reducción del tamaño de las actualizaciones mensuales, ya que la conexión remota ha cambiado mucho de mes a mes, lo que aumenta el tamaño de las diferencias.
Si observa los datos restantes, en total puede exprimir el mismo 10%, sin embargo, el precio será incomparablemente más alto. Hasta ahora hemos decidido no tocar.
Optimizar el formato de almacenamiento actual
Como se escribió anteriormente, creamos 1 páginas KiB y empacamos no todos los repositorios binarios.
Lo primero que hacemos es tratar de empaquetar también páginas con enlaces, y verificar que la diferencia en la velocidad de recepción de datos esté en la región del error.
El siguiente elemento es elegir el tamaño de página óptimo. Cuanto mayor es el tamaño de la página, más eficientemente se comprimen los datos, pero más lento se obtienen los datos. Y si al aumentar el tamaño de la página el tiempo y los costos de memoria crecen linealmente, la ganancia se vuelve cada vez menos notable. Después de las pruebas, decidimos aumentar el tamaño a 8 KiB.
El efecto del tamaño de página en grandes seleccionesSi se espera que la ampliación de la página ralentice las selecciones pequeñas, entonces las grandes, de cientos de elementos, incluso se aceleran. Esto significa que, en el buen sentido, debe elegir diferentes tamaños de almacenamiento dependiendo de los casos de uso de los datos almacenados en ellos.
En total, ¡solo estos dos puntos pueden reducir la base en un 18%!
Cambiar el formato de compresión
zlib, por supuesto, es un clásico, pero
zstd proporciona una mayor velocidad de descompresión con una mayor relación de compresión. Además, zstd le permite primero construir un único diccionario para todos los datos disponibles, y luego guardarlo una vez y comprimirlo con todas las páginas. Por lo tanto, ralentizamos decentemente el proceso de creación de un archivo con una base de datos, pero exprimimos un 8% adicional.
Añadir porches
Manera fácil
La forma más fácil es hacer que cada entrada sea un objeto separado, indexarlos por separado (de acuerdo con estimaciones aproximadas + 10% del tamaño del índice) y almacenar por separado su geometría en los datos para dibujar el mapa.
Este método inflará la base en un total de 3%. En las etapas anteriores, ganamos más que suficiente para calmarnos y trabajar con las entradas de acuerdo con el esquema habitual, pero ... en el momento del inicio del trabajo, no estábamos seguros de esto, y el trabajo en un formato alternativo era en paralelo.
Evaluación detallada, para los interesados.Tratemos de evaluar el aumento en el tamaño del paquete con la base de datos para cada objeto:
8 bytes - identificador,
6 bytes: números de almacenamientos usados (datos + cinco propiedades; las propiedades se extraen de los datos principales y se almacenan en forma binaria, ya que a menudo se necesitan para una gran cantidad de objetos a la vez),
3 bytes - índice en el almacén de datos,
2 bytes: datos de desplazamiento del objeto,
5 bytes - valores de datos - 2 bytes por circuito, 3 bytes en promedio para la información del departamento (creemos que habrá muchos duplicados y los datos en sí se almacenan una vez),
6 bytes: coordenadas de datos de desplazamiento (otras propiedades tienen muchos valores duplicados y colapsarán),
8 bytes: valores de coordenadas.
Total 38 bytes por objeto. En el caso de Moscú, esto es 4.5 MiB por más de 124 mil entradas recolectadas.
Luego, necesitamos almacenar también la conexión entre la casa y las entradas, es de 2.5 bytes para cada edificio de apartamentos y 8 bytes para cada entrada. 1 más MiB.
Ahora consideramos cuánto tomará todo esto en el mapa.
Primero, debemos almacenar la geometría. Para las polilíneas, el primer punto siempre toma 8 bytes, y todos los siguientes se almacenan como diferencias de la precisión requerida. Aquí estamos satisfechos con la precisión de decímetros. La mayoría de las entradas consisten en dos puntos que no están muy lejos el uno del otro y, por lo tanto, se puede suponer que la geometría misma ocupará 10 bytes. Total 1.2 MiB.
También necesitamos asociar el identificador de entrada y el objeto con su geometría. Un índice es el mismo almacenamiento binario que todo lo demás, solo se almacenan el destino de comunicación (1 byte), el número de capa (1 byte) y el número de objeto (3 bytes). Más 8 bytes por identificador, así como un árbol de búsqueda rápida. Total otros 1.5 MiB.
Como se dijo al comienzo del artículo, queremos mostrar constantemente las entradas en el mapa, y la forma más fácil de hacerlo es descargar otra capa con puntos, pero ... también puede reutilizar la capa con geometrías, creando un nuevo
símbolo que mostrará la imagen que necesitamos en el último punto de la polilínea.
El 10% del índice de búsqueda es 5.9 MiB. Resumiendo todo, obtenemos 14.2 MiB, que es solo un poco más del 3%.
Opción actual
En lugar de indexar las entradas e inflar el índice de búsqueda, buscamos casas, pero adicionalmente marcamos las palabras de consulta y seleccionamos las direcciones (relevantes para buscar entradas en Kaliningrado), entradas y / o apartamentos. Por lo tanto, a la salida tenemos el identificador de la casa y los campos de texto escritos, por los cuales debemos encontrar la escalera que necesitamos.
NotaEste es un punto controvertido. Por un lado, nos permite reducir el tamaño de la base de datos y, por otro, impone restricciones en el formato de entrada: las entradas no estarán en muchas solicitudes que se procesarían correctamente mediante una búsqueda honesta.
Además, en lugar de descargar objetos individuales, incluimos toda la información sobre las entradas directamente en los datos del edificio.
Y finalmente, transferimos parte de las geometrías al directorio.
Vale la pena revelar esto último con más detalle.
En primer lugar, notamos que la mayoría de las entradas son dos puntos y tienen la misma longitud. Dichas entradas se pueden almacenar en forma de un punto + dirección, es decir. Ahorre 1 byte por entrada.
En segundo lugar, suponemos que la mayoría de las casas en las ciudades modernas son típicas, por lo tanto, los desplazamientos de los puntos de sus entradas en relación con el punto central de la casa coincidirán hasta un giro.
Ya tenemos los puntos centrales de los edificios.
¿Qué sucede si agregamos una nueva propiedad para el edificio, su "dirección" entera, y para cada entrada dos más, compensaciones enteras en decímetros a lo largo y perpendiculares a la línea de dirección? Teniendo en cuenta cómo almacenamos json con información, la geometría de entrada en promedio ocupará poco más de dos bytes.Una ventaja adicional es que, dado que la geometría está en el directorio, ya no necesitamos almacenar la correspondencia entre el identificador de entrada y el número de objeto en la capa del mapa.Menos: el código se ha vuelto más complicado. Anteriormente acabamos de decirle al mapa "mostrar tales y tales objetos", y ahora al mostrar las entradas extraemos estos datos de json y agregamos objetos dinámicos al mapa. Aquí no todo da mucho miedo. En el momento de mostrar las teclas de flecha de las entradas json, ya tenemos los objetos correspondientes, es decir, no es necesario ir a la base de datos adicionalmente. Con los puntos de entrada mostrados, todo es un poco peor: ahora tenemos que determinar en el fondo qué casas son visibles, extraer los datos de estas casas de la base de datos, desmontar json y, si hay entradas, crear objetos dinámicos para ellas.Como ya hemos escrito código adicional para mostrar las entradas a las entradas, nada nos impide comenzar a almacenar entradas de dos puntos en la organización en el directorio. La ganancia en este caso será pequeña, pero gratuita.¿Cuánto nos dio? 3% convertido en 0.5%. Podríamos haber hecho aún menos, pero dejamos identificadores en los datos (que están comprimidos bastante mal) para simplificar el procesamiento de mensajes de usuario sobre entradas inexactas.Resultado
Agregamos una gran cantidad de entradas, mientras redujimos el tamaño del archivo con los datos del mapa en un 0.5% y redujimos en un 26.6% el tamaño del archivo con los datos del directorio. Este último sigue siendo el más grande de nuestros archivos, pero es solo uno de los cuatro archivos "pesados", por lo que el cambio general resultó ser más modesto: 10.1%.Las entradas aún no están recogidas. El tamaño de las bases crecerá un poco con el tiempo (según las estimaciones actuales, el mismo Moscú aumentará en un 0,4%), pero en cualquier caso, el objetivo es liberar las entradas sin aumentar el tamaño, más de lo que se logró.Que sigue
Si hablamos de mejoras en los alimentos, vamos a apoyar las entradas y apartamentos en los consejos de búsqueda, así como en la búsqueda de los puntos de inicio y finalización de la búsqueda de direcciones. También pensamos en mostrar entradas importantes a los edificios (principalmente en centros comerciales) de la misma manera que los porches.En los planes técnicos, hay una verificación de varias ideas que pueden conducir a una mayor reducción en el tamaño del archivo con datos de referencia, y debe observar cuidadosamente otros archivos.Y, por supuesto, corregiremos los errores que tenemos hasta ahora.Un pensamiento más: use JSON sabiamente
De lo anterior, la conclusión sugiere que no se puede pensar demasiado en formatos binarios y solo usar JSON. Esto no es del todo cierto.
Esto funciona para nosotros, porque al mismo tiempo necesitamos recibir varias decenas de objetos de la fuerza. Además, utilizamos rapidjson, y es muy inteligente y consume poca memoria.También vale la pena restringir la transferencia de datos JSON de C ++ a UI, escritos en otro idioma.Primero, debes convertirlo en una cuerda.En segundo lugar, los analizadores disponibles en la parte de la interfaz de usuario volverán a montar esta línea y lo harán mucho más lento.Es mejor obtener todos los datos de JSON por su cuenta y lanzar interfaces simples adaptadas para mostrar elementos específicos en el lado de la interfaz de usuario.