Bikey

TL;DR: en este post os presento Bikey una librería de colecciones de Java para crear Maps y Sets cuyos elementos tienen dos claves, consumiendo desde un 70%-85% a un 99% menos de memoria que con estructuras de datos habituales. Es Open Source, publicada en https://github.com/jerolba/bikey y está disponible en Maven Central.

En dos de mis últimos artículos hablando sobre HashMaps planteaba los problemas que hay cuando gestionamos información referenciada con una clave formada por dos valores: Map<Pair<K1, K2>, V>. Si analizamos las opciones disponibles vemos que el consumo por unidad de información es relativamente elevada.

¿Por qué se consume tanta memoria si el 60% de la información está repetida?.

¿Hay alguna librería que implemente mapas y sets con clave compuesta de forma eficiente? Yo no la he encontrado.

Requisitos

Las librerías de colecciones que te puedes encontrar en Internet no suelen implementar esta estructura de datos, y las que lo implementan, ninguna presta especial atención al consumo de memoria.

¿Qué debería cumplir la librería que estoy buscando?

• Aunque con una cardinalidad acotada, debe admitir un número variable de valores dentro de cada elementos de la clave. Debe admitir objetos cuya clave esté basada en valores discretos (nombres, códigos, enteros, fechas, etc), en rango y valores no conocidos a priori. Por su naturaleza, dejaré fuera valores continuos (es decir, doubles).
• Debe mantener las propiedades de un HashMap, con coste O(1) en inserción y consulta.
• El rendimiento a la hora de añadir o consultar un elemento debe ser del mismo orden de magnitud que las soluciones ya exploradas.
• El límite del número de elementos es la memoria disponible.
• El coste en memoria de añadir nuevos elementos debería ser decreciente con el número de elementos, tendiendo a 4 bytes (el coste de guardar el puntero al valor asociado).

Estado del arte

Las soluciones que he encontrado se basan en alguna de estas tres opciones:

• Un mapa anidado: Map<R, Map<C, V>>, mecanismo que usa la implementación HashBasedTable de Guava.
• Un mapa con una tupla de elementos: Map<Tuple, V>, que es la propuesta de Commons Collection en su MultiKeyMap o de CQEngine en CompoundIndex. Tienen la flexibilidad de admitir más de dos elementos en la clave compuesta, pero no es parte de los requisitos, ya que he acotado a tuplas de dos elementos (también conocidos como Tuple2 o Pair).
• Una matriz bidimensional: (Object[][]), usada en la versión ArrayTable de Guava, pero que te obliga a configurar su tamaño y posibles valores de las claves desde el constructor, y no permite hacerlo crecer en ninguna de las dos dimensiones.

Las dos primeras opciones consumen demasiada memoria: de media 40 bytes por registro. Muy lejos de esos 4 bytes mínimos teóricos del puntero al valor asociado, ya que desperdicia recursos en guardar información redundante (los elementos de la clave).

En el caso de CQEngine, es incluso peor porque el consumo de memoria es casi un orden de magnitud mayor. CQEngine es una herramienta muy potente con índices y queries complejas, pero no es eficiente en memoria.

La solución ArrayTable de Guava con una matriz bidimensional es la que mejor resuelve el problema de memoria, pero sólo si tienes un alto porcentaje de la matriz rellena (fill rate): si sólo tienes presente 1/4 de los elementos posibles, estará desperdiciando el 75% de los registros de la matriz.

Además, como ya he mencionado, en la matriz necesita configurar sus elementos en el constructor, restando flexibilidad ya que en tu lógica de negocio muchas veces no sabes qué entidades van a ser usadas.

En la matriz, dados n posibles valores de la primera parte de la clave, y dados m posibles valores de la segunda parte de la clave, añadir un nuevo valor a n haría aumentar el tamaño total de la matriz en m.

Por tanto, el consumo de memoria en la matriz es de orden n * m, mientras que en los otros dos casos el consumo es de orden lineal, y depende sólo del número de elementos presentes en el mapa.

Lo ideal sería una estructura de datos que consuma pocos bytes por registro adicional, pero que no crezca con el producto cartesiano de sus claves.

Set

En el caso de querer representar un conjunto de claves, se pone peor el tema: no he encontrado nada que nos ayude a implementar de forma eficiente un Set<Tuple<R, C>>, aparte de usar un HashSet<Tuple<R,C>> o un HashMap<R, HashSet<C>>.

Bikey

Después de mucho buscar en distintas librerías, leer papers, pensar y probar, di con la forma de implementar la funcionalidad cumpliendo todos esos requisitos!

Aunque podéis encontrar el código fuente publicado en GitHub y ver cómo está implementado, en el próximo post contaré los detalles. No esperéis ciencia espacial, ni nada tan complicado como F14, la última y más rápida implementación de Hash Table de la gente de Facebook.

Existen dos implementaciones del mapa:

