[go: up one dir, main page]

KR101756136B1 - A fault tolerant method for a hierarchical system - Google Patents

A fault tolerant method for a hierarchical system Download PDF

Info

Publication number
KR101756136B1
KR101756136B1 KR1020160007955A KR20160007955A KR101756136B1 KR 101756136 B1 KR101756136 B1 KR 101756136B1 KR 1020160007955 A KR1020160007955 A KR 1020160007955A KR 20160007955 A KR20160007955 A KR 20160007955A KR 101756136 B1 KR101756136 B1 KR 101756136B1
Authority
KR
South Korea
Prior art keywords
nodes
node
fault tolerance
information
data
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 - Fee Related
Application number
KR1020160007955A
Other languages
Korean (ko)
Inventor
박기현
우민우
Original Assignee
계명대학교 산학협력단
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by 계명대학교 산학협력단 filed Critical 계명대학교 산학협력단
Priority to KR1020160007955A priority Critical patent/KR101756136B1/en
Application granted granted Critical
Publication of KR101756136B1 publication Critical patent/KR101756136B1/en
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

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/16—Error detection or correction of the data by redundancy in hardware
    • G06F11/20—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
    • G06F11/2002—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements where interconnections or communication control functionality are redundant
    • G06F11/2007—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements where interconnections or communication control functionality are redundant using redundant communication media
    • G06F11/201—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements where interconnections or communication control functionality are redundant using redundant communication media between storage system components
    • 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/14—Error detection or correction of the data by redundancy in operation
    • G06F11/1402—Saving, restoring, recovering or retrying
    • G06F11/1446—Point-in-time backing up or restoration of persistent data
    • G06F11/1448—Management of the data involved in backup or backup restore
    • 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/14—Error detection or correction of the data by redundancy in operation
    • G06F11/1402—Saving, restoring, recovering or retrying
    • G06F11/1446—Point-in-time backing up or restoration of persistent data
    • G06F11/1458—Management of the backup or restore process
    • 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/16—Error detection or correction of the data by redundancy in hardware
    • G06F11/20—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
    • G06F11/202—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements where processing functionality is redundant
    • G06F11/2023—Failover techniques
    • 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/16—Error detection or correction of the data by redundancy in hardware
    • G06F11/20—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
    • G06F11/2053—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements where persistent mass storage functionality or persistent mass storage control functionality is redundant

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Quality & Reliability (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Small-Scale Networks (AREA)

Abstract

본 발명은 계층적 구조를 갖는 시스템의 정보 결함허용 방법에 관한 것으로서, 보다 구체적으로는 서버(100)에서, (1) 시스템 제어정보를 분산 저장 가능한 하위의 노드 수를 확인하고, 상기 확인된 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하며, 상기 선택된 결함허용 방법에 따라 시스템 제어정보가 상기 시스템 내의 분산 저장 가능한 노드들에 분산 저장되도록 하는 단계(S100), (2) 상기 시스템 제어정보를 분산 저장하고 있는 노드들 중, 원본 데이터에 결함이 발생한 노드로부터 원본 데이터 복구를 요청받는 단계(S200), 및 (3) 상기 단계 (1)에서 선택된 결함허용 방법에 따라 원본 데이터가 복구되도록 하는 단계(S300)를 포함하는 것을 그 구성상의 특징으로 한다.
본 발명에서 제안하고 있는 계층적 구조를 갖는 시스템의 정보 결함허용 방법에 따르면, 계층적 구조를 갖는 시스템에서 시스템 제어정보를 분산 저장 가능한 서버 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법, 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하고, 선택된 결함허용 방법에 의해 시스템 제어정보를 시스템 내의 분산 저장 가능한 노드들에 분산 저장하여, 원본 제어정보에 결함이 발생하였을 때, 분산 저장된 정보를 바탕으로 원본 시스템 제어정보를 복구함으로써, 지속적이고 안정적인 소프트웨어 동작을 보장할 수 있다.The present invention relates to a method of permitting an information defect in a system having a hierarchical structure, and more particularly, to an information defect tolerance method in a server (100), in which (1) Permitting method, a RAID 4 + Daisy Chain fault tolerance method, an EVENODD fault tolerance method, and an LT fault tolerance method according to the number of nodes of the distributed storable node (S200) of requesting recovery of original data from a node where a defect occurs in the original data among the nodes distributing and storing the system control information (S200); and (3) And restoring the original data according to the fault tolerance method selected in the step (1) (S300).
According to the information fault tolerance method of a system having a hierarchical structure proposed in the present invention, in a system having a hierarchical structure, a RAID4 + Daisy chain fault tolerance method, an EVENODD A fault tolerance method, and a LT fault tolerance method, and system control information is distributedly stored in the distributed storable nodes in the system by the selected fault tolerance method. When a defect occurs in the original control information , And restores the original system control information based on the distributed stored information, thereby ensuring continuous and stable software operation.

Description

계층적 구조를 갖는 시스템의 정보 결함허용 방법{A FAULT TOLERANT METHOD FOR A HIERARCHICAL SYSTEM}FIELD OF THE INVENTION [0001] The present invention relates to a method for permitting an information fault in a system having a hierarchical structure,

본 발명은 시스템의 정보 결함허용 방법에 관한 것으로서, 보다 구체적으로는 RAID+Daisy Chain 결함허용 알고리즘, EVENODD 결함허용 알고리즘 및 LT 결함허용 알고리즘을 통해 원본 시스템 제어정보에 결함이 발생했을 때 원본 시스템 제어정보를 복구하여 지속적이고 안정적인 소프트웨어 동작을 보장하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법에 관한 것이다.The present invention relates to an information defect tolerance method of a system, and more particularly, to a method and system for information defect tolerance in a system, when a defect occurs in original system control information through a RAID + Daisy chain fault tolerance algorithm, an EVENODD fault tolerance algorithm, To ensure continuous and stable software operation, and to an information fault tolerant method for a system having a hierarchical structure.

일반적으로 결함허용 시스템이란 하드웨어의 오동작, 소프트웨어의 에러 또는 정보 오염이 일어나도 주어진 일을 올바르게 수행할 수 있는 시스템을 말한다.
In general, a fault tolerant system is a system that can correctly perform a given task even if hardware malfunctions, software errors, or information contamination occur.

최근 사물과 사람이 네트워크로 연결되는 초연결 사회로 변화가 진행되고 있고, 교통, 보건, 기상, 물류 등의 다양한 산업과 네트워크가 융합되어 지능화됨으로써, 인간의 삶은 보다 편리하고 풍요로워졌지만, 인간의 네트워크에 대한 의존도는 급속도로 높아지고 있다.
Recently, human being's life has become more convenient and enriched by the change of the connection system of objects and people connected to the network, and various industries and networks such as traffic, health, weather, and logistics are fused and intelligent. Is increasing rapidly.

이처럼 높아진 네트워크에 대한 의존도로 인해 네트워크에 연결된 하드웨어의 오동작, 또는 소프트웨어의 에러 등으로 전체 시스템의 동작에 치명적인 오류가 발생되면 인간 사회 전체에 극도의 혼란을 야기할 수 있기 때문에, 이와 같은 문제가 발생되더라도 주어진 임무를 올바르게 수행할 수 있는 결함허용 방법이 필수적으로 요구되고 있다.
Due to the increased dependency on the network, if a fatal error occurs in the operation of the entire system due to a malfunction of the hardware connected to the network, or an error of the software, the entire human society may be extremely confused, A defect-tolerant method that can correctly perform a given task is indispensable.

이와 같은 결함허용과 관련하여, 등록특허 제10-0475280호(발명의 명칭: 결함허용 고속링형 통신망 구축 방법, 공개일자: 2005년 03월 10일), 등록특허 제10-0733971호(발명의 명칭; 결함허용 전이중방식 분산제어시스템, 공고일자: 2007년 06월 29일) 등이 개시된바 있다.Regarding such defect acceptance, Patent No. 10-0475280 (Title of the invention: Method of establishing a fault-tolerant high speed ring network, published on Mar. 10, 2005), Registration No. 10-0733971 ; Fault-tolerant full-duplex distributed control system, announcement date: June 29, 2007).

본 발명은 기존에 제안된 방법들의 상기와 같은 문제점들을 해결하기 위해 제안된 것으로서, 계층적 구조를 갖는 시스템에서 시스템 제어정보를 분산 저장 가능한 서버 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하고, 선택된 결함허용 방법에 의해 시스템 제어정보를 시스템 내의 분산 저장 가능한 노드들에 분산 저장하여, 원본 제어정보에 결함이 발생하였을 때, 분산 저장된 정보를 바탕으로 원본 시스템의 제어정보를 복구함으로써, 지속적이고 안정적인 소프트웨어 동작을 보장할 수 있는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법을 제공하는 것을 그 목적으로 한다.The present invention has been proposed in order to solve the above-mentioned problems of the existing methods. The present invention proposes a RAID4 + Daisy Chain fault tolerance method according to the number of nodes under a server capable of distributing system control information in a system having a hierarchical structure, EVENODD fault tolerance method and LT fault tolerance method, and system control information is distributedly stored in the distributed storable nodes by the selected fault tolerance method. When a defect occurs in the original control information It is an object of the present invention to provide an information defect tolerance method for a system having a hierarchical structure that can guarantee continuous and stable software operation by restoring control information of an original system based on distributed stored information.

상기한 목적을 달성하기 위한 본 발명의 특징에 따른, 계층적 구조를 갖는 시스템의 정보 결함허용 방법은,According to an aspect of the present invention, there is provided an information defect tolerance method for a system having a hierarchical structure,

시스템의 정보 결함허용 방법으로서, 서버에서,A method for permitting an information fault in a system,

(1) 시스템 제어정보를 분산 저장 가능한 하위의 노드 수를 확인하고, 상기 확인된 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하며, 상기 선택된 결함허용 방법에 따라 시스템 제어정보가 상기 시스템 내의 분산 저장 가능한 노드들에 분산 저장되도록 하는 단계(S100);(1) a fault tolerance method of one of RAID 4 + Daisy Chain fault tolerance method, EVENODD fault tolerance method, and LT fault tolerance method according to the number of the lower-level nodes that are capable of distributing system control information, (S100) the system control information to be distributedly stored in the distributed storable nodes in the system according to the selected fault tolerance method;

(2) 상기 시스템 제어정보를 분산 저장하고 있는 노드들 중, 원본 데이터에 결함이 발생한 노드로부터 원본 데이터 복구를 요청받는 단계(S200); 및(2) a step (S200) of requesting restoration of original data from a node where a defect occurs in the original data among the nodes distributing and storing the system control information; And

(3) 상기 단계 (1)에서 선택된 결함허용 방법에 따라 원본 데이터가 복구되도록 하는 단계(S300)를 포함하는 것을 그 구성상의 특징으로 한다.
(3) restoring the original data according to the fault tolerance method selected in the step (1) (S300).

바람직하게는, 상기 서버는,Preferably, the server further comprises:

상기 시스템 제어정보를 분산 저장 가능한 하위의 노드가 추가 또는 삭제되는 작업이 수행될 때마다 상기 시스템 제어정보를 분산 저장 가능한 하위의 노드 수를 확인하고, 상기 확인된 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하며, 상기 선택된 결함허용 방법에 따라 시스템 제어정보가 상기 시스템 내의 분산 저장 가능한 노드들에 분산 저장되도록 할 수 있다.
The system control information can be distributed and stored every time an operation for adding or deleting a lower node capable of distributing the system control information is performed, A method of selecting a fault tolerance method of one of a fault tolerance method, a chain fault tolerance method, an EVENODD fault tolerance method and an LT fault tolerance method, and system control information may be distributedly stored in distributedly storable nodes in the system according to the selected fault tolerance method .

바람직하게는, 상기 단계 (1)에서,Preferably, in said step (1)

상기 시스템 제어정보를 분산 저장 가능한 하위의 노드 수가 5개 미만인 경우에는 RAID4+Daisy Chain 결함허용 방법, 5개 이상 20개 미만인 경우에는 EVENODD 결함허용 방법, 20개 이상인 경우에는 LT 결함허용 방법을 선택할 수 있다.
A RAID4 + Daisy Chain fault tolerance method when the number of lower nodes capable of distributing the system control information is less than 5, an EVENODD fault tolerance method when more than 5 and less than 20 nodes are available, and an LT fault tolerance method when more than 20 nodes are available have.

바람직하게는, 상기 서버는, 결함허용 방법으로서 상기 RAID4+Daisy Chain 결함허용 방법이 선택된 경우,Preferably, when the RAID4 + Daisy Chain fault tolerance method is selected as the fault tolerance method,

