Spark与Hadoop关 TeraGen/TeraSort的对比实验

自从 hadoop 问世以来，MapReduce 在很长时间内都是排序基准测试的纪录保持者，但这一垄断在最近被基于内存计算的 Spark 打破了。在今年Databricks与AWS一起完成的一个Daytona Gray类别的Sort Benchmark中，Spark 完胜 Hadoop MapReduce：“1/10计算资源，1/3耗时”。这是个很有意思的对比实验，因此笔者也在一个小规模集群上做了一个微缩版的类似试验。

1、Hadoop 与 Spark 集群环境完全相同：

- Hadoop 2.2.0

- Spark 1.0

- 5 节点集群:

    node1: NameNode, ResourceManger 

    node2 - node 5: NodeManager

- Hardware:

8 core cpu, 32 GB memory, 400 GB disk

2、排序数据规模：100 GB

3、Hadoop 排序：

3.1 TeraGen:

在4个slaves上共启动了120个mapper：

hadoop jar ${HADOOP_EXAMPLE_JAR_PATH} teragen -Dmapred.map.tasks=120 ${TERAGEN_ROW} ${TERAGEN_OUTPUT}

3.2 TeraSort:

在4个slaves上共启动了32个reducer：

hadoop jar ${HADOOP_EXAMPLE_JAR_PATH} terasort -Dmapred.reduce.tasks=32 ${TERAGEN_OUTPUT} ${TERASORT_OUTPUT}

3.3 生成100 GB测试数据、完成排序总共花费的时间：

总计：6723 秒

4、Spark 排序：

4.1 源代码：

4.1.1 来源：

https://github.com/apache/spark/pull/1242
https://github.com/rxin/spark/tree/adcae69145905162fa3b6932f70be2c932f95f87/examples/src/main/scala/org/apache/spark/examples/terasort

4.1.2 为了便于大家阅读源代码，我把源代码也附于本文文末(已做些许更改)

4.2 生成测试数据、完成排序(如果输出文件格式为text file，则排序结果的文件总大小为309.2 GB)总共花费的时间：

- 试验一：

  * 任务提交参数：num-executors: 4， executor-memory: 8g， executor-cores: 4

  * 输出文件格式：Sequence File

  * 输出文件所占空间为：20.8 GB

  * 总时间为:  2203 秒

- 试验二：

  * 任务提交参数：num-executors: 4， executor-memory: 16g， executor-cores: 6

  * 输出文件格式：Text File

  * 输出文件所占空间为：309.2 GB

  * 总时间为: 9849 秒

- 试验三：

  * 任务提交参数：num-executors: 4， executor-memory: 16g， executor-cores: 6

  * 输出文件格式：Sequence File

  * 输出文件所占空间为：20.8 GB

  * 总时间为: 2212 秒

- 试验四：

  * 任务提交参数：num-executors: 8， executor-memory: 7g， executor-cores: 3

  * 输出文件格式：Sequence File

  * 输出文件所占空间为：20.8 GB

  * 总时间为: 1213 秒

- 试验五：

  * 任务提交参数：num-executors: 28， executor-memory: 2g， executor-cores: 1

  * 输出文件格式：Sequence File

  * 输出文件所占空间为：20.8 GB

  * 总时间为: 483 秒

- 试验六：

  * 任务提交参数：num-executors: 56， executor-memory: 1g， executor-cores: 1

  * 输出文件格式：Sequence File

  * 输出文件所占空间为：20.8 GB

  * 总时间为: 434 秒

5、小结：

5.1 Hadoop 与 Spark 比较：

当然，执行过程肯定还有调优空间，但 Spark 明显快于 Hadoop MapReduce。这个结果也很正常：这是内存对于硬盘的胜利。

5.2 Spark 几次试验之间的比较：

- 输出结果为Sequence file时，要大大快于输出结果为 Text file时。因为Sequence file大大压缩了输出文件大小，也减少了大量 disk IO，这样也就很大地缩短了执行时间

- 如果单个executor的计算并不需要过大的内存，不如降低单个executor的内存共给量，同时增加executor的并发数（如果任务适合并发）

- 一旦单个worker的内存与cpu已经被充分利用，而且并发的executor数也比较合理，那么再进一步分割executor数并不会增加效率

附：Spark Sort 源代码

a. GenSort.scala

[javascript] view plaincopy

