hadoop-mapreduce-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dhr...@apache.org
Subject svn commit: r1027822 - in /hadoop/mapreduce/trunk: ./ src/contrib/raid/src/java/org/apache/hadoop/raid/ src/contrib/raid/src/test/org/apache/hadoop/raid/
Date Wed, 27 Oct 2010 06:00:53 GMT
Author: dhruba
Date: Wed Oct 27 06:00:52 2010
New Revision: 1027822

URL: http://svn.apache.org/viewvc?rev=1027822&view=rev
Log:
MAPREDUCE-1970.  Reed-Solomon code implementation for HDFS RAID.
(Scott Chen via dhruba)


Added:
    hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ErasureCode.java
    hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/GaloisField.java
    hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ReedSolomonCode.java
    hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestErasureCodes.java
    hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestGaloisField.java
Modified:
    hadoop/mapreduce/trunk/CHANGES.txt

Modified: hadoop/mapreduce/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/CHANGES.txt?rev=1027822&r1=1027821&r2=1027822&view=diff
==============================================================================
--- hadoop/mapreduce/trunk/CHANGES.txt (original)
+++ hadoop/mapreduce/trunk/CHANGES.txt Wed Oct 27 06:00:52 2010
@@ -18,6 +18,9 @@ Trunk (unreleased changes)
     MAPREDUCE-220. Collect cpu and memory statistics per task. (Scott Chen via
     acmurthy)
 
+    MAPREDUCE-1970.  Reed-Solomon code implementation for HDFS RAID.
+    (Scott Chen via dhruba)
+
   IMPROVEMENTS
 
     MAPREDUCE-2140. Regenerate fair scheduler design doc PDF. (matei)

Added: hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ErasureCode.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ErasureCode.java?rev=1027822&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ErasureCode.java
(added)
+++ hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ErasureCode.java
Wed Oct 27 06:00:52 2010
@@ -0,0 +1,60 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.raid;
+
+public interface ErasureCode {
+  /**
+   * Encodes the given message.
+   * @param message The data of the message. The data is present in the least
+   *                significant bits of each int. The number of data bits is
+   *                symbolSize(). The number of elements of message is
+   *                stripeSize().
+   * @param parity  (out) The information is present in the least
+   *                significant bits of each int. The number of parity bits is
+   *                symbolSize(). The number of elements in the code is
+   *                paritySize().
+   */
+  public void encode(int[] message, int[] parity);
+
+  /**
+   * Generates missing portions of data.
+   * @param data The message and parity. The parity should be placed in the
+   *             first part of the array. In each integer, the relevant portion
+   *             is present in the least significant bits of each int.
+   *             The number of elements in data is stripeSize() + paritySize().
+   * @param erasedLocations The indexes in data which are not available.
+   * @param erasedValues    (out)The decoded values corresponding to erasedLocations.
+   */
+  public void decode(int[] data, int[] erasedLocations, int[] erasedValues);
+
+  /**
+   * The number of elements in the message.
+   */
+  public int stripeSize();
+
+  /**
+   * The number of elements in the code.
+   */
+  public int paritySize();
+
+  /**
+   * Number of bits for each symbol.
+   */
+  public int symbolSize();
+}

