Apache Accumulo

Accumulo es una Base de Datos NoSQL que esta basada en la definición de Big Table de Google, es una de las 3 Bases de Datos más populares abajo de Apache HBase y de Apache Cassandra, siendo la primera Base de Datos NoSQL en el mercado.

Data Model

La forma de almacenamiento de Apache Accumulo es de la forma key-value, como se muestra a continuación.

Y aunque es almacenado de una forma key-value no solo se limita a esta estructura, ya que la llave esta compuesta de los siguientes componentes, donde la key se compone de un rowID, Column y un Timestamp como se muestra a continuación.

Pero si ustedes creen que esto es todo, déjenme decirles que no es así, ya que Column cuenta con otras tres características más las cuales son Family, Qualifier y Visibility, si alguna vez han escuchado que a las Bases de Datos NoSQL les llaman Bases de Datos no estructuradas, esta es la razón de que las llamen así.

Pero bueno, por que tiene esta estructura nuestra Tabla, muy sencillo, Apache Accumulo, basandonos en nuestra segunda imagen Apache Accumulo provee una forma de ordenación de los elementos de manera lexicográfica en orden ascendente, si que los ordena dándole el siguiente orden de prioridad a nuestra información, Row ID y si un elemento es igual el siguiente elemento de discriminación para la ordenación sería el la Column y si esta es igual los discriminará por el Timestamp garantizando que toda nuestra información esta ordenada y tener un acceso más rápido a la información, los componentes del par key-value son guardados como un array de bytes lo que implica que la escritura y lectura sea mucho más eficiente a excepción del Timestamp el cuál se almacena como un tipo de dato Long para que podamos ordenarlo de forma descendente cuando Accumulo toma el Timestamp como forma de ordenación.

Las tablas consisten en conjuntos de información de la forma key-value ordenados.

Arquitectura

Una instancia de Accumulo incluye varios TabletServers,Un proceso llamado Garbage Collector, un Master y varios Clientes. 

• Master: Es responsable de detectar y responde al fallo de algún TabletServer. También es encargado de balancear las cargas entre los TabletServers asignando los Tablets de forma cuidadosa e indicando al TableServer que quite de la memoria RAM Tablets cuando sea necesario, también tiene la responsabilidad de checar que que todos los Tablets están asignados a un TableServer y así mismo es el encargado de manipular las peticiones de un cliente de Creación, Alteración o Borrado.
  El Master es encargado del inicio del clúster, como la detención del mismo de una manera segura y por si fuera poco es el encargado de realizar las replicaciones en caso de que un TabletServer falle por medio de write-ahead logs (Es una técnica)
  
  Al igual que en Hadoop Accumulo te provee la High Availability no de manera natural, si no dejándonos tener más de un Master que estarán como Backups cuando el Master principal caiga.
• TabletServers: Este componente es encargado de almacenar algunos de los Tablets que se generan por cada Tabla, pero el trabajo de un TabletServer va más aún allá de solo el almacenamiento de Tablets, ya que también puede recibir peticiones de escritura desde los clientes persistiendo las escrituras por medio de write-ahead log, ordenando esos nuevos pares key-values en su memoria y de forma periódica liberando la información que ya esta ordenada en nuevas filas en HDFS, y también siendo obvio, puede realizar operaciones de lectura sobre su información  
• Garbage Collector: Los procesos de Accumulo comparte información almacenada en HDFS, de manera periódica checa si hay filas que no se necesiten más por los procesos de Accumulo y los elimina, múltiples instancias de garbage collector pueden ejecutarse al mismo tiempo esto se realiza para proveer un soporte del tipo hot-standby (es un método redundante en el que un sistema o aplicación corre simultáneamente con un proceso primario idéntico al original.  En caso de falla de el proceso principal el hot-standby inmediatamente toma como proceso principal el otro proceso idéntico al original remplazando el primero que ahora se encuentra caído mientras todo esto sucede la información es replicada al nuevo sistema en tiempo real) Ellos tienen la facilidad de realizar la elección del líder entre todas las instancias de los garbage collector para elegir solo una instancia activa y dejar las demás en standby, la idea de este componente de Accumulo podemos creer que es la misma del Garbage Collector de la JVM.
• Tracer: El proceso Tracer soporta la API timing que es de forma distribuida 
• Monitor: Es una aplicación Web que nos provee de mucho información acerca del estado de la instancia del clúster de Accumulo, muestra gráficas y tablas que contienen información acerca de las tasas de lectura y escritura  
• Cliente: Accumulo incluye un cliente que se puede ligar con cada aplicación que creemos. El cliente contiene la lógica para encontrar el servidor que maneja un Tablet en particular y la facilidad de comunicarse con el TabletServer para escribir y recibir la información en forma de key-value.

 Replicación