시스템 제어정보를 분산 저장 가능한 하위의 모든 노드들에게 순차적인 인덱스를 부여하고, 상기 인덱스가 부여된 각각의 노드들에게 하기의 수학식을 이용하여 후속 노드의 인덱스를 지정하도록 하여 Daisy Chain이 형성되도록 하며, 상기 형성된 Daisy Chain 정보를 저장할 수 있다.A sequential index is assigned to all lower nodes capable of distributing system control information, and an index of a subsequent node is designated to each of the nodes to which the index is assigned by using the following equation so that a daisy chain is formed And store the generated Daisy chain information.

[수학식][Mathematical Expression]

Nodei -> Node<i+1>M, 0 ≤ i ≤ M-1Nodei -> Node <i + 1> M , 0? I? M-1

여기서, M은 노드 수, i는 인덱스, ‘->’화살표는 i인 인덱스 노드에 후속 노드를 배정하는 것, <i+1>M은 i+1 Modulo M을 나타낸다.
Here, M represents the number of nodes, i represents an index, and arrows '->' indicate assignments of subsequent nodes to an index node i, and <i + 1> M represents i + 1 Modulo M.

더욱 바람직하게는, 상기 서버는,More preferably, the server further comprises:

상기 인덱스가 부여된 모든 노드들에게 후속 노드의 접속 정보가 포함된 백업 유도 메시지를 전송하여, 상기 노드들이 각각의 원본 데이터를 후속 노드에게 전송하도록 할 수 있다.
A backup induction message including connection information of a subsequent node may be transmitted to all nodes to which the index is assigned, so that the nodes transmit respective original data to a subsequent node.

더욱더 바람직하게는, 상기 서버는,Even more preferably,

상기 백업을 수행한 모든 노드들로부터 원본 데이터가 전송되도록 하며, 상기 전송받은 모든 노드들의 원본 데이터와 저장된 원본 데이터를 XOR 연산하여 패리티 데이터를 생성한 후 저장할 수 있다.
The original data is transmitted from all the nodes that have performed the backup, and the original data of all the received nodes and the stored original data are XOR'ed to generate parity data and then stored.

바람직하게는, 상기 서버는, 결함허용 방법으로서 상기 EVENODD 결함허용 방법이 선택된 경우,Preferably, when the EVENODD fault tolerance method is selected as the fault tolerance method,

상기 시스템 제어정보를 분산 저장 가능한 하위의 모든 노드들에게 상기 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송할 수 있다.
It is possible to transmit connection information of nodes capable of distributing and storing the system control information to all lower nodes capable of distributing the system control information.

더욱 바람직하게는, 상기 서버는,More preferably, the server further comprises:

상기 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 각각의 노드들에서 각각의 원본 데이터가 EVENODD 코드를 기반으로 부호화되도록 하고, 상기 생성된 부호화 데이터가 열 단위로 분할되어, 상기 분할된 부호화 데이터가 상기 시스템 제어정보를 분산 저장 가능한 노드들로 전송되도록 할 수 있다.
Each of the nodes receiving the connection information of the nodes capable of distributing the system control information is caused to encode each original data based on the EVENODD code, and the generated encoded data is divided into columns, Data may be transmitted to the nodes capable of distributing the system control information.

더욱더 바람직하게는,Even more preferably,

상기 열 단위로 분할된 부호화 데이터는 각각의 열의 인덱스를 포함할 수 있다.
The coded data divided by the column unit may include an index of each column.

더욱더 바람직하게는, 상기 서버는,Even more preferably,

상기 각각의 노드들에서 열 단위로 분할된 부호화 데이터를 전송받아 분산 저장하고 있는 상기 각각의 노드들로부터 상기 분산 저장 정보가 전송되도록 할 수 있다.
And the distributed storage information may be transmitted from each of the nodes that receive and store the encoded data divided in columns by the respective nodes.

더욱더 바람직하게는, 상기 서버는,Even more preferably,

상기 각각의 노드들로부터 전송받은 분산 저장 정보를 저장할 수 있다.
And may store the distributed storage information transmitted from the respective nodes.

바람직하게는, 상기 서버는, 결함허용 방법으로서 상기 LT 결함허용 방법이 선택된 경우,Advantageously, the server, when the LT fault tolerance method is selected as a fault tolerance method,

상기 시스템 제어정보를 분산 저장 가능한 하위의 모든 노드들에게 상기 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송할 수 있다.
It is possible to transmit connection information of nodes capable of distributing and storing the system control information to all lower nodes capable of distributing the system control information.

더욱 바람직하게는, 상기 서버는,More preferably, the server further comprises:

상기 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 각각의 노드들에서 원본 심볼의 수가 선택되도록 하고, 상기 선택된 원본 심볼의 수에 따라 각각의 원본 데이터가 분할되도록 하며, 상기 분할된 각각의 원본 데이터가 LT 코드 기반으로 부호화되도록 할 수 있다.
The number of original symbols is selected in each of the nodes to which connection information of nodes capable of distributively storing the system control information is transmitted, and each original data is divided according to the number of the selected original symbols, The original data can be encoded based on the LT code.

더욱더 바람직하게는, 상기 서버는,Even more preferably,

상기 각각의 노드들로부터 생성된 부호화 데이터들이 분산 저장 가능한 노드들에게 전송되어 저장되도록 할 수 있다.
The encoded data generated from the respective nodes may be transmitted to and stored in nodes capable of distributively storing.

더욱더 바람직하게는, 상기 서버는,Even more preferably,

상기 각각의 노드들에서 부호화된 데이터를 전송받아 분산 저장하고 있는 상기 각각의 노드들로부터 상기 분산 저장 정보가 전송되도록 하며, 상기 전송받은 분산 저장 정보를 저장할 수 있다.
The distributed storage information may be transmitted from each of the nodes that receive encoded data from the respective nodes and store the distributed storage information, and may store the transmitted distributed storage information.

바람직하게는, 상기 단계 (3)은,Preferably, the step (3)

상기 단계 (1)에서 상기 RAID4+Daisy Chain 결함허용 방법이 선택된 경우,If the RAID4 + Daisy chain fault tolerance method is selected in step (1)

(3-R1) 상기 복구를 요청한 노드의 수를 확인하는 단계(R310);(3-R1) confirming the number of nodes requesting the recovery (R310);

(3-R2) 상기 단계 (3-R1)에서 확인된 복구를 요청한 노드의 수가 1개인 경우, 상기 복구를 요청한 노드의 후속 노드를 검색한 후, 상기 후속 노드에게 복구를 요청한 노드의 접속 정보를 추가한 복구 요청 메시지를 전달하는 단계(R320);(3-R 2) If the number of nodes requested to be restored in the step (3-R 1) is 1, a search is made for the next node of the node requesting the restoration, Transmitting an added recovery request message (R320);

(3-R3) 상기 복구 요청 메시지를 수신한 상기 후속 노드에서 상기 복구를 요청한 노드에 백업 데이터가 전송되도록 하는 단계(R330); 및(R3-R3) the backup data is transmitted to the node requesting the recovery from the succeeding node that received the recovery request message (R330); And

(3-R4) 상기 단계 (3-R3)을 통해 전송된 백업 데이터를 이용하여 상기 복구를 요청한 노드의 원본 데이터가 복구되도록 하는 단계(R340)를 더 포함할 수 있다.
(3-R4) Restoring the original data of the node requesting the recovery using the backup data transmitted through the step (3-R3) (R340).

더욱 바람직하게는, 상기 단계 (3)은,More preferably, the step (3)

상기 단계 (1)에서 상기 RAID4+Daisy Chain 결함허용 방법이 선택된 경우,If the RAID4 + Daisy chain fault tolerance method is selected in step (1)

(3-R1) 상기 복구를 요청한 노드의 수를 확인하는 단계(R310);(3-R1) confirming the number of nodes requesting the recovery (R310);

(3-R2) 상기 단계 (3-R1)에서 확인된 복구를 요청한 노드의 수가 2개이고, 상기 2개 노드의 인덱스가 연속적인 경우, 상기 복구를 요청한 2개의 노드 중 높은 인덱스를 가진 노드의 후속 노드에 상기 높은 인덱스를 가진 노드의 접속 정보를 포함한 복구 요청 메시지를 전달하고, 상기 단계 (3-R3) 및 (3-R4)를 통해 높은 인덱스를 가진 노드의 원본 데이터가 복구되도록 하는 단계(R320);(3-R2) If the number of nodes requested to be restored in step (3-R1) is two and the indices of the two nodes are consecutive, a subsequent one of the two nodes (3-R3) and (3-R4) to recover the original data of the node having the high index (R320 );

(3-R3) 상기 복구를 요청한 2개의 노드 중 낮은 인덱스를 가진 노드를 제외한 모든 노드들로부터 각각의 원본 데이터가 전송되도록 하며, 상기 전송받은 모든 원본 데이터와 상기 저장되어 있는 패리티 데이터를 XOR 연산하여, 상기 낮은 인덱스를 가진 노드의 원본 데이터를 생성하는 단계(R330); 및(3-R3) The original data is transmitted from all the nodes except for the node having the low index among the two nodes requesting the restoration, and the original data and the stored parity data are XORed Generating (R330) original data of the node having the lower index; And

(3-R4) 단계 (3-R3)을 통해 생성된 원본 데이터를 낮은 인덱스를 가진 노드에게 전송하여, 상기 낮은 인덱스를 가진 노드의 원본 데이터가 복구되도록 하는 단계(R340)를 더 포함할 수 있다.
(3-R4) transmitting the original data generated through the step (3-R3) to the node having the lower index, and restoring the original data of the node having the lower index (step R340) .

더욱 바람직하게는, 상기 단계 (3)은,More preferably, the step (3)

상기 단계 (1)에서 상기 RAID4+Daisy Chain 결함허용 방법이 선택된 경우,If the RAID4 + Daisy chain fault tolerance method is selected in step (1)

(3-R1) 상기 복구를 요청한 노드의 수를 확인하는 단계(R310);(3-R1) confirming the number of nodes requesting the recovery (R310);

(3-R2) 상기 단계 (3-R1)에서 확인된 복구를 요청한 노드의 수가 2개이고, 상기 2개 노드의 인덱스가 비연속적인 경우, 상기 복구를 요청한 각각의 노드의 후속 노드를 검색한 후, 상기 각각의 후속 노드에게 복구를 요청한 각각의 노드의 접속 정보를 추가한 복구 요청 메시지를 전달하는 단계(R320);(3-R2) If the number of nodes requested to be restored in step (3-R1) is two and the indexes of the two nodes are non-contiguous, a subsequent node of each node requesting the restoration is searched (R320) of adding a connection request of each node requesting recovery to each of the subsequent nodes;

(3-R3) 상기 복구 요청 메시지를 수신한 상기 각각의 후속 노드로부터 상기 복구를 요청한 각각의 노드에 백업 데이터가 전송되도록 하는 단계(R330); 및(R3-R3) transferring backup data to each node that requested the recovery from each subsequent node that received the recovery request message (R330); And

(3-R4) 상기 단계 (3-R3)을 통해 전송된 백업 데이터를 이용하여 상기 복구를 요청한 각각의 노드의 원본 데이터가 복구되도록 하는 단계(R340)를 더 포함할 수 있다.
(3-R4) restoring the original data of each node requesting the recovery using the backup data transmitted through the step (3-R3) (R340).

바람직하게는, 상기 단계 (3)은,Preferably, the step (3)

상기 단계 (1)에서 상기 EVENODD 결함허용 방법이 선택된 경우,If the EVENODD fault tolerance method is selected in step (1)

(3-E1) 상기 분산 저장 정보를 통해 복구를 요청한 노드의 부호화 데이터들이 저장되어 있는 노드들을 찾고, 상기 노드들에게 복구를 요청한 노드의 접속 정보가 포함된 복구 요청 메시지를 전달하는 단계(E310);(E310) searching for nodes storing coded data of a node requesting recovery through the distributed storage information, and delivering a recovery request message including access information of a node requesting recovery to the nodes (E310) ;

(3-E2) 상기 복구를 요청한 노드의 부호화 데이터들을 분산 저장하고 있는 노드들로부터 분산 저장된 부호화 데이터들이 상기 복구를 요청한 노드로 전송되도록 한 후, 상기 부호화 데이터들에 포함된 인덱스를 통해 상기 부호화 데이터들의 배열이 재구성되도록 하는 단계(E320);(3-E2) the encoded data distributed and stored from the nodes storing the encoded data of the node requesting the restoration to be transmitted to the node requesting the restoration, and then transmitting the encoded data through the index included in the encoded data (E320);

(3-E3) 상기 단계 (3-E2)를 통해 상기 부호화 데이터들의 배열이 재구성되도록 한 후, 분산 저장된 부호화 데이터들 중 손실된 데이터 개수 따라 그에 해당되는 EVENODD 코드 복호화가 수행되도록 하는 단계(E330); 및(3-E3) causing the arrangement of the encoded data to be reconstructed through the step (3-E2), and performing EVENODD code decoding corresponding to the number of lost data among the distributed coded data E330 ; And