1. package scala.spark.examples.terasort 
2.  
3. /** 
4.  * Licensed to the Apache Software Foundation (ASF) under one 
5.  * or more contributor license agreements. See the NOTICE file 
6.  * distributed with this work for additional information 
7.  * regarding copyright ownership. The ASF licenses this file 
8.  * to you under the Apache License, Version 2.0 (the 
9.  * "License"); you may not use this file except in compliance 
10.  * with the License. You may obtain a copy of the License at 
11.  * 
12.  * http://www.apache.org/licenses/LICENSE-2.0 
13.  * 
14.  * Unless required by applicable law or agreed to in writing, software 
15.  * distributed under the License is distributed on an "AS IS" BASIS, 
16.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
17.  * See the License for the specific language governing permissions and 
18.  * limitations under the License. 
19.  */ 
20.  
21. import org.apache.hadoop.io.{ BytesWritable, NullWritable } 
22. import org.apache.hadoop.io.compress.BZip2Codec 
23. import org.apache.spark.SparkContext 
24. import org.apache.spark.SparkContext._ 
25. import org.apache.spark._ 
26. import SparkContext._ 
27. object GenSort { 
28.   def main(args: Array[String]) { 
29.     if (args.length < 3) { 
30.       println("usage:") 
31.       println("MASTER=[spark-master] bin/run-example org.apache.spark.examples.terasort.GenSort " + 
32.         " [num-parts] [records-per-part] [output-path]") 
33.       System.exit(0) 
34.     } 
35.     val master = sys.env.getOrElse("MASTER", "local") 
36.     val parts = args(0).toInt 
37.     val recordsPerPartition = args(1).toInt 
38.     val numRecords = parts.toLong * recordsPerPartition.toLong 
39.     val output = args(2) 
40.     println(s"Generating $numRecords records on $parts partitions") 
41.     println(s"Output path: $output") 
42. //    val sc = new SparkContext(master, "GenSort") 
43.     val conf = new SparkConf().setAppName("GenSort") 
44.     val sc = new SparkContext(conf) 
45.     val dataset = sc.parallelize(1 to parts, parts).mapPartitionsWithIndex { 
46.       case (index, _) => 
47.         val one = new Unsigned16(1) 
48.         val firstRecordNumber = new Unsigned16(index * recordsPerPartition) 
49.         val recordsToGenerate = new Unsigned16(recordsPerPartition) 
50.         val recordNumber = new Unsigned16(firstRecordNumber) 
51.         val lastRecordNumber = new Unsigned16(firstRecordNumber) 
52.         lastRecordNumber.add(recordsToGenerate) 
53.         val rand = Random16.skipAhead(firstRecordNumber) 
54.         val row: Array[Byte] = new Array[Byte](100) 
55.         Iterator.tabulate(recordsPerPartition) { offset => 
56.           Random16.nextRand(rand) 
57.           generateRecord(row, rand, recordNumber) 
58.           recordNumber.add(one) 
59.           row 
60.         } 
61.     } 
62.     // Save output result as text file 
63.     dataset.map(row => (NullWritable.get(), new BytesWritable(row))).saveAsTextFile(output) 
64.      
65.     // Save output result as sequence file 
66. //    dataset.map(row => (NullWritable.get(), new BytesWritable(row))) 
67. //      .saveAsSequenceFile(output, Some(classOf[BZip2Codec])) 
68.   } 
69.   /** 
70.    * Generate a binary record suitable for all sort benchmarks except PennySort. 
71.    * 
72.    * @param recBuf record to return 
73.    */ 
74.   def generateRecord(recBuf: Array[Byte], rand: Unsigned16, recordNumber: Unsigned16): Unit = { 
75.     // Generate the 10-byte key using the high 10 bytes of the 128-bit random number 
76.     var i = 0 
77.     while (i < 10) { 
78.       recBuf(i) = rand.getByte(i) 
79.       i += 1 
80.     } 
81.     // Add 2 bytes of "break" 
82.     recBuf(10) = 0x00.toByte 
83.     recBuf(11) = 0x11.toByte 
84.     // Convert the 128-bit record number to 32 bits of ascii hexadecimal 
85.     // as the next 32 bytes of the record. 
86.     i = 0 
87.     while (i < 32) { 
88.       recBuf(12 + i) = recordNumber.getHexDigit(i).toByte 
89.       i += 1 
90.     } 
91.     // Add 4 bytes of "break" data 
92.     recBuf(44) = 0x88.toByte 
93.     recBuf(45) = 0x99.toByte 
94.     recBuf(46) = 0xAA.toByte 
95.     recBuf(47) = 0xBB.toByte 
96.     // Add 48 bytes of filler based on low 48 bits of random number 
97.     i = 0 
98.     while (i < 12) { 
99.       val v = rand.getHexDigit(20 + i).toByte 
100.       recBuf(48 + i * 4) = v 
101.       recBuf(49 + i * 4) = v 
102.       recBuf(50 + i * 4) = v 
103.       recBuf(51 + i * 4) = v 
104.       i += 1 
105.     } 
106.     // Add 4 bytes of "break" data 
107.     recBuf(96) = 0xCC.toByte 
108.     recBuf(97) = 0xDD.toByte 
109.     recBuf(98) = 0xEE.toByte 
110.     recBuf(99) = 0xFF.toByte 
111.   } 
112. } 

b. Random16.java

[javascript] view plaincopy