La replicación es una característica para garantizarnos la Tolerancia a Particiones, como ya podrán haberse dado cuenta Accumulo es una Base de Datos NoSQL del tipo CP (Consistencia y Tolerancia a Particiones), por lo cuál no nos garantiza la Disponibilidad, pero el nos provee un mecanismo para cumplir la alta disponibilidad dejando tener varios maestros en standby y uno activo.

Manejo de la Información

Como ya les mencione anteriormente Accumulo trabaja con tablas y las tablas se dividen en subconjuntos de información del tipo key-value llamado Tablets los cuales se generan a partir de particionar las tablas por Row ID, por lo que todas las columnas y valores por un row en particular están en el mismo Tablet. El maestro es encargado de asignar Tablet a un TabletServer uno a la vez, esto hace que las transacciones row-level se realicen de una forma más sencilla sin tantas complicaciones. Los TableServer como clientes pueden escribir y hacer queries sobre la información y como máquinas pueden ser removidas, perdidas o agradas al clúster de tal manera que el Maestro se encarga de migrar Tables a las nuevas máquinas o de las máquinas perdidas a otras de tal manera que se mantengan disponibles los Tablets y que la ingesta y las peticiones de carga se mantengan balanceadas en el clúster de Accumulo, este proceso podría ejemplificarse con la siguiente imagen.

Tablet Service

Los TabletService si se quieren ver comparándolo con  un clúster de Hadoop, podría decirse que fungen con la misma tarea que los datanodes, cuando una petición de escritura llega a alguno de los TabletService esta operación es escrita en el sistema write-ahead log y después se realizará la inserción en una estructura del tipo sorted data structure que se encuentra en la memoria RAM llamada MemTable. Y siempre trabajar con la memoria RAM es algo riesgoso, pero cuando la memoria alcanza cierto tamaño, el TabletServer en cuestión empieza a escribir los pares ordenados key-value en una fila de HDFS llamada Relative Key File (RFile) que es un tipo de archivo del tipo Indexed Sequential Access Method (ISAM).

Compresión

Para poder manejar el número de filas por Tablet, constantemente el TabletServer realiza procesos de compresión que le pertenecen a un Tablet, como vimos en el apartado anterior se crea un RFile por información que ya no aguante la RAM, entonces puede haber n RFiles por Tablet, y aquí es donde se realizan los procesos de compresión, más que un proceso de compresión es un proceso de unión, ya que todos los RFiles que haya correspondientes a un Tablet los unirá en un solo RFile, así que en este proceso tenemos n+1 archivos, que son los n RFiles y el RFile total, pero gracias al Garbage Collector los n RFiles serán eliminados solo persistiendo el RFile total ya que a hadoop le cuesta más trabajo lidiar con n archivos pequeños que con un archivo muy grande.

Y gracias a esto se tiene la oportunidad de eliminar permanentemente los pareces key-value que se realiza en una operación de borrado.

Splitting

Cuando una tabla es creada por default se crea un Tablet por row ID, pero aunque a hadoop le cuesta menos trabajo manipular archivos grandes a archivos pequeños, pero como un Tablet es como un bloque de información, si es muy grande en tamaño es obvio que al nodo en este caso el TabletServer le costará más recursos que si el archivo fuera más pequeño, por eso es que el TabletServer cuando cree que el archivo es muy grande, divide ese Tablet en dos Tablets, obviamente uno de esos dos Tablets se migrara a otro TabletServer esto se realiza por que como anteriormente comentamos el clúster de acumulo se preocupa por mantenerse balanceado en todo momento de su vida. Entonces conforme los Tablets sigan creciendo estos se irán particionando y moviéndome entre los TabletServer del clúster, la decisión de como ir realizando estas particiones es tomada de forma automática por el tamaño de los archivos RFiles.