(3-E4) 상기 단계 (3-E3)을 통해 생성된 복호화 데이터들이 원본 데이터가 분할된 역순으로 합병되도록 하여, 원본 데이터가 복구되도록 하는 단계(E340)를 더 포함할 수 있다.
(3-E4) The decrypted data generated through the step (3-E3) may be merged in the reverse order in which the original data is divided, so that the original data is recovered (E340).

바람직하게는, 상기 단계 (3)은,Preferably, the step (3)

상기 단계 (1)에서 상기 LT 결함허용 방법이 선택된 경우,If the LT fault tolerance method is selected in step (1)

(3-L1) 상기 분산 저장 정보를 통해 복구를 요청한 노드의 부호화 데이터들이 저장되어 있는 노드들을 찾고, 상기 노드들에게 복구를 요청한 노드의 접속 정보가 포함된 복구 요청 메시지를 전달하는 단계(L310);(L310) searching for nodes storing coded data of a node requesting recovery through the distributed storage information and delivering a recovery request message including access information of a node requesting recovery to the nodes, ;

(3-L2) 상기 복구를 요청한 노드의 부호화 데이터를 분산 저장하고 있는 노드들로부터 분산 저장된 부호화 데이터들이 상기 복구를 요청한 노드로 전송되도록 한 후, 상기 전송된 부호화 데이터들에 대해 LT 코드 복호화가 수행되도록 하는 단계(L320); 및(3-L2), the encoded data distributedly stored from the nodes storing the encoded data of the node requesting the recovery is transmitted to the node requesting the recovery, and then the LT code decoding is performed on the transmitted encoded data (L320); And

(3-L3) 상기 단계 (3-L2)의 LT 코드 복호화를 통해 생성된 원본 심볼들이 원본 데이터가 분할된 역순으로 합병되도록 하여, 원본 데이터가 복구되도록 하는 단계(L330)를 더 포함할 수 있다.(3-L3) The step (L330) may cause the original symbols generated through the LT code decoding in the step (3-L2) to be merged in the reverse order in which the original data is divided so that the original data is recovered .

본 발명에서 제안하고 있는 계층적 구조를 갖는 시스템의 정보 결함허용 방법에 따르면, 계층적 구조를 갖는 시스템에서 시스템 제어정보를 분산 저장 가능한 서버 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법, 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하고, 선택된 결함허용 방법에 의해 시스템 제어정보를 시스템 내의 분산 저장 가능한 노드들에 분산 저장하여, 원본 제어정보에 결함이 발생하였을 때, 분산 저장된 정보를 바탕으로 원본 시스템 제어정보를 복구함으로써, 지속적이고 안정적인 소프트웨어 동작을 보장할 수 있다.According to the information fault tolerance method of a system having a hierarchical structure proposed in the present invention, in a system having a hierarchical structure, a RAID4 + Daisy Chain fault tolerance method according to the number of nodes under a server capable of distributedly storing system control information, an EVENODD A fault tolerance method, and a LT fault tolerance method, and system control information is distributedly stored in the distributed storable nodes in the system by the selected fault tolerance method. When a defect occurs in the original control information , And restores the original system control information based on the distributed stored information, thereby ensuring continuous and stable software operation.

도 1은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법의 흐름을 도시한 흐름도.
도 2는 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법이 선택되는 하위 노드 수의 범위를 나타내는 표.
도 3은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법이 선택된 경우, 서버에서 인덱스가 부여된 노드들에게 후속 노도의 접속 정보가 포함된 백업 유도 메시지를 전송하여, 노드들이 각각의 원본 데이터를 후속 노드에게 전송하는 모습을 도시한 도면.
도 4는 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, EVENODD 결함허용 방법이 선택된 경우, 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 노드에서 원본 데이터가 EVENODD 코드를 기반으로 부호화되고, 생성된 부호화 데이터가 열 단위로 분할되어, 분할된 부호화 데이터가 시스템 제어정보를 분산 저장 가능한 노드들에게 전송되는 장면을 도시한 도면.
도 5는 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, LT 결함허용 방법이 선택된 경우, 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 노드에서, 원본 심볼의 수에 따라 원본 데이터가 분할되고, 분할된 데이터가 LT 코드 기반으로 부호화되는 장면을 도시한 도면.
도 6은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, LT 코드 기반으로 부호화된 데이터들이 분산 저장 가능한 노드들로 전송되는 장면을 도시한 도면.
도 7은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법이 선택되고, 하나의 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드의 데이터가 복구되는 과정을 도시한 도면.
도 8은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법이 선택되고, 2개의 연속적인 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드들의 데이터가 복구되는 과정을 도시한 도면.
도 9는 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법이 선택되고, 2개의 비연속적인 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드들의 데이터가 복구되는 과정을 도시한 도면.
도 10은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, EVENODD 결함허용 방법이 선택되고, 하나의 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드의 데이터가 복구되는 과정을 도시한 도면.
도 11에서 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, LT 결함허용 방법이 선택되고, 하나의 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드의 데이터가 복구되는 과정을 도시한 도면.BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a flowchart showing a flow of an information defect tolerance method of a system having a hierarchical structure according to an embodiment of the present invention; FIG.
FIG. 2 is a diagram illustrating a range of the number of lower nodes for which the RAID4 + Daisy chain fault tolerance method, the EVENODD fault tolerance method, and the LT fault tolerance method are selected in the information fault tolerance method of a system having a hierarchical structure according to an embodiment of the present invention. Table indicating.
FIG. 3 is a flowchart illustrating a method of permitting access to the next row to nodes indexed by the server when the RAID4 + Daisy Chain fault tolerance method is selected in the information fault tolerance method of a system having a hierarchical structure according to an embodiment of the present invention. And transmitting the included backup guiding message, so that the nodes transmit respective original data to the subsequent node.
FIG. 4 is a diagram illustrating a method of allowing an EVENODD fault in a system having a hierarchical structure according to an exemplary embodiment of the present invention. When an EVENODD fault tolerance method is selected, Is encoded based on an EVENODD code, the generated encoded data is divided in units of columns, and the divided encoded data is transmitted to nodes capable of distributing system control information.
FIG. 5 is a diagram illustrating a method of permitting an information defect in a system having a hierarchical structure according to an embodiment of the present invention. In the method, when an LT fault-tolerant method is selected, FIG. 8 is a diagram showing a scene in which original data is divided according to the number of symbols and the divided data is encoded based on an LT code.
6 is a diagram illustrating a scene in which data encoded based on an LT code is transmitted to nodes capable of distributed storage in an information fault tolerance method of a system having a hierarchical structure according to an embodiment of the present invention.
FIG. 7 is a flowchart illustrating a method of allowing a RAID4 + Daisy Chain fault tolerance method in a system having a hierarchical structure according to an exemplary embodiment of the present invention. When an information defect occurs in one distributed storage node, And recovering the data of the generated node.
FIG. 8 is a flowchart illustrating a method of allowing a RAID 4 + Daisy Chain fault tolerance method in an information fault tolerance method of a system having a hierarchical structure according to an exemplary embodiment of the present invention. When an information defect occurs in two consecutive distributed storage nodes, FIG. 4 is a diagram illustrating a process of recovering data of defective nodes. FIG.
FIG. 9 is a flowchart illustrating a method of allowing a RAID4 + Daisy Chain fault tolerance method in a system having a hierarchical structure according to an exemplary embodiment of the present invention, when an information defect occurs in two discontinuous distributed storage nodes , And data of defective nodes are recovered.
FIG. 10 is a diagram illustrating a method of allowing an EVENODD fault in a system having a hierarchical structure according to an embodiment of the present invention. When an EVENODD fault tolerance method is selected and information defects are generated in one distributed storage node, FIG. 3 is a diagram showing a process in which data is recovered; FIG.
11, in the information fault tolerance method of a system having a hierarchical structure according to an embodiment of the present invention, when an LT fault tolerance method is selected and an information defect occurs in one distributed storage node, FIG. 3 is a diagram showing a process in which data is recovered; FIG.

이하에서는 첨부된 도면을 참조하여 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자가 본 발명을 용이하게 실시할 수 있도록 바람직한 실시예를 상세히 설명한다. 다만, 본 발명의 바람직한 실시예를 상세하게 설명함에 있어, 관련된 공지 기능 또는 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략한다. 또한, 유사한 기능 및 작용을 하는 부분에 대해서는 도면 전체에 걸쳐 동일 또는 유사한 부호를 사용한다.
Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those skilled in the art can easily carry out the present invention. In the following detailed description of the preferred embodiments of the present invention, a detailed description of known functions and configurations incorporated herein will be omitted when it may make the subject matter of the present invention rather unclear. The same or similar reference numerals are used throughout the drawings for portions having similar functions and functions.

덧붙여, 명세서 전체에서, 어떤 부분이 다른 부분과 ‘연결’되어 있다고 할 때, 이는 ‘직접적으로 연결’되어 있는 경우뿐만 아니라, 그 중간에 다른 소자를 사이에 두고 ‘간접적으로 연결’되어 있는 경우도 포함한다. 또한, 어떤 구성요소를 ‘포함’한다는 것은, 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성요소를 더 포함할 수 있다는 것을 의미한다.
In addition, in the entire specification, when a part is referred to as being 'connected' to another part, it may be referred to as 'indirectly connected' not only with 'directly connected' . Also, to "include" an element means that it may include other elements, rather than excluding other elements, unless specifically stated otherwise.

도 1은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법의 흐름을 도시한 흐름도이다. 도 1에 도시된 바와 같이, 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법은, 서버(100)에서, (1) 시스템 제어정보를 분산 저장 가능한 하위의 노드 수를 확인하고, 확인된 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하며, 선택된 결함허용 방법에 따라 시스템 제어정보가 시스템 내의 분산 저장 가능한 노드들에 분산 저장되도록 하는 단계(S100), (2) 시스템 제어정보를 분산 저장하고 있는 노드들 중, 원본 데이터에 결함이 발생한 노드로부터 원본 데이터 복구를 요청받는 단계(S200), 및 단계 (1)에서 선택된 결함허용 방법에 따라 원본 데이터가 복구되도록 하는 단계(S300)를 포함하여 구성될 수 있다.
1 is a flowchart illustrating a flow of an information defect tolerance method of a system having a hierarchical structure according to an embodiment of the present invention. As shown in FIG. 1, an information fault tolerance method of a system having a hierarchical structure according to an embodiment of the present invention is a method in which a server 100 calculates (1) the number of lower nodes capable of distributing system control information And selects a fault tolerance method of one of RAID4 + Daisy Chain fault tolerance method, EVENODD fault tolerance method and LT fault tolerance method according to the number of confirmed lower nodes, and according to the selected fault tolerance method, (S200) for requesting restoration of original data from a node where defect occurs in the original data among the nodes that distributively store the system control information, and Allowing the original data to be recovered according to the fault tolerance method selected in step (1) (S300).

이하에서는, 본 발명에서 제안하고 있는 계층적 구조를 갖는 시스템의 정보 결함허용 방법의 각각의 단계, 및 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법에 대하여 도면을 참조하여 상세하게 설명하기로 한다.
Hereinafter, each step of the information fault tolerance method of a system having a hierarchical structure proposed in the present invention and the RAID 4 + Daisy Chain fault tolerance method, EVENODD fault tolerance method and LT fault tolerance method will be described in detail with reference to the drawings. .

단계 S100에서 서버(100)는, 시스템 제어정보를 분산 저장 가능한 하위의 노드 수를 확인하고, 확인된 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하여, 선택된 결함허용 방법에 따라 시스템 제어정보가 시스템 내의 분산 저장 가능한 노드들에 분산 저장되도록 할 수 있다. 여기서 서버(100)는, 시스템 제어정보를 분산 저장 가능한 하위의 노드가 추가 또는 삭제되는 작업이 수행될 때마다 시스템 제어정보를 분산 저장 가능한 하위의 노드 수를 확인하고, 확인된 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하여, 선택된 결함허용 방법에 따라 시스템 제어정보가 시스템 내의 분산 저장 가능한 노드들에 분산 저장되도록 할 수 있다. 이하에서는, 도 2를 참조하여 단계 S100에서 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법이 선택되는 하위 노드 수의 범위에 대해 설명하기로 한다.
In step S100, the server 100 confirms the number of lower-level nodes capable of distributing system control information and determines whether or not the RAID 4 + Daisy chain fault tolerance method, the EVENODD fault tolerance method, and the LT fault tolerance method One fault tolerant method may be selected to allow system control information to be distributedly stored in distributed storable nodes in the system according to the selected fault tolerant method. Here, the server 100 confirms the number of lower-level nodes capable of distributing system control information every time an operation of adding or deleting a lower node capable of distributing system control information is performed, + Daisy Chain fault tolerance method, EVENODD fault tolerance method and LT fault tolerance method so that the system control information is distributedly stored in the distributed storage nodes in the system according to the selected fault tolerance method . Hereinafter, the range of the number of lower nodes in which the RAID4 + Daisy chain fault tolerance method, the EVENODD fault tolerance method, and the LT fault tolerance method are selected will be described with reference to FIG.

