El bienestar de la mayoría, supera al bienestar de la minoría. . . . O de uno solo. (Spock)

Technology, Java, Linux, FLOSS

Construyendo un Arbol B+ (B+Tree)

Deja un comentario Publicado por technobcn en 2012/08/19

B+ tree data structure diagram.

Introducción e historia:

Los Arboles B+ son una evolucion de los Arboles B, inventados en 1972 (Rudolf Bayer y Edward McCreight), son un tipo de estructura para mantener datos ordenados de modo eficiente O(log-n), esto significa que a medida que el volumen de datos crece, la eficiencia decrece aunque no de modo lineal. Por comparacion, en una tabla hash -o un array- el tiempo es O(1) -constante- independientemente del numero de registros, aunque su utilidad no es la misma que la de un arbol.

La principal diferencia con un Arbol B standard es que almacenan los valores en los nodos hoja y los nodos intermedios solo almacenan referencias a otros nodos (internos u hojas). Otra caracteristica es que se podría iterar sobre todos los nodos hojas de modo secuencial siguiendo los apuntadores, sin tener que recorrer los nodos internos desde la raiz.

Motivación:

Las implementaciones de Java (TreeMap, HashMap, etc) funcionan muy bien en memoria y valen para casi cualquier cosa (son muy genericas), pero el coste del todo terreno suele ser memoria y CPU; y cuando necesitas trabajar con muchos datos y una gran velocidad… la memoria se acaba y los recursos, por definicion, no son ilimitados.

Mi primer intento consistió en buscar alguna implementacion existente para almacenar en disco algo sencillo, claves/valores (long/long) con una velocidad relativamente buena, encontré una librería con buena pinta (JDBM3 -y sus versiones anteriores-), tambien probé varias bbdd SQL { H2-database, HSQLDB y MySQL }.

Por desgracia todas morian en el intento (y no fue por falta de configuración/tuning):

MySQL/InnoDB a penas llegaba a 3,5k inserts/segundo.
El rendimiento del H2 (embed) de 85k/s al superar el millon de registros caia en picado a 7k/s y el I/O wait moría casi en los 3millones.
JDBM3 iba degradandose poco a poco, 250k a 27k/s, 500k a 20k/s, 1millon a 12k/s.
El DB_File de Perl (BerkeleyDB), corria a unos 20k/s de modo bastante constante hasta los 3millones.

Resultó algo bastante frustrante al inicio. Era hora de buscar una solucion y mi objetivo eran los 5 millones a 100k/s.

Bitacora (2012):

El 10 de julio a las 19:56
* El preintento, pruebas de diferentes cosas… (mysql, h2, jdbm3).

El 22 de julio a las 13:37
* Inicio, empiezo a documentarme

El 28 de julio a las 20:38
* Primera implementacion (Arbol B standard sin valores, solo claves).

El 1 de agosto a las 21:44
* Primera prueba, 1millon de Inserts:
Random {
Linux=11seg (90k/s)
Win=77seg (12k/s)
}
Secuencial {
Linux=2seg (500k/s)
Win=7seg (142k/s)
}

El 2 de agosto a las 22:38
* Optimizaciones (Inserts Random, Linux):
1millon {
Sync cada 10k inserts=11s (90k/s)
Sync cada 1 segundo=4s (250k/s)
Sync cada 2 segundos=4s (250k/s)
}
5millones {
Sync cada 1 segundo=75s (67k/s)
Sync cada 2 segundos=63s (79k/s)
Sync cada 2 segundos+pool de buffers=48s (104k/s)
}

El 3 de agosto a la(s) 21:37
* Arbol B+ limitado, solo insert y get, con claves y valores, sin enlace entre nodos hoja.