• TableBikeyMap: optimizada para el consumo de memoria, y con un rendimiento similar a las implementaciones que ya hemos visto.
• MatrixBikeyMap: optimiza el rendimiento, pero con el inconveniente de consumir más memoria con fill rates bajos. Incumple mi criterio de no crecer en consumo con el número de claves (n * m) porque se comporta como una matriz (sin llegar a serlo), pero tiene sus casos de uso donde puede ser rentable.

Ambas implementan el mismo interface BikeyMap<R, C, V>, por lo que son intercambiables según varíen tus necesidades.

Del Set sólo hay una implementación, TableBikeySet, que se caracteriza por tener un consumo de memoria ridículo comparado con las versiones basadas en HashSet.

Ejemplos de uso

La librería está disponible en Maven Central y la podéis usar añadiendo esta dependencia a vuestro pom.xml:

<dependency>
  <groupId>com.jerolba</groupId>
  <artifactId>bikey</artifactId>
  <version>0.9.0</version>
</dependency>

Aunque el código fuente está publicado en GitHub en https://github.com/jerolba/bikey con licencia Apache 2.0, podéis encontrar el JavaDoc publicado aquí.

Si miráis el API, veréis que es “idéntico” al que definen Map y Set, sólo que donde se hace referencia a la clave con un parámetro, pasan a ser dos. Como he adoptado la metáfora de que el mapa es como una tabla bidimensional, el primer valor de la clave es la fila y el segundo es la columna.

Para simplificar el ejemplo voy a utilizar String para referencias las claves, pero en código real podrían ser objetos de tipo Product y Store, y sus identificadores ser los utilizados en los métodos hashCode y equals.

También para simplificar, en vez de guardar como valor un objeto con varios atributos sobre cada producto/tienda (stock, ventas, stockout, fecha de disponibilidad, etc), he usado sólo su stock.

//Dado un stock de algunos productos y tiendas
//BikeyMap<Product, Store, Stock> stock = new TableBikeyMap<>();
BikeyMap<String, String, Integer> stock = new TableBikeyMap<>();
stock.put("shirt-ref-123", "store-76", 10);
stock.put("pants-ref-456", "store-12", 24);
...
stock.put("tie-ref-789", "store-23", 2);

//Obtener el stock de un producto/tienda
Integer inStock = stock.get("shirt-ref-1234", "store-45");

//Stock total en store-123
stock.entrySet().stream()
     .filter(entry -> entry.getColumn().equals("store-123"))
     .mapToInt(entry -> entry.getValue())
     .sum();

//Stock total de pants-ref-457
stock.entrySet().stream()
     .filter(entry -> entry.getRow().equals("pants-ref-457"))
     .mapToInt(entry -> entry.getValue())
     .sum();

//Todos los productos existentes
Set<String> products = stock.rowKeySet();

//Todas las tiendas existentes
Set<String> stores = stock.columnKeySet();

//Si contiene un producto/tienda?
if (stock.containsKey("tie-ref-789", "store-23")) {
    ....
}

//Obtener todos los productos/tiendas presentes en el mapa
BikeySet<String, String> productStores = map.bikeySet();

//BikeySet<R, C> implementa también Set<Bikey<R, C>>
Set<Bikey<String, String>> productStoresSet = map.bikeySet();

//Obtener todos los producto/tiendas con stock
BikeySet<String, String> withStock = stock.entrySet().stream()
    .filter(entry -> entry.getValue() > 0)
    .map(BikeyEntry::getKey)
    .collect(BikeyCollectors.toSet());

//Hacer algo con cada elementos del mapa
stock.forEach((product, store, units) -> {
    System.out.println("Product " + product + " has " + units + " in store " + store);
});

Las implementaciones TableBikeyMap y MatrixBikeyMap son intercambiables y puedes usar una u otra en función de tus necesidades. Yo recomiendo usar por defecto la de TableBikeyMap.

Del mapa podemos extraer el conjunto de todas sus claves llamando al método bikeySet, pero también podemos construir y usar un BikeySet directamente.

Si hablamos de películas de Marvel y sus protagonistas:

BikeySet<String, String> avengerFilms = new TableBikeySet<>();
avengerFilms.add("Hulk", "The Avengers");
avengerFilms.add("Iron Man", "The Avengers");
avengerFilms.add("Thor", "Avengers: Age of Ultron");
avengerFilms.add("Thor", "Thor: Ragnarok");
avengerFilms.add("Captain America", "Avengers: Infinity War");
....

if (avengerFilms.contains("Iron Man", "Black Panther")) {
    ....
}

//Películas en el Set
Set<String> filmsInSet = avengerFilms.columnKeySet();

//Vengadores en el Set
Set<String> avengersInSet = avengerFilms.rowKeySet();

//Películas con Iron Man
List<String> ironManFilms = avengerFilms.stream()
    .filter(entry -> entry.getRow().equals("Iron Man"))
    .map(Bikey::getColumn)
    .collect(toList());

//Llamar a un BiFunction por cada elemento
bikeySet.forEach(this::doSomething);