도 2는 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법이 선택되는 하위 노드 수의 범위를 나타내는 표이다. 단계 S100에서 서버(100)는, 도 2에 도시된 바와 같이, 시스템 제어정보를 분산 저장 가능한 하위의 노드 수가 5개 미만인 경우에 RAID4+Daisy Chain 결함허용 방법, 5개 이상 20개 미만인 경우에 EVENODD 결함허용 방법, 20개 이상인 경우에 LT 결함허용 방법을 선택할 수 있다. 이하에서는, 단계 S100에서 시스템 제어정보를 분산 저장 가능한 하위의 노드 수가 5개 미만인 경우에 선택되는 RAID4+Daisy Chain 결함허용 방법에 대해 도면을 참조하여 상세히 설명하도록 한다.
FIG. 2 is a diagram illustrating a range of the number of lower nodes for which the RAID4 + Daisy chain fault tolerance method, the EVENODD fault tolerance method, and the LT fault tolerance method are selected in the information fault tolerance method of a system having a hierarchical structure according to an embodiment of the present invention. Respectively. As shown in FIG. 2, in step S100, the server 100 executes a RAID4 + Daisy Chain fault tolerance method when the number of subordinate nodes capable of distributively storing system control information is less than 5, an EVENODD Fault tolerance method, and when there are more than 20 LT fault tolerant methods can be selected. Hereinafter, a RAID4 + Daisy Chain fault tolerant method selected when the number of lower nodes capable of distributing and storing system control information is less than 5 in step S100 will be described in detail with reference to the drawings.

단계 S100에서 결함허용 방법으로서 RAID4+Daisy Chain 결함허용 방법이 선택된 경우, 서버(100)는 시스템 제어정보를 분산 저장 가능한 하위의 모든 노드들에게 순차적인 인덱스를 부여하고, 인덱스가 부여된 각각의 노드들에게 하기의 수학식 1을 이용하여 후속 노드의 인덱스를 지정하도록 해서 Daisy Chain이 형성되도록 하며, 형성된 Daisy Chain 정보를 저장할 수 있다. 예를 들어, 서버(100)에서 서버: 0, 노드 A: 1, 노드 B: 2, 노드 C: 3의 순차적인 인덱스를 부여한 경우, 하기의 수학식 1을 이용하여 인덱스를 부여받은 각각의 노드들에게 다시 후속 노드의 인덱스를 지정하도록 하여, 서버->노드 A->노드 B->노드 C->서버의 Daisy Chain을 형성되도록 할 수 있고, 형성된 Daisy Chain 정보를 저장할 수 있다.When the RAID4 + Daisy Chain fault tolerance method is selected as the fault tolerance method in step S100, the server 100 assigns sequential indexes to all the lower nodes capable of distributing system control information, , Daisy chain is formed by designating the index of the subsequent node using Equation (1) below, and the generated Daisy chain information can be stored. For example, when a sequential index of a server: 0, a node A: 1, a node B: 2, and a node C: 3 is given from the server 100, The node A-> node B-> node C-> Daisy chain of the server, and store the formed Daisy chain information.

Figure 112016007355416-pat00001
Figure 112016007355416-pat00001

여기서, M은 노드 수, i는 인덱스, ‘->’화살표는 i인 인덱스 노드에 후속 노드를 배정하는 것, <i+1>M은 i+1 Modulo M을 나타낸다.
Here, M represents the number of nodes, i represents an index, and arrows '->' indicate assignments of subsequent nodes to an index node i, and <i + 1> M represents i + 1 Modulo M.

도 3은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법이 선택된 경우, 서버에서 인덱스가 부여된 노드들에게 후속 노도의 접속 정보가 포함된 백업 유도 메시지를 전송하여, 노드들이 각각의 원본 데이터를 후속 노드에게 전송하는 모습을 도시한 도면이다. 이처럼, 서버(100)는 도 3의 (a)에 도시된 바와 같이, 인덱스가 부여된 모든 노드들에게 후속 노드의 접속 정보가 포함된 백업 유도 메시지를 전송하고, 도 3의 (b)에 도시된 바와 같이, 백업 유도 메시지를 전송받은 노드들에서 각각의 원본 데이터가 후속 노드에게 전송되도록 하여, 서버(100)의 후속 노드인 노드 A에서 서버의 원본 데이터를, 노드 A의 후속 노드인 노드 B에서 노드 A의 원본 데이터를, 노드 B의 후속 노드인 노드 C에서 노드 B의 원본 데이터를, 노드 C의 후속 노드인 서버(100)에서 노드 C의 원본 데이터가 백업되어 저장되도록 할 수 있다.
FIG. 3 is a flowchart illustrating a method of permitting access to the next row to nodes indexed by the server when the RAID4 + Daisy Chain fault tolerance method is selected in the information fault tolerance method of a system having a hierarchical structure according to an embodiment of the present invention. And transmits the included backup induction message, so that the nodes transmit respective original data to the subsequent node. 3 (a), the server 100 transmits a backup induction message including access information of a subsequent node to all the indexed nodes, The source data of the server is transmitted from the node A, which is the succeeding node of the server 100, to the node B which is the subsequent node of the node A, The original data of the node A can be stored in the server 100 which is the succeeding node of the node C and the original data of the node B in the subsequent node C of the node B.

또한, 서버(100)는 백업을 수행한 모든 노드들로부터 각각의 노드들의 원본 데이터가 서버(100)로 전송되도록 하고, 전송된 모든 노드들의 원본 데이터와 서버(100)의 원본 데이터를 XOR 연산하여 패리티 데이터를 생성한 후, 생성한 패리티 데이터를 저장할 수 있다.
In addition, the server 100 causes the original data of each node to be transmitted from the all nodes that have performed the backup to the server 100, XORs the original data of all the transmitted nodes and the original data of the server 100 After generating the parity data, the generated parity data can be stored.

이하에서는, 단계 S100에서 시스템 제어정보를 분산 저장 가능한 하위의 노드 수가 5개 이상 20개 미만인 경우에 선택되는 EVENODD 결함허용 방법에 대해 도면을 참조하여 상세히 설명하도록 한다.
Hereinafter, an EVENODD fault tolerance method, which is selected when the number of lower-level nodes capable of distributing and storing system control information is less than 20 and less than 20 in step S100, will be described in detail with reference to the drawings.

단계 S100에서 결함허용 방법으로서 EVENODD 결함허용 방법이 선택된 경우, 서버(100)는 시스템 제어정보를 분산 저장 가능한 하위의 모든 노드들에게 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송할 수 있다. 또한, 서버(100)는 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 각각의 노드들에서 각각의 원본 데이터가 EVENODD 코드 기반으로 부호화되도록 하고, 생성된 부호화 데이터가 열 단위로 분할되어, 분할된 부호화 데이터가 시스템 제어정보를 분산 저장 가능한 노드들로 전송되도록 할 수 있다.
If the EVENODD fault tolerance method is selected as the fault tolerance method in step S100, the server 100 may transmit connection information of nodes capable of distributing system control information to all lower nodes capable of distributing system control information. In addition, the server 100 causes each of the nodes, which receive the connection information of the nodes capable of distributing the system control information, to encode each original data based on the EVENODD code, and the generated encoded data is divided into columns, And the divided coded data may be transmitted to nodes capable of distributing system control information.

도 4는 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, EVENODD 결함허용 방법이 선택된 경우, 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 노드에서 원본 데이터가 EVENODD 코드를 기반으로 부호화되고, 생성된 부호화 데이터가 열 단위로 분할되어, 분할된 부호화 데이터가 시스템 제어정보를 분산 저장 가능한 노드들에게 전송되는 장면을 도시한 도면이다. 도 4(a)에 도시된 바와 같이, 서버(100)는 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 노드 A에서 노드 A의 원본 데이터가 EVENODD 코드를 기반으로 부호화되도록 하고, 도 4(b)에 도시된 바와 같이, 생성된 부호화 데이터가 열 단위로 분할되어, 분할된 부호화 데이터가 시스템 제어정보를 분산 저장 가능한 노드들에게 전송되도록 할 수 있다. 여기서, 열 단위로 분할된 부호화 데이터는 각각의 열의 인덱스를 포함하여, 복구 시 해당 데이터가 몇 번째 열의 데이터인지 식별할 수 있도록 할 수 있다.
FIG. 4 is a diagram illustrating a method of allowing an EVENODD fault in a system having a hierarchical structure according to an exemplary embodiment of the present invention. When an EVENODD fault tolerance method is selected, Is encoded based on an EVENODD code, the generated encoded data is divided into units of a column, and the divided encoded data is transmitted to nodes capable of distributing system control information. As shown in FIG. 4A, the server 100 causes the source data of the node A to be encoded based on the EVENODD code in the node A, which receives the connection information of nodes capable of distributing system control information, the generated encoded data may be divided in units of columns and the divided encoded data may be transmitted to nodes capable of distributing system control information as shown in FIG. Here, the encoded data divided into columns may include the index of each column, so that it is possible to identify the data of the corresponding column when the data is restored.

또한, 서버(100)는 각각의 노드들에서 열 단위로 분할된 부호화 데이터를 전송받아 분산 저장하고 있는 각각의 노드들로부터, 분할된 부호화 데이터들이 어느 노드에 분산 저장되었는지에 대한 분산 저장 정보가 전송되도록 하고, 각각의 노드들로부터 전송받은 분산 저장 정보를 저장하여 복구 시 이용할 수 있다.
In addition, the server 100 receives distributed encoded data from the respective nodes and distributes the encoded encoded data to the nodes. And the distributed storage information transmitted from the respective nodes is stored and used for restoration.

이하에서는, 단계 S100에서 시스템 제어정보를 분산 저장 가능한 하위의 노드 수가 20개 이상인 경우에 선택되는 LT 결함허용 방법에 대해 도면을 참조하여 상세히 설명하도록 한다.
Hereinafter, the LT fault tolerance method selected when the number of lower nodes capable of distributing and storing system control information is 20 or more in step S100 will be described in detail with reference to the drawings.

단계 S100에서 결함허용 방법으로서 LT 결함허용 방법이 선택된 경우, 서버(100)는 시스템 제어정보를 분산 저장 가능한 하위의 모든 노드들에게 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송할 수 있다. 또한, 서버(100)는 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 각각의 노드들에서 원본 심볼의 수가 선택되도록 하고, 선택된 원본 심볼의 수에 따라 각각의 원본 데이터가 분할되도록 하며, 분할된 각각의 원본 데이터가 LT 코드 기반으로 부호화되도록 할 수 있다. 여기서, 원본 심볼의 수는 Celing(분산 저장 가능한 노드의 수 / 2)를 통해 구해질 수 있고, Celing은 소수점 올림을 의미한다. 예를 들어, 분산 저장 가능한 노드의 수가 20인 경우, 원본 심볼의 수는 10이 되고, 분산 저장 가능한 노드의 수가 21인 경우, 원본 심볼의 수는 11이 될 수 있다.
If the LT fault tolerance method is selected as the fault tolerance method in step S100, the server 100 can transmit connection information of nodes capable of distributing system control information to all lower nodes capable of distributing system control information. In addition, the server 100 causes the number of original symbols to be selected in each node that receives the connection information of nodes capable of distributing system control information, and divides each original data according to the number of selected original symbols, So that each divided original data can be encoded based on the LT code. Here, the number of original symbols can be obtained through Celing (the number of distributed storable nodes / 2), and Celing means decimal point rounding. For example, when the number of distributed storable nodes is 20, the number of original symbols is 10, and when the number of distributed storable nodes is 21, the number of original symbols can be 11.

도 5는 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, LT 결함허용 방법이 선택된 경우, 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 노드에서, 원본 심볼의 수에 따라 원본 데이터가 분할되고, 분할된 데이터가 LT 코드 기반으로 부호화되는 장면을 도시한 도면이다. 도 5에 도시된 바와 같이, 서버(100)는 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 노드 A에서 노드 A의 원본 데이터가 원본 심볼의 수에 따라 분할되도록 하며, 분할된 데이터가 LT 코드 기반으로 부호화되도록 할 수 있다.
FIG. 5 is a diagram illustrating a method of permitting an information defect in a system having a hierarchical structure according to an embodiment of the present invention. In the method, when an LT fault-tolerant method is selected, The original data is divided according to the number of symbols, and the divided data is encoded based on the LT code. As shown in FIG. 5, the server 100 divides the original data of the node A in the node A, which receives the connection information of the nodes capable of distributing system control information, according to the number of the original symbols, And can be encoded based on the LT code.

