Almacenamiento distribuido de datos recuperables.

Método para sustituir un nodo fallido que almacena datos distribuidos,

que comprende:

recibir (402) una indicación de un nodo de almacenamiento nuevo, recibiéndose la indicación en cada uno de una pluralidad de nodos de almacenamiento (106), en donde dicho cada uno de la pluralidad de nodos de almacenamiento (106) contiene una pluralidad de porciones generadas a partir de un archivo de datos, generándose cada una de la pluralidad de porciones mediante la multiplicación de fragmentos del archivo de datos por coeficientes aleatorios y mediante la suma de los fragmentos multiplicados:

generar (404) una porción sustitutoria en cada uno de la pluralidad de nodos de almacenamiento (106) como respuesta a la indicación, en donde la porción sustitutoria generada en uno de la pluralidad de nodos de almacenamiento incluye una combinación de la pluralidad de porciones contenidas en el nodo de almacenamiento; y

enviar (406) las porciones sustitutorias generadas desde la pluralidad de nodos de almacenamiento (106) al nodo de almacenamiento nuevo indicado.

Almacenamiento distribuido de datos recuperables Remisión a solicitudes relacionadas

La presente solicitud reivindica el beneficio de la solicitud provisional U.S. 61/149.676, presentada el 3 de febrero de

29.

Antecedentes Sector técnico

La presente invención se refiere en general al almacenamiento distribuido de datos sobre varios nodos en una red. Descripción de la técnica relacionada

Un problema fundamental del almacenamiento es cómo almacenar datos de manera redundante, de modo que incluso si falla un elemento de almacenamiento particular, los datos se puedan recuperar a partir de otras fuentes. Una de las estrategias consiste simplemente en almacenar múltiples copias de todo. Aunque esto funciona, exige considerablemente un mayor almacenamiento para un nivel particular de fiabilidad (o, por contraposición lógica, proporciona una fiabilidad considerablemente menor para una cantidad particular de almacenamiento).

Para lograr una fiabilidad mejor, se pueden usar códigos de borrado (erasure codes). Un código de borrado toma un elemento de datos original y genera a partir de él lo que se denomina "porciones". Las porciones se diseñan de manera que siempre que haya porciones suficientes tal que su tamaño combinado sea igual al tamaño de los datos originales, los datos originales se pueden reconstruir a partir de ellas. En el esquema al que se hace referencia como codificación de borrado de k-de-n, se generan n porciones y se pueden usar k cualesquiera de ellas para reconstruir los datos originales. El tamaño de cada porción es 11k veces el tamaño de los datos originales de manera que las porciones contienen suficiente información para la reconstrucción. La n puede variar notablemente. El almacenamiento de más porciones dará como resultado una mayor fiabilidad, aunque el número de porciones puede variar desde k hasta esencialmente infinito. El esquema trivial de simplemente almacenar múltiples copias de los datos originales se puede considerar como un esquema de 1-de-n para n copias, y el esquema de muy baja fiabilidad, aunque también sencillo, en el que los datos originales se trocean en fragmentos y los mismos se almacenan todos por separado se puede considerar como un esquema de k-de-k para k fragmentos.

La técnica de codificación de borrado (erasure coding) en primer lugar descompone los datos originales en k fragmentos, a continuación trata dichos fragmentos como vectores en un campo de Galois (GF) y genera porciones multiplicando los fragmentos por coeficientes aleatorios y sumándolos entre sí. La codificación de borrado también se puede llevar a cabo tratando los fragmentos como vectores módulo un número primo. Para simplificar, la codificación de borrado que se describe más abajo usa campos de Galois. Una porción comprende entonces el resultado de ese cálculo junto con los coeficientes aleatorios. La aleatoriedad de los coeficientes provoca que exista una probabilidad de que los datos originales sean no recuperables, esencialmente igual al inverso del número de elementos del campo de Galois que se esté usando. Por motivos de almacenamiento, un campo de Galois de tamaño 232 ó 264 (correspondiente al tratamiento de secciones de 4 y 8 bytes respectivamente como unidades individuales) constituye un compromiso razonable entre la carga de cálculo y la probabilidad de que por causalidad los datos sean no recuperables, siendo esto extremadamente improbable con 232 y esencialmente imposible con 264.