1. /** 
2.  * Licensed to the Apache Software Foundation (ASF) under one 
3.  * or more contributor license agreements. See the NOTICE file 
4.  * distributed with this work for additional information 
5.  * regarding copyright ownership. The ASF licenses this file 
6.  * to you under the Apache License, Version 2.0 (the 
7.  * "License"); you may not use this file except in compliance 
8.  * with the License. You may obtain a copy of the License at 
9.  * 
10.  * http://www.apache.org/licenses/LICENSE-2.0 
11.  * 
12.  * Unless required by applicable law or agreed to in writing, software 
13.  * distributed under the License is distributed on an "AS IS" BASIS, 
14.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
15.  * See the License for the specific language governing permissions and 
16.  * limitations under the License. 
17.  */ 
18. package scala.spark.examples.terasort; 
19.  
20. /** 
21.  * This file is copied from Hadoop package org.apache.hadoop.examples.terasort. 
22.  */ 
23. /** 
24.  * This class implements a 128-bit linear congruential generator. Specifically, 
25.  * if X0 is the most recently issued 128-bit random number (or a seed of 0 if no 
26.  * random number has already been generated, the next number to be generated, 
27.  * X1, is equal to: X1 = (a * X0 + c) mod 2**128 where a is 
28.  * 47026247687942121848144207491837523525 or 0x2360ed051fc65da44385df649fccf645 
29.  * and c is 98910279301475397889117759788405497857 or 
30.  * 0x4a696d47726179524950202020202001 The coefficient "a" is suggested by: 
31.  * Pierre L'Ecuyer, "Tables of linear congruential generators of different sizes 
32.  * and good lattice structure", Mathematics of Computation, 68 pp. 249 - 260 
33.  * (1999) 
34.  * http://www.ams.org/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99 
35.  * -00996-5.pdf The constant "c" meets the simple suggestion by the same 
36.  * reference that it be odd. 
37.  *  
38.  * There is also a facility for quickly advancing the state of the generator by 
39.  * a fixed number of steps - this facilitates parallel generation. 
40.  *  
41.  * This is based on 1.0 of rand16.c from Chris Nyberg 
42.  * <chris.nyberg@ordinal.com>. 
43.  */ 
44. class Random16 { 
45.     /** 
46.      * The "Gen" array contain powers of 2 of the linear congruential generator. 
47.      * The index 0 struct contain the "a" coefficient and "c" constant for the 
48.      * generator. That is, the generator is: f(x) = (Gen[0].a * x + Gen[0].c) 
49.      * mod 2**128 
50.      *  
51.      * All structs after the first contain an "a" and "c" that comprise the 
52.      * square of the previous function. 
53.      *  
54.      * f**2(x) = (Gen[1].a * x + Gen[1].c) mod 2**128 f**4(x) = (Gen[2].a * x + 
55.      * Gen[2].c) mod 2**128 f**8(x) = (Gen[3].a * x + Gen[3].c) mod 2**128 ... 
56.      */ 
57.     private static class RandomConstant { 
58.         final Unsigned16 a; 
59.         final Unsigned16 c; 
60.  
61.         public RandomConstant(String left, String right) { 
62.             a = new Unsigned16(left); 
63.             c = new Unsigned16(right); 
64.         } 
65.     } 
66.  
67.     private static final RandomConstant[] genArray = new RandomConstant[] { 
68.             /* [ 0] */new RandomConstant("2360ed051fc65da44385df649fccf645", 
69.                     "4a696d47726179524950202020202001"), 
70.             /* [ 1] */new RandomConstant("17bce35bdf69743c529ed9eb20e0ae99", 
71.                     "95e0e48262b3edfe04479485c755b646"), 
72.             /* [ 2] */new RandomConstant("f4dd417327db7a9bd194dfbe42d45771", 
73.                     "882a02c315362b60765f100068b33a1c"), 
74.             /* [ 3] */new RandomConstant("6347af777a7898f6d1a2d6f33505ffe1", 
75.                     "5efc4abfaca23e8ca8edb1f2dfbf6478"), 
76.             /* [ 4] */new RandomConstant("b6a4239f3b315f84f6ef6d3d288c03c1", 
77.                     "f25bd15439d16af594c1b1bafa6239f0"), 
78.             /* [ 5] */new RandomConstant("2c82901ad1cb0cd182b631ba6b261781", 
79.                     "89ca67c29c9397d59c612596145db7e0"), 
80.             /* [ 6] */new RandomConstant("dab03f988288676ee49e66c4d2746f01", 
81.                     "8b6ae036713bd578a8093c8eae5c7fc0"), 
82.             /* [ 7] */new RandomConstant("602167331d86cf5684fe009a6d09de01", 
83.                     "98a2542fd23d0dbdff3b886cdb1d3f80"), 
84.             /* [ 8] */new RandomConstant("61ecb5c24d95b058f04c80a23697bc01", 
85.                     "954db923fdb7933e947cd1edcecb7f00"), 
86.             /* [ 9] */new RandomConstant("4a5c31e0654c28aa60474e83bf3f7801", 
87.                     "00be4a36657c98cd204e8c8af7dafe00"), 
88.             /* [ 10] */new RandomConstant("ae4f079d54fbece1478331d3c6bef001", 
89.                     "991965329dccb28d581199ab18c5fc00"), 
90.             /* [ 11] */new RandomConstant("101b8cb830c7cb927ff1ed50ae7de001", 
91.                     "e1a8705b63ad5b8cd6c3d268d5cbf800"), 
92.             /* [ 12] */new RandomConstant("f54a27fc056b00e7563f3505e0fbc001", 
93.                     "2b657bbfd6ed9d632079e70c3c97f000"), 
94.             /* [ 13] */new RandomConstant("df8a6fc1a833d201f98d719dd1f78001", 
95.                     "59b60ee4c52fa49e9fe90682bd2fe000"), 
96.             /* [ 14] */new RandomConstant("5480a5015f101a4ea7e3f183e3ef0001", 
97.                     "cc099c88030679464fe86aae8a5fc000"), 
98.             /* [ 15] */new RandomConstant("a498509e76e5d7925f539c28c7de0001", 
99.                     "06b9abff9f9f33dd30362c0154bf8000"), 
100.             /* [ 16] */new RandomConstant("0798a3d8b10dc72e60121cd58fbc0001", 
101.                     "e296707121688d5a0260b293a97f0000"), 
102.             /* [ 17] */new RandomConstant("1647d1e78ec02e665fafcbbb1f780001", 
103.                     "189ffc4701ff23cb8f8acf6b52fe0000"), 
104.             /* [ 18] */new RandomConstant("a7c982285e72bf8c0c8ddfb63ef00001", 
105.                     "5141110ab208fb9d61fb47e6a5fc0000"), 
106.             /* [ 19] */new RandomConstant("3eb78ee8fb8c56dbc5d4e06c7de00001", 
107.                     "3c97caa62540f2948d8d340d4bf80000"), 
108.             /* [ 20] */new RandomConstant("72d03b6f4681f2f9fe8e44d8fbc00001", 
109.                     "1b25cb9cfe5a0c963174f91a97f00000"), 
110.             /* [ 21] */new RandomConstant("ea85f81e4f502c9bc8ae99b1f7800001", 
111.                     "0c644570b4a487103c5436352fe00000"), 
112.             /* [ 22] */new RandomConstant("629c320db08b00c6bfa57363ef000001", 
113.                     "3d0589c28869472bde517c6a5fc00000"), 
114.             /* [ 23] */new RandomConstant("c5c4b9ce268d074a386be6c7de000001", 
115.                     "bc95e5ab36477e65534738d4bf800000"), 
116.             /* [ 24] */new RandomConstant("f30bbbbed1596187555bcd8fbc000001", 
117.                     "ddb02ff72a031c01011f71a97f000000"), 
118.             /* [ 25] */new RandomConstant("4a1000fb26c9eeda3cc79b1f78000001", 
119.                     "2561426086d9acdb6c82e352fe000000"), 
120.             /* [ 26] */new RandomConstant("89fb5307f6bf8ce2c1cf363ef0000001", 
121.                     "64a788e3c118ed1c8215c6a5fc000000"), 
122.             /* [ 27] */new RandomConstant("830b7b3358a5d67ea49e6c7de0000001", 
123.                     "e65ea321908627cfa86b8d4bf8000000"), 
124.             /* [ 28] */new RandomConstant("fd8a51da91a69fe1cd3cd8fbc0000001", 
125.                     "53d27225604d85f9e1d71a97f0000000"), 
126.             /* [ 29] */new RandomConstant("901a48b642b90b55aa79b1f780000001", 
127.                     "ca5ec7a3ed1fe55e07ae352fe0000000"), 
128.             /* [ 30] */new RandomConstant("118cdefdf32144f394f363ef00000001", 
129.                     "4daebb2e085330651f5c6a5fc0000000"), 
130.             /* [ 31] */new RandomConstant("0a88c0a91cff430829e6c7de00000001", 
131.                     "9d6f1a00a8f3f76e7eb8d4bf80000000"), 
132.             /* [ 32] */new RandomConstant("433bef4314f16a9453cd8fbc00000001", 
133.                     "158c62f2b31e496dfd71a97f00000000"), 
134.             /* [ 33] */new RandomConstant("c294b02995ae6738a79b1f7800000001", 
135.                     "290e84a2eb15fd1ffae352fe00000000"), 
136.             /* [ 34] */new RandomConstant("913575e0da8b16b14f363ef000000001", 
137.                     "e3dc1bfbe991a34ff5c6a5fc00000000"), 
138.             /* [ 35] */new RandomConstant("2f61b9f871cf4e629e6c7de000000001", 
139.                     "ddf540d020b9eadfeb8d4bf800000000"), 
140.             /* [ 36] */new RandomConstant("78d26ccbd68320c53cd8fbc000000001", 
141.                     "8ee4950177ce66bfd71a97f000000000"), 
142.             /* [ 37] */new RandomConstant("8b7ebd037898518a79b1f78000000001", 
143.                     "39e0f787c907117fae352fe000000000"), 
144.             /* [ 38] */new RandomConstant("0b5507b61f78e314f363ef0000000001", 
145.                     "659d2522f7b732ff5c6a5fc000000000"), 
146.             /* [ 39] */new RandomConstant("4f884628f812c629e6c7de0000000001", 
147.                     "9e8722938612a5feb8d4bf8000000000"), 
148.             /* [ 40] */new RandomConstant("be896744d4a98c53cd8fbc0000000001", 
149.                     "e941a65d66b64bfd71a97f0000000000"), 
150.             /* [ 41] */new RandomConstant("daf63a553b6318a79b1f780000000001", 
151.                     "7b50d19437b097fae352fe0000000000"), 
152.             /* [ 42] */new RandomConstant("2d7a23d8bf06314f363ef00000000001", 
153.                     "59d7b68e18712ff5c6a5fc0000000000"), 
154.             /* [ 43] */new RandomConstant("392b046a9f0c629e6c7de00000000001", 
155.                     "4087bab2d5225feb8d4bf80000000000"), 
156.             /* [ 44] */new RandomConstant("eb30fbb9c218c53cd8fbc00000000001", 
157.                     "b470abc03b44bfd71a97f00000000000"), 
158.             /* [ 45] */new RandomConstant("b9cdc30594318a79b1f7800000000001", 
159.                     "366630eaba897fae352fe00000000000"), 
160.             /* [ 46] */new RandomConstant("014ab453686314f363ef000000000001", 
161.                     "a2dfc77e8512ff5c6a5fc00000000000"), 
162.             /* [ 47] */new RandomConstant("395221c7d0c629e6c7de000000000001", 
163.                     "1e0d25a14a25feb8d4bf800000000000"), 
164.             /* [ 48] */new RandomConstant("4d972813a18c53cd8fbc000000000001", 
165.                     "9d50a5d3944bfd71a97f000000000000"), 
166.             /* [ 49] */new RandomConstant("06f9e2374318a79b1f78000000000001", 
167.                     "bf7ab5eb2897fae352fe000000000000"), 
168.             /* [ 50] */new RandomConstant("bd220cae86314f363ef0000000000001", 
169.                     "925b14e6512ff5c6a5fc000000000000"), 
170.             /* [ 51] */new RandomConstant("36fd3a5d0c629e6c7de0000000000001", 
171.                     "724cce0ca25feb8d4bf8000000000000"), 
172.             /* [ 52] */new RandomConstant("60def8ba18c53cd8fbc0000000000001", 
173.                     "1af42d1944bfd71a97f0000000000000"), 
174.             /* [ 53] */new RandomConstant("8d500174318a79b1f780000000000001", 
175.                     "0f529e32897fae352fe0000000000000"), 
176.             /* [ 54] */new RandomConstant("48e842e86314f363ef00000000000001", 
177.                     "844e4c6512ff5c6a5fc0000000000000"), 
178.             /* [ 55] */new RandomConstant("4af185d0c629e6c7de00000000000001", 
179.                     "9f40d8ca25feb8d4bf80000000000000"), 
180.             /* [ 56] */new RandomConstant("7a670ba18c53cd8fbc00000000000001", 
181.                     "9912b1944bfd71a97f00000000000000"), 
182.             /* [ 57] */new RandomConstant("86de174318a79b1f7800000000000001", 
183.                     "9c69632897fae352fe00000000000000"), 
184.             /* [ 58] */new RandomConstant("55fc2e86314f363ef000000000000001", 
185.                     "e1e2c6512ff5c6a5fc00000000000000"), 
186.             /* [ 59] */new RandomConstant("ccf85d0c629e6c7de000000000000001", 
187.                     "68058ca25feb8d4bf800000000000000"), 
188.             /* [ 60] */new RandomConstant("1df0ba18c53cd8fbc000000000000001", 
189.                     "610b1944bfd71a97f000000000000000"), 
190.             /* [ 61] */new RandomConstant("4be174318a79b1f78000000000000001", 
191.                     "061632897fae352fe000000000000000"), 
192.             /* [ 62] */new RandomConstant("d7c2e86314f363ef0000000000000001", 
193.                     "1c2c6512ff5c6a5fc000000000000000"), 
194.             /* [ 63] */new RandomConstant("af85d0c629e6c7de0000000000000001", 
195.                     "7858ca25feb8d4bf8000000000000000"), 
196.             /* [ 64] */new RandomConstant("5f0ba18c53cd8fbc0000000000000001", 
197.                     "f0b1944bfd71a97f0000000000000000"), 
198.             /* [ 65] */new RandomConstant("be174318a79b1f780000000000000001", 
199.                     "e1632897fae352fe0000000000000000"), 
200.             /* [ 66] */new RandomConstant("7c2e86314f363ef00000000000000001", 
201.                     "c2c6512ff5c6a5fc0000000000000000"), 
202.             /* [ 67] */new RandomConstant("f85d0c629e6c7de00000000000000001", 
203.                     "858ca25feb8d4bf80000000000000000"), 
204.             /* [ 68] */new RandomConstant("f0ba18c53cd8fbc00000000000000001", 
205.                     "0b1944bfd71a97f00000000000000000"), 
206.             /* [ 69] */new RandomConstant("e174318a79b1f7800000000000000001", 
207.                     "1632897fae352fe00000000000000000"), 
208.             /* [ 70] */new RandomConstant("c2e86314f363ef000000000000000001", 
209.                     "2c6512ff5c6a5fc00000000000000000"), 
210.             /* [ 71] */new RandomConstant("85d0c629e6c7de000000000000000001", 
211.                     "58ca25feb8d4bf800000000000000000"), 
212.             /* [ 72] */new RandomConstant("0ba18c53cd8fbc000000000000000001", 
213.                     "b1944bfd71a97f000000000000000000"), 
214.             /* [ 73] */new RandomConstant("174318a79b1f78000000000000000001", 
215.                     "632897fae352fe000000000000000000"), 
216.             /* [ 74] */new RandomConstant("2e86314f363ef0000000000000000001", 
217.                     "c6512ff5c6a5fc000000000000000000"), 
218.             /* [ 75] */new RandomConstant("5d0c629e6c7de0000000000000000001", 
219.                     "8ca25feb8d4bf8000000000000000000"), 
220.             /* [ 76] */new RandomConstant("ba18c53cd8fbc0000000000000000001", 
221.                     "1944bfd71a97f0000000000000000000"), 
222.             /* [ 77] */new RandomConstant("74318a79b1f780000000000000000001", 
223.                     "32897fae352fe0000000000000000000"), 
224.             /* [ 78] */new RandomConstant("e86314f363ef00000000000000000001", 
225.                     "6512ff5c6a5fc0000000000000000000"), 
226.             /* [ 79] */new RandomConstant("d0c629e6c7de00000000000000000001", 
227.                     "ca25feb8d4bf80000000000000000000"), 
228.             /* [ 80] */new RandomConstant("a18c53cd8fbc00000000000000000001", 
229.                     "944bfd71a97f00000000000000000000"), 
230.             /* [ 81] */new RandomConstant("4318a79b1f7800000000000000000001", 
231.                     "2897fae352fe00000000000000000000"), 
232.             /* [ 82] */new RandomConstant("86314f363ef000000000000000000001", 
233.                     "512ff5c6a5fc00000000000000000000"), 
234.             /* [ 83] */new RandomConstant("0c629e6c7de000000000000000000001", 
235.                     "a25feb8d4bf800000000000000000000"), 
236.             /* [ 84] */new RandomConstant("18c53cd8fbc000000000000000000001", 
237.                     "44bfd71a97f000000000000000000000"), 
238.             /* [ 85] */new RandomConstant("318a79b1f78000000000000000000001", 
239.                     "897fae352fe000000000000000000000"), 
240.             /* [ 86] */new RandomConstant("6314f363ef0000000000000000000001", 
241.                     "12ff5c6a5fc000000000000000000000"), 
242.             /* [ 87] */new RandomConstant("c629e6c7de0000000000000000000001", 
243.                     "25feb8d4bf8000000000000000000000"), 
244.             /* [ 88] */new RandomConstant("8c53cd8fbc0000000000000000000001", 
245.                     "4bfd71a97f0000000000000000000000"), 
246.             /* [ 89] */new RandomConstant("18a79b1f780000000000000000000001", 
247.                     "97fae352fe0000000000000000000000"), 
248.             /* [ 90] */new RandomConstant("314f363ef00000000000000000000001", 
249.                     "2ff5c6a5fc0000000000000000000000"), 
250.             /* [ 91] */new RandomConstant("629e6c7de00000000000000000000001", 
251.                     "5feb8d4bf80000000000000000000000"), 
252.             /* [ 92] */new RandomConstant("c53cd8fbc00000000000000000000001", 
253.                     "bfd71a97f00000000000000000000000"), 
254.             /* [ 93] */new RandomConstant("8a79b1f7800000000000000000000001", 
255.                     "7fae352fe00000000000000000000000"), 
256.             /* [ 94] */new RandomConstant("14f363ef000000000000000000000001", 
257.                     "ff5c6a5fc00000000000000000000000"), 
258.             /* [ 95] */new RandomConstant("29e6c7de000000000000000000000001", 
259.                     "feb8d4bf800000000000000000000000"), 
260.             /* [ 96] */new RandomConstant("53cd8fbc000000000000000000000001", 
261.                     "fd71a97f000000000000000000000000"), 
262.             /* [ 97] */new RandomConstant("a79b1f78000000000000000000000001", 
263.                     "fae352fe000000000000000000000000"), 
264.             /* [ 98] */new RandomConstant("4f363ef0000000000000000000000001", 
265.                     "f5c6a5fc000000000000000000000000"), 
266.             /* [ 99] */new RandomConstant("9e6c7de0000000000000000000000001", 
267.                     "eb8d4bf8000000000000000000000000"), 
268.             /* [100] */new RandomConstant("3cd8fbc0000000000000000000000001", 
269.                     "d71a97f0000000000000000000000000"), 
270.             /* [101] */new RandomConstant("79b1f780000000000000000000000001", 
271.                     "ae352fe0000000000000000000000000"), 
272.             /* [102] */new RandomConstant("f363ef00000000000000000000000001", 
273.                     "5c6a5fc0000000000000000000000000"), 
274.             /* [103] */new RandomConstant("e6c7de00000000000000000000000001", 
275.                     "b8d4bf80000000000000000000000000"), 
276.             /* [104] */new RandomConstant("cd8fbc00000000000000000000000001", 
277.                     "71a97f00000000000000000000000000"), 
278.             /* [105] */new RandomConstant("9b1f7800000000000000000000000001", 
279.                     "e352fe00000000000000000000000000"), 
280.             /* [106] */new RandomConstant("363ef000000000000000000000000001", 
281.                     "c6a5fc00000000000000000000000000"), 
282.             /* [107] */new RandomConstant("6c7de000000000000000000000000001", 
283.                     "8d4bf800000000000000000000000000"), 
284.             /* [108] */new RandomConstant("d8fbc000000000000000000000000001", 
285.                     "1a97f000000000000000000000000000"), 
286.             /* [109] */new RandomConstant("b1f78000000000000000000000000001", 
287.                     "352fe000000000000000000000000000"), 
288.             /* [110] */new RandomConstant("63ef0000000000000000000000000001", 
289.                     "6a5fc000000000000000000000000000"), 
290.             /* [111] */new RandomConstant("c7de0000000000000000000000000001", 
291.                     "d4bf8000000000000000000000000000"), 
292.             /* [112] */new RandomConstant("8fbc0000000000000000000000000001", 
293.                     "a97f0000000000000000000000000000"), 
294.             /* [113] */new RandomConstant("1f780000000000000000000000000001", 
295.                     "52fe0000000000000000000000000000"), 
296.             /* [114] */new RandomConstant("3ef00000000000000000000000000001", 
297.                     "a5fc0000000000000000000000000000"), 
298.             /* [115] */new RandomConstant("7de00000000000000000000000000001", 
299.                     "4bf80000000000000000000000000000"), 
300.             /* [116] */new RandomConstant("fbc00000000000000000000000000001", 
301.                     "97f00000000000000000000000000000"), 
302.             /* [117] */new RandomConstant("f7800000000000000000000000000001", 
303.                     "2fe00000000000000000000000000000"), 
304.             /* [118] */new RandomConstant("ef000000000000000000000000000001", 
305.                     "5fc00000000000000000000000000000"), 
306.             /* [119] */new RandomConstant("de000000000000000000000000000001", 
307.                     "bf800000000000000000000000000000"), 
308.             /* [120] */new RandomConstant("bc000000000000000000000000000001", 
309.                     "7f000000000000000000000000000000"), 
310.             /* [121] */new RandomConstant("78000000000000000000000000000001", 
311.                     "fe000000000000000000000000000000"), 
312.             /* [122] */new RandomConstant("f0000000000000000000000000000001", 
313.                     "fc000000000000000000000000000000"), 
314.             /* [123] */new RandomConstant("e0000000000000000000000000000001", 
315.                     "f8000000000000000000000000000000"), 
316.             /* [124] */new RandomConstant("c0000000000000000000000000000001", 
317.                     "f0000000000000000000000000000000"), 
318.             /* [125] */new RandomConstant("80000000000000000000000000000001", 
319.                     "e0000000000000000000000000000000"), 
320.             /* [126] */new RandomConstant("00000000000000000000000000000001", 
321.                     "c0000000000000000000000000000000"), 
322.             /* [127] */new RandomConstant("00000000000000000000000000000001", 
323.                     "80000000000000000000000000000000") }; 
324.  
325.     /** 
326.      * generate the random number that is "advance" steps from an initial random 
327.      * number of 0. This is done by starting with 0, and then advancing the by 
328.      * the appropriate powers of 2 of the linear congruential generator. 
329.      */ 
330.     public static Unsigned16 skipAhead(Unsigned16 advance) { 
331.         Unsigned16 result = new Unsigned16(); 
332.         long bit_map; 
333.         bit_map = advance.getLow8(); 
334.         for (int i = 0; bit_map != 0 && i < 64; i++) { 
335.             if ((bit_map & (1L << i)) != 0) { 
336.                 /* 
337.                  * advance random number by f**(2**i) (x) 
338.                  */ 
339.                 result.multiply(genArray[i].a); 
340.                 result.add(genArray[i].c); 
341.                 bit_map &= ~(1L << i); 
342.             } 
343.         } 
344.         bit_map = advance.getHigh8(); 
345.         for (int i = 0; bit_map != 0 && i < 64; i++) { 
346.             if ((bit_map & (1L << i)) != 0) { 
347.                 /* 
348.                  * advance random number by f**(2**(i + 64)) (x) 
349.                  */ 
350.                 result.multiply(genArray[i + 64].a); 
351.                 result.add(genArray[i + 64].c); 
352.                 bit_map &= ~(1L << i); 
353.             } 
354.         } 
355.         return result; 
356.     } 
357.  
358.     /** 
359.      * Generate the next 16 byte random number. 
360.      */ 
361.     public static void nextRand(Unsigned16 rand) { 
362.         /* 
363.          * advance the random number forward once using the linear congruential 
364.          * generator, and then return the new random number 
365.          */ 
366.         rand.multiply(genArray[0].a); 
367.         rand.add(genArray[0].c); 
368.     } 
369. } 