또한, 서버(100)는 각각의 노드들에서 LT 코드 기반으로 생성된 부호화 데이터들이 분산 저장 가능한 노드들에게 전송되어 저장되도록 할 수 있다. 도 6은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, LT 코드 기반으로 부호화된 데이터들이 분산 저장 가능한 노드들로 전송되는 장면을 도시한 도면이다. 도 6에 도시된 바와 같이, 서버(100)는 LT 코드 기반으로 부호화된 노드 A의 부호화 데이터들이 서버(100)를 포함하여 분산 저장 가능한 노드들로 전송되도록 할 수 있다.
In addition, the server 100 may transmit the encoded data generated on the basis of the LT code in each node to the nodes capable of being distributed and stored. FIG. 6 is a diagram illustrating a scene in which data encoded on an LT code basis is transmitted to nodes capable of distributed storage in an information fault tolerance method of a system having a hierarchical structure according to an embodiment of the present invention. As shown in FIG. 6, the server 100 may transmit coded data of the node A encoded based on the LT code to nodes that can be distributedly stored including the server 100.

더 나아가, 서버(100)는 각각의 노드들에서 LT 코드 기반으로 생성된 부호화 데이터를 전송받아 분산 저장하고 있는 각각의 노드들로부터, 분할된 부호화 데이터들이 각각 어느 노드에 분산 저장되었는지에 대한 분산 저장 정보가 전송되도록 하고, 각각의 노드들로부터 전송받은 분산 저장 정보를 저장하여 복구 시 이용할 수 있다.
In addition, the server 100 distributes encoded data generated based on the LT code at each node and distributes the encoded data to each node, Information can be transmitted, and distributed storage information transmitted from each node can be stored and used for restoration.

단계 S200에서 서버(100)는 시스템 제어정보를 분산 저장하고 있는 노드들 중, 원본 데이터에 결함이 발생한 노드로부터 원본 데이터 복구를 요청받을 수 있고, 단계 S300에서는 단계 S100에서 선택된 결함허용 방법에 따라 원본 데이터가 복구되도록 할 수 있다.
In step S200, the server 100 may be requested to recover the original data from the node where the defect occurred in the original data among the nodes storing and distributing the system control information. In step S300, Data can be restored.

이하에서는, 시스템 제어정보를 분산 저장하고 있는 노드들 중, 원본 데이터에 결함이 발생한 노드로부터 원본 데이터 복구를 요청받고, 단계 S100에서 결함허용 방법으로 RAID4+Daisy Chain 결함허용 방법이 선택된 경우, 결함이 발생한 노드의 데이터가 복구되도록 하는 과정에 대해 도면을 참조하여 상세히 설명하기로 한다.
Hereinafter, if the source data is requested to be recovered from the node where the source data is defective among the nodes that distribute and store the system control information, and the RAID4 + Daisy chain fault tolerance method is selected as the fault tolerance method in step S100, The process of causing data of a node to be recovered will be described in detail with reference to the drawings.

단계 R310에서 서버(100)는, 복구를 요청한 노드의 수를 확인할 수 있다.
In step R310, the server 100 can confirm the number of nodes requesting recovery.

이하에서는, 단계 R310에서 확인된 복구를 요청한 노드의 수가 1개인 경우, 복구를 요청한 노드의 원본 데이터가 복구되는 과정에 대해 도 7을 참조하여 상세히 설명하기로 한다.
Hereinafter, the process of restoring the original data of the node that requested the recovery will be described in detail with reference to FIG. 7, when the number of nodes requested to be restored in step R310 is one.

도 7은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법이 선택되고, 하나의 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드의 데이터가 복구되는 과정을 도시한 도면이다. 서버(100)는, 도 7의 (a)에 도시된 바와 같이, 노드 A에서 결함이 발생하여, 노드 A로부터 복구를 요청받으면, 도 7의 (b)에 도시된 바와 같이, 복구를 요청한 노드 A의 후속 노드를 검색한 후, 노드 A의 후속 노드 B에게 복구를 요청한 노드 A의 접속 정보를 추가한 복구 요청 메시지를 전달하고(R320), 도 7의 (c)에 도시된 바와 같이, 복구 요청 메시지를 수신한 노드 B로부터 복구를 요청한 노드 A에 백업 데이터가 전송되도록 하며(R330), 도 7의 (d)에 도시된 바와 같이, 노드 B로부터 전송받은 백업 데이터를 이용하여 노드 A의 원본 데이터가 복구되도록 할 수 있다(R340).
FIG. 7 is a flowchart illustrating a method of allowing a RAID4 + Daisy Chain fault tolerance method in a system having a hierarchical structure according to an exemplary embodiment of the present invention. When an information defect occurs in one distributed storage node, And recovering the data of the generated node. As shown in Fig. 7 (a), the server 100, when a defect occurs in the node A and is requested to recover from the node A, (R320), and adds the connection information of the node A requesting the recovery to the succeeding node B of the node A (R320). Then, as shown in (c) of FIG. 7, The backup data is transmitted to the node A that requested the recovery from the node B that received the request message (R330). As shown in (d) of FIG. 7, Thereby allowing the data to be recovered (R340).

이하에서는, 단계 R310에서 확인된 복구를 요청한 노드의 수가 2개이며 연속적인 경우, 복구를 요청한 노드들의 원본 데이터가 복구되는 과정에 대해 도 8을 참조하여 상세히 설명하기로 한다.
Hereinafter, the process of restoring the original data of the nodes requesting the restoration in the case where the number of nodes requested to be restored in step R310 is two consecutive, will be described in detail with reference to FIG.

도 8은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법이 선택되고, 2개의 연속적인 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드들의 데이터가 복구되는 과정을 도시한 도면이다. 서버(100)는, 도 8의 (a)에 도시된 바와 같이, 노드 A 및 노드 B의 연속적인 2개의 노드에서 결함이 발생하여, 노드 A 및 노드 B로부터 복구 요청을 받으면, 도 8의 (b)에 도시된 바와 같이, 복구를 요청한 2개의 노드들 중 높은 인덱스를 가진 노드 B의 후속 노드 C에 노드 B의 접속 정보를 포함한 복구 요청 메시지를 전달하고, 도 8의 (c)에 도시된 바와 같이, 복구 요청 메시지를 수신한 노드 C에서 노드 B에 백업 데이터가 전송되도록 하며, 전송된 백업 데이터를 이용하여 노드 B의 원본 데이터가 복구되도록 할 수 있다(R320). 또한, 서버(100)는 도 8의 (d)에 도시된 바와 같이, 복구를 요청한 2개의 노드들 중 낮은 인덱스를 가진 노드 A를 제외한 노드 B 및 노드 C로부터 각각의 원본 데이터가 전송되도록 하고, 전송받은 각각의 노드들의 원본 데이터와 저장되어 있는 패리티 데이터를 XOR 연산하여, 낮은 인덱스를 가진 노드 A의 원본 데이터를 생성할 수 있으며(R330), 도 8의 (e)에 도시된 바와 같이, 생성된 노드 A의 원본 데이터를 노드 A에 전송하여, 도 8의 (f)에 도시된 바와 같이, 낮은 인덱스를 가진 노드 A의 원본 데이터가 복구되도록 할 수 있다(R340).
FIG. 8 is a flowchart illustrating a method of allowing a RAID 4 + Daisy Chain fault tolerance method in an information fault tolerance method of a system having a hierarchical structure according to an exemplary embodiment of the present invention. When an information defect occurs in two consecutive distributed storage nodes, FIG. 5 is a diagram illustrating a process of recovering data of defective nodes. FIG. As shown in FIG. 8A, the server 100 receives a recovery request from the node A and the node B when a defect occurs in two consecutive nodes of the node A and the node B, As shown in FIG. 8B, the recovery request message including the connection information of the node B is transmitted to the subsequent node C of the node B having the high index among the two nodes requesting the recovery, As a result, the backup data is transmitted to the node B from the node C that received the recovery request message, and the original data of the node B can be recovered using the transmitted backup data (R320). 8 (d), the server 100 causes each original data to be transmitted from the node B and the node C excluding the node A having the low index among the two nodes that requested the recovery, The source data of the node A having the low index can be generated by performing the XOR operation on the original data of the transmitted nodes and the stored parity data (R330). As shown in (e) of FIG. 8, The original data of the node A that has been indexed can be transmitted to the node A so that the original data of the node A having the low index can be recovered as shown in (f) of FIG. 8 (R340).

이하에서는, 단계 R310에서 확인된 복구를 요청한 노드의 수가 2개이며 비연속적인 경우, 복구를 요청한 노드들의 원본 데이터가 복구되는 과정에 대해 도 9를 참조하여 상세히 설명하기로 한다.
Hereinafter, the process of restoring the original data of the nodes requesting the restoration in the case where the number of nodes requested to be restored in step R310 is two and discontinuous, will be described in detail with reference to FIG.

도 9는 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, RAID4+Daisy Chain 결함허용 방법이 선택되고, 2개의 비연속적인 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드들의 데이터가 복구되는 과정을 도시한 도면이다. 서버(100)는, 도 9의 (a)에 도시된 바와 같이, 노드 A 및 노드 C의 비연속적인 2개의 노드에서 결함이 발생하여, 노드 A 및 노드 C로부터 복구 요청을 받으면, 노드 A 및 노드 C의 후속 노드를 검색한 후, 도 9의 (b)에 도시된 바와 같이 노드 A의 후속 노드 B에 복구를 요청한 노드 A의 접속정보를 추가한 복구 요청 메시지를 전달하여(R320), 복구 요청 메시지를 수신한 노드 B로부터 노드 A에 백업 데이터가 전송되도록 하고(R330), 도 9의 (c)에 도시된 바와 같이 노드 C의 후속 노드인 서버(100)에서 노드 C로 백업 데이터를 전송하여, 전송된 백업 데이터를 이용하여 복구를 요청한 노드 A 및 노드 C의 원본 데이터가 도 9의 (d)에 도시된 바와 같이 복구되도록 할 수 있다(R340).
FIG. 9 is a flowchart illustrating a method of allowing a RAID4 + Daisy Chain fault tolerance method in a system having a hierarchical structure according to an exemplary embodiment of the present invention, when an information defect occurs in two discontinuous distributed storage nodes , And data of defective nodes are restored. The server 100 receives a recovery request from the node A and the node C when a defect occurs in two discontinuous nodes of the node A and the node C as shown in Fig. After retrieving the subsequent node of the node C, a recovery request message to which the connection information of the node A requesting the recovery to the succeeding node B of the node A is added as shown in FIG. 9B (R320) The backup data is transmitted from the node B that has received the request message to the node A (R330), and the backup data is transmitted from the server 100, which is the subsequent node of the node C, to the node C as shown in FIG. Then, the original data of the node A and the node C that requested the recovery using the transmitted backup data may be restored as shown in FIG. 9D (R340).

이하에서는, 시스템 제어정보를 분산 저장하고 있는 노드들 중, 원본 데이터에 결함이 발생한 노드로부터 원본 데이터 복구를 요청받고, 단계 S100에서 결함허용 방법으로 EVENODD 결함허용 방법이 선택된 경우, 결함이 발생한 노드의 데이터가 복구되도록 하는 과정에 대해 도면을 참조하여 상세히 설명하기로 한다.
Hereinafter, when the original data is requested to be recovered from the node where the defect occurs in the original data among the nodes storing and storing the system control information, and the EVENODD fault tolerance method is selected as the fault tolerance method in step S100, The process of allowing data to be recovered will be described in detail with reference to the drawings.