La técnica anterior se enfrenta a limitaciones cuando se usa para un almacenamiento distribuido a través de Internet. Para el almacenamiento en Internet, el recurso escaso es el ancho de banda, y la capacidad de almacenamiento de los nodos extremos es esencialmente infinita (o por lo menos suficientemente económica como para no constituir un factor limitativo), lo cual da como resultado una situación en la que el factor limitativo sobre cualquier almacenamiento es la cantidad de ancho de banda para enviarlo. Para el almacenamiento inicial, esto da como resultado un modelo muy similar a aquel en el que el factor limitativo es la capacidad de almacenamiento; existe una sustitución unívoca de almacenamiento por ancho de banda. Sin embargo, después del almacenamiento inicial, se pueden consumir recursos significativos de ancho de banda para sustituir soportes de almacenamiento fallidos (y todos los soportes de almacenamiento acaban fallando). Normalmente, cuando el almacenamiento redundante se está llevando a cabo de manera local, por ejemplo, en una red de área local, se lleva a cabo una recuperación completa de los datos originales correspondientes a las porciones contenidas por los soportes fallidos y la misma se almacena de manera temporal, a continuación se crean porciones nuevas y las mismas se almacenan en otro elemento de soporte, y seguidamente la copia completa temporal es eliminada. Hacer lo mismo por Internet requeriría la recuperación de k porciones de los diversos soportes de almacenamiento restantes, la reconstrucción de los datos originales, la generación de k porciones nuevas, y el envío de las porciones a los soportes de almacenamiento (incluyendo los soportes de almacenamiento sustitutorios). Esto requiere 2k veces el tamaño de la porción que se está usando en ancho de banda a través de internet, lo cual se convierte rápidamente en inaceptable a medida que k crece.

El simple almacenamiento de múltiples copias de los datos es una mejor solución para evitar el uso de ancho de

banda, aunque presenta unas propiedades de fiabilidad mucho peores y representa un despilfarro por si mismo de la escala de n. ya que cuantas más copias de algo es necesario guardar, más ancho de banda se usa cuando dichas copias se deterioran.

El documento US277982 propone un sistema de almacenamiento digital de archivos de datos en el cual archivos de datos originales a almacenar se dispersan usando alguna forma de algoritmo de dispersión de información en una serie de "fracciones" o subconjuntos de archivos, de tal manera que los datos de cada porción de archivo son menos utilizables o menos reconocibles o totalmente inútiles o totalmente irreconocibles por sí mismos excepto cuando se combinan con parte o la totalidad de las otras porciones del archivo.

El documento US27177739 propone una técnica de duplicación de datos para proporcionar una duplicación, con codificación de borrado, de grandes conjuntos de datos sobre un conjunto de réplicas distribuidas geográficamente. La técnica utiliza un árbol de multidifusión para almacenar, reenviar, y codificar por borrado el conjunto de datos. La codificación por borrado de datos se puede llevar a cabo en varias posiciones dentro del árbol de multidifusión, incluyendo el origen, nodos intermedios, y nodos de destino. En una realización, el sistema comprende un nodo de origen para almacenar el conjunto de datos originales, una pluralidad de nodos intermedios, y una pluralidad de nodos hoja para almacenar los fragmentos de réplica únicos. Los nodos están configurados como un árbol de multidifusión para convertir los datos originales en los fragmentos de réplica únicos llevando a cabo una codificación de borrado distribuida en una pluralidad de niveles del árbol de multidifusión.

El documento US25216813 propone un esquema de protección de archivos para contenido fijo en un archivo de datos distribuidos usando cálculos que aprovechan operadores de permutación de un código cíclico. En una realización ilustrativa, se describe una técnica de codificación de N+K para su uso con el fin de proteger datos que se están distribuyendo en una matriz redundante de nodos independientes (RAIN). Los propios datos pueden ser de cualquier tipo, y también pueden incluir metadatos del sistema.

Sumario

Según un primer aspecto de la presente invención, se proporciona un método tal como se expone en la reivindicación independiente 1 adjunta. De acuerdo con un segundo aspecto de la presente invención, se proporciona un sistema tal como se expone en la reivindicación independiente 7 adjunta.

Breve descripción de los dibujos

La FIG. 1 ilustra un entorno que incluye nodos de almacenamiento para el almacenamiento distribuido de

datos, en una realización.

La FIG. 2 es un diagrama de flujo que ilustra un método para el almacenamiento distribuido de datos, en una realización.

La FIG. 3 es un diagrama de flujo que ilustra un método para dividir un archivo de datos en porciones y enviar porciones a nodos de almacenamiento, en una realización.

La FIG. 4 es un diagrama de flujo que ilustra un método de generación de porciones para un nodo de almacenamiento sustitutorio, en una realización.

La FIG. 5 es un diagrama esquemático que ilustra la generación... [Seguir leyendo]

1. Método para sustituir un nodo fallido que almacena datos distribuidos, que comprende:

recibir (42) una indicación de un nodo de almacenamiento nuevo, recibiéndose la indicación en cada uno de una pluralidad de nodos de almacenamiento (16), en donde dicho cada uno de la pluralidad de nodos de almacenamiento (16) contiene una pluralidad de porciones generadas a partir de un archivo de datos, generándose cada una de la pluralidad de porciones mediante la multiplicación de fragmentos del archivo de datos por coeficientes aleatorios y mediante la suma de los fragmentos multiplicados:

generar (44) una porción sustitutoria en cada uno de la pluralidad de nodos de almacenamiento (16) como respuesta a la indicación, en donde la porción sustitutoria generada en uno de la pluralidad de nodos de almacenamiento incluye una combinación de la pluralidad de porciones contenidas en el nodo de almacenamiento; y

