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.

Tipo: Patente Internacional (Tratado de Cooperación de Patentes). Resumen de patente/invención. Número de Solicitud: PCT/US2010/023075.

Solicitante: BitTorrent, Inc.

Nacionalidad solicitante: Estados Unidos de América.

Dirección: 303 Second Street, Suite S200 San Francisco, CA 94107 ESTADOS UNIDOS DE AMERICA.

Inventor/es: BRAM,COHEN.

Fecha de Publicación: .

Clasificación Internacional de Patentes:

  • G06F12/00 FISICA.G06 CALCULO; CONTEO.G06F PROCESAMIENTO ELECTRICO DE DATOS DIGITALES (sistemas de computadores basados en modelos de cálculo específicos G06N). › Acceso, direccionamiento o asignación en sistemas o arquitecturas de memoria (entrada digital a partir de, o salida digital hacia soportes de registro, p. ej. hacia unidades de almacenamiento de disco G06F 3/06).
  • G06F13/00 G06F […] › Interconexión o transferencia de información u otras señales entre memorias, dispositivos de entrada/salida o unidades de procesamiento (circuitos de interfaz para dispositivos de entrada/salida específicos G06F 3/00; sistemas multiprocesadores G06F 15/16).

PDF original: ES-2528245_T3.pdf

 


Fragmento de la descripción:

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]

 


Reivindicaciones:

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.


 

Patentes similares o relacionadas:

Sistema de distribución de contenido para una función de tarjeta sin contacto y método de distribución de contenido para una función de tarjeta sin contacto, del 27 de Mayo de 2020, de NTT DOCOMO, INC.: Sistema para distribuir contenidos para una función de tarjeta de proximidad, que comprende: un aparato de proveedor de información, un primer aparato (1A) de terminal […]

Dispositivo de procesamiento de información, método de procesamiento de información y programa, del 20 de Mayo de 2020, de SONY CORPORATION: Un dispositivo de procesamiento de información que comprende: una unidad de comunicación inalámbrica configurada para intercambiar un tren para […]

Dispositivo inalámbrico y procedimiento para visualizar un mensaje, del 25 de Marzo de 2020, de QUALCOMM INCORPORATED: Un dispositivo inalámbrico para visualizar un mensaje, comprendiendo el dispositivo inalámbrico: un visualizador gráfico ; una unidad de comunicaciones inalámbricas […]

Sistemas y procedimientos para proporcionar almacenamiento de datos en servidores de un sistema de entrega de medios bajo demanda, del 22 de Enero de 2020, de Rovi Guides, Inc: Un procedimiento para su uso en un sistema de guía interactivo que proporciona a los usuarios acceso a programas, comprendiendo el procedimiento: generar, […]

Nuevo rúter y método de enrutamiento de mensajería instantánea, del 8 de Enero de 2020, de Beijing VRV Software Corporation Ltd: Un método de ruteo o enrutamiento de mensajería instantánea (o IM, por las siglas en inglés de 'Instant Messaging') que se implementa en una red de rúteres IM […]

Dispositivo de control de descarga, del 20 de Mayo de 2019, de Maxell, Ltd: Un aparato de control de descarga para descargar contenidos, que comprende: una unidad de recepción que está adaptada para recibir metainformación de control […]

Procesamiento de servidor en el suministro de mensajes para un dispositivo inalámbrico que se conecta a un servidor, del 6 de Mayo de 2019, de QUALCOMM INCORPORATED: Un procedimiento para procesar un mensaje de destino para mostrar en un dispositivo inalámbrico que se comunica con un servidor de descarga de […]

Sistema descentralizado para monitorización en tiempo real en remoto, del 24 de Abril de 2019, de SANTOS, EDUARDO PEDROSA: Sistema descentralizado para monitorización en tiempo real en remoto de transformadores de potencia, reactores, disyuntores, transformadores de instrumento, […]

Utilizamos cookies para mejorar nuestros servicios y mostrarle publicidad relevante. Si continua navegando, consideramos que acepta su uso. Puede obtener más información aquí. .