Migrate Linear Mode to RAID5

by thinker

關鍵字:

將 disks 從 linear mode 轉到 RAID5 會遇到資料必需搬來搬去的問題，例如 chunk[i] 要從 linear mode 位置搬到 RAID5 的位置時，可能該位置有其它資料 chunk[j] 必需先搬走。而該 chunk[j] 在 RAID5 的位置，可能也有其它資料必需先搬走。於是資料就必需這樣搬來搬去。和 tick 在 email 上討論時，tick 提出一個 O(nlog(n)) 的演算法，雖然在 disk 上 O(nlog(n)) 是一個很大的問題，但卻讓我從複雜度的觀點去找新的演算法。

下面是我想到的方法
* 設 s(i,j) 是 disk i 的第 j 個 slot ，每個 slot 為一個 chunk 的大小.
* chunk(i) 是資料的第 i 個 chunk 。
* 每個 disk 能容納 L 個 chunk 。
* 我們有兩個 disk 以 linear mode 存放 data，加入第三顆打算migrate 到 raid5。
* initial:
  * chunk[i] at s(i / L, i % L)
* step 1:
  * move chunk[i] to s(2, i / 2) where 0 <= i < L and i % 2 == 1
* step 2:
  * move chunk[i] to s(2, i / 2) where L <= i < 2L and i % 2 == 1
* step 3
  * move chunk[i] to s(1, i / 2 + 1) where 0 <= i < L and i % 2 == 0
  * chunk[i] where 0 <= i < 2L and i % 2 == 0 全都在 disk 1
* step 4
  * move chunk[i] to s(0, i / 2) where 0 <= i < L and i % 2 == 0
* step 5
  * move chunk[i] to s(0, i / 2) where L <= i < 2L and i % 2 == 0
  * disk 0 和 disk 2 的內容變成 raid 0 的配置方式
* step 6
  * 以 raid0 to raid5 的形式進行 migration

此演算法的複雜度為 O(n)，
最大 seeking 的距離為 1 個 cylinder。
和 raid0 to raid5 相較，平均每個 chunk 多搬 1.25 次。

最後更新時間: 2009-01-20 00:12:18 CST | 引用

查詢:

COMMENTS:

on 2009-01-20 11:49:06 CST

Lu, Jye said ..

In step 5, the interval of i should be [L, 2L). The disk access time may vary when access type changes; however, this is still an interesting research.

on 2009-01-20 18:35:51 CST

Thinker said ..

Typo was fixed. Thank you!!

on 2009-01-20 18:53:39 CST

Thinker said ..

如果 access type 是指 access pattern，每個 step 裡的 access pattern全都為 sequential access ，除了最後一個步驟 RAID0 to RAID5 的轉換。但 RAID0 to RAID5 的轉換，大部分相臨的 access 是發生在同一個 cylinder ，因此 access time 的 variance 不大。

on 2009-01-21 12:09:11 CST

Lu, Jye said ..

If steps 1-5 occurred in same cylinder, the total seek time may be reduced. IMHO, modify the "每個 disk 能容納 L 個 chunk" to "每個 cylinder 能容納 L 個 chunk ", this algorithm maybe work better.