El 4 de agosto a la(s) 3:30
* Optimizaciones (Inserts Random, Linux):
-5millones
-base: sync 2 segundos + pool de buffers
-extra: 2 caches (leaf/internal) 32k-elements, dynamic B-order (leaf/internal)
block 512 {
buf heap=55s (90k/s)
buf direct=55s (90k/s)
buf direct+mmap=44s (113k/s)
}
block 1024 {
buf heap=49s (102k/s)
buf direct=48s (104k/s)
buf direct+mmap=42s (119k/s)
}
block 1536 {
buf heap=49s (102k/s)
buf direct=48s (104k/s)
buf direct+mmap=43s (116k/s)
}
block 2048 {
buf heap=52s (96k/s)
buf direct=49s (102k/s)
buf direct+mmap=44s (113k/s)
}

El 5 de agosto a las 5:00
* Optimizaciones (Inserts Random, Linux):
-5millones
-base: sync 2 segundos + pool de buffers + dynamic B-order (leaf/internal)
-extra: 2 caches (leaf/internal) dynamic-bytes
block 512 {
buf heap=49s (102k/s)
buf direct=49s (102k/s)
buf direct+mmap=43s (116k/s)
}
block 2048 {
buf heap=48s (104k/s)
buf direct=49s (102k/s)
buf direct+mmap=43s (116k/s)
}

El 7 de agosto a la 1:47
* Dandole a la cabeza para implementar el delete…

El 9 de agosto a las 21:09
* Solucionado, ahora toca limpiar codigo :-)

El 12 de agosto a las 3:54
* Comparativa (H2 Database):
-5millones, inserts random (cache 256mb)=143s (35k/s)

El 14 de agosto a las 3:23
* Pruebas/Optimizaciones (Insert Random, Linux):
-5 millones,… caches (hash) indexados por tipos nativos (eliminacion de autoboxing)
weakreferences {
block 512=44s (113k/s)
block 4096=31s (161k/s)
}
strongreferences {
block 512=37s (133k/s)
block 4096=27s (182k/s)
}

El 16 de agosto a las 6:46
* Corrigiendo poltergeist… (IntHashMap)

El 19 de agosto a las 2:52
* Benchmark con el ultimo codigo (click para verlo en grande).

Benchmark B+Tree (claves aleatorias): Valores altos mejores. Operaciones por segundo (miles/s), inserts y removes, en funcion del tamaño de bloque (512, 1024,…) y numero de registros (millones) total. Actualizado el 19 de Agosto de 2012.

Benchmark B+Tree (claves secuenciales): Valores altos mejores. Operaciones por segundo (miles/s), inserts y removes, en funcion del tamaño de bloque (512, 1024,…) y numero de registros (millones) total. Actualizado el 19 de Agosto de 2012.

El 19 de agosto a las 21:37
* Ahora solo queda dejarlo reposar un poco por si se me ocurren algunas ideas, hacerle muchisimas pruebas, y pulirlo todo, a ver como funciona.

El 28 de agosto a las 23:26
* Despues de días de pruebas funcionales y estabilizacion de codigo se limpia el codigo, se desdobla en una clase abstracta y la implementacion en fichero y se añade una segunda implementacion en memoria. Se añaden los comentarios (javadoc) a todos los metodos que habia sin documentar. Se implementa el resto del Arbol B+ (enlace entre nodos hoja para acceso secuencial). Hay que hacer más pruebas funcionales.

El 31 de agosto a las 1:29
* Se cambian las funciones recursivas de insercion y borrado por versiones iterativas.

El 2 de septiembre a las 23:42
* Se cambia la funcion recursiva por la iterativa del toString del arbol, se mejoran las funciones de insercion en nodos y se añaden los metodos de busqueda de claves aproximadas (floorKey, ceilingKey, lowerKey, higherKey).

El 22 de septiembre a las 22:39
* El codigo ya esta.

El 4 de noviembre a las 12:45
* Tenia esto un poco olvidado, ya puede descargarse de GitHub

El 18 de Diciembre a la 1:11
* He renombrado el proyecto en GitHub: KVStore

