You are viewing a plain text version of this content. The canonical link for it is here.
Posted to mapreduce-issues@hadoop.apache.org by "Scott Chen (JIRA)" <ji...@apache.org> on 2010/07/27 00:24:16 UTC
[jira] Created: (MAPREDUCE-1969) Allow raid to use Reed-Solomon
erasure codes
Allow raid to use Reed-Solomon erasure codes
--------------------------------------------
Key: MAPREDUCE-1969
URL: https://issues.apache.org/jira/browse/MAPREDUCE-1969
Project: Hadoop Map/Reduce
Issue Type: New Feature
Components: contrib/raid
Reporter: Scott Chen
Fix For: 0.22.0
Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
This way we can get a good file corrupt probability even if we set the replication to 1.
Here are some simple comparisons:
1. No raid, replication = 3:
File corruption probability = O(p^3), Storage space = 3x
2. Signal parity raid with stripe size = 10, replication = 2:
File corruption probability = O(p^4), Storage space = 2.2x
3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
File corruption probability = O(p^5), Storage space = 1.4x
where p is the missing block probability.
Reed-Solomon code can save lots of space without compromising the corruption probability.
To achieve this, we need some changes to raid:
1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
3. Allow raid to use general erasure code. It is now hard coded using Xor.
4. Add a Reed-Solomon code implementation
We are planing to use it on the older data only.
Because setting replication = 1 hurts the data locality.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MAPREDUCE-1969) Allow raid to use Reed-Solomon
erasure codes
Posted by "Scott Chen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1969?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12920326#action_12920326 ]
Scott Chen commented on MAPREDUCE-1969:
---------------------------------------
Wittawat:
The RS implementation has a complexity of
O(n^2) where n is the parity length.
In our case, the parity length is really small (we pick 4).
So we think the efficiency should not be a problem here.
> Allow raid to use Reed-Solomon erasure codes
> --------------------------------------------
>
> Key: MAPREDUCE-1969
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-1969
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: contrib/raid
> Reporter: Scott Chen
> Fix For: 0.22.0
>
>
> Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
> Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
> This way we can get a good file corrupt probability even if we set the replication to 1.
> Here are some simple comparisons:
> 1. No raid, replication = 3:
> File corruption probability = O(p^3), Storage space = 3x
> 2. Single parity raid with stripe size = 10, replication = 2:
> File corruption probability = O(p^4), Storage space = 2.2x
> 3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
> File corruption probability = O(p^5), Storage space = 1.4x
> where p is the missing block probability.
> Reed-Solomon code can save lots of space without compromising the corruption probability.
> To achieve this, we need some changes to raid:
> 1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
> 2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
> 3. Allow raid to use general erasure code. It is now hard coded using Xor.
> 4. Add a Reed-Solomon code implementation
> We are planing to use it on the older data only.
> Because setting replication = 1 hurts the data locality.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MAPREDUCE-1969) Allow raid to use Reed-Solomon
erasure codes
Posted by "Wittawat Tantisiriroj (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1969?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12904327#action_12904327 ]
Wittawat Tantisiriroj commented on MAPREDUCE-1969:
--------------------------------------------------
How fast this RS implementation encode per sec? In case we need a faster encoder, I am thinking about porting Cauchy Reed-Solomon as described @ http://www.cs.utk.edu/~plank/plank/papers/FAST-2009.pdf to Java. James S. Plank, the author, has already given me a permission to release it with Apache License.
> Allow raid to use Reed-Solomon erasure codes
> --------------------------------------------
>
> Key: MAPREDUCE-1969
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-1969
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: contrib/raid
> Reporter: Scott Chen
> Fix For: 0.22.0
>
>
> Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
> Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
> This way we can get a good file corrupt probability even if we set the replication to 1.
> Here are some simple comparisons:
> 1. No raid, replication = 3:
> File corruption probability = O(p^3), Storage space = 3x
> 2. Single parity raid with stripe size = 10, replication = 2:
> File corruption probability = O(p^4), Storage space = 2.2x
> 3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
> File corruption probability = O(p^5), Storage space = 1.4x
> where p is the missing block probability.
> Reed-Solomon code can save lots of space without compromising the corruption probability.
> To achieve this, we need some changes to raid:
> 1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
> 2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
> 3. Allow raid to use general erasure code. It is now hard coded using Xor.
> 4. Add a Reed-Solomon code implementation
> We are planing to use it on the older data only.
> Because setting replication = 1 hurts the data locality.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MAPREDUCE-1969) Allow raid to use Reed-Solomon
erasure codes
Posted by "dhruba borthakur (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1969?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12901709#action_12901709 ]
dhruba borthakur commented on MAPREDUCE-1969:
---------------------------------------------
for all these proposals, the unwritten assumption is that all the blocks in a stripe belong to the same hdfs file. In that case, when the data file is deleted, the parity file can be deleted too.
> Allow raid to use Reed-Solomon erasure codes
> --------------------------------------------
>
> Key: MAPREDUCE-1969
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-1969
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: contrib/raid
> Reporter: Scott Chen
> Fix For: 0.22.0
>
>
> Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
> Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
> This way we can get a good file corrupt probability even if we set the replication to 1.
> Here are some simple comparisons:
> 1. No raid, replication = 3:
> File corruption probability = O(p^3), Storage space = 3x
> 2. Single parity raid with stripe size = 10, replication = 2:
> File corruption probability = O(p^4), Storage space = 2.2x
> 3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
> File corruption probability = O(p^5), Storage space = 1.4x
> where p is the missing block probability.
> Reed-Solomon code can save lots of space without compromising the corruption probability.
> To achieve this, we need some changes to raid:
> 1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
> 2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
> 3. Allow raid to use general erasure code. It is now hard coded using Xor.
> 4. Add a Reed-Solomon code implementation
> We are planing to use it on the older data only.
> Because setting replication = 1 hurts the data locality.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (MAPREDUCE-1969) Allow raid to use Reed-Solomon
erasure codes
Posted by "Scott Chen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1969?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Scott Chen reassigned MAPREDUCE-1969:
-------------------------------------
Assignee: Ramkumar Vadali
> Allow raid to use Reed-Solomon erasure codes
> --------------------------------------------
>
> Key: MAPREDUCE-1969
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-1969
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: contrib/raid
> Reporter: Scott Chen
> Assignee: Ramkumar Vadali
> Fix For: 0.22.0
>
>
> Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
> Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
> This way we can get a good file corrupt probability even if we set the replication to 1.
> Here are some simple comparisons:
> 1. No raid, replication = 3:
> File corruption probability = O(p^3), Storage space = 3x
> 2. Single parity raid with stripe size = 10, replication = 2:
> File corruption probability = O(p^4), Storage space = 2.2x
> 3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
> File corruption probability = O(p^5), Storage space = 1.4x
> where p is the missing block probability.
> Reed-Solomon code can save lots of space without compromising the corruption probability.
> To achieve this, we need some changes to raid:
> 1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
> 2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
> 3. Allow raid to use general erasure code. It is now hard coded using Xor.
> 4. Add a Reed-Solomon code implementation
> We are planing to use it on the older data only.
> Because setting replication = 1 hurts the data locality.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MAPREDUCE-1969) Allow raid to use Reed-Solomon
erasure codes
Posted by "Scott Chen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1969?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Scott Chen updated MAPREDUCE-1969:
----------------------------------
Description:
Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
This way we can get a good file corrupt probability even if we set the replication to 1.
Here are some simple comparisons:
1. No raid, replication = 3:
File corruption probability = O(p^3), Storage space = 3x
2. Single parity raid with stripe size = 10, replication = 2:
File corruption probability = O(p^4), Storage space = 2.2x
3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
File corruption probability = O(p^5), Storage space = 1.4x
where p is the missing block probability.
Reed-Solomon code can save lots of space without compromising the corruption probability.
To achieve this, we need some changes to raid:
1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
3. Allow raid to use general erasure code. It is now hard coded using Xor.
4. Add a Reed-Solomon code implementation
We are planing to use it on the older data only.
Because setting replication = 1 hurts the data locality.
was:
Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
This way we can get a good file corrupt probability even if we set the replication to 1.
Here are some simple comparisons:
1. No raid, replication = 3:
File corruption probability = O(p^3), Storage space = 3x
2. Signal parity raid with stripe size = 10, replication = 2:
File corruption probability = O(p^4), Storage space = 2.2x
3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
File corruption probability = O(p^5), Storage space = 1.4x
where p is the missing block probability.
Reed-Solomon code can save lots of space without compromising the corruption probability.
To achieve this, we need some changes to raid:
1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
3. Allow raid to use general erasure code. It is now hard coded using Xor.
4. Add a Reed-Solomon code implementation
We are planing to use it on the older data only.
Because setting replication = 1 hurts the data locality.
> Allow raid to use Reed-Solomon erasure codes
> --------------------------------------------
>
> Key: MAPREDUCE-1969
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-1969
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: contrib/raid
> Reporter: Scott Chen
> Fix For: 0.22.0
>
>
> Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
> Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
> This way we can get a good file corrupt probability even if we set the replication to 1.
> Here are some simple comparisons:
> 1. No raid, replication = 3:
> File corruption probability = O(p^3), Storage space = 3x
> 2. Single parity raid with stripe size = 10, replication = 2:
> File corruption probability = O(p^4), Storage space = 2.2x
> 3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
> File corruption probability = O(p^5), Storage space = 1.4x
> where p is the missing block probability.
> Reed-Solomon code can save lots of space without compromising the corruption probability.
> To achieve this, we need some changes to raid:
> 1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
> 2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
> 3. Allow raid to use general erasure code. It is now hard coded using Xor.
> 4. Add a Reed-Solomon code implementation
> We are planing to use it on the older data only.
> Because setting replication = 1 hurts the data locality.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MAPREDUCE-1969) Allow raid to use Reed-Solomon
erasure codes
Posted by "Dick King (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1969?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12901603#action_12901603 ]
Dick King commented on MAPREDUCE-1969:
--------------------------------------
Proposal 3 would have to be applied only to data that essentially never gets deleted, because deleting a block would affect four parity blocks.
> Allow raid to use Reed-Solomon erasure codes
> --------------------------------------------
>
> Key: MAPREDUCE-1969
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-1969
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: contrib/raid
> Reporter: Scott Chen
> Fix For: 0.22.0
>
>
> Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
> Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
> This way we can get a good file corrupt probability even if we set the replication to 1.
> Here are some simple comparisons:
> 1. No raid, replication = 3:
> File corruption probability = O(p^3), Storage space = 3x
> 2. Single parity raid with stripe size = 10, replication = 2:
> File corruption probability = O(p^4), Storage space = 2.2x
> 3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
> File corruption probability = O(p^5), Storage space = 1.4x
> where p is the missing block probability.
> Reed-Solomon code can save lots of space without compromising the corruption probability.
> To achieve this, we need some changes to raid:
> 1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
> 2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
> 3. Allow raid to use general erasure code. It is now hard coded using Xor.
> 4. Add a Reed-Solomon code implementation
> We are planing to use it on the older data only.
> Because setting replication = 1 hurts the data locality.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MAPREDUCE-1969) Allow raid to use Reed-Solomon
erasure codes
Posted by "Ramkumar Vadali (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1969?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12904333#action_12904333 ]
Ramkumar Vadali commented on MAPREDUCE-1969:
--------------------------------------------
Our feeling is that IO costs will dominate CPU cost, but we do not have experimental results yet.
> Allow raid to use Reed-Solomon erasure codes
> --------------------------------------------
>
> Key: MAPREDUCE-1969
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-1969
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: contrib/raid
> Reporter: Scott Chen
> Fix For: 0.22.0
>
>
> Currently raid uses one parity block per stripe which corrects one missing block on one stripe.
> Using Reed-Solomon code, we can add any number of parity blocks to tolerate more missing blocks.
> This way we can get a good file corrupt probability even if we set the replication to 1.
> Here are some simple comparisons:
> 1. No raid, replication = 3:
> File corruption probability = O(p^3), Storage space = 3x
> 2. Single parity raid with stripe size = 10, replication = 2:
> File corruption probability = O(p^4), Storage space = 2.2x
> 3. Reed-Solomon raid with parity size = 4 and stripe size = 10, replication = 1:
> File corruption probability = O(p^5), Storage space = 1.4x
> where p is the missing block probability.
> Reed-Solomon code can save lots of space without compromising the corruption probability.
> To achieve this, we need some changes to raid:
> 1. Add a block placement policy that knows about raid logic and do not put blocks on the same stripe on the same node.
> 2. Add an automatic block fixing mechanism. The block fixing will replace the replication of under replicated blocks.
> 3. Allow raid to use general erasure code. It is now hard coded using Xor.
> 4. Add a Reed-Solomon code implementation
> We are planing to use it on the older data only.
> Because setting replication = 1 hurts the data locality.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.