¿Cómo implementa la clasificación y paginación en datos distribuidos?

Question

Aquí está el problema que estoy tratando de resolver:

Necesito ser capaz de mostrar una tabla paginada, clasificada de datos que se almacena en varios fragmentos de la base de datos.

La localización y la clasificación son problemas bien conocidos que la mayoría de nosotros puede resolver de muchas maneras cuando los datos provienen de una sola fuente. Pero si divide los datos en fragmentos o usa una base de datos de documentos distribuidos o DHT o cualquier otro que prefiera de NoSQL, las cosas se complican.

Aquí tenemos una imagen simple de un muy pequeño conjunto de datos:

Fragmento | Datos
1 | A
1 | D
1 | G
2 | B
2 | E
2 | H
3 | C
3 | F
3 | Me

Ordenado en páginas (tamaño de página = 3):

página | Datos
1 | A
1 | B
1 | C
2 | D
2 | E
2 | F
3 | G
3 | H
3 | Me

Y si hemos querido mostrar la página de usuario 2, nos gustaría volver:

D
E
F

Si el tamaño de la tabla en cuestión es algo así como 10 millones de filas , o 100 millones, no puede simplemente desplegar todos los datos en un servidor web/de aplicaciones para ordenarlos y devolver la página correcta. Y obviamente no puede dejar que cada fragmento individual clasifique y page su propia porción de los datos porque los fragmentos no se conocen entre sí.

Para complicar las cosas, los datos que necesito presentar no pueden estar muy desactualizados, por lo que no es práctico calcular previamente un conjunto de tipos útiles y almacenar los resultados para su posterior recuperación.

Answer 1

hay varias soluciones, algunas de las cuales pueden no ser factible para usted, pero tal vez uno de ellos se adhieren:

1. ¿Tienen el sharding por rangos de entrada para este valor (por ejemplo, fragmento 1 contiene AC, fragmento 2 DF, etc.). Alternativamente, use otra tabla con claves externas a esta tabla como índice, y utilice la shard de la tabla de índice usando este sistema. De esta forma, puede localizar y obtener fácilmente rangos especificados. Esta solución es probablemente la mejor en términos de rendimiento, si puede hacerlo (se supone que la cantidad de fragmentos es estática y los fragmentos son confiables).
2. Identifique los elementos de página por búsqueda binaria. Por ejemplo, supongamos que quiere los elementos 100 a 110. Para cada fragmento, cuente el número de valores lexicográficamente debajo de "M".Si la suma de los números es superior a 100, reduzca el punto de pivote, de lo contrario aumente (utilizando la búsqueda binaria). Después de identificar el artículo número 100 (el primer elemento en su página), tome los primeros 9 (10 - 1) elementos más grandes que ese elemento de cada fragmento, búsquelos, clasifique la lista completa, tome los primeros 9 de la lista, anteponga el primer artículo y está tu página! Este enfoque es más difícil de implementar y requerirá consultas O(log(n)) por lo que es más lento que (1), pero aún puede ser razonablemente rápido si la carga no es muy pesada.
3. Almacene el número de página con cada valor. Esto le da lecturas increíblemente rápidas, pero escribe horriblemente lento, por lo que solo funciona en el escenario donde hay muy pocas escrituras (o solo se agrega en términos de la variable ordenada).