도 10은 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, EVENODD 결함허용 방법이 선택되고, 하나의 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드의 원본 데이터가 복구되는 과정을 도시한 도면이다. 실시예에 따라, 서버(100)는 원본 데이터에 결함이 발생한 노드 A로부터 복구를 요청받으면, 저장되어 있는 분산 저장 정보를 통해 복구를 요청한 노드 A의 부호화 데이터들이 저장되어 있는 노드들을 찾고, 도 10의 (a)에 도시된 바와 같이, 해당 노드들에게 노드 A의 접속 정보가 포함된 복구 요청 메시지를 전달하고(E310), 도 10의 (b)에 도시된 바와 같이, 노드 A의 부호화 데이터를 분산 저장하고 있는 노드들로부터 분산 저장된 부호화 데이터들이 노드 A로 전송되도록 한 후, 부호화 데이터들에 포함된 인덱스를 통해 부호화 데이터들의 배열이 재구성되도록 하며(E320), 분산 저장한 부호화 데이터 중 손실된 데이터와 인덱스를 확인하여 손실된 데이터의 수가 도 10의 (c)에 도시된 바와 같이 1이면, 하나의 열을 손실한 경우의 EVENODD 코드 복호화가 수행되도록 하고(E330), 생성된 복호화 데이터들이 원본 데이터가 분할된 역순으로 합병되도록 하여 노드 A의 원본 데이터가 복구되도록 할 수 있다(E340). 여기서, 실시예에 따라, 분산 저장된 부호화 데이터 중 손실된 데이터 열의 개수가 2이면, 두 열을 손실한 경우에 해당되는 EVENODD 코드 복호화가 수행되도록 할 수 있다. 이처럼, 분산 저장된 부호화 데이터 중 손실된 데이터의 열의 개수에 따라, EVENODD 코드 복호화 과정은 다르므로, 손실된 데이터의 열의 개수에 해당되는 EVENODD 코드 복호화가 수행되도록 할 수 있다.
FIG. 10 is a diagram illustrating a method of allowing an EVENODD fault in a system having a hierarchical structure according to an embodiment of the present invention. When an EVENODD fault tolerance method is selected and information defects are generated in one distributed storage node, FIG. 5 is a diagram showing a process in which original data is recovered. FIG. According to an embodiment, when the server 100 receives a request for recovery from a node A having a defect in original data, the server 100 searches for nodes storing encoded data of the node A requesting recovery through the stored distributed storage information, As shown in (a) of FIG. 10, transmits a recovery request message including the connection information of the node A to the nodes (E310), and transmits the encoded data of the node A The encoded data distributed and stored from the distributed nodes are transmitted to the node A, the encoded data is rearranged through the index included in the encoded data (E320), and the lost data And the index is checked and if the number of lost data is 1 as shown in FIG. 10 (c), the decoding of the EVENODD code in the case where one row is lost is performed (E330). The generated decoded data may be merged in the reverse order in which the original data is divided, so that the original data of the node A can be recovered (E340). Here, according to the embodiment, when the number of lost data strings is 2 among the distributed stored encoded data, EVENODD code decoding corresponding to the loss of two columns can be performed. Since the decoding process of the EVENODD code differs according to the number of columns of the lost data among the distributed coded data, the decoding of the EVENODD code corresponding to the number of the lost data rows can be performed.

이하에서는, 시스템 제어정보를 분산 저장하고 있는 노드들 중, 원본 데이터에 결함이 발생한 노드로부터 원본 데이터 복구를 요청받고, 단계 S100에서 결함허용 방법으로 LT 결함허용 방법이 선택된 경우, 결함이 발생한 노드의 데이터가 복구되도록 하는 과정에 대해 도면을 참조하여 상세히 설명하기로 한다.
Hereinafter, when the source data is requested to be recovered from the node where the source data is defective among the nodes that distribute and store the system control information, and the LT fault tolerance method is selected as the fault tolerance method in step S100, The process of allowing data to be recovered will be described in detail with reference to the drawings.

도 11에서 본 발명의 일실시예에 따른 계층적 구조를 갖는 시스템의 정보 결함허용 방법에서, LT 결함허용 방법이 선택되고, 하나의 분산 저장 노드에서 정보 결함이 발생되었을 때, 결함이 발생한 노드의 데이터가 복구되는 과정을 도시한 도면이다. 실시예에 따라, 서버(100)는 원본 데이터에 결함이 발생한 노드 A로부터 복구를 요청받으면, 저장되어 있는 분산 저장 정보를 통해 복구를 요청한 노드 A의 부호화 데이터들이 저장되어 있는 노드들을 찾고, 도 11의 (a)에 도시된 바와 같이, 해당 노드들에게 노드 A의 접속 정보가 포함된 복구 요청 메시지를 전달하고(L310), 도 11의 (b)에 도시된 바와 같이, 노드 A의 부호화 데이터를 분산 저장하고 있는 노드들로부터 분산 저장된 부호화 데이터들이 노드 A로 전송되도록 한 후, 전송된 부호화 데이터들에 대해 LT 코드 복호화가 수행되도록 하며(L320), 도 11의 (c)에 도시된 바와 같이, LT 코드 복호화를 통해 생성된 원본 심볼들이 원본 데이터가 분할된 역순으로 합병되도록 하여, 노드 A의 원본 데이터가 복구되도록 할 수 있다(L330).
11, in the information fault tolerance method of a system having a hierarchical structure according to an embodiment of the present invention, when an LT fault tolerance method is selected and an information defect occurs in one distributed storage node, FIG. 5 is a diagram showing a process in which data is recovered. FIG. According to the embodiment, when the server 100 is requested to recover from the node A having a defect in the original data, the server 100 searches for the nodes storing the encoded data of the node A that requested the recovery through the stored distributed storage information, As shown in (a) of FIG. 11, a recovery request message including the connection information of the node A is transmitted to the nodes (L310), and as shown in FIG. 11 (b) The encoded data distributed and stored from the distributed nodes are transmitted to the node A, and the LT code decoding is performed on the transmitted encoded data (L320). As shown in FIG. 11C, The original symbols generated through the LT code decoding may be merged in the reverse order in which the original data is divided so that the original data of the node A can be recovered (L330).

이상 설명한 바와 같이, 본 발명에서 제안하고 있는 계층적 구조를 갖는 시스템의 정보 결함허용 방법에 따르면, 계층적 구조를 갖는 시스템에서 시스템 제어정보를 분산 저장 가능한 서버 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하고, 선택된 결함허용 방법에 의해 시스템 제어정보를 시스템 내의 분산 저장 가능한 노드들에 분산 저장하여, 원본 제어정보에 결함이 발생하였을 때, 분산 저장된 정보를 바탕으로 원본 시스템 제어정보를 복구함으로써, 지속적이고 안정적인 소프트웨어 동작을 보장할 수 있다.
As described above, according to the information fault tolerance method for a system having a hierarchical structure proposed in the present invention, in a system having a hierarchical structure, the system control information can be distributed and stored in a RAID4 + Daisy chain A defect-tolerant method, a fault-tolerant method, an EVENODD fault-tolerant method and an LT fault-tolerant method, and distributes the system control information to the distributed storable nodes in the system by the selected fault- It is possible to guarantee continuous and stable software operation by restoring the original system control information based on the distributed stored information.

이상 설명한 본 발명은 본 발명이 속한 기술분야에서 통상의 지식을 가진 자에 의하여 다양한 변형이나 응용이 가능하며, 본 발명에 따른 기술적 사상의 범위는 아래의 특허청구범위에 의하여 정해져야 할 것이다.The present invention may be embodied in many other specific forms without departing from the spirit or essential characteristics of the invention.

100: 서버
S100: 시스템 제어정보를 분산 저장 가능한 하위의 노드 수를 확인하고, 확인된 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하며, 선택된 결함허용 방법에 따라 시스템 제어정보가 시스템 내의 분산 저장 가능한 노드들에 분산 저장되도록 하는 단계
S200: 시스템 제어정보를 분산 저장하고 있는 노드들 중, 원본 데이터에 결함이 발생한 노드로부터 원본 데이터 복구를 요청받는 단계
S300: 단계 S100에서 선택된 결함허용 방법에 따라 원본 데이터가 복구되도록 하는 단계
R310: 복구를 요청한 노드의 수를 확인하는 단계
R320: 단계 R310에서 확인된 복구를 요청한 노드의 수가 1개인 경우, 복구를 요청한 노드의 후속 노드를 검색한 후, 후속 노드에게 복구를 요청한 노드의 접속 정보를 추가한 복구 요청 메시지를 전달하는 단계
R330: 복구 요청 메시지를 수신한 후속 노드에서 복구를 요청한 노드에 백업 데이터가 전송되도록 하는 단계
R340: 단계 R330을 통해 전송된 백업 데이터를 이용하여 복구를 요청한 노드의 원본 데이터가 복구되도록 하는 단계
R320: 단계 R310에서 확인된 복구를 요청한 노드의 수가 2개이고, 2개 노드의 인덱스가 연속적인 경우, 복구를 요청한 2개의 노드 중 높은 인덱스를 가진 노드의 후속 노드에 높은 인덱스를 가진 노드의 접속 정보를 포함한 복구 요청 메시지를 전달하고, 단계 R330 및 R340을 통해 높은 인덱스를 가진 노드의 원본 데이터가 복구되도록 하는 단계
R330: 복구를 요청한 2개의 노드 중 낮은 인덱스를 가진 노드를 제외한 모든 노드들로부터 각각의 원본 데이터가 전송되도록 하며, 전송받은 모든 원본 데이터와 저장되어 있는 패리티 데이터를 XOR 연산하여, 낮은 인덱스를 가진 노드의 원본 데이터를 생성하는 단계
R340:단계 R330을 통해 생성된 원본 데이터를 낮은 인덱스를 가진 노드에게 전송하여, 낮은 인덱스를 가진 노드의 원본 데이터가 복구되도록 하는 단계
R320: 단계 R310에서 확인된 복구를 요청한 노드의 수가 2개이고, 2개 노드의 인덱스가 비연속적인 경우, 복구를 요청한 각각의 노드의 후속 노드를 검색한 후, 각각의 후속 노드에게 복구를 요청한 각각의 노드의 접속 정보를 추가한 복구 요청 메시지를 전달하는 단계
R330: 복구 요청 메시지를 수신한 각각의 후속 노드로부터 복구를 요청한 각각의 노드에 백업 데이터가 전송되도록 하는 단계
R340: 단계 R330을 통해 전송된 백업 데이터를 이용하여 복구를 요청한 각각의 노드의 원본 데이터가 복구되도록 하는 단계
E310: 분산 저장 정보를 통해 복구를 요청한 노드의 부호화 데이터들이 저장되어 있는 노드들을 찾고, 노드들에게 복구를 요청한 노드의 접속 정보가 포함된 복구 요청 메시지를 전달하는 단계
E320: 복구를 요청한 노드의 부호화 데이터들을 분산 저장하고 있는 노드들로부터 분산 저장된 부호화 데이터들이 복구를 요청한 노드로 전송되도록 한 후, 부호화 데이터들에 포함된 인덱스를 통해 부호화 데이터들의 배열이 재구성되도록 하는 단계
E330: 단계 E320을 통해 부호화 데이터들의 배열이 재구성되도록 한 후, 분산 저장된 부호화 데이터들 중 손실된 데이터 개수 따라 그에 해당되는 EVENODD 코드 복호화가 수행되도록 하는 단계
E340: 단계 E330을 통해 생성된 복호화 데이터들이 원본 데이터가 분할된 역순으로 합병되도록 하여, 원본 데이터가 복구되도록 하는 단계
L310: 분산 저장 정보를 통해 복구를 요청한 노드의 부호화 데이터들이 저장되어 있는 노드들을 찾고, 노드들에게 복구를 요청한 노드의 접속 정보가 포함된 복구 요청 메시지를 전달하는 단계
L320: 복구를 요청한 노드의 부호화 데이터를 분산 저장하고 있는 노드들로부터 분산 저장된 부호화 데이터들이 복구를 요청한 노드로 전송되도록 한 후, 전송된 부호화 데이터들에 대해 LT 코드 복호화가 수행되도록 하는 단계
L330: 단계 L320의 LT 코드 복호화를 통해 생성된 원본 심볼들이 원본 데이터가 분할된 역순으로 합병되도록 하여, 원본 데이터가 복구되도록 하는 단계100: Server
S100: Check the number of subordinate nodes that can distribute system control information and select the fault tolerance method of one of RAID4 + Daisy Chain fault tolerance method, EVENODD fault tolerance method and LT fault tolerance method according to the number of nodes identified. And causing system control information to be distributedly stored in the distributed storable nodes in the system according to the selected fault tolerant method
S200: Receiving the original data recovery request from the node where the source data is defective among the nodes storing and storing the system control information
S300: step of restoring the original data according to the fault tolerance method selected in step S100
R310: Checking the number of nodes that requested recovery
R320: If the number of nodes requesting recovery is 1 in step R310, a subsequent node of the node requesting recovery is searched, and then a recovery request message to which the connection information of the node requesting recovery is added to the subsequent node
R330: step of causing backup data to be transmitted to the node that requested recovery from the succeeding node that received the recovery request message
R340: Restoring the original data of the node that requested the recovery using the backup data transmitted through step R330
R320: If the number of nodes requested to be restored in step R310 is 2, and the indexes of two nodes are consecutive, the connection information of a node having a high index to a subsequent node of a node having a high index among the two nodes requesting restoration And restoring the original data of the node having the high index through steps R330 and R340
R330: Each original data is transmitted from all the nodes except the node having the low index among the two nodes that requested the recovery, and XOR operation is performed on all the transmitted original data and the stored parity data, A step of generating source data of
R340: transmitting original data generated through step R330 to a node having a low index so that original data of a node having a low index is recovered
R320: If the number of nodes requested to be recovered in step R310 is 2, and the indices of two nodes are non-contiguous, after searching for the next node of each node requesting recovery, A step of transmitting a recovery request message to which the connection information of the node of the node
R330: causing backup data to be transmitted to each node requesting recovery from each subsequent node that received the recovery request message
R340: Restoring original data of each node requesting recovery using the backup data transmitted through step R330
E310: searching nodes storing coded data of a node requesting recovery through distributed storage information, and delivering a recovery request message including access information of a node requesting recovery to nodes
E320: causing distributed encoded data to be transmitted to nodes requesting recovery from distributed nodes storing encoded data of a node requesting recovery, and then reconstructing an array of encoded data through an index included in encoded data
E330: After allowing the arrangement of the encoded data to be reconstructed through step E320, the EVENODD code decoding corresponding to the number of lost data stored in the distributed coded data is performed
E340: decrypting the decrypted data generated in step E330 by merging the original data in the reverse order in which the original data is divided, so that the original data is recovered
L310: searching for nodes storing coded data of a node requesting recovery through distributed storage information, and delivering a recovery request message including access information of a node requesting recovery to nodes
L320: causing the encoded data distributedly stored from distributed nodes to be transmitted to the node requesting recovery, and then performing LT code decoding on the transmitted encoded data
L330: causing the original symbols generated through the LT code decoding in step L320 to be merged in the reverse order in which the original data is divided, so that the original data is recovered

