Báo cáo Tìm hiểu Hadoop, MapReduce, và các bài toán ứng dụng

Báo cáo Tìm hiểu Hadoop, MapReduce, và các bài toán ứng dụng

Mục lục

Phần I. Giới thiệu chung. 5

1.1. Hadoop l { gì ?. 51.2. MapReduce l { gì ?. 5Phần II. Cài đặt Hadoop. 71. Cài đặt máy ảo Ubuntu 10.10 ( 32 bit ) trên VMware. 71. Cài đặt Vmware tools cho Ubuntu. 72. Cài openSSH cho ubuntu. 73. Cài java :. 74. Thêm user hadoop vào nhóm hadoop. 85. Cấu hình ssh. 96. Vô hiệu hóa IPv6. 117. Download và thiết lập hadoop. 12a. Download Hadoop 0.20.2 và lưu vào thư mục / usr / local /. 12b. Cấu hình. 12c. Định dạng các tên node. 13d. Chạy hadoop trên cụm một node. 138. Chạy một ví dụ MapReduce. 149. Cài đặt và sử dụng Hadoop trên Eclipse. 17Phần III. Thành phần của Hadoop. 201. Một số thuật ngữ. . 202. C | c trình nền của Hadoop. 212.1. NameNode. 212.2. DataNode. 212.3. Secondary NameNode. 222.4. JobTracker. 22

2.5. TaskTracker. 23

Phần IV. Lập trình MapReduce cơ bản. 251. Tổng quan một chương trình MapReduce. 252. Các loại tài liệu mà Hadoop tương hỗ. 262.1. Mapper. 272.2. Reducer. 282.3. Partitioner – chuyển hướng đầu ra từ Mapper. 29Phần V. Sơ lược về các thuật toán tin sinh. 305.1. Thuật toán Blast. 305.2. Thuật toán Landau-Vishkin. 315.2.1. Một số khái niệm. 315.2.2. Khớp xâu xê dịch ( Approximate String Matching ). 325.2.3. Giải pháp quy hoạch động. 32Phần VI. Sơ lược về BlastReduce. 346.1. Tóm tắt :. 346.2. Read Mapping. 346.3. Thuật toán BlastReduce. 356.3.1. MerReduce : tính các Mer giống nhau. 366.3.2. SeedReduce : tích hợp các Mer đồng nhất. 376.3.3. ExtendReduce : lan rộng ra các hạt giống. 37

pdf38 trang | Chia sẻ : maiphuongdc| Lượt xem : 6848

| Lượt tải: 21

download

Bạn đang xem nội dung tài liệu Báo cáo Tìm hiểu Hadoop, MapReduce, và các bài toán ứng dụng, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

ree software ; the exact distribution terms for each program are described in the individual files in / usr / share / doc / * / copyright. Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by applicable law. # disable ipv6 net.ipv6.conf.all. disable_ipv6 = 1 net.ipv6.conf.default. disable_ipv6 = 1 net.ipv6.conf.lo. disable_ipv6 = 1 USD cd / USD cat / proc / sys / net / ipv6 / conf / all / disable_ipv6 Vũ Minh Ngọc 12 7. Download và thiết lập hadoop a. Download Hadoop 0.20.2 và lưu vào thư mục / usr / local / b. Cấu hình i. hadoop-env.sh C { i đặt JAVA_HOME. Thay đổi # The java implementation to use. Required. # export JAVA_HOME = / usr / lib / j2sdk1. 5 – sun Th { nh : # The java implementation to use. Required. export JAVA_HOME = / usr / lib / jvm / java-6-sun ii. conf / core-site.xml hadoop.tmp.dir / your / path / to / hadoop / tmp / dir / hadoop – USD { user.name } A base for other temporary directories. fs.default.name hdfs : / / localhost : 54310 The name of the default file system. A URI whose scheme and authority determine the FileSystem implementation. The uri’s scheme determines the config property ( fs. SCHEME.impl ) naming the FileSystem implementation class. The uri’s authority is used to determine the host, port, etc. for a filesystem. iii. conf / mapred-site.xml mapred.job.tracker localhost : 54311 The host and port that the MapReduce job tracker runs at. If ” local “, then jobs are run in-process as a single map and reduce task. USD cd / usr / local USD sudo tar xzf hadoop-0.20.2.tar.gz USD sudo mv hadoop-0. 20.2 hadoop USD sudo chown – R hadoop : hadoop hadoop Vũ Minh Ngọc 13 iv. conf / hdfs-site.xml dfs.replication 1 Default block replication. The actual number of replications can be specified when the file is created. The default is used if replication is not specified in create time. c. Định dạng các tên node Đầu tiên để khởi động Hadoop vừa của bạn l { định dạng lại mạng lưới hệ thống tệp tin Hadoop m { được triển khai trên đầu của mạng lưới hệ thống tệp tin của bạn. Bạn cần phải l { m việc n { y trong lần đầu chạy. Bạn chạy lệnh sau : Kết quả : d. Chạy hadoop trên cụm một node Sử dụng c } u lệnh : USD / bin / start-all.sh Kết quả như sau : hadoop @ ubuntu : ~ USD / hadoop / bin / hadoop namenode – format Vũ Minh Ngọc 14 Một tool kh | thuật tiện để kiểm tra xem c | c tiến trình Hadoop đang chạy l { jps : Bạn cũng hoàn toàn có thể kiểm tra với netstart nếu Hadoop đang nghe trên c | c cổng đ ~ được thông số kỹ thuật : e. Dừng hadoop trên cụm một node Sử dụng lệnh : / bin / stop-all.sh 8. Chạy một ví dụ MapReduce Chúng ta chạy ví dụ WordCount có sẵn trong phần ví dụ của Hadoop. Nó xẽ đếm c | c từ trong file v { số lần Open. file đầu v { o v { đầu ra đề l { dạng text, mỗi dòng trong file đầu ra chứa từ v { số lần Open, ph } n c | ch với nhau bởi dấu TAB. a. Download dữ liệu đầu v { o Download 3 cuốn s | ch từ Project Gutenberg : The Outline of Science, Vol. 1 ( of 4 ) by J. Arthur Thomson The Notebooks of Leonardo Da Vinci Ulysses by James Joyce Chọn file trong Plain Text UTF-8, sau đó copy v { o thư mục tmp của Hadoop : / tmp / gutenberg, kiểm tra lại như sau : Vũ Minh Ngọc 15 Restart lại hadoop cluster : hadoop @ ubuntu : ~ USD / bin / start-all.sh b. Copy dữ liệu v { o HDFS c. Chạy MapReduce job Sử dụng c } u lệnh sau : Trong c } u lệnh n { y bạn sửa th { nh phiên bản m { bạn đang sử dụng. Bạn hoàn toàn có thể kiểm tra trong thư mục c { i Hadoop có chứa file *. jar n { y. C } u lệnh n { y sẽ đọc toàn bộ c | c file trong thư mục butenberg từ HDFS, giải quyết và xử lý v { lưu tác dụng v { o gutenberg-output. Kết quả đầu ra như sau : 01 hadoop @ ubuntu : / usr / local / hadoop USD bin / hadoop dfs – copyFromLocal / tmp / gutenberg gutenberg 02 hadoop @ ubuntu : / usr / local / hadoop USD bin / hadoop dfs – ls 03 Found 1 items 04 drwxr-xr-x – hadoop supergroup 0 2010 – 05-08 17 : 40 / user / hadoop / gutenberg 05 hadoop @ ubuntu : / usr / local / hadoop USD bin / hadoop dfs – ls gutenberg 06 Found 3 items 07 – rw-r–r — 3 hadoop supergroup 674566 2011 – 03-10 11 : 38 / user / hadoop / gutenberg / pg20417.txt 08 – rw-r–r — 3 hadoop supergroup 1573112 2011 – 03-10 11 : 38 / user / hadoop / gutenberg / pg4300.txt 09 – rw-r–r — 3 hadoop supergroup 1423801 2011 – 03-10 11 : 38 / user / hadoop / gutenberg / pg5000.txt 10 hadoop @ ubuntu : / usr / local / hadoop USD hadoop @ ubuntu : / usr / local / hadoop USD bin / hadoop jar hadoop — examples.jar wordcount gutenberg gutenberg-output Vũ Minh Ngọc 16 Kiểm tra hiệu quả nếu lưu th { nh công : Vũ Minh Ngọc 17 Nếu bạn muốn sửa đổi c | c thiết lập của Hadoop giống như tăng số task Reduce lên, bạn hoàn toàn có thể sử dụng tùy chọn “ – D ” như sau : d. Lấy tác dụng từ HDFS Để kiểm tra c | c file, bạn hoàn toàn có thể copy nó từ HDFS đến mạng lưới hệ thống file địa phương. Ngo { i ra, bạn hoàn toàn có thể sử dụng lệnh sau : Trong ví dụ n { y, tất cả chúng ta hoàn toàn có thể copy như sau : 9. Cài đặt và sử dụng Hadoop trên Eclipse a. Download v { c { i đặt plug-in C | c bạn tải về :  Eclipse SDK Version : 3.5.2  Hadoop plug-in cho Eclipse : hadoop-0. 20.1 – eclipse – plugin.jar  Copy hadoop-0.20.1-eclipse-plugin.jar v { o trong thư mục plug-ins của Eclipse b. C { i đặt MapReduce location Khởi động Eclipse, bạn bấm v { o nút trong vòng đỏ : hadoop @ ubuntu : / usr / local / hadoop USD bin / hadoop jar hadoop-0. 20.2 – examples.jar wordcount – D mapred.reduce.tasks = 16 gutenberg gutenberg-output hadoop @ ubuntu : / usr / local / hadoop USD bin / hadoop dfs – cat gutenberg – output / part-r-00000gutenberg-output Vũ Minh Ngọc 18 Sau đó chọn Other … => MapRecude => OK Kích chuột phải v { o phần trống của Location trong TAB Map / Recude Locations, chọn New Hadoop location … V { điền c | c tham số như hình dưới : Vũ Minh Ngọc 19 Khởi động Hadoop cluster như trên, v { kiểm tra DFS như hình dưới đ } y Vũ Minh Ngọc 20 Phần III. Thành phần của Hadoop 1. Một số thuật ngữ. – MapReduce job l { một đơn vị chức năng của việc làm m { kh | ch h { ng ( client ) muốn được triển khai : nó gồm có tài liệu đầu v { o, chương trình MapReduce, v { thông tin thông số kỹ thuật. Hadoop chạy c | c việc làm ( job ) n { y bằng c | ch chia nó th { nh c | c trách nhiệm ( task ), trong đó có hai kiểu chính l { : c | c trách nhiệm map ( map task ) v { c | c trách nhiệm reduce ( reduce task ) – Có hai loại node điều kiển qu | trình thực thi việc làm ( job ) : một jobtracker v { một số ít tasktracker. Jobtracker tích hợp tổng thể c | c việc làm trên mạng lưới hệ thống bằng c | ch lập lịch việc làm chạy trên c | c tasktracker. Tasktracker chạy c | c trách nhiệm ( task ) v { gửi b | o c | o triển khai cho jobtracker, c | i lưu giữ c | c bản nghi về qu | trình giải quyết và xử lý tổng thể và toàn diện cho mỗi việc làm ( job ) – Hadoop chia đầu v { o cho mỗi việc làm MapReduce v { o c | c mảnh ( piece ) có kích cỡ cố định và thắt chặt gọi l { c | c input split hoặc l { c | c split. Hadoop tạo ra một task map cho mỗi split, c | i chạy mỗi trách nhiệm map do người sử dụng định nghĩa cho mỗi bản ghi ( record ) trong split. – Có rất nhiều c | c split, điều n { y có nghĩa l { thời hạn giải quyết và xử lý mỗi split nhỏ hơn so với thời hạn giải quyết và xử lý to { n bộ đầu v { o. Vì vậy, nếu tất cả chúng ta giải quyết và xử lý c | c split một c | ch song song, thì qu | trình giải quyết và xử lý sẽ tốt hơn c } n bằng tải, nếu c | c split nhỏ, khi đó một chiếc m | y tính nhanh hoàn toàn có thể giải quyết và xử lý tương tự nhiều split trong qu | trình thực thi việc làm hơn l { một m | y tính chậm. Ngay cả khi c | c m | y tính giống hệt nhau, việc giải quyết và xử lý không th { nh công hay c | c việc làm kh | c đang chạy đồng thời l { m cho cần bằng tải như mong ước, v { chất lượng của c } n bằng tải tăng như l { chia c | c splits th { nh c | c hạt mịn hơn – Mặt kh | c, nếu chia t | ch qu | nhỏ, sau đó ngân sách cho việc quản trị c | c split v { của tạo ra c | c map task mở màn chiếm rất nhiều tổng thời hạn của qu | trình giải quyết và xử lý việc làm. Đối với hầu hết việc làm, kích cỡ split tốt nhất thường l { kích cỡ của một block của HDFS, mặc định l { 64MB, mặc dầu nó hoàn toàn có thể biến hóa được cho mỗi cluster ( cho toàn bộ c | c file mới được tạo ra ) hoặc định rõ khi mỗi file được tạo ra. – Hadoop l { m tốt nhất c | c việc làm của nó chạy c | c map task trên một node khi m { tài liệu đầu v { o của nó cư trú ngay trong HDFS. Nó được gọi l { tối ưu hóa dữ liệu địa phương. B } y giờ tất cả chúng ta sẽ l { m rõ tại sao size split tối ưu lại bằng kích cỡ của block : nó l { kích cỡ lớn nhất của một đầu v { o m { hoàn toàn có thể được bảo vệ để được lưu trên một node đơn. Nếu split được chia th { nh 2 block, nó sẽ không chắc l { bất kể node HDFS n { o tàng trữ cả hai block, vì vaayjmootj số split phải được chuyển trên mạng đến node chạy map tast, như vậy rõ r { ng l { sẽ ít hiệu suất cao hơn việc chạy to { n bộ map task sử dụng tài liệu cục bộ. – C | c map task ghi đầu ra của chúng trên đĩa cụ bộ, không phải l { v { o HDFS. Tại sao lại như vậy ? Đầu ra của map l { đầu ra trung gian, nó được giải quyết và xử lý bởi reduce task để tạo ra Vũ Minh Ngọc 21 đầu ra ở đầu cuối, v { một khi việc làm được ho { n th { nh đầu ra của map hoàn toàn có thể được bỏ đi. Vì vậy việc tàng trữ nó trong HDFS, với c | c nh } n bản, l { không thiết yếu. Nếu c | c node chạy maptask bị lỗi trước khi đầu ra map đ ~ được sử dụng bởi một reduce task, khi đó Hadoop sẽ tự động hóa chạy lại map task trên một node kh | c để tạo ra một đầu ra map. – Khi “ chạy Hadoop ” có nghĩa l { chạy một tập c | c trình nền – daemon, hoặc c | c chương trình thường trú, trên c | c m | y chủ kh | c nhau trên mạng của bạn. Những trình nền có vai trò đơn cử, một số ít chỉ sống sót trên một m | y chủ, 1 số ít hoàn toàn có thể sống sót trên nhiều m | y chủ. C | c daemon gồm có : ● NameNode ● DataNode ● SecondaryNameNode ● JobTracker ● TaskTracker 2. Các trình nền của Hadoop 2.1. NameNode L { một trình nền quan trọng nhất của Hadoop – c | c NameNode. Hadoop sử dụng một kiển trúc master / slave cho cả tàng trữ ph } n t | n v { giải quyết và xử lý ph } n t | n. Hệ thống tàng trữ ph } n t | n được gọi l { Hadoop File System hay HDFS. NameNode l { master của HDFS để chỉ huy c | c trình nền DataNode slave để thực thi c | c trách nhiệm I / O mức thấp. NadeNode l { nh } n viên kế to | n của HDFS ; nó theo dõi c | ch c | c tập tin của bạn được ph } n kia th { nh c | c block, những node n { o lưu c | c khối đó, v { “ kiểm tra sức khỏe thể chất ” toàn diện và tổng thể của mạng lưới hệ thống tệp ph } n t | n. Chức năng của NameNode l { nhớ ( memory ) v { I / O chuyên s } u. Như vậy, m | y chủ lư trữ NameNode thường không tàng trữ bất kỳ tài liệu người dùng hoặc triển khai bất kỳ một tính to | n n { o cho một ứng dụng MapReduce để giảm khổi lượng việc làm trên m | y. Điều n { y có nghĩa l { m | y chủ NameNode không gấp đôi ( double ) như l { DataNode hay một TaskTracker. Có điều đ | ng tiếc l { có một góc nhìn xấu đi đến tầm quan trọng của NameNode nó có một điểm của thất bại của một cụm Hadoop của bạn. Đối với bất kể một trình nền kh | c, nếu c | c nút m | y của chúng bị hỏng vì nguyên do ứng dụng hay phần cứng, c | c Hadoop cluster hoàn toàn có thể liên tục hoạt động giải trí thông suốt hoặc bạn hoàn toàn có thể khởi động nó một c | ch nhanh gọn. Nhưng không hề | p dụng cho c | c NameNode. 2.2. DataNode Mỗi m | y slave trong cluster của bạn sẽ tàng trữ ( host ) một trình nền DataNode để thực thi c | c việc làm n { o đó của mạng lưới hệ thống file ph } n t | n – đọc v { ghi c | c khối HDFS Vũ Minh Ngọc 22 tới c | c file trong thực tiễn trên mạng lưới hệ thống file cục bộ ( local filesytem ). Khi bạn muốn đọc hay ghi một file HDFS, file đó được chia nhỏ th { nh c | c khối v { NameNode sẽ nói cho c | c client của bạn nơi c | c mỗi khối trình nền DataNode sẽ nằm trong đó. Client của bạn liên lạc trực tiếp với c | c trình nền DataNode để giải quyết và xử lý c | c file cục bộ tương ứng với c | c block. Hơn nữa, một DataNode hoàn toàn có thể tiếp xúc với c | c DataNode kh | c để nh } n bản c | c khối tài liệu của nó để dự trữ. Hình 2.1 minh họa vai trò của NameNode v { DataNode. Trong c | c số liệu n { y chỉ ra 2 file tài liệu, một c | i ở / user / chuck / data1 v { một c | i kh | c ở / user / james / data2. File Data1 chiếm 3 khối, m { được trình diễn l { 1 2 3. V { file Data2 gồm c | c khối 4 v { 5. Nội dung của c | c file được ph } n t | n trong c | c DataNode. Trong minh họa n { y, mỗi block có 3 nh } n bản. Cho ví dụ, lock 1 ( sử dụng ở data1 ) l { được nh } n bản hơn 3 lần trên hầu hết c | c DataNodes. Điều n { y bảo vệ rằng nếu có một DataNode gặp tai nạn thương tâm hoặc không hề truy vấn qua mạng được, bạn vẫn hoàn toàn có thể đọc được c | c tệp tin. C | c DataNode liên tục b | o c | o với c | c NameNode. Sa khi khởi tạo, mỗi DataNode thông b | o với NameNode của c | c khối m { nó hiện đang tàng trữ. Sau khi Mapping ho { n th { nh, c | c DataNode liên tục thăm dò ý kiến NameNode để cung ứng thông tin về đổi khác cục bộ cũng như nhận được hướng dẫn để tạo, chuyển dời hoặc xóa c | c blocks từ đĩa địa phương ( local ). 2.3. Secondary NameNode C | c Secondary NameNode ( SNN ) l { một trình nền tương hỗ gi | m s | t trạng th | i của c | c cụm HDFS. Giống như NameNode, mỗi cụm có một SNN, v { nó thường trú trên một m | y của mình. Không có c | c trình nền DataNode hay TaskTracker chạy trên cùng một server. SNN kh | c với NameNode trong qu | trình giải quyết và xử lý của nó không nhận hoặc ghi lại bất kể đổi khác thời hạn thực tới HDFS. Thay v { o đó, nó tiếp xúc với c | c NameNode bằng c | ch chụp những bức ảnh của siêu dữ liệu HDFS ( HDFS metadata ) tại nhưng khoảng chừng x | c định bởi thông số kỹ thuật của c | c cluster. Như đ ~ đề cập trước đó, NameNode l { một điểm truy vấn duy nhất của lỗi ( failure ) cho một cụm Hadoop, v { c | c bức ảnh chụp SNN giúp giảm thiểu thời hạn ngừng ( downtime ) v { mất tài liệu. Tuy nhiên, một NameNode không yên cầu sự can thiệp của con người để thông số kỹ thuật lại c | c cluster sẻ dụng SSN như l { NameNode chính. 2.4. JobTracker Trình nền JobTracker l { một liên lạc giữa ứng dụng của bạn { Hadoop. Một khi bạn gửi m ~ nguồn của bạn tới c | c cụm ( cluster ), JobTracker sẽ quyết định hành động kế hoạch triển khai bằng c | ch x | c định những tập tin n { o sẽ giải quyết và xử lý, c | c nút được giao c | c trách nhiệm kh | c nhau, v { theo dõi tổng thể c | c trách nhiệm khi dúng đang chạy. Nếu một trách nhiệm ( task ) thất bại ( fail ), JobTracker sẽ tự động hóa chạy lại trách nhiệm đó, hoàn toàn có thể trên một node kh | c, cho đến một số lượng giới hạn n { o đó được định sẵn của việc thử lại n { y. Vũ Minh Ngọc 23 Chỉ có một JobTracker trên một cụm Hadoop. Nó thường chạy trên một m | y chủ như l { một nút master của cluster. 2.5. TaskTracker Như với c | c trình nền tàng trữ, c | c trình nền tính to | n cũng phải tu } n theo kiến trúc master / slave : JobTracker l { gi | m s | t tổng việc thực thi chung của một việc làm MapRecude v { c | c taskTracker quản trị việc triển khai c | c trách nhiệm riêng trên mỗi node slave. Hình 2.2 minh họa tương t | c n { y. Mỗi TaskTracker chịu tr | ch nhiệm triển khai c | c task riêng m { c | c JobTracker giao cho. Mặc dù có một TaskTracker duy nhất cho một node slave, mỗi TaskTracker hoàn toàn có thể sinh ra nhiều JVM để giải quyết và xử lý c | c trách nhiệm Map hoặc Reduce song song. Một trong những tr | ch nhiệm của c | c TaskTracker l { liên tục liên lạc với JobTracker. NeeusJobTracker không nhận được nhịp đập từ mootjTaskTracker trong vòng một lượng thời hạn đ ~ lao lý, nó sẽ cho rằng TaskTracker đ ~ bị treo ( cashed ) v { sẽ gửi lại trách nhiệm tương ứng cho c | c nút kh | c trong cluster. Hình 2.2 Tương tác giữa JobTracker và TaskTracker. Sau khi client gọi JobTracker mở màn việc làm giải quyết và xử lý tài liệu, các phân vùng JobTracker thao tác và giao các trách nhiệm Map và Recude khác nhau cho mỗi TaskTracker trong cluster. Vũ Minh Ngọc 24 Hình 2.3 Cấu trúc link của một nhóm Hadoop nổi bật. Đó là một kiến trúc master / slave trong đó NameNode và JobTracker là Master và DataNode và TaskTracker là slave. Cấu trúc link n { y có một node Master l { trình nền NameNode v { JobTracker v { một node đơn với SNN trong trường hợp node Master bị lỗi. Đối với c | c cụm nhở, thì SNN hoàn toàn có thể thường chú trong một node slave. Mặt kh | c, so với c | c cụm lớn, ph } n t | ch NameNode v { JobTracker th { nh hai m | y riêng. C | c m | y slave, mỗi m | y chỉ tàng trữ một DataNode v { Tasktracker, để chạy c | c trách nhiệm trên cùng một node nơi lưu dữ liệu của chúng. Chúng tôi sẽ thiết lập một cluster Hadoop khá đầy đủ với mẫu như trên bằng c | ch tiên phong thiết lập c | c nút Master v { kiếm so | t kênh giữa c | c node. Nếu một cluster Hadoop của bạn đ ~ có sẵn, bạn có thẻ nhay qua phần c { i đặt kênh Secure Shell ( SSH ) giữa c | c node. Bạn cũng có một v { i lựa chọn để chạy Hadoop l { sử dụng trên Một m | y đơn, hoặc chính sách giả ph } n t | n. Chúng sẽ hữu dụng để ph | t triển. Cấu hình Haddop để chạy trong hai node hoặc c | c cluster chuẩn ( chế độ ph } n t | n không thiếu ) được đề cập trong chương 2.3 Vũ Minh Ngọc 25 Phần IV. Lập trình MapReduce cơ bản 1. Tổng quan một chương trình MapReduce Như tất cả chúng ta đã biết, một chương trình MapReuduce giải quyết và xử lý tài liệu bằng cách tao thác với các cặp ( key / value ) theo công thức chung : map : ( K1, V1 ) ➞ list ( K2, V2 ) reduce : ( K2, list ( V2 ) ) ➞ list ( K3, V3 ) Trong phần này tất cả chúng ta học cụ thể hơn về từng tiến trình trong chương trình MapReduce nổi bật. Hình 3.1 trình diễn biểu đồ hạng sang của hàng loạt quy trình, và chúng tôi liên tục mỏ xẻ từng phần : Vũ Minh Ngọc 26 2. Các loại tài liệu mà Hadoop tương hỗ MapReduce framework có một các định nghĩa cặp khóa key / value tuần tự để hoàn toàn có thể chuyển dời chúng qua mạng, và chỉ các lớp tương hỗ kiểu tuần tự có chúng năm giống như key và value trong framework. Cụ thể hơn, các lớp mà implement giao diện Writable hoàn toàn có thể làm value, và các lớp mà implement giao diện WritableComparable hoàn toàn có thể làm cả key và value. Lưu ý rằng giao diện WritableComparable là một sự phối hợp của Writeable và giao diện java.lang. Comparable. Chúng ta cần nhu yếu so sánh các khóa chính bới chúng sẽ được sắp xếp ở quy trình tiến độ reduce, trong khi giá trị thì đơn thuần được cho qua. Hadoop đi kèm một số ít lớp được định nghĩa trước mà implement WritableComparable, gồm có các lớp bọ cho tát cả các loại tài liệu cơ bản như trong bảng 3.1 sau : Bạn cũng hoàn toàn có thể tùy chỉnh một kiểu tài liệu bằng cách implement Writable ( hay WritableComparable ). Như ví dụ 3.2 sau, lớp trình diễn các cạnh trong mạng, như đường bay giữa hai thành phố : Vũ Minh Ngọc 27 import java.io. DataInput ; import java.io. DataOutput ; import java.io. IOException ; import org.apache.hadoop.io. WritableComparable ; public class Edge implements WritableComparable { private String departureNode ; / / Node khoi hanh hao private String arrivalNode ; / / Node den public String getDepartureNode ( ) { return departureNode ; } @ Override public void readFields ( DataInput in ) throws IOException { / / TODO Auto-generated method stub departureNode = in. readUTF ( ) ; arrivalNode = in. readUTF ( ) ; } @ Override public void write ( DataOutput out ) throws IOException { / / TODO Auto-generated method stub out. writeUTF ( departureNode ) ; out. writeUTF ( arrivalNode ) ; } @ Override public int compareTo ( Edge o ) { / / TODO Auto-generated method stub return ( departureNode. compareTo ( o. departureNode ) ! = 0 ) ? departureNode. compareTo ( departureNode ) : arrivalNode. compareTo ( o. arrivalNode ) ; } } Lớp Edge thực thi hai phương pháp readFields ( ) và write ( ) của giao diện Writeable. Chúng thao tác với lớp Java DataInput và DataOutput để tuần tự nội dung của các lớp. Thự hiện chiêu thức compareTo ( ) cho interface Comparable. Nó trả lại giá trị – 1, 0, + 1. Với kiểu tài liệu được định nghĩa tại giao diện, tất cả chúng ta hoàn toàn có thể triển khai quá trình tiên phong của giải quyết và xử lý luồng tài liệu như trong hình 3.1 : mapper. 2.1. Mapper Để phục làm một Mapper, một lớp implements từ interface Mapper và thừa kế từ lớp MapReduceBase. Lớp MapReduceBase, đóng vai trò là lớp cơ sở cho cả mapper và reducer. Nó Vũ Minh Ngọc 28 gồm có hai phương pháp hoạt động giải trí hiệu suất cao như là hàm khởi tạo và hàm hủy của lớp : – void configure ( JobConf job ) – trong hàm nay, bạn hoàn toàn có thể trích xuất các thông số kỹ thuật setup hoặc bằng các file XML thông số kỹ thuật hoặc trong các lớp chính của ứng dụng của bạn. Gọi cái hàm này trước khi giải quyết và xử lý tài liệu. – void close ( ) – Như hành vi cuối trước khi chấm hết trách nhiệm map, hàm này nên được gọi bất kể khi nào kết thúc – liên kết cơ sở tài liệu, các file đang mở. Giao diện Mapper chịu nghĩa vụ và trách nhiệm cho bước giải quyết và xử lý tài liệu. Nó sử dụng Java Generics của mẫu Mapper chỗ mà các lớp key và các lớp value mà implements từ interface WriteableComparable và Writable. Phương pháp duy nhất của nó để giải quyết và xử lý các cặp ( key / value ) như sau : void map ( K1 key, V1 value, OutputCollector output, Reporter reporter ) throws IOException Phương thức này tạo ra một list ( hoàn toàn có thể rỗng ) các cặp ( K2, V2 ) từ một cặp nguồn vào ( K1, V1 ). OuputCollector nhận hiệu quả từ đầu ra của quy trình mapping, và Reporter phân phối các tùy chọn để ghi lại thông tin thêm về mapper như tiến triển việc làm. Hadoop cung cấu một vài setup Mapper hữu dụng. Bạn hoàn toàn có thể thấy một vài cái như trong bản 3.2 sau : Bảng 3.2. Một vài lớp thực thi Mapper được định nghĩa trước bởi Hadoop – IdentityMapper : với setup Mapper và ánh xạ đầu vào trực tiếp vào đầu ra – InverseMapper : với setup Mapper và đảo ngược cặp ( K / V ) – RegexMapper : với cài đặ Mapper và sinh ra cặp ( match, 1 ) cho mỗi ánh xạ ( match ) biểu thức liên tục. – TokenCountMapper : với thiết lập Mapper sinh ra một cặp ( token, 1 ) khi một giá trị nguồn vào là tokenized. 2.2. Reducer Với bất kỳ thiết lập Mapper, một reducer tiên phong phải lan rộng ra từ lớp MapReduce base để cho phép thông số kỹ thuật và quét dọn. Ngoài ra, nó cũng phải implement giao diện Reducer chỉ có một phương pháp duy nhất sau : void reduce ( K2 key, Iterator values, OutputCollector output, Reporter reporter ) throws IOException Khi nhận được các task từ đầu ra của các Mapper khác nhau, nó sắp xếp các tài liệu đến theo các khóa của các cặp ( key / value ) và nhóm lại các giá trị cùng khóa. Hàm reduce ( ) được gọi sau đó, nó sinh ra một list ( hoàn toàn có thể rỗng ) các cặp ( K3, V3 ) bằng cách tái diễn trên các giá trị Vũ Minh Ngọc 29 được link với khóa đã cho. OutputCollector nhận từ đầu ra của quy trình reduce và ghi nó ra đầu ra file. Reporter cung ứng tùy chọn ghi lại thông tin thêm về reducer như thể một tiến triển việc làm. Bảng 3.3 liệt kê một vài reducer cơ bản được tiến hành phân phối bởi Hadoop – IdentityReducer : với setup Reducer và ánh xạ đầu vào trực tiếp vào đầu ra – LongSumReducer : với cài đạt Reducer và quyết định hành động thổng hợp toàn bộ các giá trị tương tứng với các key đã cho Có một bước quan trọng giữa 2 bước map và reduce : chỉ huy hiệu quả của các Mapper tới các Reducer. Đây là nghĩa vụ và trách nhiệm của partitioner ( phân vùng ). 2.3. Partitioner – chuyển hướng đầu ra từ Mapper Với nhiều reducer, tất cả chúng ta cần một vài cách để xác lập một trong những cặp ( key / value ) là đầu ra của một mapper được gửi đi. Hành vi mặc định là băm key để xác lập reducer. Hadoop thực thi kiến lược này bằng cách sử dụng lớp HashPartitioner. Thỉnh thoáng lớp này sẽ thao tác hiệu suất cao. Trở lại ví dụ Edge như trong phần 3.2.1. Giả sử bạn sử dụng lớp Edge để nghiên cứu và phân tích tài liệu thông tin chuyến bay để xác lập số lượng hành khác khởi hành từ mỗi trường bay. Ví dụ như tài liệu sau : ( San Francisco, Los Angeles ) Chuck Lam ( San Francisco, Dallas ) James Warren … Nếu bạn sử dụng HashPartitioner, hai dòng sẽ được gửi tới 2 reducer khác nhau. Số các điểm khới hành sẽ được giải quyết và xử lý 2 lần và cả hai lần đều sai. Làm thế nào tất cả chúng ta hoàn toàn có thể tùy chỉnh Partitioner cho ứng dụng của bạn ? Trong tinh hình này, tất cả chúng ta muốn toàn bộ các đường bay với một điểm khởi hành sẽ được gửi tới cùng một reducer. Điều này được dễ làm bằng cách băm departureNode của Edge : public class EdgePartitioner implements Partitioner { @ Override public int getPartition ( Edge key, Writable value, int numPartitions ) { return key. getDepartureNode ( ). hashCode ( ) % numPartitions ; } @ Override public void configure ( JobConf conf ) { } } Vũ Minh Ngọc 30 Phần V. Sơ lược về các thuật toán tin sinh 5.1. Thuật toán Blast Ý tưởng của BLAST dựa trên cơ sở x | c suất rằng những chuỗi bắt cặp trình tự ( alignment ) thường chiếm hữu nhiều đoạn chuỗi con có tính tựa như cao. Những chuỗi con n { y được lan rộng ra để tăng tính tương tự như trong qu | trình tìm kiếm. Thuật to | n của BLAST có 2 phần, một phần tìm kiếm v { một phần đ | nh gi | thống kê dựa trên tác dụng tìm được. Thuật to | n tìm kiếm của BLAST gồm có 3 bước sau : Bước 1 : BLAST tìm kiếm c | c chuỗi con ngắn với chiều d { i cố định và thắt chặt W có tính tương tự như cao ( không được cho phép khoảng trống gaps ) giữa chuỗi truy vấn v { c | c chuỗi trong cơ sở tài liệu. Những chuỗi con với chiều d { i W được BLAST gọi l { một từ ( word ). Gi | trị W tìm hiểu thêm cho Protein l { 3 v { DNA l { 11. Những chuỗi con n { y được đ | nh gi | cho điểm dựa trên ma trận thay thế sửa chữa ( Substitutionsmatrix ) BLOSUM hoặc PAM, những chuỗi con n { o có số điểm lớn hơn một gi | trị ngưỡng T ( threshold value ) thì được gọi l { tìm thấy v { được BLAST gọi l { Hits. Ví dụ, khi cho sẵn c | c chuỗi AGTTAH v { ACFTAQ v { một từ có chiều d { i W = 3, BLAST sẽ x | c định chuỗi con TAH v { TAQ với số điểm theo ma trận PAM l { 3 + 2 + 3 = 8 v { gọi chúng l { một Hit. Bước 2 : BLAST liên tục tìm kiếp những cặp Hits tiếp theo dựa trên cơ sở những Hit đ ~ tìm được trong bước 1. Những cặp Hits n { y được BLAST số lượng giới hạn bởi một gi | trị cho trước d, gọi l { khoảng chừng c | ch giữa những Hits. Những cặp Hits có khoảng chừng c | ch lớn hơn d sẽ bị BLAST bỏ lỡ. Gi | trị d phụ thuộc vào v { o độ d { i W ở bước 1, ví dụ nếu W = 2 thì gi | trị d ý kiến đề nghị l { d = 16. Bước 3 : Cuối cùng
Các file đính kèm theo tài liệu này :

  • pdfTH055.pdf
Rate this post
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments