¿Cómo diseñar el almacenamiento de datos para el sistema de etiquetado particionado?

Question

Cómo diseñar almacenamiento de datos para un sistema de etiquetado enorme (como digg o delicious)?

Ya existe discussion al respecto, pero se trata de una base de datos centralizada. Dado que se supone que los datos crecerán, tendremos que dividir los datos en fragmentos múltiples pronto o después. Entonces, la pregunta es: ¿Cómo diseñar el almacenamiento de datos para el sistema de etiquetado particionado?

El sistema de etiquetado básicamente tiene 3 mesas:

Item (item_id, item_content) 

Tag (tag_id, tag_title) 

TagMapping(map_id, tag_id, item_id) 

que funciona bien para encontrar todos los artículos de etiqueta dada y encontrar todas las etiquetas para el tema dado, si la tabla se almacena en una base de datos de instancia. Si necesitamos dividir los datos en varias instancias de bases de datos, no es tan fácil.

Para la mesa artículo, que puede particionar su contenido con su clave item_id. Para la tabla Tag, podemos dividir su contenido con su clave tag_id. Por ejemplo, queremos dividir la tabla Tag en K bases de datos. Simplemente podemos elegir el número (tag_id% K) para almacenar la etiqueta dada.

Pero, ¿cómo dividir la tabla TagMapping?

TagMapping tabla representa la relación muchos a muchos. Solo puedo obtener una imagen para tener una duplicación. Es decir, el mismo contenido de TagMappping tiene dos copias. Uno está particionado con tag_id y el otro está particionado con item_id. En el escenario para encontrar etiquetas para un elemento dado, utilizamos la partición con tag_id. Si el escenario para encontrar elementos para la etiqueta dada, usamos la partición con item_id.

Como resultado, hay redundancia de datos. Y, el nivel de aplicación debe mantener la consistencia de todas las tablas. Parece difícil.

¿Hay alguna solución mejor para resolver este problema de partición de muchos a muchos?

Answer 1

Dudo que haya un solo enfoque que optimice todos los posibles escenarios de uso. Como dijo, hay dos escenarios principales que admite la tabla TagMapping: encontrar etiquetas para un elemento determinado y encontrar elementos con una etiqueta determinada. Creo que hay algunas diferencias en cómo usará la tabla TagMapping para cada escenario que pueda ser de su interés. Solo puedo hacer suposiciones razonables basadas en aplicaciones típicas de etiquetado, así que ¡perdónenme si esto está fuera de contexto!

Etiquetas Encontrando para un determinado artículo

A1. Vas a mostrar todos de las etiquetas para un artículo dado a la vez

A2. Vas a garantizar que todos los de etiquetas de un elemento son únicas

Búsqueda de elementos para una determinada etiqueta

B1. Va a necesitar algunos de los elementos para una etiqueta determinada a la vez (para completar una página de resultados de búsqueda)

B2. Puede permitir que los usuarios especifiquen varias etiquetas, por lo que necesitaría encontrar algunos de los elementos que coinciden con varias etiquetas

B3. Vas a ordenar los elementos para una determinada etiqueta (o etiquetas) por alguna medida de popularidad

Dado lo anterior, creo que un buen enfoque sería dividir TagMapping por artículo. De esta forma, todas las etiquetas para un artículo dado están en una partición. El particionamiento puede ser más detallado, ya que es probable que haya muchos más elementos que etiquetas y cada elemento tiene solo un puñado de etiquetas. Esto hace que la recuperación sea fácil (A1) y la exclusividad se puede aplicar dentro de una única partición (A2). Además, esa única partición puede decirle si un elemento coincide con varias etiquetas (B2).

ya que sólo necesita algunos de los elementos para una determinada etiqueta (o etiquetas) a la vez (B1), puede consultar las particiones de uno en uno en algún orden hasta que tenga el mayor número de registros que sean necesarios para llenar una página de resultados. Cuántas particiones tendrá que consultar dependerá de la cantidad de particiones que tenga, el número de resultados que desea mostrar y la frecuencia con que se utiliza la etiqueta. Cada partición tendría su propio índice en tag_id para responder esta consulta de manera eficiente.