Claims (20)

시스템의 정보 결함허용 방법으로서, 서버(100)에서,
(1) 시스템 제어정보를 분산 저장 가능한 하위의 노드 수를 확인하고, 상기 확인된 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하며, 상기 선택된 결함허용 방법에 따라 시스템 제어정보가 상기 시스템 내의 분산 저장 가능한 노드들에 분산 저장되도록 하는 단계(S100);
(2) 상기 시스템 제어정보를 분산 저장하고 있는 노드들 중, 원본 데이터에 결함이 발생한 노드로부터 원본 데이터 복구를 요청받는 단계(S200); 및
(3) 상기 단계 (1)에서 선택된 결함허용 방법에 따라 원본 데이터가 복구되도록 하는 단계(S300)를 포함하되,
상기 단계 (1)에서,
상기 시스템 제어정보를 분산 저장 가능한 하위의 노드 수가 5개 미만인 경우에는 RAID4+Daisy Chain 결함허용 방법, 5개 이상 20개 미만인 경우에는 EVENODD 결함허용 방법, 20개 이상인 경우에는 LT 결함허용 방법을 선택하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
As an information fault tolerant method of the system, in the server 100,
(1) a fault tolerance method of one of RAID 4 + Daisy Chain fault tolerance method, EVENODD fault tolerance method, and LT fault tolerance method according to the number of the lower-level nodes that are capable of distributing system control information, (S100) the system control information to be distributedly stored in the distributed storable nodes in the system according to the selected fault tolerance method;
(2) a step (S200) of requesting restoration of original data from a node where a defect occurs in the original data among the nodes distributing and storing the system control information; And
(3) causing the original data to be recovered in accordance with the fault tolerance method selected in the step (1) (S300)
In the step (1)
A RAID4 + Daisy Chain fault tolerance method when the number of lower nodes capable of distributing the system control information is less than 5, an EVENODD fault tolerance method when more than 5 but less than 20, and an LT fault tolerance method when more than 20 nodes are selected Wherein the error information is information of the information structure of a system having a hierarchical structure.
제1항에 있어서, 상기 서버(100)는,
상기 시스템 제어정보를 분산 저장 가능한 하위의 노드가 추가 또는 삭제되는 작업이 수행될 때마다 상기 시스템 제어정보를 분산 저장 가능한 하위의 노드 수를 확인하고, 상기 확인된 하위의 노드 수에 따라 RAID4+Daisy Chain 결함허용 방법, EVENODD 결함허용 방법 및 LT 결함허용 방법 중 하나의 결함허용 방법을 선택하며, 상기 선택된 결함허용 방법에 따라 시스템 제어정보가 상기 시스템 내의 분산 저장 가능한 노드들에 분산 저장되도록 하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
The server (100) according to claim 1, wherein the server (100)
The system control information can be distributed and stored every time an operation for adding or deleting a lower node capable of distributing the system control information is performed, Wherein the system control information is distributedly stored in the distributed storable nodes in the system in accordance with the selected fault tolerance method. The system according to claim 1, wherein the fault tolerance method comprises a fault tolerance method, a chain fault tolerance method, an EVENODD fault tolerance method and an LT fault tolerance method. Wherein the information error tolerance method is a system having a hierarchical structure.
삭제delete 제1항에 있어서, 상기 서버(100)는, 결함허용 방법으로서 상기 RAID4+Daisy Chain 결함허용 방법이 선택된 경우,
시스템 제어정보를 분산 저장 가능한 하위의 모든 노드들에게 순차적인 인덱스를 부여하고, 상기 인덱스가 부여된 각각의 노드들에게 하기의 수학식을 이용하여 후속 노드의 인덱스를 지정하도록 해서 Daisy Chain이 형성되도록 하며, 상기 형성된 Daisy Chain 정보를 저장하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
[수학식]
Nodei -> Node<i+1>M, 0 ≤ i ≤ M-1
여기서, M은 노드 수, i는 인덱스, ‘->’화살표는 i인 인덱스 노드에 후속 노드를 배정하는 것, <i+1>M은 i+1 Modulo M을 나타낸다.
2. The method of claim 1, wherein the server (100), when the RAID4 + Daisy Chain fault tolerance method is selected as a fault tolerance method,
A sequential index is assigned to all the lower nodes capable of distributing system control information, and an index of a subsequent node is assigned to each of the nodes to which the index is assigned by using the following equation so that a daisy chain is formed And stores the generated Daisy chain information.
[Mathematical Expression]
Nodei -> Node <i + 1> M , 0? I? M-1
Here, M represents the number of nodes, i represents an index, and arrows '->' indicate assignments of subsequent nodes to an index node i, and <i + 1> M represents i + 1 Modulo M.
제4항에 있어서, 상기 서버(100)는,
상기 인덱스가 부여된 모든 노드들에게 후속 노드의 접속 정보가 포함된 백업 유도 메시지를 전송하여, 상기 노드들이 각각의 원본 데이터를 후속 노드에게 전송하도록 하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
5. The system according to claim 4, wherein the server (100)
Wherein the node transmits a backup induction message including connection information of a subsequent node to all nodes to which the index is assigned, so that the nodes transmit respective original data to a subsequent node. Information fault tolerance method.
제5항에 있어서, 상기 서버(100)는,
상기 백업을 수행한 모든 노드들로부터 원본 데이터가 전송되도록 하며, 상기 전송받은 모든 노드들의 원본 데이터와 저장된 원본 데이터를 XOR 연산하여 패리티 데이터를 생성한 후 저장하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
6. The method of claim 5, wherein the server (100)
The source data is transmitted from all the nodes that have performed the backup, and XOR operation is performed on the original data of all the received nodes and the stored original data to generate parity data, and then the parity data is stored. Information fault tolerance method in the system.
제1항에 있어서, 상기 서버(100)는, 결함허용 방법으로서 상기 EVENODD 결함허용 방법이 선택된 경우,
상기 시스템 제어정보를 분산 저장 가능한 하위의 모든 노드들에게 상기 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
2. The method of claim 1, wherein the server (100), when the EVENODD fault tolerance method is selected as a fault tolerance method,
Wherein the connection information of nodes capable of distributively storing the system control information is transmitted to all lower nodes capable of distributing the system control information.
제7항에 있어서, 상기 서버(100)는,
상기 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 각각의 노드들에서 각각의 원본 데이터가 EVENODD 코드를 기반으로 부호화되도록 하고, 상기 생성된 부호화 데이터가 열 단위로 분할되어, 상기 분할된 부호화 데이터가 상기 시스템 제어정보를 분산 저장 가능한 노드들로 전송되도록 하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
8. The method of claim 7, wherein the server (100)
Each of the nodes receiving the connection information of the nodes capable of distributing the system control information is caused to encode each original data based on the EVENODD code, and the generated encoded data is divided into columns, Wherein data is transmitted to nodes capable of distributing the system control information. &Lt; Desc / Clms Page number 19 &gt;
제8항에 있어서,
상기 열 단위로 분할된 부호화 데이터는 각각의 열의 인덱스를 포함하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
9. The method of claim 8,
Wherein the encoded data divided by the column unit includes an index of each column.
제8항에 있어서, 상기 서버(100)는,
상기 각각의 노드들에서 열 단위로 분할된 부호화 데이터를 전송받아 분산 저장하고 있는 상기 각각의 노드들로부터, 분할된 부호화 데이터들이 어느 노드에 분산 저장되었는지에 대한 분산 저장 정보가 전송되도록 하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
The system according to claim 8, wherein the server (100)
And distributed storage information indicating to which node the divided encoded data is stored is transmitted from each of the nodes that receive and store the encoded data divided by columns in each of the nodes. A method for permitting an information fault in a system having a hierarchical structure.
제10항에 있어서, 상기 서버(100)는,
상기 각각의 노드들로부터 전송받은 분산 저장 정보를 저장하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
11. The system according to claim 10, wherein the server (100)
And storing the distributed storage information transmitted from each of the nodes.
제1항에 있어서, 상기 서버(100)는, 결함허용 방법으로서 상기 LT 결함허용 방법이 선택된 경우,
상기 시스템 제어정보를 분산 저장 가능한 하위의 모든 노드들에게 상기 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
The method of claim 1, wherein the server (100), when the LT fault tolerance method is selected as a fault tolerance method,
Wherein the connection information of nodes capable of distributively storing the system control information is transmitted to all lower nodes capable of distributing the system control information.
제12항에 있어서, 상기 서버(100)는,
상기 시스템 제어정보를 분산 저장 가능한 노드들의 접속 정보를 전송받은 각각의 노드들에서 원본 심볼의 수가 선택되도록 하고, 상기 선택된 원본 심볼의 수에 따라 각각의 원본 데이터가 분할되도록 하며, 상기 분할된 각각의 원본 데이터가 LT 코드 기반으로 부호화되도록 하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
13. The system according to claim 12, wherein the server (100)
The number of original symbols is selected in each of the nodes to which connection information of nodes capable of distributively storing the system control information is transmitted, and each original data is divided according to the number of the selected original symbols, Wherein the original data is encoded based on an LT code.
제13항에 있어서, 상기 서버(100)는,
상기 각각의 노드들로부터 생성된 부호화 데이터들이 분산 저장 가능한 노드들에게 전송되어 저장되도록 하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
14. The system according to claim 13, wherein the server (100)
Wherein the encoded data generated from each of the nodes is transmitted to and stored in nodes capable of being distributed and stored.
제14항에 있어서, 상기 서버(100)는,
상기 각각의 노드들에서 부호화된 데이터를 전송받아 분산 저장하고 있는 상기 각각의 노드들로부터, 분할된 부호화 데이터들이 어느 노드에 분산 저장되었는지에 대한 분산 저장 정보가 전송되도록 하며, 상기 전송받은 분산 저장 정보를 저장하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
15. The system of claim 14, wherein the server (100)
And distributed storage information indicating to which node the divided encoded data is distributed is transmitted from each of the nodes that receive encoded data from the respective nodes and distribute and store the distributed encoded data, The method comprising the steps of: storing information of a plurality of information elements in a hierarchical structure;
제1항에 있어서, 상기 단계 (3)은,
상기 단계 (1)에서 상기 RAID4+Daisy Chain 결함허용 방법이 선택된 경우,
(3-R1) 상기 복구를 요청한 노드의 수를 확인하는 단계(R310);
(3-R2) 상기 단계 (3-R1)에서 확인된 복구를 요청한 노드의 수가 1개인 경우, 상기 복구를 요청한 노드의 후속 노드를 검색한 후, 상기 후속 노드에게 복구를 요청한 노드의 접속 정보를 추가한 복구 요청 메시지를 전달하는 단계(R320);
(3-R3) 상기 복구 요청 메시지를 수신한 상기 후속 노드에서 상기 복구를 요청한 노드에 백업 데이터가 전송되도록 하는 단계(R330); 및
(3-R4) 상기 단계 (3-R3)을 통해 전송된 백업 데이터를 이용하여 상기 복구를 요청한 노드의 원본 데이터가 복구되도록 하는 단계(R340)를 더 포함하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
2. The method of claim 1, wherein step (3)
If the RAID4 + Daisy chain fault tolerance method is selected in step (1)
(3-R1) confirming the number of nodes requesting the recovery (R310);
(3-R 2) If the number of nodes requested to be restored in the step (3-R 1) is 1, a search is made for the next node of the node requesting the restoration, Transmitting an added recovery request message (R320);
(R3-R3) the backup data is transmitted to the node requesting the recovery from the succeeding node that received the recovery request message (R330); And
(3-R4) restoring the original data of the node requesting the recovery using the backup data transmitted through the step (3-R3) (step R340). Information fault tolerant system.
제16항에 있어서, 상기 단계 (3)은,
상기 단계 (1)에서 상기 RAID4+Daisy Chain 결함허용 방법이 선택된 경우,
(3-R1) 상기 복구를 요청한 노드의 수를 확인하는 단계(R310);
(3-R2) 상기 단계 (3-R1)에서 확인된 복구를 요청한 노드의 수가 2개이고, 상기 2개 노드의 인덱스가 연속적인 경우, 상기 복구를 요청한 2개의 노드 중 높은 인덱스를 가진 노드의 후속 노드에 상기 높은 인덱스를 가진 노드의 접속 정보를 포함한 복구 요청 메시지를 전달하고, 상기 단계 (3-R3) 및 (3-R4)를 통해 높은 인덱스를 가진 노드의 원본 데이터가 복구되도록 하는 단계(R320);
(3-R3) 상기 복구를 요청한 2개의 노드 중 낮은 인덱스를 가진 노드를 제외한 모든 노드들로부터 각각의 원본 데이터가 전송되도록 하며, 상기 전송받은 모든 원본 데이터와 상기 저장되어 있는 패리티 데이터를 XOR 연산하여, 상기 낮은 인덱스를 가진 노드의 원본 데이터를 생성하는 단계(R330); 및
(3-R4) 단계 (3-R3)을 통해 생성된 원본 데이터를 낮은 인덱스를 가진 노드에게 전송하여, 상기 낮은 인덱스를 가진 노드의 원본 데이터가 복구되도록 하는 단계(R340)를 더 포함하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
17. The method of claim 16, wherein step (3)
If the RAID4 + Daisy chain fault tolerance method is selected in step (1)
(3-R1) confirming the number of nodes requesting the recovery (R310);
(3-R2) If the number of nodes requested to be restored in step (3-R1) is two and the indices of the two nodes are consecutive, a subsequent one of the two nodes (3-R3) and (3-R4) to recover the original data of the node having the high index (R320 );
(3-R3) The original data is transmitted from all the nodes except for the node having the low index among the two nodes requesting the restoration, and the original data and the stored parity data are XORed Generating (R330) original data of the node having the lower index; And
(3-R4) transmitting the original data generated through the step (3-R3) to the node having the lower index, and restoring the original data of the node having the lower index (step R340) Wherein the information error tolerance method is a system having a hierarchical structure.
제16항에 있어서, 상기 단계 (3)은,
상기 단계 (1)에서 상기 RAID4+Daisy Chain 결함허용 방법이 선택된 경우,
(3-R1) 상기 복구를 요청한 노드의 수를 확인하는 단계(R310);
(3-R2) 상기 단계 (3-R1)에서 확인된 복구를 요청한 노드의 수가 2개이고, 상기 2개 노드의 인덱스가 비연속적인 경우, 상기 복구를 요청한 각각의 노드의 후속 노드를 검색한 후, 상기 각각의 후속 노드에게 복구를 요청한 각각의 노드의 접속 정보를 추가한 복구 요청 메시지를 전달하는 단계(R320);
(3-R3) 상기 복구 요청 메시지를 수신한 상기 각각의 후속 노드로부터 상기 복구를 요청한 각각의 노드에 백업 데이터가 전송되도록 하는 단계(R330); 및
(3-R4) 상기 단계 (3-R3)을 통해 전송된 백업 데이터를 이용하여 상기 복구를 요청한 각각의 노드의 원본 데이터가 복구되도록 하는 단계(R340)를 더 포함하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
17. The method of claim 16, wherein step (3)
If the RAID4 + Daisy chain fault tolerance method is selected in step (1)
(3-R1) confirming the number of nodes requesting the recovery (R310);
(3-R2) If the number of nodes requested to be restored in step (3-R1) is two and the indexes of the two nodes are non-contiguous, a subsequent node of each node requesting the restoration is searched (R320) of adding a connection request of each node requesting recovery to each of the subsequent nodes;
(R3-R3) transferring backup data to each node that requested the recovery from each subsequent node that received the recovery request message (R330); And
(R340) of restoring the original data of each node requesting the restoration using the backup data transmitted through the step (3-R3) in step (3-R4). Information fault tolerant system.
제1항에 있어서, 상기 단계 (3)은,
상기 단계 (1)에서 상기 EVENODD 결함허용 방법이 선택된 경우,
(3-E1) 분산 저장 정보를 통해 복구를 요청한 노드의 부호화 데이터들이 저장되어 있는 노드들을 찾고, 상기 노드들에게 복구를 요청한 노드의 접속 정보가 포함된 복구 요청 메시지를 전달하는 단계(E310);
(3-E2) 상기 복구를 요청한 노드의 부호화 데이터들을 분산 저장하고 있는 노드들로부터 분산 저장된 부호화 데이터들이 상기 복구를 요청한 노드로 전송되도록 한 후, 상기 부호화 데이터들에 포함된 인덱스를 통해 상기 부호화 데이터들의 배열이 재구성되도록 하는 단계(E320);
(3-E3) 상기 단계 (3-E2)를 통해 상기 부호화 데이터들의 배열이 재구성되도록 한 후, 분산 저장된 부호화 데이터들 중 손실된 데이터 개수 따라 그에 해당되는 EVENODD 코드 복호화가 수행되도록 하는 단계(E330); 및
(3-E4) 상기 단계 (3-E3)을 통해 생성된 복호화 데이터들이 원본 데이터가 분할된 역순으로 합병되도록 하여, 원본 데이터가 복구되도록 하는 단계(E340)를 더 포함하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.
2. The method of claim 1, wherein step (3)
If the EVENODD fault tolerance method is selected in step (1)
(E310) searching for nodes storing coded data of a node requesting recovery through distributed storage information, and transmitting a recovery request message including access information of a node requesting recovery to the nodes (E310);
(3-E2) the encoded data distributed and stored from the nodes storing the encoded data of the node requesting the restoration to be transmitted to the node requesting the restoration, and then transmitting the encoded data through the index included in the encoded data (E320);
(3-E3) causing the arrangement of the encoded data to be reconstructed through the step (3-E2), and performing EVENODD code decoding corresponding to the number of lost data among the distributed coded data E330 ; And
(E340) causing the decoded data generated in the step (3-E3) to be merged in the reverse order in which the original data is divided so that the original data is recovered. Information defect tolerance method of a system having a redundant structure.
제1항에 있어서, 상기 단계 (3)은,
상기 단계 (1)에서 상기 LT 결함허용 방법이 선택된 경우,
(3-L1) 분산 저장 정보를 통해 복구를 요청한 노드의 부호화 데이터들이 저장되어 있는 노드들을 찾고, 상기 노드들에게 복구를 요청한 노드의 접속 정보가 포함된 복구 요청 메시지를 전달하는 단계(L310);
(3-L2) 상기 복구를 요청한 노드의 부호화 데이터를 분산 저장하고 있는 노드들로부터 분산 저장된 부호화 데이터들이 상기 복구를 요청한 노드로 전송되도록 한 후, 상기 전송된 부호화 데이터들에 대해 LT 코드 복호화가 수행되도록 하는 단계(L320); 및
(3-L3) 상기 단계 (3-L2)의 LT 코드 복호화를 통해 생성된 원본 심볼들이 원본 데이터가 분할된 역순으로 합병되도록 하여, 원본 데이터가 복구되도록 하는 단계(L330)를 더 포함하는 것을 특징으로 하는, 계층적 구조를 갖는 시스템의 정보 결함허용 방법.2. The method of claim 1, wherein step (3)
If the LT fault tolerance method is selected in step (1)
(L310) searching for nodes storing coded data of the node requesting recovery through the (3-L1) distributed storage information and delivering a recovery request message including access information of the node requesting recovery to the nodes;
(3-L2), the encoded data distributedly stored from the nodes storing the encoded data of the node requesting the recovery is transmitted to the node requesting the recovery, and then the LT code decoding is performed on the transmitted encoded data (L320); And
(3-L3) The step (L330) further comprises a step (L330) of causing the original symbols generated through the LT code decoding in the step (3-L2) to merge the original data in the reverse order in which the original data is divided, Wherein the information error tolerance method is a system having a hierarchical structure.
KR1020160007955A 2016-01-22 2016-01-22 A fault tolerant method for a hierarchical system Expired - Fee Related KR101756136B1 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020160007955A KR101756136B1 (en) 2016-01-22 2016-01-22 A fault tolerant method for a hierarchical system

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020160007955A KR101756136B1 (en) 2016-01-22 2016-01-22 A fault tolerant method for a hierarchical system

