ES2318323T3 - Equilibrio de recursos redundantes en una agrupacion de unidades de almacenamiento. - Google Patents
Equilibrio de recursos redundantes en una agrupacion de unidades de almacenamiento. Download PDFInfo
- Publication number
- ES2318323T3 ES2318323T3 ES04766140T ES04766140T ES2318323T3 ES 2318323 T3 ES2318323 T3 ES 2318323T3 ES 04766140 T ES04766140 T ES 04766140T ES 04766140 T ES04766140 T ES 04766140T ES 2318323 T3 ES2318323 T3 ES 2318323T3
- Authority
- ES
- Spain
- Prior art keywords
- donor
- grouping
- receiver
- storage
- elements
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
- G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
- G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
- G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
- G06F11/1084—Degraded mode, e.g. caused by single or multiple storage removals or disk failures
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/008—Reliability or availability analysis
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2211/00—Indexing scheme relating to details of data-processing equipment not covered by groups G06F3/00 - G06F13/00
- G06F2211/10—Indexing scheme relating to G06F11/10
- G06F2211/1002—Indexing scheme relating to G06F11/1076
- G06F2211/1004—Adaptive RAID, i.e. RAID system adapts to changing circumstances, e.g. RAID1 becomes RAID5 as disks fill up
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2211/00—Indexing scheme relating to details of data-processing equipment not covered by groups G06F3/00 - G06F13/00
- G06F2211/10—Indexing scheme relating to G06F11/10
- G06F2211/1002—Indexing scheme relating to G06F11/1076
- G06F2211/1028—Distributed, i.e. distributed RAID systems with parity
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Quality & Reliability (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
- Detection And Correction Of Errors (AREA)
- Oscillators With Electromechanical Resonators (AREA)
Abstract
Un método para aumentar una tolerancia de error de una agrupación anamórfica de m unidades de almacenamiento, comprendiendo el método las operaciones de: almacenar k conjuntos a través de la agrupación de m unidades de almacenamiento, teniendo cada conjunto una pluralidad de elementos, formando cada conjunto un código de cancelación o de corrección de error que tiene una distancia de Hamming mínima d, teniendo cada conjunto n+r elementos en los que n es el número de elementos de datos, r es el número de elementos redundantes, de tal modo que m > n+r y estando almacenado cada elemento respectivo de un conjunto sobre una unidad de almacenamiento diferente; seleccionar un conjunto donante y un elemento en el conjunto donante cuando la diferencia entre la distancia mínima del conjunto donante y la distancia mínima de un conjunto receptor es mayor o igual a 2, siendo almacenado el elemento seleccionado en el conjunto donante sobre una unidad de almacenamiento que no tiene elementos del conjunto receptor; y reconstruir el contenido de un elemento perdido del conjunto receptor sobre el elemento seleccionado del conjunto donante.
Description
Equilibrado de recursos redundantes en una
agrupación de unidades de almacenamiento.
El presente invento se refiere a sistemas de
almacenamiento. En particular el presente invento se refiere a un
método para configurar una agrupación o matriz de unidades de
almacenamiento para aumentar el número de fallos de la unidad de
almacenamiento que la agrupación puede tolerar sin pérdida de datos
almacenados en la agrupación.
El documento EP 518.603 describe una agrupación
DASD en la que los datos y los bloques de paridad están distribuidos
sobre posiciones del bloque de agrupaciones de acuerdo al menos con
un diseño combinatorio para permitir una carga equilibrada. Esto
minimiza el número de accesos requeridos para reconstruir los datos
y los bloques de paridad perdidos.
El documento US 5.485.571 describe un método en
una agrupación redundante de unidades de almacenamiento que
proporciona una distribución de carga de trabajo uniforme entre las
unidades de almacenamiento. Las regiones de datos, las regiones de
paridad y las regiones de repuestos o reservas están distribuidas de
tal modo que cada unidad de almacenamiento tiene el mismo número de
regiones de paridad antes, durante y después de un fallo de una de
las unidades de almacenamiento.
Las siguientes definiciones son usadas aquí y
son ofrecidas con propósitos de ilustración y no de limitación:
Un "elemento" es un bloque de datos en una
unidad de almacenamiento.
Una "agrupación básica" es un conjunto de
elementos que comprenden una unidad de agrupación para un ECC.
Una "agrupación o agrupación" es un
conjunto de unidades de almacenamiento que contiene una o más
agrupaciones básicas.
Un "conjunto" es una agrupación básica con
una agrupación.
n es el número de unidades de datos en la
agrupación básica.
r es el número de unidades redundantes en la
agrupación básica.
m es el número de unidades de almacenamiento en
la agrupación.
d es la distancia de Hamming mínima de la
agrupación básica.
D es la distancia de Hamming mínima de la
agrupación.
En una agrupación tradicional, el número de
unidades de almacenamiento en la agrupación es igual al número de
unidades de datos en una agrupación básica más el número de
unidades redundantes en la agrupación básica. Es decir, m =
n+r. La mayor parte de las agrupaciones de almacenamiento
tradicionales usan un código de Distancia Máxima de Separación
(MDS), tal como paridad, o una técnica de formación de copia espejo
para tolerar fallos. La distancia de Hamming mínima de la
agrupación básica que usa un código MDS es igual a uno más el
número de unidades redundantes en la agrupación básica (es decir, d
= 1+r). Para una configuración en espejo, el número de unidades
redundantes en la agrupación básica es igual al número de unidades
de datos en la agrupación básica (r = n = 1), y la distancia de
Hamming mínima es d = 2.
Es posible codificar de modo anamórfico una
agrupación sobre m unidades de almacenamiento, que es mayor que el
número n de unidades de datos en la agrupación más el número r de
unidades redundantes en la agrupación, es decir, m > n+r.
En la literatura, cuando una codificación anamórfica es usada para
disponer bloques de paridad para rendimiento, tal codificación es
denominada típicamente como "paridad de
des-agrupamiento". Como se ha usado aquí, tal
esquema de codificación es denominado como un esquema de
codificación anamórfico, debido a que identifica más exactamente
que el esquema de codificación puede proporcionar nuevas propiedades
para una agrupación.
El anamorfismo es conseguido disponiendo
selectivamente un conjunto de agrupaciones básicas dentro de una
agrupación. Por ejemplo, considérese la agrupación ejemplar 200
mostrada en la fig. 2 que usa un código de cuatro elementos. La
agrupación 200 incluye seis unidades de almacenamiento D1
representadas en forma de columnas. Para la agrupación 200, m = 6.
La agrupación 200 incluye también varias agrupaciones básicas que
están formadas cada una a partir de n unidades de datos más r
unidades redundantes. Es decir, para cada agrupación básica, n+r =
4. Las agrupaciones básicas respectivas son numeradas
secuencialmente como conjuntos 1 en la fig. 2 para indicar que el
código de cuatro elementos de la agrupación 200 está dispersado a
través de unidades D1 de almacenamiento. Hay cuatro bloques en cada
conjunto y cada conjunto actúa como una agrupación básica
independiente. La distancia mínima de la agrupación es
consiguientemente, el mínimo de todas las distancias Hamming mínimas
de los conjuntos respectivos, es decir, D = min(d_{i}),
donde D_{i} es la distancia mínima del conjunto i.
Como se ha configurado, la agrupación anamórfica
200 puede tolerar la pérdida de al menos r unidades de
almacenamiento de un conjunto de m unidades de almacenamiento sin
pérdida de datos, en vez de r unidades exactamente a partir de un
conjunto de n unidades de almacenamiento. Así, si r = 2, y el código
usado es MDS, entonces cualesquiera dos unidades de almacenamiento
pueden fallar sin pérdida de datos. Un conjunto fallará si
cualquiera de tres de sus elementos se pierden. Hay sin embargo,
algunas combinaciones de tres fallos de unidades que pueden ser
tolerados por la agrupación anamórfica 200. Por ejemplo, si falla
cada una de las unidades de almacenamiento D1, D3 y D5, dos
elementos de conjunto 1, dos elementos de conjunto 2 y dos elementos
del conjunto 3 se pierden, pero ningún conjunto ha perdido tres
elementos. La agrupación anamórfica 200 es así, sobre especificada y
puede ser ventajosamente explotada.
Cuando es necesario hay una técnica que mejora
la distancia de Hamming mínima de un ECC cuando es usado con una
agrupación anamórfica de unidades de almacenamiento, y aumentando
por ello la distancia mínima efectiva de la agrupación.
El presente invento proporciona una técnica que
mejora la distancia de Hamming mínima de un ECC que es usado con
una agrupación anamórfica de unidades de almacenamiento, aumentando
por ello la distancia mínima de la agrupación.
Las ventajas del presente invento son
proporcionadas por una primera realización que es un método y un
sistema para aumentar una tolerancia de error de una agrupación
anamórfica de m unidades de almacenamiento en la que k conjuntos
son almacenados a través de la agrupación de m unidades de
almacenamiento. Cada conjunto tiene n+r elementos que corresponden
a un código simétrico que tiene una distancia de Hamming mínima d =
r+1 y en la que n es un número de unidades de almacenamiento de
datos en una agrupación básica de la agrupación de m unidades de
almacenamiento y r es un número de unidades redundantes en la
agrupación básica. Adicionalmente, n = r, n \geq 2, m > n+r,
jm = k(n+r), y j y k son enteros. Cada elemento respectivo de
un conjunto es almacenado en una unidad de almacenamiento
diferente. Un elemento es seleccionado cuando una diferencia entre
una distancia mínima de un conjunto donante y una distancia mínima
de un conjunto receptor es mayor o igual a 2. El elemento
seleccionado es reconstruido sobre una unidad de almacenamiento que
no tiene elementos del conjunto receptor. Antes de que el elemento
perdido sea reconstruido, las unidades de almacenamiento que
almacenan el conjunto donante son hechas conocedoras de que el
elemento seleccionado ha sido donado de modo que los datos no son
leídos o descritos en el elemento seleccionado como parte del
conjunto donante. Un elemento perdido del conjunto receptor es a
continuación reconstruido sobre el elemento seleccionado. De acuerdo
con el presente invento, distancia de Hamming mínima del conjunto
receptor es d \geq 1 antes de que el elemento en el conjunto
donante sea seleccionado. El elemento seleccionado de conjunto
donante puede ser además seleccionado basado en un impacto de
rendimiento mínimo sobre la agrupación. Adicionalmente, la
información del receptor es seleccionada basado en un rendimiento
mejorado de la agrupación. La agrupación del sistema de
almacenamiento incluye redundancia basada en un código de
corrección de cancelación o de error, tal como un código de paridad,
un código Winograd, un código simétrico, un código de
Reed-Solomon, un código EVENODD, o un derivado de un
código EVENODD. Alternativamente, la agrupación incluye redundancia
basada en un producto de una pluralidad de códigos correctores de
cancelación o de error en el que al menos uno de los códigos
correctores de cancelación o de error es un código de paridad, un
código Winograd, un código simétrico, un código de
Reed-Solomon, un código EVENODD, o un derivado de un
código EVENODD.
Cuando un elemento en el conjunto donante falla
durante la operación de reconstrucción de al menos una parte de la
información del receptor procedente del conjunto receptor en el
elemento seleccionado, la operación de reconstrucción de al menos
una parte de información de receptor procedente del conjunto
receptor en el conjunto seleccionado es terminada. Un segundo
conjunto donante es seleccionado de la pluralidad de conjuntos
cuando una diferencia entre una distancia mínima del segundo
conjunto donante y una distancia mínima del segundo conjunto
receptor es mayor o igual a 2. Un elemento donante es seleccionado
en el segundo conjunto donante. Al menos una parte de la
información de receptor perdida del conjunto receptor es
reconstruida sobre el elemento seleccionado en el segundo conjunto
donante. Cuando un elemento de repuesto o de reserva resulta
disponible, el elemento de repuesto es asignado a una unidad de
almacenamiento seleccionada.
El presente invento está ilustrado a modo de
ejemplo y no a modo de limitación en las figuras adjuntas en las
que números de referencia similares indican elementos similares y en
las que:
La fig. 1a muestra una configuración típica de
un sistema de almacenamiento con una pluralidad de agrupaciones
conectadas a un controlador de almacenamiento común;
La fig. 1b muestra una configuración típica de
un sistema de almacenamiento con una pluralidad de agrupaciones
conectadas a controladores de almacenamiento separados;
La fig. 2 representa una agrupación anamórfica
ejemplar que tiene seis unidades de almacenamiento;
La fig. 3 representa una agrupación anamórfica
ejemplar que tiene nueve unidades de almacenamiento para ilustrar
los beneficios de una operación de calibrado de acuerdo con una
realización del presente invento;
La fig. 4 representa una primera disposición de
tres fallos de unidades de almacenamiento de la agrupación
anamórfica representada en la fig. 3;
La fig. 5 representa una segunda disposición de
tres fallos de unidades de almacenamiento de la agrupación
anamórfica representada en la fig. 3;
La fig. 6 representa la agrupación de la fig. 5
después de realizar una operación de calibrado de acuerdo con una
realización del presente invento;
La fig. 7 representa una tercera disposición de
tres fallos de unidades de almacenamiento de la agrupación
anamórfica representada en la fig. 3;
La fig. 8 representa la agrupación de la fig. 7
después de realizar una operación de calibrado de acuerdo con una
realización del presente invento;
La fig. 9 representa una agrupación ejemplar que
tiene ocho unidades de almacenamiento usando un código simétrico
(3+3);
La fig. 10 representa un sistema que tiene tres
agrupaciones de 8 unidades de almacenamiento;
La fig. 11 representa el sistema de agrupación
de la fig. 10 después de realizar una operación de calibrado
externa de acuerdo con una realización del presente invento; y
La fig. 12 representa una décima agrupación de
unidades de almacenamiento con tres unidades de almacenamiento que
han fallado después de un conjunto de operaciones de calibrado.
La presente solicitud está relacionada con la
Solicitud de Patente Norteamericana nº de serie 10/619.649 (Attorney
Docket Nº ARC92003015US1), titulada "Intercambio de Paridad
Automático", la Solicitud de Patente Norteamericana nº de serie
10/619.633 (Attorney Docket Nº ARC9, titulada "Recuperación de
Datos en Múltiples Trayectos A Partir de una Agrupación
Redundante", y la Solicitud de Patente Norteamericana nº de serie
10/619.648 (Attorney Docket Nº ARC9 titulada "RAID 3+3". La
presente solicitud está también relacionada con la Solicitud de
Patente Norteamericana pendiente también y cedida a la misma
cesionaria de nº de serie 10/600.593 (Attorney Docket Nº
YOR9-2003-0069US1).
El número máximo de fallos de una agrupación que
puede ser tolerado por un Código de Corrección de Error (ECC) o de
Cancelación, tal como un código de paridad, un código Winograd, un
código simétrico, un código Reed-Solomon, un código
EVENODD, o un derivado de un código EVENODD, es al menos la
distancia de Hamming mínima d de ECC menos uno, es decir, d - 1. El
presente invento mejora la distancia de Hamming mínima de un ECC
utilizando una operación, denominada aquí como una operación de
"calibrado", para proporcionar una "distancia efectiva"
que es mayor que la distancia de Hamming del ECC. Así, el número de
fallos que una agrupación puede tolerar, si un fallo es un fallo de
dispositivo o un error grave, es aumentado más allá de la distancia
mínima proporcionada por el ECC. Como se han usado aquí, los
términos "distancia efectiva" y "distancia mínima
efectiva" se refieren a uno más el número de fallos que puede
ser tolerado por una agrupación que utiliza una o más operaciones
de calibrado de acuerdo con el presente invento.
En lo que sigue, una operación de calibrado es
un proceso en la que un conjunto dentro de una agrupación es
seleccionado para donar un elemento a un conjunto receptor, y la
información del receptor es reconstruida sobre el elemento donado,
aumentando por ello la distancia mínima de la agrupación. Una
operación de calibrado puede ser realizada en un par de conjuntos
(i,j) cuando la distancia d_{i} > d_{j} + 2. Después de la
operación de calibrado, el conjunto donante bajará en la distancia
por 1. En contraste, el conjunto receptor aumentará en la distancia
en 1. Cuando una operación de calibrado puede ser realizada en todos
los conjuntos que están en la distancia de la agrupación mínima,
entonces la distancia de la agrupación mínima total será aumentada.
Una operación de calibrado puede ocurrir a distancias variables
dependiendo de la configuración de la agrupación.
La fig. 1a muestra un sistema de almacenamiento
ejemplar, indicado generalmente como 100, que comprende dos
agrupaciones de almacenamiento 102 y 103 que están conectadas a un
controlador de agrupación común 101. Las agrupaciones de
almacenamiento 102 y 103 comprenden múltiples unidades de
almacenamiento 104 y comunican con el controlador de agrupación 101
sobre la interfaz 105. El controlador de agrupación 101 comunica con
otros controladores y sistemas anfitriones sobre la interfaz 106.
Tal configuración permite que un controlador de agrupación se
comunique con múltiples agrupaciones de almacenamiento.
La fig. 1b muestra un sistema de almacenamiento
ejemplar, indicado generalmente como 150, que comprende dos
agrupaciones de almacenamiento 153 y 154, que están conectadas
respectivamente a diferentes controladores de agrupación 152 y 151.
La agrupación de almacenamiento 153 comunica con el controlador de
agrupación 152 sobre la interfaz 157, y la agrupación de
almacenamiento 154 comunica con el controlador de agrupación 151
sobre la interfaz 156. Los controladores de agrupación 151 y 152
comunican respectivamente con otros controladores de agrupación y
sistemas de almacenamiento sobre las interfaces 158 y 159. También
mostrada en la fig. 1b hay una conexión de comunicación 160 que
permite que los controladores de agrupación 151 y 152 se comuniquen
entre sí.
Los controladores de agrupación mostrados en las
figs. 1a y 1b pueden estar diseñados como controladores de hardware
o de software. El término controlador será usado aquí generalmente
para referirse a cualquiera de las configuraciones descritas
antes.
Muchas agrupaciones anamórficas pueden
beneficiarse del calibrado. La capacidad de una agrupación
anamórfica para beneficiarse de la operación de calibrado puede ser
verificada por inspección de combinaciones de fallos para la
agrupación. Por ejemplo, la fig. 3 muestra una agrupación anamórfica
ejemplar 300 que tiene nueve unidades de almacenamiento. Para este
ejemplo, la agrupación 300 usa un código simétrico (3 + 3) que es
MDS con n = 3, r = 3, y d = 4. La agrupación 300 está dispuesta
para tener tres elementos redundantes que pueden corregir
cualquiera de los tres elementos que han fallado de los seis
elementos en un conjunto. Tres conjuntos únicos, indicados
respectivamente como 1, 2 y 3, están dispuestos dentro de la
agrupación 300. Cualquiera de los tres fallos de las unidades de
almacenamiento no afectará más que a tres elementos de cualquier
conjunto. Así, la agrupación 300 tiene una distancia mínima D =
4.
Para ilustrar que una operación de calibrado de
acuerdo con el presente invento puede ser realizada para aumentar
la distancia mínima efectiva de la agrupación 300, hay sólo tres
disposiciones de tres fallos de unidades de almacenamiento que
necesitan consideración. La primera disposición de tres fallos de
unidades de almacenamiento está mostrada en la fig. 4, en la que
una X dentro de un bloque indica un fallo en la unidad de
almacenamiento. En esta disposición de fallo particular, dos
bloques de cada conjunto han fallado. Consiguientemente, cada
conjunto tiene aún una distancia mínima d = 2 y, por ello, la
agrupación 300 tiene una distancia mínima D = 2. Así, la agrupación
300, como se ha mostrado en la fig. 4, puede tolerar un fallo
adicional en la unidad de almacenamiento sin posible pérdida de
datos.
Una segunda disposición de tres fallos de
unidades de almacenamiento está mostrada en la fig. 5 en que una X
dentro de un bloque indica un fallo de unidad de almacenamiento. En
la segunda disposición de tres fallos de unidades de
almacenamiento, el conjunto 1 ha perdido tres elementos, el conjunto
2 ha perdido dos elementos y el conjunto 3 ha perdido un elemento.
Así, el conjunto 1 tiene la distancia mínima d = 1 y no puede
tolerar otros fallos de la unidad de almacenamiento sin pérdida de
datos. El conjunto 2 tiene la distancia mínima d = 2, y el conjunto
3 tiene la distancia mínima d = 3. Consiguientemente, la agrupación
300 tiene la distancia mínima D = 1.
Una operación de calibrado puede ser realizada
para la segunda disposición de tres fallos de unidades de
almacenamiento reconstruyendo los contenidos de uno de los
elementos perdidos en el conjunto 1 de una manera bien conocida
sobre uno de los elementos que no han fallado del conjunto 3. La
fig. 6 representa la agrupación de la fig. 5 después de realizar
una operación de calibrado. Los datos reconstruidos en la fig. 6
están subrayados. Aquí, el elemento del conjunto 3 en la unidad D9
ha sido donado al conjunto 1. Después de la operación de calibrado,
todos los conjuntos tienen la distancia mínima d = 2 y, por lo
tanto, la agrupación 300 tiene la distancia mínima D = 2. La
configuración de la agrupación después de la operación de calibrado
puede tolerar ahora otro fallo sin que se pierdan datos.
Una tercera disposición de tres fallos de
unidades de almacenamiento está mostrada en la fig. 7 en la que una
X en un bloque indica un fallo en la unidad de almacenamiento. En la
tercera disposición de tres fallos de las unidades de
almacenamiento, los conjuntos 1 y 2 han perdido cada uno tres
elementos, y tienen una distancia mínima d = 1. El conjunto 3, sin
embargo, no ha perdido ningún elemento y, consiguientemente, tiene
una distancia mínima d = 4. Una operación de calibrado puede ser
realizada para la tercera disposición de tres fallos de las
unidades de almacenamiento reconstruyendo el contenido de un
elemento perdido de cada uno de los conjuntos 1 y 2 (d = 1) de una
manera bien conocida en elementos diferentes del conjunto 3 (d =
4). Por ejemplo, el contenido del elemento 1 en la unidad de
almacenamiento D1 puede ser reconstruido en el elemento 3 del disco
D9, y el contenido del elemento 2 en el disco D1 reconstruido en el
elemento 3 del disco D4.
La fig. 8 representa la agrupación de la fig. 7
después de haber realizado una operación de calibrado. Los datos
reconstruidos en la fig. 8 están subrayados. El resultado será otra
vez que todos los conjuntos tienen la distancia mínima d = 2 y,
consiguientemente, la agrupación 300 tiene la distancia mínima D =
2. Después de la operación de calibrado, es importante que ninguna
unidad de almacenamiento contenga dos elementos del mismo conjunto.
Es decir, ninguno de los elementos del conjunto 3 almacenado en
unidades de almacenamiento D4-D6 es seleccionado
para reconstruir cualquiera de los elementos perdidos de conjunto 1
ya que cada una de las unidades de almacenamiento
D4-D6 contiene ya un elemento de conjunto 1. De
manera similar, ninguno de los elementos de conjunto 3 almacenado
en las unidades de almacenamiento D7-D9 es
seleccionado para reconstruir cualquiera de los elementos perdidos
de conjunto 2.
El calibrado proporciona así una técnica para
restaurar la distancia mínima de la agrupación 300 de la fig. 3
desde D = 1 a D = 2 después de cualquiera de los tres fallos de la
unidad de almacenamiento. Además, la distancia mínima efectiva de
la agrupación 300 ha sido aumentada desde d = 4 a d = 5, incluso
aunque el sistema de la agrupación 300 tenga el rendimiento de
escritura de un código que tiene la distancia d = 4.
La menor agrupación anamórfica para un código (3
+ 3) en que la distancia efectiva es aumentada es una agrupación de
nueve unidades de almacenamiento. Todas las agrupaciones que son
mayores de nueve unidades de almacenamiento tendrán también la
propiedad de una distancia efectiva aumentada cuando es usado un
código (3 + 3). Una agrupación de ocho unidades de almacenamiento
para un código (3 + 3) no tiene la propiedad de tener una distancia
efectiva aumentada. Un código (4 + 4) utilizado sobre doce unidades
de almacenamiento tiene también la propiedad de una distancia
efectiva aumentada. Una operación de calibrado, sin embargo, debería
ocurrir cuando la distancia de la agrupación mínima es d = 2.
Consiguientemente, se puede tolerar otro fallo en la unidad de
almacenamiento durante la operación de calibrado.
De acuerdo con una realización del invento, una
operación de calibrado puede ser realizada dentro de una agrupación,
entre agrupaciones separadas, o entre una agrupación y un grupo de
repuesto, denominada aquí como una operación de calibrado externa.
Aunque es posible una operación de calibrado realizada para un grupo
de repuesto, normalmente es mejor realizar una operación de
reconstrucción completa sobre un repuesto y realizar una operación
de calibrado solamente cuando el grupo de repuesto esté exhausto.
Esto es debido a que una operación de calibrado reconstruye
solamente algunos elementos de una unidad de almacenamiento que ha
fallado sobre una unidad de almacenamiento donada, mientras una
operación de repuesto reconstruye todo los elementos de una unidad
de almacenamiento que ha fallado sobre una unidad de almacenamiento
de repuesto.
Una operación de calibrado externa es diferente
de una operación de intercambio de paridad, tal como se ha descrito
por el documento US-A-7281177. Es
decir, una operación de calibrado es realizada en una base de
conjunto, mientras que una operación de intercambio de paridad es
realizada sobre una base de unidad de almacenamiento.
Para ilustrar las ventajas proporcionadas por
una operación de calibrado (agrupación a agrupación) externa de
acuerdo con el presente invento, se considera una agrupación
ejemplar 900 mostrada en la fig. 9. La agrupación 900 incluye ocho
unidades de almacenamiento D1 y usa un código simétrico (3 + 3). La
agrupación 900 incluye también cuatro conjuntos, indicados por los
números 1-4. Cada conjunto tiene seis elementos y
tiene la distancia d = 4. Como se ha mencionado previamente, una
operación de calibrado que es interna a una agrupación de ocho
unidades de almacenamiento que usa un código (3 + 3), tal como la
agrupación 900, no aumenta la distancia de Hamming mínima efectiva
de la agrupación ya que hay muy pocos conjuntos restantes sin fallo
para compensar el número de conjuntos que son afectados por
múltiples fallos de unidad.
En contraste, se considera un sistema de
agrupación ejemplar 1000, mostrado en la fig. 10, que comprende tres
agrupaciones de ocho unidades de almacenamiento,
1001-1003. Específicamente, la agrupación 1001
incluye unidades de almacenamiento D1-D8, la
agrupación 1002 incluye unidades de almacenamiento
D9-D16 y la agrupación 1003 incluye unidades de
almacenamiento D17-D24. Cada agrupación 1001
respectiva incluye también cuatro conjuntos dispuestos dentro de la
agrupación. Por ejemplo, la agrupación 1001 incluye los conjuntos
1-4, la agrupación 1002 incluye los conjuntos
5-8 y la agrupación 1003 incluye los conjuntos
9-12.
Se supone que después de cualquiera de los tres
fallos de la unidad de almacenamiento, una operación de intercambio
de paridad, tal como se ha descrito en el documento
US-A-7281177, es usada para asegurar
que cada agrupación 1001 tiene una unidad de almacenamiento que ha
fallado. Los resultados de una operación de intercambio de paridad
están representados, por ejemplo, por las unidades de almacenamiento
D1, D9 y D17 habiéndose mostrado que tienen X dentro de los bloques
de la unidad de almacenamiento. Se supone además que un cuarto fallo
en la unidad de almacenamiento ocurre subsiguientemente a la
operación de intercambio de paridad. Un cuarto fallo en la unidad
de almacenamiento está representado, por ejemplo, por la unidad de
almacenamiento D2 en la agrupación 1001 que se ha mostrado que
tiene X dentro de los bloques de la unidad de almacenamiento D2.
Después del cuarto fallo en la unidad de almacenamiento, las
agrupaciones 1001, 1002 y 1003 tienen respectivamente las distancias
D = (2, 3, 3). Debería comprenderse que otra unidad de
almacenamiento distinta de la unidad de almacenamiento D2 podría
fallar como el cuarto fallo en la unidad de almacenamiento y un
procedimiento que es similar al procedimiento descrito más abajo
sería realizado para aumentar la distancia efectiva del sistema de
almacenamiento.
Los conjuntos 1, 2 y 3 en la agrupación 1001 son
ahora solamente la distancia d = 2. Una operación de calibrado que
es interna a la agrupación 1001 fallará debido a que se requieren al
menos tres elementos que tienen la distancia d = 4 para aumentar la
distancia mínima de la agrupación 1001 desde 2 a 3. Solamente el
conjunto 4 en la agrupación 1001 tiene la distancia d = 4. Sin
embargo, una operación de calibrado externa entre agrupaciones
permite que la distancia mínima de la agrupación 1001 sea aumentada
de 2 a 3 sin cambiar las distancias mínimas de las agrupaciones
1002 y 1003. Para conseguir esto, el contenido para uno de los
elementos perdidos de cada uno de los conjuntos 1 es reconstruido
de una manera bien conocida sobre elementos de otros conjuntos que
están aún a la distancia d = 4, tal como el conjunto 4 en la
agrupación 1001, el conjunto 8 en la agrupación 1002 y el conjunto
12 en la agrupación 1003.
La fig. 11 representa el sistema de agrupación
1000 de la fig. 10 después de realizar una operación de calibrado
externa de acuerdo con el presente invento. Los datos reconstruidos
en la fig. 11 están subrayados. Específicamente, un elemento de
conjunto 3 es seleccionado para ser reconstruido sobre el conjunto 4
dentro de la unidad de almacenamiento D3. Un elemento de conjunto 2
es seleccionado para ser reconstruido sobre el conjunto 8 dentro de
la unidad de almacenamiento D10. Finalmente un elemento de conjunto
1 es seleccionado para ser reconstruido sobre la operación 12
dentro de la unidad de almacenamiento D17.
Cuando un elemento es seleccionado en un
conjunto donante, la unidad de almacenamiento que contiene el
elemento seleccionado no puede contener un elemento del conjunto
receptor. Por ejemplo, un elemento del conjunto 4 contenido en la
unidad de almacenamiento D7 o en la unidad de almacenamiento D8
puede ser seleccionado para reconstruir un elemento que ha fallado
del conjunto 1 ya que ambas unidades de almacenamiento D7 y D8 no
contienen elementos del conjunto 1. De manera similar, un elemento
del conjunto 4 que está contenido en cualquiera de las unidades de
almacenamiento D5 o D6 puede ser seleccionado para reconstruir un
elemento que ha fallado del conjunto 2 ya que ambas unidades de
almacenamiento D7 y D8 no contienen elementos de conjunto D2.
Finalmente, un elemento del conjunto 4 que está contenido en
cualquiera de las unidades de almacenamiento D3 o D4 puede ser
seleccionado para reconstruir un elemento que ha fallado del
conjunto 3 ya que ambas unidades de almacenamiento D3 o D4 no
contienen elementos de conjunto 3. Para los propósitos de este
ejemplo, se supone que un elemento de conjunto 4 contenido en la
unidad de almacenamiento D3 es seleccionado para ser un elemento
donante para reconstruir un elemento de conjunto 3.
Cualquiera de los elementos de conjunto 8, que
tiene d = 4, podría ser seleccionado para reconstruir un elemento
que ha fallado de cualquiera de las listas restantes, cada una de
las cuales tiene d = 2, y cualquiera de los elementos de conjunto
12, que tiene d = 4, podría ser seleccionado para reconstruir un
elemento que ha fallado del último conjunto restante que tiene d =
2. Para propósitos de este ejemplo ilustrativo, se supone que un
elemento de conjunto 8 contenido en la unidad de almacenamiento D11
es seleccionado para ser un elemento donante para reconstruir un
elemento de conjunto 2, y que un elemento de conjunto 12 contenido
en la unidad de almacenamiento D19 es seleccionado para ser un
elemento donante para reconstruir un elemento de conjunto 1. Para
cada una de las selecciones de calibrado de este ejemplo ilustrativo
anterior a la operación de calibrado, un conjunto donante tenía la
distancia d = 4, y un conjunto receptor (es decir, conjuntos 1)
tenía la distancia d = 2.
El resultado neto de la operación de calibrado
externa es que el sistema de agrupación 1000 tiene la distancia
mínima D = 3 después de cuatro fallos. En contraste, la distancia
mínima habría sido solamente de 2 usando solamente una operación de
intercambio de paridad, tal como se ha descrito por la solicitud de
patente pendiente también de nº de serie (Attorney Docket Nº
ARC9-2003-0015-US1).
Consiguientemente, cuando una operación de calibrado externa es
utilizada para el sistema de agrupación 1000, son requeridos cinco
fallos para que el sistema de agrupación 1000 tenga una distancia
mínima de d = 2. Este es el mismo resultado para un sistema de
agrupación de 24 unidades que están dispuestas como cuatro
agrupaciones de seis unidades y en las que cada agrupación usa
solamente una operación de intercambio de paridad como se ha
descrito por la solicitud de patente también pendiente de nº de
serie (Attorney Docket Nº
ARC9-2003-0015-US1).
Así, una operación de calibrado en combinación con una operación de
intercambio de paridad proporciona que la fiabilidad del sistema es
independiente de la configuración de la agrupación.
e calibrado generalizada en combinación con una
operación de intercambio de paridad puede continuar con cada fallo
adicional de la unidad de almacenamiento. Los elementos que han
fallado son reconstruidos sobre elementos supervivientes de tal
manera que la distancia mínima para cada agrupación es maximizada,
como se ha descrito antes. En el sistema de agrupación ejemplar de
24 unidades de las figs. 9 y 10, se requieren ocho fallos de la
unidad de almacenamiento para una distancia mínima de d = 2, ya no
es posible realizar operaciones de intercambio de paridad u
operaciones de calibrado para aumentar la distancia efectiva del
sistema. Consiguientemente, otros dos fallos pueden dar como
resultado una pérdida de datos.
En el tiempo, las operaciones de calibrado
generalizada resultan en conjuntos que ya no son locales a una
agrupación dada. Así, la selección de un conjunto donante puede ser
realizada como seleccionando un elemento donante.
Una vez que una unidad de repuesto resulta
disponible, tal como a través del mantenimiento, puede ser asignada
para reemplazar cualquiera de las unidades que han fallado. Es
preferible reconstruir elementos de los conjuntos con las menores
distancias mínimas sobre la unidad de repuesto. Se considera el
ejemplo de la fig. 12. La agrupación 1200 incluye diez unidades de
almacenamiento D1-D10 y usa un código simétrico (3 +
3). La agrupación 1200 incluye también cinco conjuntos, indicados
por los números 1. Cada conjunto tiene seis elementos y tiene la
distancia d = 4. Tres unidades de almacenamiento, D1, D2 y D4 han
sido mostradas como que han fallado, y un elemento de conjunto 1 ha
sido reconstruido a través de una operación de calibrado sobre un
elemento de conjunto 4 en la unidad D10, y un elemento de conjunto
4 ha sido reconstruido a través de una operación de calibrado sobre
un segundo elemento de conjunto 5 en la unidad D8. En este punto,
los conjuntos 1, 2, 4 y 5 tienen todos la distancia d = 2, y el
conjunto 3 tiene la distancia d = 3. Si un repuesto es hecho
subsiguientemente disponible para la agrupación 1200, la información
de los conjuntos a la distancia d = 2 debería ser reconstruida
sobre el repuesto. Los elementos para reconstruir sobre el repuesto
deberían ser elegidos del conjunto de elementos no presentes
actualmente en el conjunto. Por ejemplo, se supone que el elemento
de conjunto 1 en la unidad D2 fue reconstruido sobre la unidad D8.
Los elementos que han de ser reconstruidos sobre el repuesto no
pueden incluir estos elementos reconstruidos de los conjuntos 1 y 4.
Una vez que los elementos que han de ser reconstruidos han sido
seleccionados, la información es reconstruida sobre el repuesto de
una manera bien conocida.
El criterio principal para seleccionar un
elemento donante está basado en seleccionar un elemento donante que
tiene el menor impacto sobre la fiabilidad del conjunto donante. Un
criterio secundario está basado en seleccionar el elemento de
almacenamiento que tiene el menor impacto sobre rendimiento, tal
como elemento con el cálculo de redundancia más costoso. En el
ejemplo de la fig. 12, los elementos de conjunto 5 fueron elegidos
principalmente debido a que el conjunto 5 tenía la mayor distancia,
y en segundo lugar debido a que D8 y D10 tenían los cálculos de
paridad más costosos. D9 podría no ser elegido para reconstruir un
elemento de conjunto 4, debido a que D9 ya contenía un elemento de
conjunto 4. El criterio principal para seleccionar la información
que ha de ser reconstruida está basado en el conjunto de información
que proporciona el mayor aumento de fiabilidad. Un criterio
secundario es seleccionar el conjunto de información que proporciona
el mejor rendimiento de agrupación después de la operación de
reconstrucción. En el ejemplo de la fig. 12, los elementos de
conjuntos 1 y 4 fueron elegidos para ser reconstruidos basados
principalmente en sus distancias restantes, y en segundo lugar
debido a que la reconstrucción de los elementos elegidos maximiza el
rendimiento después de la operación de calibrado.
Hay además un efecto importante de calibrado
generalizado. En el ejemplo de las figs. 9 y 10, se realizó una
operación de calibrado generalizada entre agrupaciones cuando el
conjunto receptor estaba a una distancia d = 2, mientras que se
realizó una operación de calibrado interna sobre la agrupación de
nueve unidades (figs. 6 y 7), cuando el conjunto receptor estaba a
una distancia d = 1. Así, se requerían dos fallos dentro de los
conjuntos implicados en la operación de calibrado externa para
pérdida de datos durante la operación de calibrado externa.
Calibrado un elemento desde un conjunto donante
a un conjunto receptor requiere que el sistema de almacenamiento
sea capaz de asignar elementos de un conjunto a otro conjunto.
Cuando los conjuntos donado y receptor están conectados a un
controlador 101 de agrupaciones como una, como se ha mostrado en la
fig. 1a entonces el controlador 101 puede realizar esta operación
interiormente. Cuando los conjuntos donante y receptor están
conectados a controladores separados 151 y 152, como se ha mostrado
en la fig. 1b, entonces los controladores 151 y 152 intercambian
información. Por ejemplo los controladores podrían exponer las
unidades individuales sobre la conexión de comunicación 160, tal
como en la manera de una configuración de agrupaciones Solo un Grupo
de Discos ("Just a Bunch of Disks") (JBOD). Alternativamente,
los controladores podrían intercambiar información relativa a los
datos que han de ser leídos y escritos desde las posiciones en las
unidades de almacenamiento implicadas.
La técnica de calibrado ha sido descrita para
agrupaciones anamórficas. El calibrado puede ser usado con conjuntos
de agrupaciones que tienen la distancia mínima de d = 3 o más. El
calibrado generalizado, a pesar de ello, trabaja mejor con
agrupaciones simétricas.
El calibrado puede ser usado más allá
simplemente aumentando la distancia mínima de un sistema de
almacenamiento. Muchos otros factores pueden ser incluidos en la
determinación sobre si realizar calibrado y elegir donantes y
receptores. Por ejemplo, las probabilidades de fallo individual de
componentes cuando no son uniformes, las combinaciones de fallos
que conducen a pérdida de datos, y los efectos sobre el rendimiento
del sistema pueden ser todos considerados. En tales casos, la
distancia mínima del sistema podría permanecer sin cambios después
del calibrado.
Aunque el presente invento ha sido descrito en
términos de agrupaciones de almacenamiento y formadas a partir de
unidades de almacenamiento de HDD, el presente invento es aplicable
a sistemas de almacenamiento formados a partir de agrupaciones u
otros dispositivos de memoria, tales como dispositivos de
almacenamiento de Memoria de Acceso Aleatorio (RAM) (tanto volátil
como no volátil), dispositivos de almacenamiento óptico, y
dispositivos de almacenamiento en cinta. Adicionalmente, es
adecuado para sistemas de almacenamiento virtuales, tales como
agrupaciones construidas a partir de almacenamiento unido a la red.
Es además aplicable a cualquier sistema redundante en el que hay
alguna información de estado que asocia un componente redundante a
un subconjunto de componentes particular, y que la información de
estado puede ser transferida usando una operación de donación.
Aunque el anterior invento ha sido descrito en
algún detalle con propósitos de claridad de comprensión, las
actuales realizaciones han de ser consideradas como ilustrativas y
no restrictivas, y el invento no ha de estar limitado a los
detalles dados en ellas, sino que puede ser modificado dentro del
marco de las reivindicaciones adjuntas.
Claims (15)
-
\global\parskip0.950000\baselineskip
1. Un método para aumentar una tolerancia de error de una agrupación anamórfica de m unidades de almacenamiento, comprendiendo el método las operaciones de: almacenar k conjuntos a través de la agrupación de m unidades de almacenamiento, teniendo cada conjunto una pluralidad de elementos, formando cada conjunto un código de cancelación o de corrección de error que tiene una distancia de Hamming mínima d, teniendo cada conjunto n+r elementos en los que n es el número de elementos de datos, r es el número de elementos redundantes, de tal modo que m > n+r y estando almacenado cada elemento respectivo de un conjunto sobre una unidad de almacenamiento diferente; seleccionar un conjunto donante y un elemento en el conjunto donante cuando la diferencia entre la distancia mínima del conjunto donante y la distancia mínima de un conjunto receptor es mayor o igual a 2, siendo almacenado el elemento seleccionado en el conjunto donante sobre una unidad de almacenamiento que no tiene elementos del conjunto receptor; y reconstruir el contenido de un elemento perdido del conjunto receptor sobre el elemento seleccionado del conjunto donante. - 2. El método según la reivindicación 1ª, en el que la distancia de Hamming mínima del conjunto receptor es d \geq 2 antes de la operación de selección del elemento en el conjunto donante.
- 3. El método según la reivindicación 1ª, que comprende además una operación de indicar a las unidades de almacenamiento que almacenan el conjunto donante que el elemento seleccionado ha sido donado antes de la operación de reconstrucción del elemento perdido del conjunto receptor sobre el elemento seleccionado.
- 4. El método según cualquiera de las reivindicaciones precedentes, en el que el conjunto donante es además seleccionado basado en un impacto de rendimiento mínimo sobre la agrupación.
- 5. El método según cualquiera de las reivindicaciones precedentes, que comprende además una operación de seleccionar la información de receptor basado en un rendimiento mejorado de la agrupación.
- 6. El método según cualquiera de las reivindicaciones precedentes, en el que el código de cancelación o de corrección de error es uno de entre un código de paridad; un código Winograd, un código simétrico; un código Reed-Solomon; un código EVENODD; o un derivado de un código EVENODD.
- 7. El método según cualquiera de las reivindicaciones precedentes, en el que cuando un elemento en el conjunto donante falla durante la operación de reconstrucción de al menos una parte de información de receptor a partir del conjunto receptor sobre el elemento seleccionado, el método comprende además las operaciones de: terminar la operación de reconstrucción de al menos una parte de la información de receptor a partir del conjunto receptor sobre el elemento seleccionado; seleccionar un segundo conjunto donante de la pluralidad de conjuntos cuando una diferencia entre una distancia mínima del segundo conjunto donante y una distancia mínima del segundo conjunto receptor es mayor o igual a 2; seleccionar un elemento donante en el segundo conjunto donante; y reconstruir al menos una parte de información de receptor perdida a partir del conjunto receptor sobre el elemento seleccionado en el segundo conjunto donante.
- 8. El método según cualquiera de las reivindicaciones precedentes, en el que cuando un elemento de repuesto resulta disponible, el método comprende además una operación de asignar el elemento de repuesto a una unidad de almacenamiento seleccionada.
- 9. Un sistema de almacenamiento datos, que comprende: una agrupación anamórfica de m unidades de almacenamiento, siendo almacenados k conjuntos a través de la agrupación de m unidades de almacenamiento, teniendo cada conjunto una pluralidad de elementos, formando cada conjunto un código de cancelación o de corrección de error que tiene una distancia de Hamming mínima d, teniendo cada conjunto n+r elementos en los que n es el número de elementos de datos, r es el número de elementos redundantes, de tal modo que m > n+r y siendo almacenado cada elemento respectivo de un conjunto sobre una unidad de almacenamiento diferente; y un controlador de agrupación de sistema que selecciona un conjunto donante y un elemento en un conjunto donante cuando la diferencia entre la distancia mínima del conjunto donante y la distancia mínima de un conjunto receptor es mayor o igual a 2, siendo almacenado el elemento seleccionado en el conjunto donante sobre una unidad de almacenamiento que no tiene elementos del conjunto receptor; el controlador de agrupación de sistema que reconstruye el contenido de un elemento perdido del conjunto receptor sobre el elemento seleccionado del conjunto donante.
- 10. El sistema de almacenamiento de datos según la reivindicación 9ª, en el que la distancia de Hamming mínima del conjunto receptor es d > 2 antes de que el controlador de agrupación del sistema seleccione el elemento en el conjunto donante.
- 11. El sistema de almacenamiento de datos según la reivindicación 9ª o 10ª, en el que el controlador de agrupación de sistema indica a las unidades de almacenamiento que almacenan el conjunto donante que el elemento seleccionado ha sido donado antes de que el elemento perdido del conjunto receptor sea reconstruido sobre el elemento seleccionado.
- 12. El sistema de almacenamiento de datos según cualquiera de las reivindicaciones 9ª a 11ª, en el que el controlador de agrupaciones del sistema selecciona el conjunto donante basado además sobre un impacto mínimo de rendimiento sobre la agrupación.
\global\parskip1.000000\baselineskip
- 13. El sistema de almacenamiento de datos según cualquiera de las reivindicaciones 9ª a 12ª, en el que el controlador de agrupación del sistema selecciona la información de receptor basado en un rendimiento mejorado de la agrupación.
- 14. El sistema de almacenamiento de datos según cualquiera de las reivindicaciones 9ª a 13ª, en el que cuando un elemento en el conjunto donante falla cuando el controlador de agrupación de sistema está reconstruyendo al menos una parte de información de receptor a partir del conjunto receptor sobre el elemento seleccionado, el controlador de agrupación del sistema termina la reconstrucción de la información de receptor a partir del conjunto receptor sobre el elemento seleccionado, selecciona un segundo conjunto donante a partir de la pluralidad de conjuntos cuando una diferencia entre una distancia mínima del segundo conjunto donante y una distancia mínima del segundo conjunto receptor es mayor o igual a 2, selecciona un elemento donante en el segundo conjunto donante, y reconstruye al menos una parte de información de receptor perdida a partir del conjunto receptor sobre el elemento seleccionado en el segundo conjunto donante.
- 15. El sistema de almacenamiento de datos según cualquiera de las reivindicaciones 9ª a 14ª, en el que cuando un elemento de repuesto resulta disponible, el controlador de agrupación del sistema asigna el elemento de repuesto a una unidad de almacenamiento seleccionada.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US619641 | 2003-07-14 | ||
| US10/619,641 US7533325B2 (en) | 2003-07-14 | 2003-07-14 | Anamorphic codes |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2318323T3 true ES2318323T3 (es) | 2009-05-01 |
Family
ID=34062605
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES04766140T Expired - Lifetime ES2318323T3 (es) | 2003-07-14 | 2004-07-07 | Equilibrio de recursos redundantes en una agrupacion de unidades de almacenamiento. |
Country Status (12)
| Country | Link |
|---|---|
| US (2) | US7533325B2 (es) |
| EP (1) | EP1644851B1 (es) |
| JP (1) | JP4756704B2 (es) |
| KR (1) | KR101054814B1 (es) |
| CN (1) | CN100465908C (es) |
| AT (1) | ATE423350T1 (es) |
| CA (1) | CA2532997C (es) |
| DE (1) | DE602004019534D1 (es) |
| ES (1) | ES2318323T3 (es) |
| SG (1) | SG145728A1 (es) |
| TW (1) | TWI317475B (es) |
| WO (1) | WO2005006215A2 (es) |
Families Citing this family (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6730883B2 (en) * | 2002-10-02 | 2004-05-04 | Stratagene | Flexible heating cover assembly for thermal cycling of samples of biological material |
| JP2011199414A (ja) * | 2010-03-17 | 2011-10-06 | Toshiba Corp | 素材収録装置及び素材収録方法 |
| US8392805B2 (en) | 2010-07-15 | 2013-03-05 | Hewlett-Packard Development Company, L. P. | Non-MDS erasure codes for storage systems |
| US8433979B2 (en) * | 2011-02-28 | 2013-04-30 | International Business Machines Corporation | Nested multiple erasure correcting codes for storage arrays |
| US8874995B2 (en) * | 2012-02-02 | 2014-10-28 | International Business Machines Corporation | Partial-maximum distance separable (PMDS) erasure correcting codes for storage arrays |
| CN103577274B (zh) * | 2012-07-31 | 2016-07-06 | 国际商业机器公司 | 管理存储器阵列的方法和装置 |
| CN102929743A (zh) * | 2012-11-28 | 2013-02-13 | 中国人民解放军国防科学技术大学 | 具有软错误容错功能的一级缓存数据存储方法及装置 |
| TWI461901B (zh) | 2012-12-10 | 2014-11-21 | Ind Tech Res Inst | 資料儲存與重建的方法與系統 |
| US9594634B2 (en) * | 2014-06-02 | 2017-03-14 | Intel Corporation | Techniques to efficiently compute erasure codes having positive and negative coefficient exponents to permit data recovery from more than two failed storage units |
| WO2017039274A1 (ko) * | 2015-08-30 | 2017-03-09 | 엘지전자 주식회사 | 무선 통신 시스템에서 클러스터 기반 협력 전송 방법 및 이를 위한 장치 |
| EP3364541B1 (en) | 2016-12-24 | 2019-08-14 | Huawei Technologies Co., Ltd. | Storage controller, data processing chip, and data processing method |
| CN114601378A (zh) | 2021-07-16 | 2022-06-10 | 北京石头世纪科技股份有限公司 | 基站及清洁机器人系统 |
Family Cites Families (36)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3949208A (en) * | 1974-12-31 | 1976-04-06 | International Business Machines Corporation | Apparatus for detecting and correcting errors in an encoded memory word |
| US5148432A (en) | 1988-11-14 | 1992-09-15 | Array Technology Corporation | Arrayed disk drive system and method |
| US5680574A (en) | 1990-02-26 | 1997-10-21 | Hitachi, Ltd. | Data distribution utilizing a master disk unit for fetching and for writing to remaining disk units |
| US5134619A (en) * | 1990-04-06 | 1992-07-28 | Sf2 Corporation | Failure-tolerant mass storage system |
| US5579475A (en) | 1991-02-11 | 1996-11-26 | International Business Machines Corporation | Method and means for encoding and rebuilding the data contents of up to two unavailable DASDS in a DASD array using simple non-recursive diagonal and row parity |
| US5258984A (en) | 1991-06-13 | 1993-11-02 | International Business Machines Corporation | Method and means for distributed sparing in DASD arrays |
| US5301297A (en) | 1991-07-03 | 1994-04-05 | Ibm Corp. (International Business Machines Corp.) | Method and means for managing RAID 5 DASD arrays having RAID DASD arrays as logical devices thereof |
| US5257391A (en) | 1991-08-16 | 1993-10-26 | Ncr Corporation | Disk controller having host interface and bus switches for selecting buffer and drive busses respectively based on configuration control signals |
| US5506977A (en) | 1991-12-17 | 1996-04-09 | Dell Usa, L.P. | Method and controller for minimizing reads during partial stripe write operations to a disk drive |
| US5398253A (en) | 1992-03-11 | 1995-03-14 | Emc Corporation | Storage unit generation of redundancy information in a redundant storage array system |
| US5555404A (en) * | 1992-03-17 | 1996-09-10 | Telenor As | Continuously available database server having multiple groups of nodes with minimum intersecting sets of database fragment replicas |
| US5666511A (en) | 1992-10-08 | 1997-09-09 | Fujitsu Limited | Deadlock suppressing schemes in a raid system |
| US6269453B1 (en) | 1993-06-29 | 2001-07-31 | Compaq Computer Corporation | Method for reorganizing the data on a RAID-4 or RAID-5 array in the absence of one disk |
| US5485571A (en) * | 1993-12-23 | 1996-01-16 | International Business Machines Corporation | Method and apparatus for providing distributed sparing with uniform workload distribution in failures |
| US5862158A (en) * | 1995-11-08 | 1999-01-19 | International Business Machines Corporation | Efficient method for providing fault tolerance against double device failures in multiple device systems |
| KR100275900B1 (ko) | 1996-09-21 | 2000-12-15 | 윤종용 | 알에이아이디 서브시스템에 있어서 분할패러티 예비 디스크 구현방법 |
| US6161165A (en) | 1996-11-14 | 2000-12-12 | Emc Corporation | High performance data path with XOR on the fly |
| JP3595099B2 (ja) * | 1997-03-17 | 2004-12-02 | 富士通株式会社 | デバイスアレイ・システム |
| US6154853A (en) | 1997-03-26 | 2000-11-28 | Emc Corporation | Method and apparatus for dynamic sparing in a RAID storage system |
| US6028933A (en) * | 1997-04-17 | 2000-02-22 | Lucent Technologies Inc. | Encrypting method and apparatus enabling multiple access for multiple services and multiple transmission modes over a broadband communication network |
| US5937428A (en) | 1997-08-06 | 1999-08-10 | Lsi Logic Corporation | Method for host-based I/O workload balancing on redundant array controllers |
| US6081812A (en) * | 1998-02-06 | 2000-06-27 | Ncr Corporation | Identifying at-risk components in systems with redundant components |
| US6353895B1 (en) | 1998-02-19 | 2002-03-05 | Adaptec, Inc. | RAID architecture with two-drive fault tolerance |
| US6138125A (en) | 1998-03-31 | 2000-10-24 | Lsi Logic Corporation | Block coding method and system for failure recovery in disk arrays |
| US6279138B1 (en) | 1998-08-04 | 2001-08-21 | International Business Machines Corporation | System for changing the parity structure of a raid array |
| US7000069B2 (en) | 1999-04-05 | 2006-02-14 | Hewlett-Packard Development Company, L.P. | Apparatus and method for providing very large virtual storage volumes using redundant arrays of disks |
| US6275898B1 (en) | 1999-05-13 | 2001-08-14 | Lsi Logic Corporation | Methods and structure for RAID level migration within a logical unit |
| US6530004B1 (en) | 2000-06-20 | 2003-03-04 | International Business Machines Corporation | Efficient fault-tolerant preservation of data integrity during dynamic RAID data migration |
| US6883131B2 (en) * | 2001-09-28 | 2005-04-19 | Sun Microsystems, Inc. | XOR processing incorporating error correction code data protection |
| US7346831B1 (en) * | 2001-11-13 | 2008-03-18 | Network Appliance, Inc. | Parity assignment technique for parity declustering in a parity array of a storage system |
| US20030149750A1 (en) * | 2002-02-07 | 2003-08-07 | Franzenburg Alan M. | Distributed storage array |
| US7350126B2 (en) | 2003-06-23 | 2008-03-25 | International Business Machines Corporation | Method for constructing erasure correcting codes whose implementation requires only exclusive ORs |
| US7281177B2 (en) | 2003-07-14 | 2007-10-09 | International Business Machines Corporation | Autonomic parity exchange |
| US7379974B2 (en) | 2003-07-14 | 2008-05-27 | International Business Machines Corporation | Multipath data retrieval from redundant array |
| US7254754B2 (en) | 2003-07-14 | 2007-08-07 | International Business Machines Corporation | Raid 3+3 |
| US7970994B2 (en) * | 2008-03-04 | 2011-06-28 | International Business Machines Corporation | High performance disk array rebuild |
-
2003
- 2003-07-14 US US10/619,641 patent/US7533325B2/en not_active Expired - Fee Related
-
2004
- 2004-07-07 ES ES04766140T patent/ES2318323T3/es not_active Expired - Lifetime
- 2004-07-07 AT AT04766140T patent/ATE423350T1/de not_active IP Right Cessation
- 2004-07-07 JP JP2006519917A patent/JP4756704B2/ja not_active Expired - Fee Related
- 2004-07-07 WO PCT/EP2004/051382 patent/WO2005006215A2/en not_active Ceased
- 2004-07-07 CA CA2532997A patent/CA2532997C/en not_active Expired - Fee Related
- 2004-07-07 SG SG200805903-2A patent/SG145728A1/en unknown
- 2004-07-07 DE DE602004019534T patent/DE602004019534D1/de not_active Expired - Lifetime
- 2004-07-07 EP EP04766140A patent/EP1644851B1/en not_active Expired - Lifetime
- 2004-07-07 CN CNB2004800204003A patent/CN100465908C/zh not_active Expired - Fee Related
- 2004-07-07 KR KR1020067000036A patent/KR101054814B1/ko not_active Expired - Fee Related
- 2004-07-08 TW TW093120447A patent/TWI317475B/zh not_active IP Right Cessation
-
2009
- 2009-01-23 US US12/358,593 patent/US8386891B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| EP1644851B1 (en) | 2009-02-18 |
| WO2005006215A3 (en) | 2006-08-17 |
| CA2532997C (en) | 2012-07-24 |
| JP2007529061A (ja) | 2007-10-18 |
| KR101054814B1 (ko) | 2011-08-05 |
| US20050015656A1 (en) | 2005-01-20 |
| JP4756704B2 (ja) | 2011-08-24 |
| TWI317475B (en) | 2009-11-21 |
| CN100465908C (zh) | 2009-03-04 |
| CN1898650A (zh) | 2007-01-17 |
| EP1644851A2 (en) | 2006-04-12 |
| WO2005006215A2 (en) | 2005-01-20 |
| CA2532997A1 (en) | 2005-01-20 |
| DE602004019534D1 (de) | 2009-04-02 |
| US7533325B2 (en) | 2009-05-12 |
| TW200515141A (en) | 2005-05-01 |
| SG145728A1 (en) | 2008-09-29 |
| KR20060037319A (ko) | 2006-05-03 |
| US20090132890A1 (en) | 2009-05-21 |
| US8386891B2 (en) | 2013-02-26 |
| ATE423350T1 (de) | 2009-03-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8386891B2 (en) | Anamorphic codes | |
| US10884889B2 (en) | Allocating part of a raid stripe to repair a second raid stripe | |
| JP4516846B2 (ja) | ディスク・アレイ・システム | |
| US8839028B1 (en) | Managing data availability in storage systems | |
| US5303244A (en) | Fault tolerant disk drive matrix | |
| US6453428B1 (en) | Dual-drive fault tolerant method and system for assigning data chunks to column parity sets | |
| US7386757B2 (en) | Method and apparatus for enabling high-reliability storage of distributed data on a plurality of independent storage devices | |
| US7149847B2 (en) | RAID 6 disk array architectures | |
| CN1106560A (zh) | 容错存储器系统 | |
| US20080016416A1 (en) | Autonomic Parity Exchange | |
| Jian et al. | Parity helix: Efficient protection for single-dimensional faults in multi-dimensional memory systems | |
| US20110239042A1 (en) | Method to establish redundancy and fault tolerance better than raid level 6 without using parity | |
| US6792391B1 (en) | Method and system for three disk fault tolerance in a disk array | |
| US7103716B1 (en) | RAID 6 disk array with prime number minus one disks | |
| CN108780411B (zh) | 数据存储系统中的自主奇偶交换 | |
| JP3676793B2 (ja) | ディスクアレイ装置 | |
| EP0481128B1 (en) | Data processor system based on an (N, k) symbol code having symbol error correctibility and plural error mendability | |
| Xie et al. | V 2-code: A new non-mds array code with optimal reconstruction performance for raid-6 | |
| Wang et al. | Combinatorial constructions of multi-erasure-correcting codes with independent parity symbols for storage systems |