public void doSomething(String avenger, String film) {
  ....
}

Análisis de rendimiento

No os estaría dando la tabarra si los números no fueran buenos. No estamos hablando de cierto porcentaje de mejora, sino de ser X veces más eficiente en consumo de memoria con un rendimiento similar.

Sin entrar en mucha profundidad, siguiendo el ejemplo de productos y tiendas que he usado en mi anterior post, y con la misma metodología de tests, tenemos estos resultados:

Memoria: Mapa

Para un dominio de 10.000 productos y 1.000 tiendas, si añadimos de forma aleatoria elementos en el mapa, la evolución del consumo de memoria es:

Si nos fijamos en la versión de TableBikeyMap, en un mapa donde sólo estén presentes la cuarta parte de las posibles combinaciones de valores, el consumo de memoria es casi 4 veces menor, mientras que si llegamos a la mitad es 5 veces menor. En el caso de completar el 100% de las combinaciones, el consumo es 7 veces menor.

En la versión MatrixBikeyMap, el consumo de memoria es constante. Hasta que no alcanza un 10% de fill rate no compensa en consumo sobre las versiones clásicas, y el 70% sobre la versión TableBikeyMap.

¿Qué pasa cuando el fill rate es muy bajo? o lo que es lo mismo, ¿Qué pasa cuando el número de posibles valores de las claves es alto pero el número de combinaciones presentes es bajo? Si en la gráfica anterior hacemos zoom en la parte inferior izquierda veremos qué pasa cuando se han insertado pocos elementos, pero cada valor distinto de la clave ya ha sido usado al menos una vez:

Con pocos elementos el consumo de memoria es similar, pero las gráficas se separan al llegar al 5% de fill rate. Mientras que la pendiente de TableBikeyMap baja, las otras dos siguen igual.

Como ya he comentado, MatrixBikeyMap es una recta plana que no cambia por comportarse como una matriz (sin serlo).

Memoria: Set

Para el mismo dominio, si añadimos de forma aleatoria esos 10 millones de elementos en el Set, la evolución del consumo de memoria es:

En este caso pasamos a consumir entre un 1% y un 2% de memoria.

En todos los benchmarks, en el caso de usar Tuple he implementado una función hash que no crea colisiones evitando un consumo de memoria aún mayor. Además no estoy teniendo en cuenta el consumo propio de las instancias del Tuple de dos elementos o Pair.

Rendimiento en indexación: Mapa

Siguiendo la misma metodología que usé en el anterior post, el tiempo que tarda en indexar colecciones de distintos tamaños es:

Una de las principales preocupaciones al implementar la librería era que al final la complejidad añadida penalizara el rendimiento. No sólo se ha mantenido en el mismo orden de magnitud, sino que lo iguala o incluso mejora notablemente en el caso de MatrixBikeyMap.

Rendimiento en acceso: Mapa

Dado un mapa de cierto tamaño, ¿cuánto se tarda en acceder a todos sus elementos de forma aleatoria?

Otra vez vuelve a estar en un rendimiento similar. Además la versión MatrixBikeyMap es el doble de rápido en la mayoría de las ocasiones.

Rendimiento en escritura: Set

El tiempo empleado en crear un Set que contenga 10.000 productos y 1.000 tiendas evoluciona de esta forma:

El tiempo necesario es entre 2 y 3 veces menor en TableBikeySet por tener que crear y gestionar menos objetos en memoria al basarse en el uso de un BitSet.

Rendimiento en lectura: Set

Dado un Set que contiene 10.000 productos y 1.000 tiendas, ¿cuánto tarda en consultar si existe cada elementos de forma aleatoria?

En este caso mi propuesta es un 20% más lenta que la de HashSet<Tuple>, aunque sigue estando dentro del mismo orden de magnitud.

Conclusión

No sé si es que no he sabido buscarlo, o es una estructura de datos poco usada y con poco interés, pero me ha sorprendido no encontrar nada (ni a nivel de librerías ni de papers) que hable de cómo implementar en memoria un simple índice compuesto de dos valores.

Como en anteriores ocasiones, empecé buscando una librería que me resolviera una necesidad real. Al no encontrarla investigué sobre el tema y acabé implementando una solución que me lo resolviera, aunque el fin no era construir una librería.

Por el camino he conocido estructuras de datos muy interesantes que no me enseñaron en su momento. Imitando el API de Map y Set he aprendido mucho sobre el API de colecciones de Java (muy recomendable construir al menos una vez algo que implemente Collection y un Iterator).

En un próximo post os contaré los detalles de la implementación y las dos idea básicas sobre las que está construida.

Esta librería me permite, cambiando de implementación del mapa de una forma transparente, bajar el tamaño de las máquinas que utilizamos actualmente en Nextail en la ejecución de ciertos procesos pesados, reduciendo además de la factura de AWS, la huella ecológica.

Como ya he dicho, la librería tiene licencia Open Source y cualquier comentario, fix o contribución será bienvenida.