之前就写了博文就FAST12 的NCCloud 进行了分析，今天写了个NCCloud 的一个修复部分的实现，只对相应的编、解码矩阵进行操作，不涉及具体的文件读、写和传输操作。
NCCloud 的失效节点修复特点有两个：一是不需要节点内部的计算，对一般的云存储具有通用性；二是修复是功能性修复（functional repair），即修复的节点数据和失效的节点数据不必相同。
流程
一个例子
下面通过一个实例来讲解NCCloud 中的功能性修复。
初始节点数据对应的系数组成的矩阵（GF(256) 有限域内，n = 4，k = 2，因此每两个行对应一个节点）：
67 c6 69 73
51 ff 4a ec
29 cd ba ab
f2 fb e3 46
7c c2 54 f8
1b e8 e7 8d
76 5a 2e 63
33 9f c9 9a
当第三个节点失效时，对应的系数标记为0；
67 c6 69 73
51 ff 4a ec
29 cd ba ab
f2 fb e3 46
00 00 00 00
00 00 00 00
76 5a 2e 63
33 9f c9 9a
随机生成一个 (n-k)×(n-1) 大小的矩阵
32 0d b7
31 58 a3
然后从 n-1 个节点分别随机选择一行系数（文中对应的ECV）
67 c6 69 73
f2 fb e3 46
33 9f c9 9a
上面两个矩阵相乘，得到新的节点的系数矩阵
4a ee 9f 86
e8 ed 97 13
将新节点矩阵系数代替到原来失效的节点中，检查是否k 个节点满足MDS 性质
67 c6 69 73
51 ff 4a ec
29 cd ba ab
f2 fb e3 46
4a ee 9f 86
e8 ed 97 13
76 5a 2e 63
33 9f c9 9a
满足，则是一次成功的修复
几点说明
- check_full() 是程序中的一个函数，讲的是任意k 个节点系数组成的k(n-k)×k(n-k) 的矩阵满秩，这等同于任意k 个节点可以恢复出原始数据，等同于所有节点系数组成的n(n-k)×k(n-k) 的矩阵，两两行不相关。
- 基于第一点NCCloud 论文中，任取一节点失效，然后再进行一次修复的工作是无用功的，如果读者有不同意见可以探讨。
- 从实验中可以看出，当n 和k 增大时，修复需要循环的次数变多（当n=4，k=2 时，测试10000 次，一次性修复成功为7303 次，两次随机生成矩阵修复成功1975 次，三次及其以上修复成功为722 次；而当n=8，k=4 的时候，10000 次中一次性修复成功为1501 次，两次随机生成矩阵修复成功1319 次，三次及其以上修复成功为7180 次）。可见这个方法还是有改进的地方的。
代码
1: #include <stdio.h>
2: #include <stdlib.h>
3: #include <stdint.h>
4: #include "../galois.h"
5: #include "../nc.h"
6:
7: int n,k,piece;
8: int r[3] = {0, 0, 0};
9:
10: void printa(int *a){
11: int i;
12:
13: for(i = 0; i < k; i++ ){
14: printf("%d ",*(a+i));
15: }
16: printf("\n");
17: }
18:
19: int check_full(Matrix8g &mat){
20: int i, j;
21: int temp;
22: int count = 0;
23: int a[100];
24: int cur;
25: Matrix8g mat_chk;
26: vector<int> shift; /* shift used to move k non-zero elements
27: * and store the result */
28:
29: for(i = 0; i < n; i++){
30: mat_chk = Slice_matrix(mat, i*piece, piece);
31: if(0 == Is_full(mat_chk))
32: return 0;
33: }
34: /* Any k nodes combine into a k(n-k)*k(n-k) matrix *
35: * which is a full-rank matrix */
36: for(i = 0; i < k; i++){
37: a[i] = i;
38: }
39: cur = k-1;
40: do{
41: if(a[cur]-cur <= n-k){
42: for(i = 0; i < k; i++){
43: if(0 == i){
44: mat_chk = Slice_matrix(mat, a[i]*piece, piece);
45: }
46: else
47: mat_chk.Append_matrix(mat, a[i]*piece, piece);
48: }
49:
50: if(0 == Is_full(mat_chk))
51: return 0;
52: a[cur]++;
53: continue;
54: }else{
55: if(0 == cur)
56: break;
57: --cur;
58: a[cur]++;
59: for(i = 1; i < k - cur; i++){
60: a[cur+i]=a[cur]+i;
61: }
62: if(a[cur] - cur < n - k)
63: cur = k - 1;
64: }
65: }while(1);
66: return 1;
67: }
68:
69: /* invalid a random node and let factors 0*/
70: int invalid_node(Matrix8g &mat){
71: int xnode;
72:
73: xnode = NC_random(n);
74: printf(">>>>> Invalid node %d\n", xnode);
75: mat.Wipe_matrix(xnode*piece, piece, 0);
76:
77: return xnode;
78: }
79:
80: int repair(Matrix8g &mat, int xnode){
81: Matrix8g mat_rep, mat_rand, mat_n;
82: int count;
83: int i, j;
84: int times = 1;
85:
86: count = 1;
87: /* a (n-k)*(n-1) matrix */
88: NOTE("a (n-k)*(n-1) matrix");
89: mat_rand.Make_random(piece, n-1);
90: mat_rand.Print();
91:
92: /* get one row from each node form mat_n*/
93: for(i = 0; i < n; i++){
94: if(i == xnode)
95: continue;
96: if((i == 0)||((1 == i)&&(0 == xnode))){
97: mat_n = Slice_matrix(mat, i*piece + NC_random(piece), 1);
98: continue;
99: }
100: mat_n.Append_matrix(Slice_matrix(mat, i*piece + NC_random(piece), 1));
101: }
102: NOTE("matrix from n-1 nodes");
103: mat_n.Print();
104:
105: /*Replace matrix*/
106: mat_rep = Prod(mat_rand, mat_n);
107: NOTE("Rep matrix");
108: mat_rep.Print();
109:
110: mat.Replace_matrix(mat_rep, xnode*piece);
111: NOTE("new matrix");
112: mat.Print();
113:
114: while(0 == check_full(mat)){
115: ++times;
116: NOTE("another Repair matrix");
117: if(count >= 1000)
118: return 0;
119: count++;
120: mat_rand.Make_random(piece, n-1);
121: mat_rand.Print();
122:
123: /* get one row from each node form mat_n*/
124: for(i = 0; i < n; i++){
125: if(i == xnode)
126: continue;
127: if((i == 0)||((1 == i)&&(0 == xnode))){
128: mat_n = Slice_matrix(mat, i*piece + NC_random(piece), 1);
129: continue;
130: }
131: mat_n.Append_matrix(Slice_matrix(mat, i*piece + NC_random(piece), 1));
132: }
133: NOTE("matrix from n-1 nodes");
134: mat_n.Print();
135:
136: /*Replace matrix*/
137: mat_rep = Prod(mat_rand, mat_n);
138: NOTE("Rep matrix");
139: mat_rep.Print();
140:
141: mat.Replace_matrix(mat_rep, xnode*piece);
142: NOTE("new matrix");
143: mat.Print();
144: }
145: if(times >= 3)
146: times=3;
147: ++r[times-1];
148: return 1;
149: }
150:
151: /* test Insert_matrix and Append_matrix */
152: int main(int argc, char *argv[]){
153: Matrix8g mat;
154: int rows, cols;
155: int xnode;
156: int times;
157:
158: /******************
159: * Initialization
160: * ****************/
161: if(argc >= 3){
162: n = atoi(argv[1]);
163: k = atoi(argv[2]);
164: assert(n > k);
165: }else{
166: n = 4;
167: k = 2;
168: }
169:
170: piece = n-k;
171: rows = n*piece;
172: cols = k*piece;
173: mat.Make_random(rows, cols);
174: NOTE(" mat matrix ");
175: mat.Print();
176: NOTE("Begin to check!");
177: while(0 == check_full(mat)){
178: NOTE("Property not satisfied!");
179: mat.Make_random(rows, cols);
180: }
181:
182: /*************************
183: * invalid a random node
184: * **********************/
185: times = 100;
186: while(times > 0){
187: xnode = invalid_node(mat);
188: NOTE(" After invalid a node ");
189: mat.Print();
190: if(1 == repair(mat, xnode)){
191: NOTE("Success repair, after repair");
192: mat.Print();
193: }else{
194: NOTE(" Fail to repair ");
195: break;
196: }
197: --times;
198: getchar();
199: }
200: printf("100 times, one repair: %d, two repair: %d, three+ repair: %d\n", r[0], r[1], r[2]);
201: }