Added: hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/GaloisField.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/GaloisField.java?rev=1027822&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/GaloisField.java
(added)
+++ hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/GaloisField.java
Wed Oct 27 06:00:52 2010
@@ -0,0 +1,282 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.raid;
+
+/**
+ * Implementation of Galois field arithmetics with 2^p elements.
+ * The input must be unsigned integers.
+ */
+public class GaloisField {
+  
+  private final int[] logTable;
+  private final int[] powTable;
+  private final int[][] mulTable;
+  private final int[][] divTable;
+  private final int fieldSize;
+  private final int primitivePeriod;
+  private final int primitivePolynomial;
+
+  // Field size 256 is good for byte based system
+  private static final int DEFAULT_FIELD_SIZE = 256;
+  // primitive polynomial 1 + X + X^2 + X^4 + X^8
+  private static final int DEFAULT_PRIMITIVE_POLYNOMIAL = 285;
+
+  /**
+   * An object can perform Galois field arithmetics
+   * @param fieldSize size of the field
+   * @param primitivePolynomial a primitive polynomial corresponds to the size
+   */
+  public GaloisField(int fieldSize, int primitivePolynomial) {
+    this.fieldSize = fieldSize;
+    this.primitivePeriod = fieldSize - 1;
+    this.primitivePolynomial = primitivePolynomial;
+    logTable = new int[fieldSize];
+    powTable = new int[fieldSize];
+    mulTable = new int[fieldSize][fieldSize];
+    divTable = new int[fieldSize][fieldSize];
+    int value = 1;
+    for (int pow = 0; pow < fieldSize - 1; pow++) {
+      powTable[pow] = value;
+      logTable[value] = pow;
+      value = value * 2;
+      if (value >= fieldSize) {
+        value = value ^ primitivePolynomial;
+      }
+    }
+    // building multiplication table
+    for (int i = 0; i < fieldSize; i++) {
+      for (int j = 0; j < fieldSize; j++) {
+        if (i == 0 || j == 0) {
+          mulTable[i][j] = 0;
+          continue;
+        }
+        int z = logTable[i] + logTable[j];
+        z = z >= primitivePeriod ? z - primitivePeriod : z;
+        z = powTable[z];
+        mulTable[i][j] = z;
+      }
+    }
+    // building division table
+    for (int i = 0; i < fieldSize; i++) {
+      for (int j = 1; j < fieldSize; j++) {
+        if (i == 0) {
+          divTable[i][j] = 0;
+          continue;
+        }
+        int z = logTable[i] - logTable[j];
+        z = z < 0 ? z + primitivePeriod : z;
+        z = powTable[z];
+        divTable[i][j] = z;
+      }
+    }
+  }
+
+  /**
+   * An object can perform Galois field arithmetics
+   */
+  public GaloisField() {
+    this(DEFAULT_FIELD_SIZE, DEFAULT_PRIMITIVE_POLYNOMIAL);
+  }
+
+  /**
+   * Return number of elements in the field
+   * @return number of elements in the field
+   */
+  public int getFieldSize() {
+    return fieldSize;
+  }
+
+  /**
+   * Return the primitive polynomial in GF(2)
+   * @return primitive polynomial as a integer
+   */
+  public int getPrimitivePolynomial() {
+    return primitivePolynomial;
+  }
+
+  /**
+   * Compute the sum of two fields
+   * @param x input field
+   * @param y input field
+   * @return result of addition
+   */
+  public int add(int x, int y) {
+    assert(x >= 0 && x < getFieldSize() && y >= 0 && y <
getFieldSize());
+    return x ^ y;
+  }
+
+  /**
+   * Compute the multiplication of two fields
+   * @param x input field
+   * @param y input field
+   * @return result of multiplication
+   */
+  public int multiply(int x, int y) {
+    assert(x >= 0 && x < getFieldSize() && y >= 0 && y <
getFieldSize());
+    return mulTable[x][y];
+  }
+
+  /**
+   * Compute the division of two fields
+   * @param x input field
+   * @param y input field
+   * @return x/y
+   */
+  public int divide(int x, int y) {
+    assert(x >= 0 && x < getFieldSize() && y > 0 && y <
getFieldSize());
+    return divTable[x][y];
+  }
+
+  /**
+   * Compute power n of a field
+   * @param x input field
+   * @param n power
+   * @return x^n
+   */
+  public int power(int x, int n) {
+    assert(x >= 0 && x < getFieldSize());
+    if (n == 0) {
+      return 1;
+    }
+    if (x == 0) {
+      return 0;
+    }
+    x = logTable[x] * n;
+    if (x < primitivePeriod) {
+      return powTable[x];
+    }
+    x = x % primitivePeriod;
+    return powTable[x];
+  }
+
+  /**
+   * Given a Vandermonde matrix V[i][j]=x[j]^i and vector y, solve for z such
+   * that Vz=y. The output z will be placed in y.
+   * @param x the vector which describe the Vandermonde matrix
+   * @param y right-hand side of the Vandermonde system equation.
+   *          will be replaced the output in this vector
+   */
+  public void solveVandermondeSystem(int[] x, int[] y) {
+    solveVandermondeSystem(x, y, x.length);
+  }
+
+  /**
+   * Given a Vandermonde matrix V[i][j]=x[j]^i and vector y, solve for z such
+   * that Vz=y. The output z will be placed in y.
+   * @param x the vector which describe the Vandermonde matrix
+   * @param y right-hand side of the Vandermonde system equation.
+   *          will be replaced the output in this vector
+   * @param len consider x and y only from 0...len-1
+   */
+  public void solveVandermondeSystem(int[] x, int[] y, int len) {
+    assert(x.length <= len && y.length <= len);
+    for (int i = 0; i < len - 1; i++) {
+      for (int j = len - 1; j > i; j--) {
+        y[j] = y[j] ^ mulTable[x[i]][y[j - 1]];
+      }
+    }
+    for (int i = len - 1; i >= 0; i--) {
+      for (int j = i + 1; j < len; j++) {
+        y[j] = divTable[y[j]][x[j] ^ x[j - i - 1]];
+      }
+      for (int j = i; j < len - 1; j++) {
+        y[j] = y[j] ^ y[j + 1];
+      }
+    }
+  }
+
+  /**
+   * Compute the multiplication of two polynomials. The index in the
+   * array corresponds to the power of the entry. For example p[0] is the
+   * constant term of the polynomial p. 
+   * @param p input polynomial
+   * @param q input polynomial
+   * @return polynomial represents p*q
+   */
+  public int[] multiply(int[] p, int[] q) {
+    int len = p.length + q.length - 1;
+    int[] result = new int[len];
+    for (int i = 0; i < len; i++) {
+      result[i] = 0;
+    }
+    for (int i = 0; i < p.length; i++) {
+      for (int j = 0; j < q.length; j++) {
+        result[i + j] = add(result[i + j], multiply(p[i], q[j]));
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Compute the remainder of a dividend and divisor pair. The index in the
+   * array corresponds to the power of the entry. For example p[0] is the
+   * constant term of the polynomial p. 
+   * @param dividend dividend polynomial, the remainder will be placed here when return
+   * @param divisor divisor polynomial
+   */
+  public void remainder(int[] dividend, int[] divisor) {
+    for (int i = dividend.length - divisor.length; i >= 0; i--) {
+      int ratio =
+        divTable[dividend[i + divisor.length - 1]][divisor[divisor.length - 1]];
+      for (int j = 0; j < divisor.length; j++) {
+        int k = j + i;
+        dividend[k] = dividend[k] ^ mulTable[ratio][divisor[j]];
+      }
+    }
+  }
+
+  /**
+   * Compute the sum of two polynomials. The index in the
+   * array corresponds to the power of the entry. For example p[0] is the
+   * constant term of the polynomial p. 
+   * @param p input polynomial
+   * @param q input polynomial
+   * @return polynomial represents p+q
+   */
+  public int[] add(int[] p, int[] q) {
+    int len = Math.max(p.length, q.length);
+    int[] result = new int[len];
+    for (int i = 0; i < len; i++) {
+      if (i < p.length && i < q.length) {
+        result[i] = add(p[i], q[i]);
+      } else if (i < p.length) {
+        result[i] = p[i];
+      } else {
+        result[i] = q[i];
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Substitute x into polynomial p(x). 
+   * @param p input polynomial
+   * @param x input field
+   * @return p(x)
+   */
+  public int substitute(int[] p, int x) {
+    int result = 0;
+    int y = 1;
+    for (int i = 0; i < p.length; i++) {
+      result = result ^ mulTable[p[i]][y];
+      y = mulTable[x][y];
+    }
+    return result;
+  }
+}

Added: hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ReedSolomonCode.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ReedSolomonCode.java?rev=1027822&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ReedSolomonCode.java
(added)
+++ hadoop/mapreduce/trunk/src/contrib/raid/src/java/org/apache/hadoop/raid/ReedSolomonCode.java
Wed Oct 27 06:00:52 2010
@@ -0,0 +1,103 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.raid;
+
+public class ReedSolomonCode implements ErasureCode {
+
+  private final int stripeSize;
+  private final int paritySize;
+  private final int[] generatingRoots;
+  private final int[] generatingPolynomial;
+  private final int PRIMITIVE_ROOT = 2;
+  private final GaloisField GF = new GaloisField();
+  private int[] errSignature;
+  private final int[] paritySymbolLocations;
+  private final int[] dataBuff;
+
+  public ReedSolomonCode(int stripeSize, int paritySize) {
+    assert(stripeSize + paritySize < GF.getFieldSize());
+    this.stripeSize = stripeSize;
+    this.paritySize = paritySize;
+    this.errSignature = new int[paritySize];
+    this.paritySymbolLocations = new int[paritySize];
+    this.dataBuff = new int[paritySize + stripeSize];
+    for (int i = 0; i < paritySize; i++) {
+      paritySymbolLocations[i] = i;
+    }
+    this.generatingRoots = new int[paritySize];
+    
+    // compute generating polynomial
+    int[] gen = {1};
+    int[] poly = new int[2];
+    for (int i = 0; i < paritySize; i++) {
+      generatingRoots[i] = GF.power(PRIMITIVE_ROOT, i);
+      poly[0] = generatingRoots[i];
+      poly[1] = 1;
+      gen = GF.multiply(gen, poly);
+    }
+    // generating polynomial has all generating roots
+    generatingPolynomial = gen;
+  }
+
+  @Override
+  public void encode(int[] message, int[] parity) {
+    assert(message.length == stripeSize && parity.length == paritySize);
+    for (int i = 0; i < paritySize; i++) {
+      dataBuff[i] = 0;
+    }
+    for (int i = 0; i < stripeSize; i++) {
+      dataBuff[i + paritySize] = message[i];
+    }
+    GF.remainder(dataBuff, generatingPolynomial);
+    for (int i = 0; i < paritySize; i++) {
+      parity[i] = dataBuff[i];
+    }
+  }
+
+  @Override
+  public void decode(int[] data, int[] erasedLocation, int[] erasedValue) {
+    if (erasedLocation.length == 0) {
+      return;
+    }
+    assert(erasedLocation.length == erasedValue.length);
+    for (int i = 0; i < erasedLocation.length; i++) {
+      data[erasedLocation[i]] = 0;
+    }
+    for (int i = 0; i < erasedLocation.length; i++) {
+      errSignature[i] = GF.power(PRIMITIVE_ROOT, erasedLocation[i]);
+      erasedValue[i] = GF.substitute(data, generatingRoots[i]);
+    }
+    GF.solveVandermondeSystem(errSignature, erasedValue, erasedLocation.length);
+  }
+
+  @Override
+  public int stripeSize() {
+    return this.stripeSize;
+  }
+
+  @Override
+  public int paritySize() {
+    return this.paritySize;
+  }
+
+  @Override
+  public int symbolSize() {
+    return (int) Math.round(Math.log(GF.getFieldSize()) / Math.log(2));
+  }
+}

Added: hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestErasureCodes.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestErasureCodes.java?rev=1027822&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestErasureCodes.java
(added)
+++ hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestErasureCodes.java
Wed Oct 27 06:00:52 2010
@@ -0,0 +1,186 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.raid;
+
+import java.util.HashSet;
+import java.util.Random;
+import java.util.Set;
+
+import junit.framework.TestCase;
+
+public class TestErasureCodes extends TestCase {
+  final int TEST_CODES = 100;
+  final int TEST_TIMES = 1000;
+  final Random RAND = new Random();
+
+  public void testEncodeDecode() {
+    for (int n = 0; n < TEST_CODES; n++) {
+      int stripeSize = RAND.nextInt(99) + 1; // 1, 2, 3, ... 100
+      int paritySize = RAND.nextInt(9) + 1; //1, 2, 3, 4, ... 10
+      ErasureCode ec = new ReedSolomonCode(stripeSize, paritySize);
+      for (int m = 0; m < TEST_TIMES; m++) {
+        int symbolMax = (int) Math.pow(2, ec.symbolSize());
+        int[] message = new int[stripeSize];
+        for (int i = 0; i < stripeSize; i++) {
+          message[i] = RAND.nextInt(symbolMax);
+        }
+        int[] parity = new int[paritySize];
+        ec.encode(message, parity);
+        int[] data = new int[stripeSize + paritySize];
+        int[] copy = new int[data.length];
+        for (int i = 0; i < paritySize; i++) {
+          data[i] = parity[i];
+          copy[i] = parity[i];
+        }
+        for (int i = 0; i < stripeSize; i++) {
+          data[i + paritySize] = message[i];
+          copy[i + paritySize] = message[i];
+        }
+        int erasedLen = paritySize == 1 ? 1 : RAND.nextInt(paritySize - 1) + 1;
+        int[] erasedLocations = randomErasedLocation(erasedLen, data.length);
+        for (int i = 0; i < erasedLocations.length; i++) {
+          data[erasedLocations[i]] = 0;
+        }
+        int[] erasedValues = new int[erasedLen];
+        ec.decode(data, erasedLocations, erasedValues);
+        for (int i = 0; i < erasedLen; i++) {
+          assertEquals("Decode failed", copy[erasedLocations[i]], erasedValues[i]);
+        }
+      }
+    }
+  }
+
+  public void testRSPerformance() {
+    int stripeSize = 10;
+    int paritySize = 4;
+    ErasureCode ec = new ReedSolomonCode(stripeSize, paritySize);
+    int symbolMax = (int) Math.pow(2, ec.symbolSize());
+    byte[][] message = new byte[stripeSize][];
+    int bufsize = 1024 * 1024 * 10;
+    for (int i = 0; i < stripeSize; i++) {
+      message[i] = new byte[bufsize];
+      for (int j = 0; j < bufsize; j++) {
+        message[i][j] = (byte) RAND.nextInt(symbolMax);
+      }
+    }
+    byte[][] parity = new byte[paritySize][];
+    for (int i = 0; i < paritySize; i++) {
+      parity[i] = new byte[bufsize];
+    }
+    long encodeStart = System.currentTimeMillis();
+    int[] tmpIn = new int[stripeSize];
+    int[] tmpOut = new int[paritySize];
+    for (int i = 0; i < bufsize; i++) {
+      // Copy message.
+      for (int j = 0; j < stripeSize; j++) tmpIn[j] = 0x000000FF & message[j][i];
+      ec.encode(tmpIn, tmpOut);
+      // Copy parity.
+      for (int j = 0; j < paritySize; j++) parity[j][i] = (byte)tmpOut[j];
+    }
+    long encodeEnd = System.currentTimeMillis();
+    float encodeMSecs = (encodeEnd - encodeStart);
+    System.out.println("Time to encode rs = " + encodeMSecs +
+      "msec (" + message[0].length / (1000 * encodeMSecs) + " MB/s)");
+
+    // Copy erased array.
+    int[] data = new int[paritySize + stripeSize];
+    // 4th location is the 0th symbol in the message
+    int[] erasedLocations = new int[]{4, 1, 5, 7};
+    int[] erasedValues = new int[erasedLocations.length];
+    byte[] copy = new byte[bufsize];
+    for (int j = 0; j < bufsize; j++) {
+      copy[j] = message[0][j];
+      message[0][j] = 0;
+    }
+
+    long decodeStart = System.currentTimeMillis();
+    for (int i = 0; i < bufsize; i++) {
+      // Copy parity first.
+      for (int j = 0; j < paritySize; j++) {
+        data[j] = 0x000000FF & parity[j][i];
+      }
+      // Copy message. Skip 0 as the erased symbol
+      for (int j = 1; j < stripeSize; j++) {
+        data[j + paritySize] = 0x000000FF & message[j][i];
+      }
+      // Use 0, 2, 3, 6, 8, 9, 10, 11, 12, 13th symbol to reconstruct the data
+      ec.decode(data, erasedLocations, erasedValues);
+      message[0][i] = (byte)erasedValues[0];
+    }
+    long decodeEnd = System.currentTimeMillis();
+    float decodeMSecs = (decodeEnd - decodeStart);
+    System.out.println("Time to decode = " + decodeMSecs +
+      "msec (" + message[0].length / (1000 * decodeMSecs) + " MB/s)");
+    assertTrue("Decode failed", java.util.Arrays.equals(copy, message[0]));
+  }
+
+  public void testXorPerformance() {
+    java.util.Random RAND = new java.util.Random();
+    int stripeSize = 10;
+    byte[][] message = new byte[stripeSize][];
+    int bufsize = 1024 * 1024 * 10;
+    for (int i = 0; i < stripeSize; i++) {
+      message[i] = new byte[bufsize];
+      for (int j = 0; j < bufsize; j++) {
+        message[i][j] = (byte)RAND.nextInt(256);
+      }
+    }
+    byte[] parity = new byte[bufsize];
+
+    long encodeStart = System.currentTimeMillis();
+    for (int i = 0; i < bufsize; i++) {
+      for (int j = 0; j < stripeSize; j++) parity[i] ^= message[j][i];
+    }
+    long encodeEnd = System.currentTimeMillis();
+    float encodeMSecs = encodeEnd - encodeStart;
+    System.out.println("Time to encode xor = " + encodeMSecs +
+      " msec (" + message[0].length / (1000 * encodeMSecs) + "MB/s)");
+
+    byte[] copy = new byte[bufsize];
+    for (int j = 0; j < bufsize; j++) {
+      copy[j] = message[0][j];
+      message[0][j] = 0;
+    }
+
+    long decodeStart = System.currentTimeMillis();
+    for (int i = 0; i < bufsize; i++) {
+      for (int j = 1; j < stripeSize; j++) message[0][i] ^= message[j][i];
+      message[0][i] ^= parity[i];
+    }
+    long decodeEnd = System.currentTimeMillis();
+    float decodeMSecs = decodeEnd - decodeStart;
+    System.out.println("Time to decode xor = " + decodeMSecs +
+      " msec (" + message[0].length / (1000 * decodeMSecs) + "MB/s)");
+    assertTrue("Decode failed", java.util.Arrays.equals(copy, message[0]));
+  }
+
+  private int[] randomErasedLocation(int erasedLen, int dataLen) {
+    int[] erasedLocations = new int[erasedLen];
+    for (int i = 0; i < erasedLen; i++) {
+      Set<Integer> s = new HashSet<Integer>();
+      while (s.size() != erasedLen) {
+        s.add(RAND.nextInt(dataLen));
+      }
+      int t = 0;
+      for (int erased : s) {
+        erasedLocations[t++] = erased;
+      }
+    }
+    return erasedLocations;
+  }
+}

Added: hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestGaloisField.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestGaloisField.java?rev=1027822&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestGaloisField.java
(added)
+++ hadoop/mapreduce/trunk/src/contrib/raid/src/test/org/apache/hadoop/raid/TestGaloisField.java
Wed Oct 27 06:00:52 2010
@@ -0,0 +1,168 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.raid;
+
+import java.util.Random;
+import java.util.Set;
+import java.util.HashSet;
+
+import junit.framework.TestCase;
+
+public class TestGaloisField extends TestCase {
+
+  final int TEST_TIMES = 10000;
+  final Random RAND = new Random();
+  final static GaloisField GF = new GaloisField();
+
+  private int randGF() {
+    return 0x000000FF & RAND.nextInt(GF.getFieldSize());
+  }
+  private int[] randGFPoly(int len) {
+    int[] result = new int[len];
+    for (int i = 0; i < len; i++) {
+      result[i] = randGF();
+    }
+    return result;
+  }
+
+  public void testDistributivity() {
+    for (int i = 0; i < TEST_TIMES; i++) {
+      int a = RAND.nextInt(GF.getFieldSize());
+      int b = RAND.nextInt(GF.getFieldSize());
+      int c = RAND.nextInt(GF.getFieldSize());
+      int result1 = GF.multiply(a, GF.add(b, c));
+      int result2 = GF.add(GF.multiply(a, b), GF.multiply(a, c));
+      assertTrue("Distributivity test #" + i + " failed: " + a + ", " + b + ", "
+                 + c, result1 == result2);
+    }
+  }
+
+  public void testDevision() {
+    for (int i = 0; i < TEST_TIMES; i++) {
+      int a = RAND.nextInt(GF.getFieldSize());
+      int b = RAND.nextInt(GF.getFieldSize());
+      if (b == 0) {
+        continue;
+      }
+      int c = GF.divide(a, b);
+      assertTrue("Division test #" + i + " failed: " + a + "/" + b + " = " + c,
+                 a == GF.multiply(c, b));
+    }
+  }
+
+  public void testPower() {
+    for (int i = 0; i < TEST_TIMES; i++) {
+      int a = randGF();
+      int n = RAND.nextInt(10);
+      int result1 = GF.power(a, n);
+      int result2 = 1;
+      for (int j = 0; j < n; j++) {
+        result2 = GF.multiply(result2, a);
+      }
+      assert(result1 == result2);
+    }
+  }
+
+  public void testPolynomialDistributivity() {
+    final int TEST_LEN = 15;
+    for (int i = 0; i < TEST_TIMES; i++) {
+      int[] a = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
+      int[] b = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
+      int[] c = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
+      int[] result1 = GF.multiply(a, GF.add(b, c));
+      int[] result2 = GF.add(GF.multiply(a, b), GF.multiply(a, c));
+      assertTrue("Distributivity test on polynomials failed",
+                 java.util.Arrays.equals(result1, result2));
+    }
+  }
+
+  public void testSubstitute() {
+    final int TEST_LEN = 15;
+    for (int i = 0; i < TEST_TIMES; i++) {
+      int[] a = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
+      int[] b = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
+      int[] c = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
+      int x = randGF();
+      // (a * b * c)(x)
+      int result1 = GF.substitute(GF.multiply(GF.multiply(a, b), c), x);
+      // a(x) * b(x) * c(x)
+      int result2 =
+        GF.multiply(GF.multiply(GF.substitute(a, x), GF.substitute(b, x)),
+                    GF.substitute(c, x));
+      assertTrue("Substitute test on polynomial failed",
+                 result1 == result2);
+    }
+  }
+
+  public void testSolveVandermondeSystem() {
+    final int TEST_LEN = 15;
+    for (int i = 0; i < TEST_TIMES; i++) {
+      int[] z = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
+      // generate distinct values for x
+      int[] x = new int[z.length];
+      Set<Integer> s = new HashSet<Integer>();
+      while (s.size() != z.length) {
+        s.add(randGF());
+      }
+      int t = 0;
+      for (int v : s) {
+        x[t++] = v;
+      }
+      // compute the output for the Vandermonde system
+      int[] y = new int[x.length];
+      for (int j = 0; j < x.length; j++) {
+        y[j] = 0;
+        for (int k = 0; k < x.length; k++) {
+          //y[j] = y[j] + z[k] * pow(x[k], j);
+          y[j] = GF.add(y[j], GF.multiply(GF.power(x[k], j), z[k]));
+        }
+      }
+
+      GF.solveVandermondeSystem(x, y);
+      assertTrue("Solving Vandermonde system failed",
+                 java.util.Arrays.equals(y, z));
+    }
+  }
+
+  public void testRemainder() {
+    final int TEST_LEN = 15;
+    for (int i = 0; i < TEST_TIMES; i++) {
+      int[] quotient = null;
+      int[] divisor = null;
+      int[] remainder = null;
+      int[] dividend = null;
+      while (true) {
+        quotient = randGFPoly(RAND.nextInt(TEST_LEN - 3) + 3);
+        divisor = randGFPoly(RAND.nextInt(quotient.length - 2) + 2);
+        remainder = randGFPoly(RAND.nextInt(divisor.length - 1) + 1);
+        dividend = GF.add(remainder, GF.multiply(quotient, divisor));
+        if (quotient[quotient.length - 1] != 0 &&
+            divisor[divisor.length - 1] != 0 &&
+            remainder[remainder.length - 1] != 0) {
+          // make sure all the leading terms are not zero
+          break;
+        }
+      }
+      GF.remainder(dividend, divisor);
+      for (int j = 0; j < remainder.length; j++) {
+        assertTrue("Distributivity test on polynomials failed",
+                   dividend[j] == remainder[j]);
+      }
+    }
+  }
+}



Mime
View raw message