c. Unsigned16.java

[javascript] view plaincopy

1. /** 
2.  * Licensed to the Apache Software Foundation (ASF) under one 
3.  * or more contributor license agreements. See the NOTICE file 
4.  * distributed with this work for additional information 
5.  * regarding copyright ownership. The ASF licenses this file 
6.  * to you under the Apache License, Version 2.0 (the 
7.  * "License"); you may not use this file except in compliance 
8.  * with the License. You may obtain a copy of the License at 
9.  * 
10.  * http://www.apache.org/licenses/LICENSE-2.0 
11.  * 
12.  * Unless required by applicable law or agreed to in writing, software 
13.  * distributed under the License is distributed on an "AS IS" BASIS, 
14.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
15.  * See the License for the specific language governing permissions and 
16.  * limitations under the License. 
17.  */ 
18. package scala.spark.examples.terasort; 
19.  
20. import java.io.DataInput; 
21. import java.io.DataOutput; 
22. import java.io.IOException; 
23. import org.apache.hadoop.io.Writable; 
24.  
25. /** 
26.  * This file is copied from Hadoop package org.apache.hadoop.examples.terasort. 
27.  */ 
28. /** 
29.  * An unsigned 16 byte integer class that supports addition, multiplication, and 
30.  * left shifts. 
31.  */ 
32. class Unsigned16 implements Writable { 
33.     private long hi8; 
34.     private long lo8; 
35.  
36.     public Unsigned16() { 
37.         hi8 = 0; 
38.         lo8 = 0; 
39.     } 
40.  
41.     public Unsigned16(long l) { 
42.         hi8 = 0; 
43.         lo8 = l; 
44.     } 
45.  
46.     public Unsigned16(Unsigned16 other) { 
47.         hi8 = other.hi8; 
48.         lo8 = other.lo8; 
49.     } 
50.  
51.     @Override 
52.     public boolean equals(Object o) { 
53.         if (o instanceof Unsigned16) { 
54.             Unsigned16 other = (Unsigned16) o; 
55.             return other.hi8 == hi8 && other.lo8 == lo8; 
56.         } 
57.         return false; 
58.     } 
59.  
60.     @Override 
61.     public int hashCode() { 
62.         return (int) lo8; 
63.     } 
64.  
65.     /** 
66.      * Parse a hex string 
67.      *  
68.      * @param s 
69.      *            the hex string 
70.      */ 
71.     public Unsigned16(String s) throws NumberFormatException { 
72.         set(s); 
73.     } 
74.  
75.     /** 
76.      * Set the number from a hex string 
77.      *  
78.      * @param s 
79.      *            the number in hexadecimal 
80.      * @throws NumberFormatException 
81.      *             if the number is invalid 
82.      */ 
83.     public void set(String s) throws NumberFormatException { 
84.         hi8 = 0; 
85.         lo8 = 0; 
86.         final long lastDigit = 0xfl << 60; 
87.         for (int i = 0; i < s.length(); ++i) { 
88.             int digit = getHexDigit(s.charAt(i)); 
89.             if ((lastDigit & hi8) != 0) { 
90.                 throw new NumberFormatException(s + " overflowed 16 bytes"); 
91.             } 
92.             hi8 <<= 4; 
93.             hi8 |= (lo8 & lastDigit) >>> 60; 
94.             lo8 <<= 4; 
95.             lo8 |= digit; 
96.         } 
97.     } 
98.  
99.     /** 
100.      * Set the number to a given long. 
101.      *  
102.      * @param l 
103.      *            the new value, which is treated as an unsigned number 
104.      */ 
105.     public void set(long l) { 
106.         lo8 = l; 
107.         hi8 = 0; 
108.     } 
109.  
110.     /** 
111.      * Map a hexadecimal character into a digit. 
112.      *  
113.      * @param ch 
114.      *            the character 
115.      * @return the digit from 0 to 15 
116.      * @throws NumberFormatException 
117.      */ 
118.     private static int getHexDigit(char ch) throws NumberFormatException { 
119.         if (ch >= '0' && ch <= '9') { 
120.             return ch - '0'; 
121.         } 
122.         if (ch >= 'a' && ch <= 'f') { 
123.             return ch - 'a' + 10; 
124.         } 
125.         if (ch >= 'A' && ch <= 'F') { 
126.             return ch - 'A' + 10; 
127.         } 
128.         throw new NumberFormatException(ch + " is not a valid hex digit"); 
129.     } 
130.  
131.     private static final Unsigned16 TEN = new Unsigned16(10); 
132.  
133.     public static Unsigned16 fromDecimal(String s) throws NumberFormatException { 
134.         Unsigned16 result = new Unsigned16(); 
135.         Unsigned16 tmp = new Unsigned16(); 
136.         for (int i = 0; i < s.length(); i++) { 
137.             char ch = s.charAt(i); 
138.             if (ch < '0' || ch > '9') { 
139.                 throw new NumberFormatException(ch 
140.                         + " not a valid decimal digit"); 
141.             } 
142.             int digit = ch - '0'; 
143.             result.multiply(TEN); 
144.             tmp.set(digit); 
145.             result.add(tmp); 
146.         } 
147.         return result; 
148.     } 
149.  
150.     /** 
151.      * Return the number as a hex string. 
152.      */ 
153.     public String toString() { 
154.         if (hi8 == 0) { 
155.             return Long.toHexString(lo8); 
156.         } else { 
157.             StringBuilder result = new StringBuilder(); 
158.             result.append(Long.toHexString(hi8)); 
159.             String loString = Long.toHexString(lo8); 
160.             for (int i = loString.length(); i < 16; ++i) { 
161.                 result.append('0'); 
162.             } 
163.             result.append(loString); 
164.             return result.toString(); 
165.         } 
166.     } 
167.  
168.     /** 
169.      * Get a given byte from the number. 
170.      *  
171.      * @param b 
172.      *            the byte to get with 0 meaning the most significant byte 
173.      * @return the byte or 0 if b is outside of 0..15 
174.      */ 
175.     public byte getByte(int b) { 
176.         if (b >= 0 && b < 16) { 
177.             if (b < 8) { 
178.                 return (byte) (hi8 >> (56 - 8 * b)); 
179.             } else { 
180.                 return (byte) (lo8 >> (120 - 8 * b)); 
181.             } 
182.         } 
183.         return 0; 
184.     } 
185.  
186.     /** 
187.      * Get the hexadecimal digit at the given position. 
188.      *  
189.      * @param p 
190.      *            the digit position to get with 0 meaning the most significant 
191.      * @return the character or '0' if p is outside of 0..31 
192.      */ 
193.     public char getHexDigit(int p) { 
194.         byte digit = getByte(p / 2); 
195.         if (p % 2 == 0) { 
196.             digit >>>= 4; 
197.         } 
198.         digit &= 0xf; 
199.         if (digit < 10) { 
200.             return (char) ('0' + digit); 
201.         } else { 
202.             return (char) ('A' + digit - 10); 
203.         } 
204.     } 
205.  
206.     /** 
207.      * Get the high 8 bytes as a long. 
208.      */ 
209.     public long getHigh8() { 
210.         return hi8; 
211.     } 
212.  
213.     /** 
214.      * Get the low 8 bytes as a long. 
215.      */ 
216.     public long getLow8() { 
217.         return lo8; 
218.     } 
219.  
220.     /** 
221.      * Multiple the current number by a 16 byte unsigned integer. Overflow is 
222.      * not detected and the result is the low 16 bytes of the result. The 
223.      * numbers are divided into 32 and 31 bit chunks so that the product of two 
224.      * chucks fits in the unsigned 63 bits of a long. 
225.      *  
226.      * @param b 
227.      *            the other number 
228.      */ 
229.     void multiply(Unsigned16 b) { 
230.         // divide the left into 4 32 bit chunks 
231.         long[] left = new long[4]; 
232.         left[0] = lo8 & 0xffffffffl; 
233.         left[1] = lo8 >>> 32; 
234.         left[2] = hi8 & 0xffffffffl; 
235.         left[3] = hi8 >>> 32; 
236.         // divide the right into 5 31 bit chunks 
237.         long[] right = new long[5]; 
238.         right[0] = b.lo8 & 0x7fffffffl; 
239.         right[1] = (b.lo8 >>> 31) & 0x7fffffffl; 
240.         right[2] = (b.lo8 >>> 62) + ((b.hi8 & 0x1fffffffl) << 2); 
241.         right[3] = (b.hi8 >>> 29) & 0x7fffffffl; 
242.         right[4] = (b.hi8 >>> 60); 
243.         // clear the cur value 
244.         set(0); 
245.         Unsigned16 tmp = new Unsigned16(); 
246.         for (int l = 0; l < 4; ++l) { 
247.             for (int r = 0; r < 5; ++r) { 
248.                 long prod = left[l] * right[r]; 
249.                 if (prod != 0) { 
250.                     int off = l * 32 + r * 31; 
251.                     tmp.set(prod); 
252.                     tmp.shiftLeft(off); 
253.                     add(tmp); 
254.                 } 
255.             } 
256.         } 
257.     } 
258.  
259.     /** 
260.      * Add the given number into the current number. 
261.      *  
262.      * @param b 
263.      *            the other number 
264.      */ 
265.     public void add(Unsigned16 b) { 
266.         long sumHi; 
267.         long sumLo; 
268.         long reshibit, hibit0, hibit1; 
269.         sumHi = hi8 + b.hi8; 
270.         hibit0 = (lo8 & 0x8000000000000000L); 
271.         hibit1 = (b.lo8 & 0x8000000000000000L); 
272.         sumLo = lo8 + b.lo8; 
273.         reshibit = (sumLo & 0x8000000000000000L); 
274.         if ((hibit0 & hibit1) != 0 | ((hibit0 ^ hibit1) != 0 && reshibit == 0)) 
275.             sumHi++; /* add carry bit */ 
276.         hi8 = sumHi; 
277.         lo8 = sumLo; 
278.     } 
279.  
280.     /** 
281.      * Shift the number a given number of bit positions. The number is the low 
282.      * order bits of the result. 
283.      *  
284.      * @param bits 
285.      *            the bit positions to shift by 
286.      */ 
287.     public void shiftLeft(int bits) { 
288.         if (bits != 0) { 
289.             if (bits < 64) { 
290.                 hi8 <<= bits; 
291.                 hi8 |= (lo8 >>> (64 - bits)); 
292.                 lo8 <<= bits; 
293.             } else if (bits < 128) { 
294.                 hi8 = lo8 << (bits - 64); 
295.                 lo8 = 0; 
296.             } else { 
297.                 hi8 = 0; 
298.                 lo8 = 0; 
299.             } 
300.         } 
301.     } 
302.  
303.     @Override 
304.     public void readFields(DataInput in) throws IOException { 
305.         hi8 = in.readLong(); 
306.         lo8 = in.readLong(); 
307.     } 
308.  
309.     @Override 
310.     public void write(DataOutput out) throws IOException { 
311.         out.writeLong(hi8); 
312.         out.writeLong(lo8); 
313.     } 
314. } 
     
315. 原文链接：http://blog.csdn.net/samhacker/article/details/42200937