El orden en que elija particiones será importante ya que afectará la forma en que se agrupan los resultados de búsqueda. Si el orden no es importante (es decir, B3 no importa), elija particiones de manera aleatoria para que ninguna de sus particiones se caliente demasiado. Si el pedido es importante, puede construir la identificación del artículo para que codifique la información relevante para el orden en el que se ordenan los resultados. Un esquema de partición apropiado sería consciente de esta codificación. Por ejemplo, si los resultados son URL ordenados por popularidad, puede combinar una ID de elemento secuencial con la puntuación de Google Page Rank para esa URL (o algo similar).El esquema de partición debe garantizar que todos los elementos dentro de una partición determinada tengan el mismo puntaje. Las consultas elegirían particiones en orden de puntuación para garantizar que se devuelvan primero los artículos más populares (B3). Obviamente, esto solo permite un tipo de clasificación y las propiedades involucradas deben ser constantes, ya que ahora son parte de una clave y determinan la partición del registro. Sin embargo, esta no es realmente una nueva limitación, ya que no es fácil admitir una variedad de géneros, o clases de propiedades volátiles, con datos particionados de todos modos.

Answer 2

La regla es que particiones por campo por las que va a consultar. De lo contrario, tendrás que mirar a través de todas las particiones. ¿Estás seguro de que necesitarás consultar la tabla Tag solo por tag_id? Creo que no, también necesitarás consultar por título de la etiqueta. No es tan obvio para la tabla de elementos, pero probablemente también desee consultar por medio de una URL para encontrar item_id cuando el otro usuario le asigne etiquetas.

Pero tenga en cuenta que las tablas de etiquetas y elementos tienen título y URL inmutables. Eso significa que puede usar la siguiente técnica:

1. Elija la partición desde el título (para la Etiqueta) o la URL (para el Elemento).
2. Elija la secuencia para esta partición para generar la identificación.

Usted o bien usa el par partition-localID como identificador global o usa conjuntos de números que no se superponen.De todos modos, ahora puedes calcular la partición desde los campos de ID y título/URL. ¿No sabes la cantidad de particiones por adelantado o te preocupas de que pueda cambiar en el futuro? Cree más de ellos y únase en grupos para que pueda reagruparlos en el futuro.

Claro, no puede hacer lo mismo para la tabla TagMapping, por lo que debe duplicar. Necesitas consultarlo por map_id, por tag_id, por item_id, ¿verdad? Entonces, incluso sin particionar, tiene que duplicar los datos creando 3 índices. Entonces, la diferencia es que utilizas diferentes particiones (por campos diferentes) para cada índice. No veo razón para preocuparse.

Answer 3

Lo más probable es que sus consultas vayan a estar relacionadas con un usuario o un tema. Lo que significa que debe tener toda la información relacionada con aquellos en un solo lugar.

Estás hablando de la distribución de DB, por lo general esto es principalmente un problema de sincronización. La lectura, que es aproximadamente el 90% del trabajo generalmente, se puede hacer en una base de datos replicada. El problema es cómo actualizar un DB y mantener la coherencia con todos los demás y sin sacrificar las actuaciones. Esto depende de los detalles de su escenario.

La otra posibilidad es dividir, como usted pidió, todos los datos sin superposición. Probablemente particiones por ID de usuario o ID de tema. Si realiza una partición por ID de tema, una base de datos podría hacer referencia a todos los temas y solo indicar qué DB dedicado contiene los datos. A continuación, puede consultar el correcto. Dado que particiones por ID, toda la información relacionada con ese tema podría estar en esa base de datos especializada. También puede dividir por idioma o país para un sitio web internacional.

Por último, pero no menos importante, es probable que termine mezclando los dos: algunos datos que no se superponen, y algunos datos superpuestos (replicados). Primero encuentre las operaciones habituales, luego encuentre cómo hacerlas en una base de datos en las consultas menos posibles.

PD: No se olvide de almacenar en caché, le ahorrará más que DB distribuido.