Fault Tolerance

Si un TabletServer falla, el Master lo detecta automáticamente y automáticamente reasigna los Tablets correspondientes al servidor caído a otros servidores para que los manejen.   

Cualquier par del tipo key-value que estuviera en memoria en el momento del fallo del TabletServer es automáticamente replicado desde el Write-Ahead Log(WAL) para prevenir cualquier tipo de perdida de información.

TabletServers escriben sus propios WALs directamente en HDFS por lo que los logs están disponibles para todos los TabletsServers para la recuperación de la información. Para hacer el proceso de recuperación un proceso eficiente, las actualizaciones sobre un log son agrupadas por Tablet.

TabletServers pueden aplicar rápidamente 

Las fallas en los TabletsServers pueden ser notadas en la página de monitoreo del Maestro en su Web Page.

Como podemos ver esta es la arquitectura y funcionamiento de Accumulo nuestra primera Base de Datos NoSQL, pero para terminar con este post debemos 

Fast Random Access 

Este concepto es muy importante para muchas aplicaciones. Random Access implica que un elemento que es buscado y no es conocido hasta el tiempo de ejecución, el tiempo de acceso para cualquier dato en particular es aproximadamente el mismo. Esto usualmente se cumple en accesos secuenciales, en el que una operación de lectura comienza al principio de un conjunto de datos y comienza a leer data de manera secuencial hasta que llega al final. En este modelo es muy importante que el tiempo de acceso sea lo suficientemente veloz como para satisfacer las necesidades de las aplicaciones. La mayoría de las aplicaciones Web existentes requieren que la información solicitada este disponible en menos de un segundo.

Hay varias técnicas para lograr un buen desempeño con las técnicas de Random Access. Y de las cuales las dos más populares como les mencione con mi primera entrada de Big Data una de ellas es a a través de Funciones Hash (Hashing) ó por técnicas de Ordenación (Sorting) estas dos poderosas herramientas que tienen fundamentos matemáticos son el corazón de el almacenamiento masivo junto con la partición de la información.

Accumulo como pudimos ver a lo largo de las explicaciones fue diseñado para almacenar información masiva de manera ordenada, gracias a esto los usuarios pueden encontrar su información de manera rápida ó almacenar información de manera eficaz en forma incremental o actualizarla.

Como vimos la tarea de Accumulo es almacenar información de la forma key-value de una forma ordenada, por lo cuál podemos afirmar que tenemos un conjunto matemático que es totalmente ordenado de acuerdo a sus keys. Y gracias a que tenemos un conjunto totalmente ordenado la búsqueda de sus elementos es muy eficiente, solventando el principal requerimiento de un cliente hacia un sistema.

Información Ordenada vs No Ordenada

Cuando contamos con un conjunto ordenado como con los que trabaja Accumulo se utiliza un algoritmos llamado Búsqueda Binaria para encontrar un par del tipo key-value en un conjunto ordenado por keys como lo hace Accumulo.

Gracias a este tipo de algoritmos se reduce el tiempo de búsqueda en gran manera afirmando que si se intenta hacer una búsqueda de información en un conjunto no ordenado donde se tiene un billón de registros de pares key-values tomaría 57 días en encontrar un resultado, pero si trabajamos con un conjunto totalmente ordenado el sistema tardaría 300 mili segundos y más aún como trabajamos con Tables que son subcojnutos ordenados el tiempo reducirá un poco más que los 300 mili segundos, en mi experiencia que he trabajado de forma profesional con HBase y Cassandra, es una realidad que las búsquedas son de este orden con grandes volúmenes de información, en mi caso he trabajado con tablas de 600 millones de registros para las dos Base anteriores y el tiempo de respuesta anda en los mili-segundos para alguna búsqueda en particular.
Los algoritmos que tienen este tipo de desempeño se dicen que proveen un acceso logarítmico en el tiempo con respecto al número de elementos de información en el almacenamiento.

Massive Scalability

Acumulo es considerado una aplicación escalable horizontal, esto significa que podemos crecer  las capacidades de nuestro sistema (Accumulo) agregando más máquinas en lugar de remplazar una máquina existente con una con mayor capacidad, esto ocurre en la mayoría de nuestras máquinas de hoy en día que se escalan de manera vertical. Las nuevas máquinas agregadas al Clúster de Accumulo comienzan a participar en el Clúster muy rápidamente, por que no hay información que mover a esta(s) máquinas para empezar a alojar Tablets de alguna Tabla.
Accumulo trabaja muy en gran escala, que hablando de clúster se refiere a que puede trabajar con miles de máquinas asociadas al Clúster de Accumulo.