Publications (1)

Publication Number Publication Date
KR101756136B1 true KR101756136B1 (en) 2017-07-26

Family

ID=59426928

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020160007955A Expired - Fee Related KR101756136B1 (en) 2016-01-22 2016-01-22 A fault tolerant method for a hierarchical system

Country Status (1)

Country Link
KR (1) KR101756136B1 (en)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108228382A (en) * 2018-01-11 2018-06-29 成都信息工程大学 A kind of data reconstruction method for EVENODD code single-deck failures
KR102067440B1 (en) * 2018-07-11 2020-01-17 인하대학교 산학협력단 Method and Apparatus for hierarchical RAID with erasure coding accelerating based on virtual GPU

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2007140829A (en) * 2005-11-17 2007-06-07 Fujitsu Ltd Backup system, method and program
JP2015201027A (en) * 2014-04-08 2015-11-12 日本電信電話株式会社 Nodes and programs

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2007140829A (en) * 2005-11-17 2007-06-07 Fujitsu Ltd Backup system, method and program
JP2015201027A (en) * 2014-04-08 2015-11-12 日本電信電話株式会社 Nodes and programs

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108228382A (en) * 2018-01-11 2018-06-29 成都信息工程大学 A kind of data reconstruction method for EVENODD code single-deck failures
CN108228382B (en) * 2018-01-11 2021-08-10 成都信息工程大学 Data recovery method for single-disk fault of EVENODD code
KR102067440B1 (en) * 2018-07-11 2020-01-17 인하대학교 산학협력단 Method and Apparatus for hierarchical RAID with erasure coding accelerating based on virtual GPU

Similar Documents

Publication Publication Date Title
EP2394220B1 (en) Distributed storage of recoverable data
US20190205209A1 (en) Layering a distributed storage system into storage groups and virtual chunk spaces for efficient data recovery
CN110212923B (en) Distributed erasure code storage system data restoration method based on simulated annealing
JP4546387B2 (en) Backup system, method and program
CN105260259B (en) A kind of locality based on system minimum memory regeneration code repairs coding method
CN109814807B (en) Data storage method and device
WO2020047707A1 (en) Data coding, decoding and repairing method for distributed storage system
CN105393225A (en) Erasure coding across multiple zones
KR101618269B1 (en) Method and Apparatus of Encoding for Data Recovery in Distributed Storage System
KR102592121B1 (en) Apparatus and method for implementing XF erase code in distributed storage system
EP2962208A1 (en) Resolving write conflicts in a dispersed storage network
CN108347306B (en) Quasi-local reconstruction code coding and node fault repair method in distributed storage system
US11748197B2 (en) Data storage methods and systems
CN114153651B (en) A data encoding method, device, equipment and medium
CN115454727B (en) A data recovery method, device, equipment and readable storage medium
CN110781024B (en) Matrix Construction Method of Symmetric Partial Repetition Code and Faulty Node Restoration Method
CN113190377A (en) Reliable redundancy method and equipment based on distributed storage system
KR101756136B1 (en) A fault tolerant method for a hierarchical system
CN108762978B (en) A Grouping Construction Method of Partially Repeated Cyclic Codes
CN117762696A (en) Node data restoration method and device, distributed storage system, device and medium
CN116400862A (en) Method, device, equipment and medium for improving erasure codes of cold and hot data
KR20190059827A (en) One-sub-symbol linear repair schemes
JP2015082150A (en) Storage system and storage program
US12223194B2 (en) Re-encoding data in a storage network based on addition of additional storage units
CN118041373A (en) Low-repair-bandwidth local repair code construction method and fault node repair method

Legal Events

Date Code Title Description
PA0109 Patent application

St.27 status event code: A-0-1-A10-A12-nap-PA0109

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

D13-X000 Search requested

St.27 status event code: A-1-2-D10-D13-srh-X000

D14-X000 Search report completed

St.27 status event code: A-1-2-D10-D14-srh-X000

PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

E13-X000 Pre-grant limitation requested

St.27 status event code: A-2-3-E10-E13-lim-X000

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U11-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 5

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 6

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 7

PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20240705

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20240705