El 22 de Diciembre a las 23:48
* Para ser justos, aunque mi objetivo eran 5millones a 100k/s y pese a que lo «conseguí»; y lo pongo entre comillas pq hay que matizar algunas cosas:
– Para conseguir ese rendimiento hay que poner un gran cache y «commitear» poco, cierto que los otros motores por más que lo intenté no consegui que dieran esa velocidad en la misma maquina (siempre me quedará la duda si era posible tocar algo y conseguirlo).
– El KVStore es rapido pq es sencillo y no tiene las funcionalidades de otros motores, principio de KiSS 100%, todo es por codigo, no hay SQL, no permite (en el formado disco) claves o valores de longitud varible, lo bueno es que eso le da velocidad, elimina la fragmentacion y la necesidad de compactar ya que reutiliza todos los bloques (algo que con Oracle y similares siempre me ha dado mucho dolor de cabeza), tampoco tiene sistemas implicitos de redo/transacciones.
– Por tanto, si necesitas un sistema Key-Value (como un TreeMap) optimizado para la velocidad y poco uso de memoria, puedes usar el KVStore en memoria (BplusTreeMemory), si ademas de velocidad el volumen de datos es mas que la memoria disponible o quieres persistencia, puedes usar el KVStore en disco (BplusTreeFile), que usara un sistema de cache para intentar maximizar su velocidad.
– Las desventajas evidentemente son… no es una base de datos con capacidades ACID, no tiene la idea de transaciones (rollback) y el tipo de datos que acepta son limitados.

El 26 de Diciembre a la 1:30
– Estoy trabajando en un sistema de Redo y recovery. Para evitar q ante un cierre catastrofico se pierdan datos.

Notas sobre las pruebas:

Todos los test sobre Linux han corrido en una maquina virtual Ubuntu 12.04.1 (32bits), mono-cpu con 512MB de RAM, la maquina fisica es un portatil con Ubuntu 10.04.4 (64bits) con procesador Intel Core i7-2630QM, 2.00GHz (quad-core) y 8GB de RAM, 2 discos en Raid1 (Seagate 500gb / 5400rpm, 2.5″, modelo ST9500325AS).

hdparm -tT /dev/sda

Timing cached reads: 7128.71 MB/sec
Timing buffered disk reads: 39.85 MB/sec

Para la ejecucion de los test se hacia un drop de buffer/caches:

sysctl -w vm.drop_caches=3 # drop de caches del S.O.

Y la JVM corria con estos parametros:

java -verbose:gc -XX:+PrintGCDetails -Xmx384m -Xms384m -cp classes/ Test

Parametros de sysctl (caches de escritura):
vm.dirty_writeback_centisecs=100
vm.dirty_expire_centisecs=200
vm.dirty_background_ratio=3
vm.dirty_ratio=5

Documentacion y Referencias:

Arboles B, B+, B*
http://www.monografias.com/trabajos32/arboles-multicaminos/arboles-multicaminos.shtml

Implementing Deletion in B+Tree
http://infolab.stanford.edu/~hyunjung/cs346/jannink.pdf

Open Data Structures – Java
http://opendatastructures.org/ods-java/

The B-tree is the classic disk-based data structure for indexing records
http://www.mec.ac.in/resources/notes/notes/ds/bplus.htm

B+tree and its Algorithm
http://es.scribd.com/doc/6792917/BTree

Indices y Ordenamiento
http://es.scribd.com/doc/37187909/Indices-B-Tree-OE-Hash

Estructuras de datos
http://subversion.assembla.com/svn/romario2008/LBEUFDB06R.pdf

Estructuras de datos (hash)
http://subversion.assembla.com/svn/romario2008/clase14-15.pdf

Indexamiento Multinivel y B-Trees
http://ict.udlap.mx/people/carlos/is215/ir07.html

B-Trees: Balanced Tree Data Structures
http://www.bluerwhite.org/btree/

B-tree and UB-tree
http://www.scholarpedia.org/article/B-tree_and_UB-tree