enviar (46) las porciones sustitutorias generadas desde la pluralidad de nodos de almacenamiento (16) al nodo de almacenamiento nuevo indicado.

2. El método según la reivindicación 1, en el que la porción sustitutoria generada comprende una combinación lineal de la pluralidad de porciones contenidas en el nodo de almacenamiento que usan coeficientes aleatorios, y/o en donde un número total de las porciones sustitutorias generadas por la pluralidad de nodos de almacenamiento (16) es igual a un parámetro de fiabilidad, en donde el parámetro de fiabilidad se basa en un número total de nodos de almacenamiento requeridos para que el archivo de datos siga siendo recuperable.

3. El método según una cualquiera de las reivindicaciones anteriores, que comprende además verificar la integridad de las porciones sustitutorias generadas.

4. El método según una cualquiera de las reivindicaciones anteriores, en el que:

cada una de la pluralidad de porciones generadas a partir del archivo de datos comprende una combinación lineal de fragmentos del archivo de datos y un conjunto de coeficientes usados para generar la combinación; y/o

la pluralidad de porciones generadas a partir del archivo de datos se genera usando codificación de borrado (erasure coding) basada en fragmentos del archivo de datos; y/o

las porciones sustitutorias generadas se usan para reconstruir el archivo de datos (21) o en donde las porciones sustitutorias generadas se usan para generar porciones sustitutorias subsiguientes para un nodo nuevo subsiguiente; y/o

la indicación se recibe desde un módulo de seguimiento (18) que monitoriza el estado de la pluralidad de nodos de almacenamiento y realiza un seguimiento de posiciones de porciones.

5. Método según la reivindicación 1, en el que el nodo de almacenamiento nuevo sustituye a un nodo de almacenamiento fallido.

6. Método según la reivindicación 1, en el que la generación de una porción sustitutoria comprende:

multiplicar cada una de la pluralidad de porciones contenidas en el nodo de almacenamiento y un conjunto de coeficientes por un valor de escala aleatorio; y

combinar las porciones multiplicadas y el conjunto multiplicado de coeficientes.

7. Sistema para sustituir un nodo fallido que almacena datos distribuidos, presentando el sistema una pluralidad de nodos de almacenamiento (16), en donde cada nodo de almacenamiento contiene una pluralidad de porciones generadas a partir de un archivo de datos, generándose cada una de la pluralidad de porciones por la multiplicación de fragmentos del archivo de datos por coeficientes aleatorios y la suma de los fragmentos multiplicados, y en donde cada nodo de almacenamiento está configurado para

recibir (42) una indicación de un nodo de almacenamiento nuevo;

generar (44) una porción sustitutoria como respuesta a la indicación, en donde la porción sustitutoria comprende una combinación de la pluralidad de porciones contenidas en el nodo de almacenamiento; y

enviar (46) la porción sustitutoria generada al nodo de almacenamiento nuevo indicado.

8. El sistema según la reivindicación 7, en el que:

la porción sustitutoria comprende una combinación lineal de la pluralidad de porciones contenidas en el

nodo de almacenamiento que usan coeficientes aleatorios; y/o

un número total de las porciones sustitutorias generadas por la pluralidad de nodos de almacenamiento (16) es igual a un parámetro de fiabilidad, en donde el parámetro de fiabilidad se basa en un número total de nodos de almacenamiento requeridos para que el archivo de datos siga siendo recuperable; y/o

cada uno de la pluralidad de nodos de almacenamiento (16) está configurado además para enviar

información de comprobación hash al nodo de almacenamiento nuevo con el fin de verificar la porción sustitutoria; y/o

cada una de la pluralidad de porciones generadas a partir del archivo de datos comprende una combinación lineal de fragmentos del archivo de datos y un conjunto de coeficientes usados para generar la 1 combinación; y/o

la pluralidad de porciones generadas a partir del archivo de datos se genera usando codificación de borrado (erasure coding) basada en fragmentos del archivo de datos; y/o

la porción sustitutoria generada se usa para reconstruir el archivo de datos o en donde la porción sustitutoria generada se usa para generar porciones sustitutorias subsiguientes para un nodo nuevo

subsiguiente; y/o

la indicación se recibe desde un módulo de seguimiento (18) que monitoriza el estado de la pluralidad de nodos de almacenamiento (16) y realiza un seguimiento de posiciones de porciones.

9. Sistema según la reivindicación 8, en el que el nodo de almacenamiento nuevo sustituye a un nodo de almacenamiento fallido.

1. Sistema según la reivindicación 8, en el que la generación de una porción sustitutoria comprende:

multiplicar cada una de la pluralidad de porciones contenidas en el nodo de almacenamiento y un conjunto de coeficientes por un valor de escala aleatorio; y

combinar las porciones multiplicadas y el conjunto multiplicado de coeficientes.