Un beneficio para levantar una instancia de Accumulo es que una aplicación puede ser escrita y deplegada en un clúster de magnitud pequeña cuando el tamaño de la información y la número de peticiones de lectura y escritura es bajo. Cuando la demanda de lectura y escritura sobre la información crece, El clúster de Accumulo nos provee la facilidad de expandirse para poder almacenar más información sin necesidad de re acomodar la información antes de expandir el clúster. 

NoSQL es un termino algo confuso y podemos encontrar este termino en varias Bases como Berkley DB, memcached, Bigtable, Accumulo, MongoDB, Neo4j, Amazon’s Dynamo y otras.

Algunas personas han agrupado el software distribuido basado de acuerdo a su data model soportado en las siguientes categorías:

Pure key-value

• Riak
• Dynamo
• memcached

Columnar (Bigtable)

• Bigtable
• Accumulo
• HBase
• Cassandra

Document

• MongoDB
• CouchDB

Graph

• Neo4j

Support for Analysis: MapReduce Integration

Accumulo nos provee una manera de analizar nuestra información de una forma rápida por medio del MapReduce que hasta este punto ya hemos visto. Accumulo guarda su información en HDFS y puede ser usado como una fuente de información de entrada para un Job del tipo MapReduce ó como un destino de información de un proceso MapReduce como en el caso de Apache Hive cuando se crea una Tabla Externa.

El Job del tipo MapReduce puede leer incluso desde los TabletServer usando la librería de cliente que Accumulo provee.

Key-Ordering

Algunas Bases de Datos NoSQL usan funciones hash para distribuir sus llaves en todas sus máquinas. Esto hace que las búsquedas simples para el cliente, pero requiere que algo de información se mueva cuando se hace un escalamiento horizontal, ya que como se comento anteriormente, Accumulo provee un balanceo de la información en el Clúster. También gracias al tipo de estructura que usa que es del tipo Sorting puede haber casos en que cuando realicemos un escaneo (lectura) a la Base en un rango secuencial de letras sea más difícil ó imposible.

Debido a que Accumulo mantiene su propia asignación dinámica de claves para las máquinas, puede manejar muy rápidamente las máquinas que se unen o abandonan el clúster, sin movimiento de datos y una interrupción mínima para los clientes. Además, el espacio clave se divide de forma dinámica y automática para que los datos se distribuyan uniformemente en todo el clúster.

Tight Hadoop Integration 

Algunas NoSQL Bases de datos tienen su propio sistema de almacenamiento. Accumulo usa HDFS, ofreciendo ciertas ventajas.

• Accumulo puede usar la salida de un Job de MapReduce sin tener que mover grandes cantidades de información para poder usarla.
• Accumulo permite el procesamiento de la información con el Framework MapReduce.

High versus eventual Consistency

Algunas Bases NoSQL son diseñadas para correr de manera distribuida con data centers de manera geográfica y permite que la información se escriba en más de un lugar de manera simultanea, esto resulta como una propiedad llamada eventual consistency, en  el que un valor leído puede no se la versión más reciente de ese dato, como vimos en el post anterior del Teorema CAP.

Accumulo esta diseñado para correr en un mismo data center y de tal manera que cumple con la alta consistencia para que podamos ver la misma información en todas las operaciones de lectura que realizamos, entonces como podemos ver Accumulo es un tipo de Base CP.

Las Bases de Datos NoSQL son muy poderosas y es que su manera en que están construidas internamente son como ya vimos hay del tipo Sorting ó Hashing, las cuales hacen que la búsqueda sea muy eficiente y como vimos anteriormente con tiempos sumamente veloces, más adelante lo comprobaremos y la razón de no llamar a Hive una Base de Datos es por que su forma de búsqueda es a través de un proceso MR de tal manera que no hay posibilidad de que Hive compita en desempeño con una Base NoSQL ya que Hive esta en el rango de segundos, mientras todas las Bases que veremos a continuación son del orden de mili segundos.