Luận văn Thạc sĩ Khoa học máy tính: Thuật toán đánh chỉ mục ngược với MapReduce và ứng dung trong việc ̣ đánh giá ý kiến của học sinh Hòa Bình trên mạng xã hội

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Lê Đinh Hợp

Thuâ ̣t toá n đánh chỉ mục ngược với MapReduce và ứ ng du ̣ng trong việc đánh giá ý kiến của học sinh Hòa Bình trên mạng xã hội

Chuyên ngành:

Khoa học máy tính

Mã số

:

60 48 01 01

Người hướng dẫn khoa học: PGS TS Đỗ Trung Tuấn

Thái Nguyên, 12 - 2016

Lời cam đoan

Tôi xin cam đoan:

Những kết quả nghiên cứu được trình bày trong luận văn là hoàn toàn trung thực, của tôi, không vi phạm bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật Việt Nam. Nếu sai, tôi hoàn toàn chịu trách nhiệm trước pháp luật.

TÁC GIẢ LUẬN VĂN

Lê Đinh Hợp

Lời cám ơn

Tôi xin chân thành cảm ơn Trường Đại học Công nghệ thông tin và Truyền

thông - Đại học Thái Nguyên đã tạo điều kiện thuận lợi cho tôi hoàn thành khóa học này.

Tôi xin chân thành cảm ơn các Thầy Cô giáo – Các nhà khoa học đã trực tiếp giảng dạy truyền đạt những kiến thức chuyên ngành Khoa học máy tính cho tôi trong những tháng năm học tập tại trường.

Đặc biệt tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới PGS TS Đỗ Trung Tuấn đã tận tình hướng dẫn, dìu dắt và chỉ bảo cho tôi những kiến thức về chuyên môn thiết thực và những chỉ dẫn khoa học quý báu để tôi hoàn thành bản luận văn này.

Luận văn này còn nhiều thiếu sót, rất mong được các thầy cô giáo trong hội

đồng chấm luận văn xem xét, góp ý kiến để luận văn được hoàn thiện hơn.

Tôi xin chân thành cảm ơn!

Thái Nguyên, tháng 12 năm 2016

iii

Mục lục

Lời cam đoan .........................................................................................................i

Lời cám ơn .......................................................................................................... iii

Mục lục ................................................................................................................iv

Danh sách các từ viết tắt ......................................................................................vi

Danh mục các hình vẽ, bảng biểu ...................................................................... vii

Chương mở đầu .................................................................................................... 9

Đặt vấn đề ..................................................................................................... 9

Đối tượng và phạm vi nghiên cứu .............................................................. 11

Hướng thực hiện đề tài ............................................................................... 11

Những nội dung nghiên cứu chính ............................................................. 11

CHƯƠNG 1 MÔ HÌNH MapReduce ................................................................. 12

1.1. Tổng quan về MapReduce ........................................................................... 12

1.1.1. Sự quan trọng của MapReduce ......................................................... 12

1.1.2. Các ý tưởng của MapReduce ........................................................... 13

1.1.3. Cấu trúc dữ liệu trong MapReduce .................................................. 15

1.1.4. Mapper và Reducer .......................................................................... 15

1.1.5. Partitioner và Combiner ................................................................... 17

1.2. Bộ khung thực thi ........................................................................................ 19

1.2.1. Lập lịch ............................................................................................. 19

1.2.2. Di chuyển dữ liệu và mã lệnh ........................................................... 19

1.2.3. Đồng bộ hóa ..................................................................................... 20

1.2.4. Xử lý lỗi ............................................................................................ 20

1.3. Hệ thống file phân tán .................................................................................. 20

1.3.1. Kiến trúc của HDFS ......................................................................... 21

1.3.2. Nhiệm vụ của NameNode ................................................................ 21

1.3.3. Nhiệm vụ của DataNode .................................................................. 22

1.3.4. Nhiệm vụ của Secondary NameNode .............................................. 23

CHƯƠNG 2THUẬT TOÁN XỬ LÝ DỮ LIỆU VĂN BẢN VỚI MapReduce 25

2.1. Thiết kế thuật toán MapReduce cơ bản ....................................................... 25

2.1.1. Gộp lớn cục bộ ................................................................................. 26

2.1.2. Bộ hai và bộ ba ................................................................................. 30

2.1.3. Tính toán tần số tương đối .................................................................. 33

2.1.4. Sắp xếp thứ cấp ................................................................................ 36

2.2 Thuật toán tính chỉ mục ngược để tìm kiếm dữ liệu văn bản ....................... 36

2.2.1. Dò tìm Web ...................................................................................... 37

2.2.2 Thuật toán chỉ mục ngược ................................................................. 39

2.2.3. Cài đặt theo cơ bản ........................................................................... 41

2.2.4. Cài đặt thuật toán cải tiến ................................................................. 43

2.2.5. Nén chỉ mục ...................................................................................... 45

2.3. Về tìm kiếm ................................................................................................. 52

CHƯƠNG 3 THỬ NGHIỆM THUẬT TOÁN ĐÁNH GIÁ Ý KIẾN TRÊN MẠNG XÃ HỘI ............................................................................................................ 56

3.1 Mã nguồn mở Solr ........................................................................................ 56

3.1.1. Giới thiệu .......................................................................................... 56

3.1.2. Các tính năng chính của Solr: .......................................................... 56

3.2 Mã nguồn mở Nutch ..................................................................................... 56

3.2.1. Các lý do để tự xây dựng một Search Engine .................................. 56

3.2.2. Các tính năng chính của Nutch ........................................................ 57

3.3. API biểu đồ Facebook ................................................................................. 58

3.4. Solr trên Hadoop và tìm kiếm thử nghiệm .................................................. 60

3.4.1. Sơ đồ ................................................................................................. 60

3.4.1. Cài đặt cụm máy Hadoop ................................................................. 62

3.4.2. Cài đặt Nutch tích hợp với Solr ........................................................ 67

3.4.3. Thu thập dữ liệu ............................................................................... 69

3.5. Thực hiện tìm kiếm thử nghiệm trên tập chỉ mục đã thu thập được. .......... 72

Kết luận .............................................................................................................. 75

Danh sách các từ viết tắt

Công nghệ Thông tin CNTT

Hadoop Distributed File System HDFS

Uniform Resource Locator URL

HyperText Markup Language HTML

LISt Processing LISP

Markup Language ML

High-Performance Computing HPC

Network-Attach Storage NAS

Storage Area Network SAN

Google File System GFS

Single Point Of Failure SPOF

Secondary NameNode SNN

Associated Press Wordstream APW

Representational State Transfer REST

Parallel Random Access Machine PRAM

Bulk Synchronous Parallel BSP

Danh mục các hình vẽ, bảng biểu

Hình 1.1. Mô hình chia để trị ............................................................................. 14

Hình 1.2. Hàm Map và Fold trong Functional Programming ............................ 15

Hình 1.3. Hai pha Map và Reduce của một MapReduce job ............................. 16

Hình 1.4. Mô hình MapReduce đầy đủ các thành phần ..................................... 19

Hình 1.5. Kiến trúc của HDFS ........................................................................... 21

Hình 1.6. Vai trò của NameNode và DataNode trong HDFS ............................ 23

Hình 1.7. Kiến trúc HDFS đầy đủ ...................................................................... 23

Hình 2.1. Bảo toàn trạng thái trong Hadoop ...................................................... 26

Hình 2.2. Tiến trình hoạt động của chương trình WordCount ........................... 27

Hình 2.3. Thời gian chạy của thuật toán "pairs" và "stripes" ............................. 32

Hình 2.4. Ví dụ minh họa cặp giá trị .................................................................. 35

Hình 2.5. Minh họa đơn giản của một chỉ mục ngược. ...................................... 40

Hình 2.6: Minh họa đơn giản cơ sở thuật toán lập chỉ mục ngược trong MapReduce với ba mapper và hai reducer .................................................................... 43

Hình 2.7. Mười số nguyên dương đầu tiên trong nguyên phân, γ, và mã Golomb (b = 5, 10) ...................................................................................................................... 49

Hình 2.8. Ma trận Term-document ..................................................................... 53

Hình 3.1. Sơ đồ hoạt động của Nutch khi sử dụng như một Crawler ................ 57

Hình 3.2. Sơ đồ đầy đủ của Nutch khi sử dụng như một Search Engine ........... 58

Hình 3.3. Facebook ............................................................................................ 58

Hình 3.4. Trao đổi qua API ................................................................................ 59

Hình 3.5: Mô hình tổng quan của hệ thống khảo sát .......................................... 60

Hình 3.6: Sơ đồ giai đoạn đánh chỉ mục ............................................................ 61

Hình 3.7: đánh chỉ mục với MapRedece trên Solr ............................................. 61

Hình 3.8: Giao diện làm việc của Solr ............................................................... 68

Hình 3.9: Giao diện làm việc của Facebook Graph API .................................... 69

Hình 3.10: Access Token của một trình Facebook Graph API .......................... 70

vii

Hình 3.11: Thu thập dữ liệu từ trang mạng của trường THPT Hoàng Văn Thụ 70

Hình 3.12:Giao diên theo dõi quá trình làm việc của MapReduce .................... 71

Bảng 3.2: Kết quả thu thập dữ liệu ở 2 chế độ ................................................... 72

Hình 3.13: Giao diện trang web tìm kiếm trên Solr ........................................... 73

Bảng 3.3: Một số kết quả truy vấn theo chủ đề .................................................. 73

viii

Chương mở đầu

Đặt vấn đề

Trong thời đại hiện nay, công nghệ thông tin được ứng dụng tại mọi lĩnh vực trong cuộc sống, với một hệ thống máy tính người ta có thể làm được rất nhiều công việc, tiết kiệm được thời gian, công sức và tiền bạc. Với sự phát triển vượt bậc của Internet hiện nay, lượng thông tin ngày càng nhiều, sự tăng trưởng có thể nói là được tính bằng cấp số nhân, theo một nghiên cứu thì cứ khoảng 5 năm thì lượng tri thức của nhân loại sẽ tăng gấp đôi, với lượng thông tin đồ sộ trên mạng hiện nay thì việc tìm kiếm và khai thác thông tin là một công việc hết sức quan trọng, mang lại nhiều lợi ích về khoa học và kinh tế.

Cùng với sự ra đời của Internet, sự xuất hiện và phát triển không ngừng của lĩnh vực thương mại điện tử, các lĩnh vực nghiên cứu xã hội khiến cho việc xúc tiến các hoạt động kinh doanh hoặc nghiên cứu, quảng bá sản phẩm dịch vụ diễn ra trên khắp các kênh thông tin xã hội, đặc biêt là trên Internet.

Như chúng ta đã biết ngày nay mọi thông tin đều được đưa lên các trang mạng xã hội dưới dạng các Posts và rất nhiều người dùng để lại các nhận xét (comments) về các thông tin được đưa lên, ta thấy đó chính là một kho thông tin vô cùng hưu ích, nếu ta có thể tìm kiếm và phân loại dữ liệu ấy, chúng ta có thể thu được các kết quả khảo sát cần thiết phục vụ cho các hoạt động nghiên cứu hoặc các hoạt động sản xuất kinh doanh. Kết quả khảo sát ấy có thể là những tỉ lệ như "thích" (like) hay là không có ý kiến gì đối với một vấn đề được đưa ra. Việc tìm kiếm và xử lý và tổng hợp các thông tin hưu ích đó cần phải có một mô hình đáp ứng được nhu cầu về việc có thể làm việc trên một lượng dữ liệu lớn và tốc độ cao.

Mô hình MapReduce là một mô hình lập trình giúp các ứng dụng có thể xử lý nhanh hơn một lượng dữ liệu lớn dữ liệu trện các máy phần tán song song, độc lập với nhau từ đó giúp rút ngắn thời gian xử lý toàn bộ dữ liệu. MapReduce có thể chạy trên các phần cứng thông thường (commodity hardware), không đòi hỏi các server chạy MapReduce phải là các máy tính có cấu hình đặc biết mạnh mẽ. Do vậy chi phí triển khai Mapreduce sẽ rẻ hơn.

MapReduce làm đơn giản hóa các giải thuật tính toán phân tán. Với MapReduce, bạn chỉ cần cung cấp hai hàm Map và Reduce cùng với một số thành phần xử lý dữ liệu đầu vào. Do vậy, các nhà phát triển ứng dụng phần tán có thể tập trung nhiều hơn cho phần logic của úng dụng, bỏ qua các chi tiết phức

tạp của việc phân tán xử lý. Sự ra đời của MapReduce đã mở ra cho các doanh nghiện và các trung tâm nhiên cứu cơ hội xử lý các nguồn dữ liệu đồ sộ với chi phí thấp và thời gian nhanh hơn. Hiện nay, đã có nhiều công ty lớn triển khai sử dụng mô hình MapReduce trong việc kinh doanh và khảo sát.

Công ty Amazon sử dụng MapReduce để xử lý các file log trong quá

trình mua hàng của khách hàng để dự đoán được xu hướng mua hàng...

Facebook có thể xử lý được khối lượng hơn 10 tỷ hình ảnh mà hộ đang lưu trữ để thu thập các thông tin về hình ảnh, và thu thập 15 terabyte dữ liệu mỗi ngày vào một kho dữ liệu quy mô Petabyte để thực hiện việc khảo sát và đánh giá xu hướng người dùng.

Việc nghiên cứu về xu hướng, đánh giá khảo sát một vấn đề trên quy mô lớn luôn là 1 vấn đề gặp nhiều khó khăn. Trước đây các nhà khảo sát, đánh giá ý kiến trên các đối tượng nghiên cứu thường sử dụng phương pháp thủ công rất tốn kém và mất rất nhiều thời gian để tổng hợp tin tức, chẳng hạn như muốn khảo sát ý kiến của học sinh đối với một số thay đổi trong chương trình học, người ta không thể lựa chọn hỏi ý kiến của tất cả các học sinh mà chỉ có thể lựa chọn một số địa điểm đặc trưng để thực hiện khảo sát, và đôi khi, kết quả của những khảo sát này không mang được tính khách quan vì tâm lý e ngại của các em học sinh. Và những cuộc khảo sát này, đôi khi phải thực hiện trong vòng một vài năm mới có thể có kết quả tổng hợp. Như vậy là mất rất nhiều công sức, của cải và thời gian. Với việc thực trạng hiện nay hầu hết rất cả các em trong lứa tuổi học sinh, sinh viên đều biết sử dụng và thích tham gia các mạng xã hội trên Internet ( đặc biết là Facebook) thì việc tìm kiếm một từ khóa có tần suất xuất hiện cao sẽ phản ánh được những xu hướng, những ý kiến của người dùng hơn là việc khảo sát thủ công rất nhiều và việc nhận về những kết quả khảo sát ý kiến. Tổng hợp các thông tin trên máy tính với sự hỗ trợ của mô hình MapReduce sẽ giúp chúng ta có thể thực hiện quá trình đánh giá, khảo sát ý kiến hết sức nhanh chóng và mang lại hiệu quả, cũng như tiết kiệm được rất nhiều thời gian và tiền bạc.

Với những nhu cầu cấp thiết trên, học viên thực hiện nghiên cứu kỹ thuật chỉ mục ngược (Inverted Indexing) đó là phương pháp thực hiện quét một lần trên văn bản sau đó lập danh sách các thuật ngữ (từ, cụm từ) trong file đó và bao gồm cả những thông tin đi kèm với mỗi thuật ngữ (term) ( vị trí, tần suất, độ quan trọng...). Các thông tin này sẽ được tổ chức theo một cấu trúc dữ liệu riêng và được gọi là chỉ mục. Với phương pháp đánh chỉ mục ngược kết hợp với mô hình MapReduce sẽ giải quyết được những hạn chế trước đây trong phương pháp thông kê, đánh giá ý kiến trên một quy mô lớn, và đó là lý do học viên lựa chọn

đề tài "Thuật toá n đánh chỉ mục ngược với MapReduce và ứ ng dụng trong việc đánh giá ý kiến của học sinh Hòa Bình trên mạng xã hội".

Đối tượng và phạm vi nghiên cứu

Luận văn tập trung nghiên cứu vào mô hình MapReduce, cấu trúc và cách thức hoạt động. Từ đó kết hợp với thuật toán đánh chỉ mục và chỉ mục ngược để thực hiện việc tìm kiếm và thống kê kết quả.

Hướng thực hiện đề tài

 Nghiên cứu về mô hình MapReduce

 Nghiên cứu về thuật toán đánh chỉ mục và chỉ mục ngược

 Thực hiện thử nghiệm và cài đặt

Những nội dung nghiên cứu chính

Luận văn được trình bày trong 3 chương. Các nội dung cơ bản của luận

văn được trình bày theo cấu trúc như sau:

1. Chương 1: Tổng quan về MapReduce; Giới thiệu khái niệm về MapReduce, một số các thành phần, mô hình lập trình của MapReduce và hệ thống phân phối tập tin của nó; Trình bày nhu cầu về đánh giá ý kiến trên mạng xã hội và khả năng áp dụng.

2. Chương 2: Thuật toán xử lý dữ liệu văn bản với MapReduce; Trình bày về thiết kế thuật toán MapReduce cơ bản và thuật toán chỉ mục ngược để tìm kiếm văn bản;

3. Chương 3: Thử nghiệm ứng dụng MapReduce và thuật toán đánh chỉ mục ngược để đánh giá ý kiến trên mạng xã hội; Trình bày mô hình hoạt động của ứng dụng đánh giá ý kiến trên mạng xã hội. Các kết quả thử nghiệm của hệ thống tìm kiếm và đánh giá ý kiến trên dữ liệu văn bản có sử dụng MapReduce và thuật toán tính chỉ mục ngược.

CHƯƠNG 1

MÔ HÌNH MapReduce

1.1. Tổng quan về MapReduce

1.1.1. Sự quan trọng của MapReduce

Về tính thiết thực, MapReduce cung cấp một công cụ rất hiệu quả để giải quyết các bài toán dữ liệu lớn. Ngoài ra, MapReduce còn quan trọng trong cách nó đã thay đổi việc sắp xếp tính toán trên quy mô lớn.

Nói một cách công bằng thì MapReduce không phải là mô hình tính toán song song đầu tiên được đưa ra. Mô hình phổ biến nhất trong lý thuyết khoa học máy tính có từ mấy thập kỷ trước là PRAM1 (Parallel Random Access Machine). Trong mô hình này, một lượng lớn các vi xử lý chia sẻ một bộ nhớ lớn không giới hạn, hoạt động đồng thời trên một lượng dữ liệu chia sẻ để tạo ra kết quả. Các mô hình khác như LogP2 và BSP3 (Bulk Synchronous Parallel), tuy nhiên không có mô hình nào có được sự thành công như MapReduce.

1 http://en.wikipedia.org/wiki/Parallel_Random_Access_Machine

2 http://en.wikipedia.org/wiki/LogP_machine

3 http://en.wikipedia.org/wiki/Bulk_Synchronous_Parallel

MapReduce là mức trừu tượng thành công nhất trên các tài nguyên tính toán mở rộng cho đến nay. Tuy nhiên, mức trừu tượng giải quyết sự phức tạp bằng cách che dấu sự chi tiết và đưa ra các hành vi được thiết kế tốt cho ngƣời sử dụng ứng với mức trừu tượng đó. Chính vì thế, mức trừu tượng không thể hoàn hảo, nó làm cho một số công việc dễ hơn, nhưng cũng làm một số công việc khác khó hơn hoặc có khi là không thể thực hiện được. Vấn đề này làm cho việc ứng dụng MapReduce trong một số bài toán cũng có mặt hạn chế. Điều đó có nghĩa MapReduce không phải là mô hình cuối cùng trong lớp mô hình lập trình mới cho phép xử lý tính toán trên quy mô lớn một cách hiệu quả.

1.1.2. Các ý tưởng của MapReduce

Giải quyết các bài toán dữ liệu lớn đòi hỏi cách tiếp cận riêng biệt mà nhiều khi đối lập với mô hình tính toán truyền thống. Dưới đây là các ý tƣởng chính của MapReduce:

Scale “out” not “up” (mở rộng chứ không nâng cấp): Để tăng sức mạnh xử lý thay vì nâng cấp bộ vi xử lý cũng như khả năng lưu trữ của máy tính (mua các server có khả năng xử lý cao – high-end server) giải pháp đưa ra là tăng số lượng các server thông dụng (low-end server). Giải pháp này kinh tế hơn nhiều so vì nó chỉ bổ sung một số máy tính và tận dụng được các server sẵn có trong khi giải pháp nâng cấp có thể dẫn đến việc mua sắm mới lại toàn bộ các server. Hơn nữa giá thành của một server chuyên dụng đắt hơn nhiều so với một cụm máy tính thông thường với khả năng xử lý tương đương.

Assume failures are common (chấp nhận việc xảy ra lỗi là thường xuyên): Với sự gia tăng về số lượng của các server trong một cluster, lỗi xảy ra là điều bình thường. Do đó các dịch vụ phân tán trên nhiều server phải tính toán đến các lỗi về phần cứng cũng như phần mềm thường xuyên xảy ra. Mô hình lập trình MapReduce có khả năng xử lý các lỗi thông qua một số cơ chế như tự động khởi động lại các task trên cluster node khác nhau.

Move processing to the data (đưa xử lý đến dữ liệu): Trong các ứng dụng tính toán hiệu năng cao truyền thống (High – Prefomance Computing - HPC). Thông thường, một siêu máy tính có các nút xử lý (processing node) và các nút lưu trữ (storage node) được kết nối với nhau qua một kết nối tốc độ cao. Nhiều công việc nặng nề về dữ liệu không phải là những đòi hỏi xử lý cao. Do đó việc tách rời việc lưu trữ dữ liệu và tính toán tạo ra sự thắt cổ chai trong mạng. Do đó sẽ hiệu quả hơn nếu chuyển sự thực thi xử lý đến dữ liệu thay vì chuyển dữ liệu đến nơi xử lý chúng. MapReduce sử dụng một kiến trúc trong đó các bộ xử lý và đĩa lưu trữ được đặt cùng với nhau. Trong sự thiết lập như vậy, chúng ta có thể tận dụng lợi thế của dữ liệu cục bộ bằng cách chạy đoạn mã trên bộ xử lý một cách trực tiếp trên khối dữ liệu cần xử lý. Hệ thống tập tin phân tán có nhiệm vụ quản lý dữ liệu mà MapReduce xử lý.

Process data sequentially and avoid random access (xử lý dữ liệu tuần tự và tránh truy cập ngẫu nhiên): Trong trường hợp xử lý một lượng lớn dữ liệu, dung lượng bộ nhớ thường không đủ cho toàn bộ dữ liệu xử lý. Do đó dữ liệu phải được lưu trữ trên đĩa. Thời gian cho việc truy cập ngẫu nhiên thường hạn chế bởi sự di chuyển của đầu đọc cũng như tốc độ đĩa do đó làm chậm công việc xử lý. Để tránh hạn chế này, MapReduce được thiết kế để xử lý các

khối dữ liệu của một tập dữ liệu lớn.

Hide system-level details from the application developer (che giấu mức chi tiết hệ thống đối với nhà phát triển): Để dễ dàng cho các lập trình viên khi viết ứng dụng xử lý phân tán, MapReduce che giấu sự thực thi phức tạp bên dưới. Thay vào đó, MapReduce cung cấp một mô hình lập trình trừu tượng với các interface đơn giản được định nghĩa sẵn.

Phương pháp thường được sử dụng để giải quyết các bài toán dữ liệu lớn hiện nay là chia để trị. Ý tưởng là phân mảnh một bài toán lớn thành các bài toán con nhỏ. Các bài toán nhỏ độc lập với nhau để có thể được giải quyết song song bởi các workers khác nhau – workers có thể là các tiến trình trong bộ vi xử lý hoặc các bộ vi xử lý trong trong bộ vi xử lý đa nhân, các bộ xử lý trên một máy, các máy trên một cụm máy tính. Các kết quả trung gian từ các worker cụ thể sẽ được gộp lại để tạo thành kết quả cuối cùng.

Hình 1.1. Mô hình chia để trị

MapReduce có nguồn gốc từ lập trình hàm (Functional Programming). Ví dụ điển hình như các ngôn ngữ lập trình Lisp và ML. Tính năng chính của lập trình hàm là khái niệm về các hàm bậc cao (higher-order functions), hoặc các hàm chấp nhận tham số của nó là một hàm. Hai hàm bậc cao thường được xây dựng sẵn là Map và Fold.

Như hình dưới, cho một danh sách, Map lấy tham số là một hàm f (có 1 tham số) và áp dụng cho toàn bộ phần tử trong danh sách. Cho một danh sách, Fold lấy tham số là một hàm g (có 2 tham số) và một giá trị khởi tạo: g đầu tiên được áp dụng cho giá trị khởi tạo và phần tử đầu tiên trong danh sách, kết quả

được lưu trong biến trung gian, tiếp tục dùng biến trung gian này để phần tử thứ 2 trong danh sách để làm tham số cho hàm g, công việc tiếp lặp đi lặp lại đến khi hết toàn bộ danh sách. Fold trả về kết quả cuối cùng là giá trị cuối cùng của biến trung gian.

Hình 1.2. Hàm Map và Fold trong Functional Programming

Hàm Map trong MapReduce tương ứng với hàm Map, hàm Reduce tương

ứng với hàm Fold trong lập trình hàm.

1.1.3. Cấu trúc dữ liệu trong MapReduce

Các cặp key-value là cấu trúc dữ liệu cơ bản trong MapReduce. Key và value có thể nhận các giá trị có kiểu cơ bản như số nguyên, số thực, chuỗi hay có thể nhận các kiểu giá trị có cấu trúc do người dùng định nghĩa.

Một phần quan trọng của giải thuật MapReduce là việc xác định cấu trúc key-value trên các tập dữ liệu cần xử lý. Ví dụ, đối với một tập các trang web, các key có thể là các URL và các value có thể là nội dung của các trang HTML, đối với một đồ thị, key có thể là node id và value có thể là danh sách kề của node đó. Trong một số thuật toán key được sử dụng để phân biệt các bộ dữ liệu (giống như khái niệm khóa trong cơ sở dữ liệu), trong khi ở một số thuật toán, các input key không quan trọng và thường được bỏ qua.

1.1.4. Mapper và Reducer

Trong MapReduce, lập trình viên định nghĩa một lớp Mapper và một lớp

Reducer với hai hàm cơ bản sau:

 map (k1, v1) → [ (k2, v2)]

 reduce (k2, [v2]) → [ (k3, v3)]

Ký hiệu […] để chỉ một danh sách các giá trị. Đầu vào của một công việc MapReduce (MapReduce job) là dữ liệu được lưu trữ trên hệ thống file phân tán (Distributed File System). Hàm map và reduce lần lượt được cài đặt trong hai lớp

Mapper và Reducer. Mapper được áp dụng cho mọi cặp key-value để tạo ra các cặp key-value trung gian. Reducer được áp dụng cho tất cả các giá trị (value) ứng với cùng một key trung gian để tạo các cặp key-value ở đầu ra. Giữa 2 pha map và reduce là một phép xử lý nhóm phân tán các cặp key-value trung gian dựa trên các key. Dữ liệu trung gian được gởi đến mỗi reducer theo thứ tự được sắp xếp bởi các key. Tuy nhiên không có một quan hệ thứ thự nào được thiết lập cho các key giữa các reducer với nhau. Các cặp key-value ở đầu ra của các reducer được ghi vào hệ thống file phân tán (các cặp key-value trung gian được bỏ qua). Đầu ra cuối cùng là r file trên hệ thống file phân tán, trong đó r là số các reducer. Trong phần lớn các trường hợp, việc tổng hợp các đầu ra của các reducer là không cần thiết bởi vì r files thường lại là đầu vào cho một MapReduce job khác. Hình 5 mô tả 2 giai đoạn của một MapReduce job.

Hình 1.3. Hai pha Map và Reduce của một MapReduce job

Ví dụ minh họa MapReduce: Ứng dụng đếm từ (Word count) trong một

tập văn bản.

 Input: Tập văn bản

 Outut: Danh sách các từ cùng số lần xuất hiện của chúng trong tập

văn bản.

class Mapper

method Map (docId a, doc d)

for all term t ϵ doc d do

Emit (term t, count 1)

class Reducer

method Reduce (term t, counts[c1, c2,…])

sum ← 0

for all count c ϵ counts[c1, c2,…] do

sum ← sum + c

Emit (term t, count sum)

Hàm Map duyệt qua từng từ trong tập văn bản ứng với mỗi từ sẽ tạo ra một cặp key-value với key chính là từ vừa gặp và value = 1. Hàm Reduce nhận đầu vào là một từ (term) và và danh sách tần số ci bắt gặp của term đó (các giá trị thực là các số 1), Reduce chỉ đơn giản cộng tất cả các giá trị ci trong danh sách counts.

1.1.5. Partitioner và Combiner

Phần trên chúng ta đã làm đơn giản cái nhìn về MapReduce, ngoài hai thành phần Mapper và Reducer, thường thì lập trình viên phải chỉ thêm 2 thành phần phụ nữa:

1.1.5.1. Thành phần Partitioner

Nó có nhiệm vụ chia không gian khóa (key) trung gian sau bƣớc Map và gán các cặp key-value trung gian tới các Reduce. Hay nói một cách khác, partitioner chỉ định tác vụ (task) mà cặp key-value trung gian phải được chuyển đến đó. Trong mỗi Reducer, các khóa được xử lý theo thứ tự đã được sắp xếp. Partitioner đơn giản nhất bao gồm việc tính toán giá trị băm của key và sau đó thực hiện phép chia lấy phần dƣ của giá trị này với số lượng reducer. Do đó các partitioner có thể gán một key và danh sách value của nó tới một reducer có số hiệu là giá trị băm vừa tính được. Thông thường hàm băm phải được tính toán sao cho số lượng key gửi đến mỗi reducer xấp xỉ bằng nhau. Tuy nhiên partitioner không chú ý đến giá trị value trong cặp key-value, do đó có thể xảy ra tình trạng phân bố dữ liệu không đồng đều trên các reducer.

1.1.5.2. Thành phần Combiner

Thành phần này trong MapReduce đóng vai trò như một thành phần tối ưu giúp giảm tải việc chuyển dữ liệu giữa từ các Mapper đến các Reducer. Có thể

xem combiner như là một reducer nhỏ (mini-reducer) đặt tại đầu ra của mapper, trước pha trộn và sắp xếp (shuffle and sort phase) gởi các cặp key-value tới các reducer. Mỗi combiner hoạt động cô lập và do đó nó không truy xuất đến các cặp key-value của các mapper khác. Đầu vào của combiner là các cặp key-value từ đầu ra của mapper và nó xử lý tất cả các cặp key-value có key giống nhau để chuyển thành cặp key-value (cùng định dạng như ở đầu vào của combiner có key không thay đổi nhưng value đã bị biến đổi) ở đầu ra. Tuy nhiên, Reducer và Combiner không thể hoán đổi vai trò cho nhau.

Hình 1.4. Mô hình MapReduce đầy đủ các thành phần

1.2. Bộ khung thực thi

Một trong những ý tưởng quan trọng nhất trong MapReduce là tách biệt việc xử lý phân tán cái gì (what) ra khỏi việc xử lý phân tán như thế nào (how). Một chương trình MapReduce (Mapreduce Job), bao gồm đoạn mã cho Mapper, Reducer và có thể thêm Partioner và Combiner được đóng gói lại với nhau với các tham số cấu hình (ví dụ vị trí các tập tin đầu vào và nơi lưu trữ đầu ra). Nhà phát triển đưa chương trình lên cho node quản lý tác vụ trong cluster (trong Hadoop gọi là JobTracker) và execution framework xử lý tất cả những thứ khác: xử lý trong suốt các vấn đề của việc thực thi mã lệnh phân tán. Các chức năng chính của Execution framework bao gồm:

1.2.1. Lập lịch

Mỗi chương trình MapReduce được chia nhỏ thành các đơn vị nhỏ gọi là tasks. Ví dụ, một map task có thể chịu trách nhiệm xử lý một khối các cặp key-value nào đó (trong Hadoop gọi là input split), tương tự, một reduce task có thể xử lý một phần của không gian khóa.

1.2.2. Di chuyển dữ liệu và mã lệnh

Ý tưởng của MapReduce là di chuyển mã lệnh, không phải di chuyển dữ liệu.

Tuy nhiên, trong một số trường hợp – để cho việc tính toán có thể thực hiện chúng ta phải đưa dữ liệu đến mã lệnh. Trong MapReduce, việc này phụ thuộc phần lớn vào hệ thống file phân tán. Để có được việc cục bộ dữ liệu, scheduler phải khởi động task tại node có chứa khối dữ liệu cần thiết cho task đó. Nếu không thể được (do đang chạy quá nhiều task), một task mới sẽ được khởi tạo ở node khác và dữ liệu được truyền qua mạng đến node đó để xử lý.

1.2.3. Đồng bộ hóa

Việc đồng bộ hóa chỉ đến các cách thức để các tiến trình đang xử lý đồng thời có thể hợp lại (“join up”), ví dụ chia sẻ kết quả trung gian hoặc trao đổi thông tin trạng thái. Trong MapReduce, việc đồng bộ hóa xảy ra giữa pha map và reduce. Các cặp key-value trung gian phải được gộp theo khóa, điều này đạt được bằng một phép toán sắp xếp phân tán lớn trên tất cả các node đã chạy map tasks và tất cả các node sẽ chạy reduce tasks. Dữ liệu trung gian được copy qua mạng, vì thế tiến trình này thường được gọi là “shuffle and sort”. Một chương trình MapReduce với m mapper và r reducer có thể có tới m x r phép toán copy vì mỗi mapper có thể có đầu ra đến tất cả các reducer.

1.2.4. Xử lý lỗi

MapReduce framework phải hoàn thành tất cả các tasks trong môi trường xảy ra lỗi thường xuyên. Vì MapReduce được thiết kế dành cho các cụm máy giá rẻ (low-end) nên việc thực thi có thể sẽ dễ xảy ra lỗi, đặc biệt trong các cụm lớn, lỗi đĩa cứng và RAM sẽ xảy ra thường xuyên. MapReduce frame work phải xử lý được các việc này.

1.3. Hệ thống file phân tán

Chúng ta đã tập trung nhiều vào việc xử lý dữ liệu lớn. Nhưng một điều không kém phần quan trọng đó là: nếu không có dữ liệu thì chúng ta không có gì để xử lý cả. Trong tính toán hiệu năng cao (HPC – High-Performance Computing) và các kiến trúc cụm truyền thống, việc lưu trữ được xem là một thành phần tách biệt với việc tính toán. Có nhiều cách cài đặt khác nhau, trong đó có Network-Attach Storage (NAS) và Storage Area Network (SAN) là được sử dụng thường xuyên. Tuy nhiên với cách cài đặt nào đi nữa thì chu trình xử lý vẫn không thay đổi: các node tính toán lấy đầu vào từ nơi lưu trữ, nạp dữ liệu vào bộ nhớ, xử lý dữ liệu và ghi kết quả ngược trở lại.

Khi kích thước dữ liệu càng tăng lên thì khả năng xử lý cũng phải tăng lên. Nhưng khi khả năng xử lý tăng thì sự liên kết giữa node lưu trữ và node xử lý lại trở thành một trở ngại. Lúc này để có hiệu năng cao thì cần phải có đường truyền mạng tốc độ cao (vd: 10 gigabit Ethernet, InfiniBand). Đây không phải là giải pháp hiệu quả về kinh tế. Một cách khác đó là bỏ qua sự tách biệt giữa lưu trữ và tính toán. Đây chính là ý tưởng của hệ thống file phân tán bên dưới MapReduce. Google File System (GFS) là cài đặt hệ thống file phân tán riêng của Google và Hadoop Distributed File System (HDFS)

là một cài đặt mã nguồn mở của GFS.

Ý tưởng chính là chia dữ liệu thành các khối và sao lưu thành các khối đó trên đĩa của các node trong cluster (mặc định là 3). Các khối dữ liệu thường có kích thước mặc định là 64MB. Hệ thống file phân tán sử dụng kiến trúc master-slave, master duy trì không gian tên file (metadata, cấu trúc thư mục, ánh xạ file đến block, vị trí các block, quyền truy cập) và slave quản lý các khối dữ liệu cụ thể. Trong GFS, master được gọi là GFS Master và slave được gọi là GFS ChunkServer. Trong Hadoop, master được gọi là NameNode và slave được gọi là DataNode. Cả 2 hệ thống này hoạt động hầu như giống nhau, tuy nhiên, trong HDFS thì không có ghi thêm vào file và hiệu suất của HDFS cũng hơi chậm hơn so với GFS.

1.3.1. Kiến trúc của HDFS

Hình 1.5. Kiến trúc của HDFS

1.3.2. Nhiệm vụ của NameNode

Việc quản lý không gian tên: NameNode chịu trách nhiệm duy trì không gian tên file, bao gồm metadata, cấu trúc thư mục, ánh xạ file đến block, vị trí của các block và quyền truy cập. Các dữ liệu này được nạp vào bộ nhớ để truy cập cho nhanh.

Định vị các phép toán trên file: Namenode điều khiển các ứng dụng khách (clients) đến datanode để đọc và cấp phát các block thích hợp để ghi. Tất cả việc trao đổi diễn ra trực tiếp giữa client và datanode. Khi một file bị xóa, HDFS không lập tức thu lại không gian lưu trữ, thay vào đó, các block sẽ được thu gom từ từ (lazily garbage collected).

Duy trì sự hoạt động của hệ thống file: Định kì, namenode sẽ gửi các thông điệp báo hiệu (heartbeat messages) đến datanode để bảo đảm sự toàn vẹn của hệ thống. Nếu namenode thấy một block nào có số bản sao thập hơn yêu cầu, nó sẽ điều khiển để tạo ra các bản sao mới. Cuối cùng, namenode chịu trách nhiệm cân bằng hệ thống file. Trong các phép toán thông thường, một datanode có thể sẽ chứa nhiều blocks hơn những cái khác, namenode sẽ cân bằng bằng cách chuyển các blocks từ các datanode có nhiều blocks đến các datanode có ít blocks hơn.

Thiết kế có một master của GFS và HDFS là một điểm yếu dễ thấy. Vì nếu master bị lỗi thì toàn bộ hệ thống và tất các MapReduce jobs sẽ bị dừng. Yếu điểm này được giảm bớt đi một phần nhờ vào bản chất của các phép toán của hệ thống file: không có dữ liệu đi qua NameNode và toàn bộ sự giao tiếp của clients và DataNode chỉ chứa metadata. Vì thế, NameNode cũng ko hẳn là một yếu điểm, trong hầu hết trường hợp đều tránh được lỗi do tràn dữ liệu. Trong thực tế, điểm chết (Single Point Of Failure - SPOF) này ko phải là một hạn chế lớn – với việc theo dõi NameNode thường xuyên thì thời gian bị lỗi sẽ không quá lâu trong các triển khai thương mại. Hơn nữa, Hadoop cũng được thiết kế thêm một NameNode dự phòng (Secondary NameNode) để có thể chuyển đổi nhanh chóng khi NameNode bị lỗi.

1.3.3. Nhiệm vụ của DataNode

DataNode có nhiệm vụ đọc và ghi các block của HDFS vào hệ thống file cục bộ. Khi muốn đọc hay ghi một file HDFS, file này sẽ được chia nhỏ thành các block và namenode sẽ cho client biết DataNode nào đang chứa block nào. Client truy cập trực tiếp đến DataNode để lấy block dữ liệu cần xử lý. Ngoài ra, các DataNode cũng giao tiếp với nhau để sao lưu dữ liệu.

Hình trên thể hiện vai trò của NameNode và DataNode. Trong hình này, ta có hai files: một tại /user/chuck/data1 và một tại /user/james/data2. File 1 có 3 block 1, 2, 3 và file 2 có 2 block 4 và 5. Nội dung của các file được lưu trữ phân tán giữa các DataNode, mỗi block có 3 bản sao. Ví dụ, block 1 được sao lưu trên 3 DataNode bên phải, điều này đảm bảo rằng nếu một DataNode bị lỗi thì vẫn có thể đọc được file trên các DataNode khác.

Hình 1.6. Vai trò của NameNode và DataNode trong HDFS

Các DataNode liên tục báo cáo lên NameNode. Sau khi khởi tạo, mỗi DataNode sẽ báo cáo lên NameNode các block nó đang lưu trữ. Sau khi hoàn tất, DataNode sẽ tiếp tục liên lạc với NameNode để cung cấp thông tin về sự thay đổi dữ liệu cục bộ và nhận các chỉ thị để tạo, di chuyển hay xóa các block từ đĩa cục bộ.

1.3.4. Nhiệm vụ của Secondary NameNode

nam

job submission

enode

node

namenode daemon

jobtracker

tasktracker

datanode daemon

Linux file system

…

slave node

Hình 1.7. Kiến trúc HDFS đầy đủ

Secondary NameNode (SNN) là một tiến trình nền (daemon) để hỗ trợ cho việc

theo dõi trạng thái của HDFS cluster. Cũng như NameNode, mỗi cluster cũng có một SNN và thường chạy trên một server riêng. Không có DataNode hoặc TaskTracker nào chạy trên server này. Điểm khác của SNN so với NameNode là nó không nhận và lưu lại sự thay đổi thời gian thực của HDFS. Thay vào đó, nó liên hệ trực tiếp với NameNode để lưu lại trạng thái của HDFS sau một khoảng thời gian do người dùng cấu hình.

Như đã nói ở trên, NameNode là một yếu điểm của Hadoop cluster và SNN giúp giảm thiểu thời gian lỗi và mất dữ liệu. Tuy nhiên, khi một NameNode gặp sự cố, thì cần có con người can thiệp và cấu hình lại cluster để SNN có thể trở thành NameNode.

CHƯƠNG 2

THUẬT TOÁN XỬ LÝ DỮ LIỆU VĂN BẢN VỚI MapReduce

2.1. Thiết kế thuật toán MapReduce cơ bản

Phần lớn sức mạnh của MapReduce đến từ sự đơn giản: để chuẩn bị cho dữ liệu đầu vào, lập trình viên chỉ cần cài đặt mapper và reducer, hoặc thêm partioner và combiner. Tất cả phần thực thi được xử lý trong suốt bởi Execution framework – trên các clusters từ một đến hàng nghìn node, trên các tập dữ liệu từ gigabytes đến petabytes. Tuy nhiên, nó cũng có nghĩa là bất cứ thuật toán nào người lập trình muốn phát triển cũng phải được diễn tả theo một cách nghiêm ngặt theo các thành phần đã được định nghĩa sẵn. Điều đó có nghĩa không phải bất kỳ thuật toán nào cũng có thể chuyển sang mô hình lập trình này. Mục đích của chương này là cung cấp, chủ yếu qua các ví dụ để thiết kế thuật toán cho MapReduce.

Đồng bộ hóa có lẽ là phần khó nhất của việc thiết kế thuật toán cho MapReduce (và các thuật toán song song hoặc phân tán nói chung). Trong các bài toán xử lý song song, các tiến trình trong các node khác nhau trong một cụm tại một thời điểm nào đó phải dồn lại với nhau, ví dụ: phân tán các kết quả từng phần từ các nodes tạo ra chúng đến các nodes sẽ sử dụng chúng. Với một MapReduce Job, chỉ có một lần đồng bộ hóa trên toàn cluster – giai đoạn sort và shuffle, lúc mà các cặp key-value trung gian được copy từ mapper đến reducer và gộp theo key. Ngoài lúc đó, mapper và reducer chạy độc lập và không có cơ chế liên lạc trực tiếp giữa chúng. Hơn nữa, người lập trình có rất ít sự điều khiển trên nhiều khía cạnh của sự thực thi, ví dụ:

 Chỉ định Node cho một Mapper hoặc Reducer cụ thể.

 Chỉ định thời gian bắt đầu và kết thúc của Mapper hoặc Reducer. Chỉ định

Mapper sẽ xử lý cặp key-value cụ thể.

 Chỉ định Reducer sẽ xử lý các cặp key-value trung gian.

Tuy nhiên, lập trình viên cũng có một số kĩ thuật để điều khiển việc thực thi và

quản lý dòng dữ liệu trong MapReduce. Bao gồm:

 Khả năng xây dựng các cấu trúc dữ liệu phức tạp dùng làm keys và values

để lưu trữ và giao tiếp các kết quả từng phần.

 Khả năng thực thi các đoạn mã của người dùng lúc bắt đầu và kết thúc

map và reduce task.

 Khả năng bảo toàn trạng thái giữa các mapper và reducer qua nhiều khóa

đầu vào hoặc trung gian.

 Khả năng điều khiển thứ tự sắp xếp của các keys trung gian, do đó có thể

biết được thứ tự các key mà reducer sẽ nhận.

 Khả năng điều khiển phân mảnh không gian khóa, do đó có thể biết được

thứ tự tập khóa mà một reducer nào đó sẽ nhận.

Một MapReduce Job không thể biểu diễn tất cả các thuật toán. Người lập trình thường phải phân tích thuật toán phức tạp thành một chuỗi các jobs, yêu cầu chuỗi các dữ liệu liên tục, vì thế đầu ra của một job trở thành đầu vào của job kế tiếp. Nhiều thuật toán thường có bản chất lặp đi lặp lại, đòi hỏi sự thực thi lặp đi lặp lại để đạt được một ngưỡng hội tụ cần thiết.

Chương này sẽ giải thích các kĩ thuật khác nhau để điều khiển sự thực thi lệnh và

dòng dữ liệu có thể được áp dụng để thiết kế thuật toán trong MapReduce.

2.1.1. Gộp lớn cục bộ

Trong việc xử lý dữ liệu lớn, một phần quan trọng nhất của sự đồng bộ hóa là việc trao đổi các kết quả trung gian từ các tiến trình tạo ra nó đến các tiến trình sẽ sử dụng nó. Trong môi trường xử lý song song thì các kết quả trung gian này phải được truyền qua mạng. Hơn nữa, trong Hadoop các kết quả trung gian được ghi vào đĩa cục bộ trước khi được gửi qua mạng. Vì độ trễ của mạng và đĩa cao hơn nhiều so với các phép toán khác nên việc giảm số lượng các kết quả trung gian sẽ làm tăng tính hiệu quả của thuật toán. Trong MapReduce, việc gộp cục bộ các kết quả trung gian là một trong các cách giúp cho thuật toán nhanh hơn. Thông qua việc sử dụng Combiner và khả năng bảo toàn trạng thái giữa các đầu vào, ta có thể giảm một lượng lớn các cặp key-value dùng cho pha shuffle and sort giữa các Mapper và Reducer.

Hình 2.1. Bảo toàn trạng thái trong Hadoop

Hình mô tả việc tạo đối tượng và bản toàn trạng thái trong Hadoop, một đối

tượng Mapper và Reducer được tạo ra tương ứng với một task, hàm Configure được chạy lúc khởi tạo đối tượng, hàm map/reduce chạy tương ứng với mỗi cặp key-value, hàm close được chạy khi hủy đối tượng. Trạng thái của đối tượng được bảo toàn qua các lần gọi hàm map/reduce.

2.1.1.1. Combiner và In-Mapper combining

Để minh họa các kỹ thuật khác nhau của hàm gộp cục bộ. Ta sử dụng ví dụ là

chương trình Wordcount:

 Input: Tập các văn bản

 Output: Các từ và số lượng của chúng trong tập các văn bản

Hình 2.2. Tiến trình hoạt động của chương trình WordCount

Class MAPPER Method MAP (docid a, doc d) For all term t in doc d do EMIT (term t, count 1) Class REDUCER Method REDUCE (term t, counts [C1, C2, …]) Sum ← 0 For all count c in counts [C1, C2, …] do Sum ← Sum + c EMIT (term t, count sum)

Chương trình Wordcount cơ bản:

Mapper đưa lên các key-value trung gian ứng với mỗi từ nó tìm thấy với key là từ

đó và value là 1, Reducer tổng các giá trị trung gian để đưa ra kết quả cuối cùng.

Class MAPPER Method MAP (docid a, doc d) H ← new ASSOCIATIVEARRAY For all term t in doc d do H{t} ← H{t} + 1 >Đếm số lượng tổng cộng một tài liệu For all term t in H do EMIT (term t, count H{t})

Word Count: Version 1 (Reducer vẫn giữ nguyên)

Thuật toán này cải thiện hơn so với chương trình wordcount cơ bản, sử dụng một mảng kết hợp để đếm số lượng các từ trong một tài liệu sau đó mới đưa lên các từ và số lượng của các từ đó trong mảng. Dễ thấy cách này sẽ làm giảm đi số lượng các key- value trung gian.

Class MAPPER Method INITIALIZE H ← new ASSOCIATIVEARRAY >bảo toàn trạng thái giữa các cặp

Word Count: Version 2

key/value

Method MAP (docid a, doc d) For all term t in doc d do H{t} ← H{t} + 1 >Đếm số lượng tổng cộng trên nhiều tài liệu Method CLOSE For all term t in H do EMIT (term t, H{t})

Cũng với ý tưởng trên, thuật toán này dựa vào sự bảo toàn trạng thái của đối tượng Mapper để khởi tạo một mảng kết hợp bên ngoài hàm map, sau đó dùng mảng này để đếm số từ giữa nhiều tài liệu trong một map task. Đến khi tất cả hàm Map đã xử lý hết dữ liệu trung gian thì hàm CLOSE sẽ được gọi, lúc này ta gửi cặp key-value tương tứng với các phần tử trong mảng kết hợp. Với kĩ thuật này, ta đang sử dụng chức năng của hàm Combiner trực tiếp ở trong Mapper. Ta không cần phải chạy các Combiner khác, vì tất cả khả năng gộp cục bộ đã được chỉ rõ. Mẫu thiết kế này trong MapReduce thường được gọi là “In-Mapper Combining”. Có hai lợi ích khi sử dụng mẫu thiết kế này:

1. Thứ nhất, nó điều khiển được khi nào việc gộp cục bộ xảy ra và chính xác xảy ra như thế nào. Ngược lại, ý nghĩa của hàm Combiner không được chỉ rõ trong MapReduce. Ví dụ: Hadoop không bảo đảm hoặc Combiner được thực hiện bao nhiêu lần hoặc có thể không thực hiện lần nào. Combiner được xem là một tối ưu hóa trong execution framework, có thể sử dụng hoặc không, có thể được gọi không hoặc nhiều lần. Trong nhiều trường hợp, sự không chắc chắn này không chấp nhận được, chính vì thế nhiều lập trình viên tự viết hàm gộp trong Mapper.

2. Thứ hai, In-Mapper Combining sẽ hiệu quả hơn các Combiner thực sự. Combiner làm giảm số lượng các key-value trung gian trong pha shuffle

and sort nhưng không làm giảm số lượng các key-value tạo ra trong pha map, việc này làm tạo ra nhiều việc tạo và hủy đối tượng. Ngược lại, trong In-Mapper Combining chỉ tạo các cặp key- value cần thiết cho pha shuffle and sort.

Tuy nhiên, trong mẫu In-Mapper Combining cũng có hạn chế. Nó làm mất đi ý

tưởng ban đầu của MapReduce vì có bảo toàn trạng thái giữa các cặp key-value. Bảo toàn trạng thái giữa các dữ liệu đầu vào, có nghĩa thuật toán có thể phụ thuộc vào thứ tự của các cặp key-value, dẫn đến có thể xảy ra các lỗi về thứ tự. Thứ hai, khi dữ liệu quá lớn thì có thể làm cho dữ liệu trung gian không thể chứa đủ trong bộ nhớ dẫn đến vấn đề về bộ nhớ. Giải pháp là giới hạn kích thước của Block và thường xuyên hủy các cấu trúc dữ liệu không dùng tới trong bộ nhớ.

2.1.1.2. Sự chính xác của thuật toán trong Local Aggregation

Mặc dù Combiner có thể làm giảm thời gian chạy của chương trình nhưng cũng

cần cẩn thận khi sử dụng chúng. Vì Combiner trong Hadoop được xem là các tối ưu phụ nên sự chính xác của thuật toán không thể phụ thuộc vào sự tính toán trên Combiner hoặc phụ thuộc vào nó. Trong các chương trình MapReduce, kiểu dữ liệu đầu vào trong Reducer phải cùng kiểu dữ liệu đầu ra của Mapper, vì thế kiểu dữ liệu đầu vào và đầu ra của Combiner phải cùng kiểu với dữ liệu đầu ra của Mapper. Trong trường hợp kiểu dữ liệu đầu vào và đầu ra của Reducer giống nhau thì Reducer có thể dùng như Combiner.

Ví dụ: Computing the Mean (Tính giá trị trung bình)

 Input: Tập dữ liệu với input key kiểu string và input value kiểu integer.

Class MAPPER Method MAP (string t, integer r) EMIT (string t, integer r) Class REDUCER

 Output: Giá trị trung bình ứng với mỗi key.

Method REDUCE (string t, integers [r1, r2, …]) Sum ← 0 Cnt ← 0 For all integer r in integers [r1, r2, …]) do Sum ← Sum + r Cnt ← Cnt + 1 ravg ← Sum/Cnt EMIT (string t, integer ravg)

Thuật toán này không thể sử dụng combiner như reducer vì trung bình của các

giá trị trung bình cục bộ không bằng trung bình của toàn bộ các giá trị.

Ví dụ: ( (3+4)/2 + (8+9+10)/3)/2 = 6.25 (3 + 4 + 8 + 9 + 10)/5 = 6.8

Dễ thấy trong ví dụ trên, hai cách tính toán cho ra hai kết quả khác nhau.

Class MAPPER Method MAP (string t, integer r) EMIT (string t, integer r) Class COMBINER Method COMBINE (string t, integers [r1, r2, …]) Sum ← 0 Cnt ← 0 For all integer r in integers [r1, r2, …]) do Sum ← Sum + r Cnt ← Cnt + 1 EMIT (string t, pair (Sum,Cnt) >Sum và Count riêng phần Class REDUCER Method REDUCE (string t, pairs [ (s1,c1), (s2,c2), …]) Sum ← 0 Cnt ← 0 For all pair (s,c) in pairs [ (s1,c1), (s2,c2), …] do Sum ← Sum + s Cnt ← Cnt + c ravg ← Sum/Cnt EMIT (string t, integer ravg)

Computing the Mean: Version 2

Thuật toán này không chính xác vì sự khác nhau về kiểu dữ liệu của key-value

giữa Combiner và Reducer (nếu Combiner không được gọi lần nào thì sẽ sai).

Class MAPPER Method MAP (string t, integer r) EMIT (string t, pair (r,1)) Class COMBINER Method COMBINE (string t, pairs [ (s1,c1), (s2,c2), …])) Sum ← 0 Cnt ← 0 For all pair (s,c) in pairs [ (s1,c1), (s2,c2), …] do Sum ← Sum + s Cnt ← Cnt + c EMIT (string t, pair (Sum,Cnt) >Sum và Count riêng phần Class REDUCER Method REDUCE (string t, pairs [ (s1,c1), (s2,c2), …]) Sum ← 0 Cnt ← 0 For all pair (s,c) in pairs [ (s1,c1), (s2,c2), …] do Sum ← Sum + s Cnt ← Cnt + c ravg ← Sum/Cnt EMIT (string t, integer ravg)

Computing the Mean: Version 3

Thuật toán đúng vì kiểu dữ liệu của Combiner và Reducer giống nhau.

Computing the Mean: Version 4

Class MAPPER Method INITIALIZE S ← new ASSOCIATIVEARRAY C ← new

ASSOCIATIVEARRAY

Method MAP (string t, integer r) S{t} ← S{t} + r C{t} ← C{t} + 1 Method CLOSE For all term t in S do EMIT (term t, pair (S{t}, C{t}))

Thuật toán sử dung In-Mapper combining

2.1.2. Bộ hai và bộ ba

Một phương pháp phổ biến cho đồng bộ hóa trong MapReduce là xây dựng các khóa và giá trị phức tạp theo một cách mà dữ liệu cần thiết cho một tính toán được tự nhiên gom lại bởi các khung thực thi. Trong một quá trình “đóng gói” từng phần sums và counts trong một giá trị phức tạp được qua một quá trình từ Mapper cho tới Combiner rồi tới Reducer. Mẫu thiết kế “bộ hai (Pairs)” và “bộ ba (Stripes)” tiêu biểu cho chiến lược này.

Bài toán tập trung vào xây dựng các ma trận số lần các từ đồng xuất hiện (co-

occurrence word) trong một tập văn bản lớn

Computer the mean

method Map (string t, integer r) Emit (string t, pair (r, 1))

method Combine (string t, pairs [ (s1, c1), (s2, c2)...]) sum ← 0 cnt ← 0 for all pair (s, c) ∈ pairs [ (s1, c1), (s2, c2)...] do sum ← sum + s cnt ← cnt + c Emit (string t, pair (sum, cnt))

class Mapper class Combiner class Reducer

method Reduce (string t, pairs [ (s1, c1), (s2, c2)...]) sum ← 0 cnt ← 0 for all pair (s, c) ∈ pairs [ (s1, c1), (s2, c2)...] do sum ← sum + s cnt ← cnt + c ravg ← sum/cnt Emit (string t, integer ravg )

Mapper này minh họa các mẫu thiết kế in-Mapper. Reducer cũng giống như ở

Computer the mean Version 4

Trên đây sẽ mô tả 2 thuật toán MapReduce mà nhiệm vụ thực hiện trên văn bản

quy mô lớn

Đếm từ trùng lặp (Tiếp cận “bộ hai”)

1: class Mapper 2: method Map (docid a, doc d) for all term w ∈ doc d do 3: for all term u ∈ Neighbors (w) do 4: Emit (pair (w, u), count 1) 5:

Þ Emit count for each co-

occurrence

1: class Reducer 2: 3: 4: 5: 6:

method Reduce (pair p, counts [c1, c2,...]) s ← 0 for all count c ∈ counts [c1, c2,...] do s ← s + c Þ Sum co-occurrence counts Emit (pair p, count s)

Trong cách tiếp cận bộ hai “Pair”, như thường lệ, các id của tài liệu và các nội dung tương ứng tạo nên các cặp key-value. Mapper xử lý mỗi tài liệu đầu vào và phát đi các cặp key-value trung gian cùng với số lần mỗi cặp từ đồng xuất hiện như là một khóa và một số nguyên như là giá trị. Điều này được thực hiện bằng cách lồng 2 vòng lặp: vòng lặp ngoài duyệt tất cả các từ (thành phần bên trái của cặp), và vòng lặp trong sẽ duyệt tất cả các từ gần với từ đầu tiên (thành phần bên phải của cặp). Số lần đồng xuất hiện các từ có thể được xác định trong cửa sổ thuật ngữ hoặc một số đơn vị theo ngữ cảnh khác như một câu. Khung thực thi MapRecude đảm bảo rằng tất cả các giá trị liện quan tới khóa được gom lại với nhau trong Reducer. Như vậy trong trường hợp Reducer đơn giản chỉ tóm tắt các các trị liên quan với cặp từ đồng xuất hiện cho tới giá trị tuyệt đối của sự kiện trong tập văn bản, sau đó sẽ được phát đi như cặp key-values cuối cùng ấy. Mỗi cặp tương ứng tới một ô trong ma trận các từ đồng hiện. Thuật toán này trình bày cách sử dụng các tổ hợp khóa để phối hợp xử lý dữ liệu phân tán.

Giống như bộ hai (Pair), lần các cặp từ đồng xuất hiện được tạo ra bởi 2 vòng lặp lồng nhau. Tuy nhiên, sự khác biệt lớn nhất giữ chúng là thay vì phát ra cặp key- value trung gian cho mỗi cặp từ đồng hiện, các thông tin đồng thời được lưu lần đầu trong một mảng kết hợp, biểu thị là H. Mapper phát ra các cặp key-value cùng với các từ như là các khóa và các mảng kết hợp tương ứng như là các giá trị. Nơi mà các mảng kết hợp mã hóa các lượt đếm của các từ cụ thể gần nghĩa (ví dụ: ngữ cảnh). Khung thực thi của MapReduce đảm bảo rẳng tất cả các mảng kết hợp cùng các khóa tương ứng sẽ được gom lại trong giai đoạn Reduce (rút gọn). Reducer thực hiện theo từng phần tử tổng của các mảng kết hợp cùng các khóa tương ứng, tích lũy với các số lượng tương ứng các ô trong ma trận đồng hiện. Cuối cùng mảng kết hợp đã phát ra các từ tương ứng như là khóa. Ngược lại với phương pháp tiếp cận bộ hai (Pair), mỗi cặp key-value cuối cùng mã hóa một hàng trong một ma trận đồng hiện.

Đếm từ trùng lặp (Tiếp cận “bộ ba”)

method Reduce (term w, stripes [H1, H2, H3,...])

1: class Mapper 2: method Map (docid a, doc d) for all term w ∈ doc d do 3: H ← new AssociativeArray 4: for all term u ∈ Neighbors (w) do 5: H{u} ← H{u} + 1 Þ Tally words co-occurring with w 6: Emit (Term w, Stripe H) 7: 1: class Reducer 2: 3: Hf ← new AssociativeArray 4: 5: 6:

for all stripe H ∈ stripes [H1, H2, H3,...] do Sum (Hf, H) Þ Element-wise sum Emit (term w, stripe Hf )

Hình 2.3. Thời gian chạy của thuật toán "pairs" và "stripes"

Dưới đây là thí nghiệm thực hiện cả 2 thuật toán trong Hadoop và áp dụng chúng vào một tập văn bản lớn gồm 2.27 triệu tài liệu từ Associated Press Wordstream (APW) với tổng dung lượng là 5,7 GB.

Hình cho thấy thời gian để tính toán ma trận đồng hiện trên các phần phân đoạn khác nhau của tập văn bản APW. Các thí nghiệm được thực hiện trên một cụm Hadoop với 19 slave, đều có hai bộ vi xử lý lõi đơn và hai đĩa.

Thấy rằng các thuật toán bộ hai (Pairs) tạo ra số lượng lớn các cặp key-value so với phương pháp tiếp cận bộ ba (stripes). Bộ ba thể hiện chặt chẽ hơn, khi cùng với các thành phần trái của pair được lặp lại cho mỗi cặp từ đồng hiện. Cách tiếp cận bộ ba (stripes) cũng tạo ra các các khóa trung gian ít hơn và ngắn hơn, và vì thế khung thực thi đã ít thực hiện xắp xếp. Tuy nhiên, giá trị trong cách tiếp cận stripes phức tạp hơn, và đi kèm với nhiều seriallization và deserialization hơn là các tiếp cận pairs.

2.1.3. Tính toán tần số tương đối

Ta sẽ xây dựng trên các cặp và các thuật toán Pairs trình bày trong phần trước và tiếp tục với ví dụ chạy của chúng ta xây dựng từ thể hiện ma trận M cho một ngữ liệu lớn. Nhớ lại rằng trong n vuông lớn × ma trận n, trong đó n = | V | (Kích thước từ vựng), tế bào mij chứa số lần từ wi đồng xảy ra với từ wj trong một bối cảnh cụ thể. Hạn chế của số lượng tuyệt đối là nó không đưa vào tài khoản thực tế là một số từ xuất hiện thường xuyên hơn những người khác. Lời wi có thể cùng xảy ra thường xuyên với wj đơn giản chỉ vì một trong những từ này là rất phổ biến. Một phương thuốc đơn giản là chuyển đổi số lượng tuyệt đối vào tần số tương đối, f (wj | wi). Đó là, những gì tỷ lệ thời gian, không có gì wj xuất hiện trong bối cảnh wi? Điều này có thể được tính toán bằng cách sử dụng phương trình sau:

Ở đây, N (•, •) cho biết số lần xảy ra đồng thời cặp từ cụ thể được quan sát thấy trong các ngữ liệu. Chúng tôi cần đếm các sự kiện chung (từ cooccurrence), chia cho những gì được gọi là cận biên (tổng của số đếm của máy biến xảy ra đồng thời với bất cứ điều gì khác).

Tính toán tần suất tương đối với cách tiếp cận Pairs là đơn giản. Trong giảm, số lượng của tất cả các từ mà cùng xảy ra với các biến điều (wi trong ví dụ trên) có sẵn trong các mảng kết hợp. Do đó, nó cũng đủ để tổng hợp tất cả những tính để đi đến biên (tức là,.wt N (wi, wr)), và sau đó chia cho tất cả các tính chung của các biên để đi đến các tần số tương đối cho tất cả các từ. Điều này thực hiện yêu cầu sửa đổi tối thiểu để các thuật toán sọc gốc trong thuật toán, và minh họa việc sử dụng các cấu trúc dữ liệu phức tạp để phối hợp tính toán phân phối trong MapReduce. Thông qua cơ cấu thích hợp của các phím và các giá trị, người ta có thể sử dụng lập bản đồ Giảm khuôn khổ thực hiện để mang lại cùng tất cả các mảnh của dữ liệu cần thiết để thực hiện một tính toán. Lưu ý rằng, như với trước đây, thuật toán này cũng tổng hợp như mỗi mảng kết hợp phù hợp với bộ nhớ.

Làm thế nào người ta có thể tính toán tần suất tương đối với cách tiếp cận cặp? Trong cách tiếp cận cặp, giảm nhận (wi, wj) như là chìa khóa và đếm như giá trị. Từ điều này một mình nó không thể tính f (wj | wi) kể từ khi chúng tôi làm không có biên. May mắn thay, như trong lập bản đồ, bộ giảm có thể bảo quản nhà nước trên nhiều phím. Bên trong giảm tốc, chúng ta có thể đệm trong bộ nhớ tất cả những từ mà đồng xảy ra với wi và tội của họ, trong bản chất xây dựng các mảng kết hợp trong cách tiếp cận sọc. Để làm công việc này, chúng ta phải xác định thứ tự sắp xếp của các cặp để khóa đầu tiên được sắp xếp theo từ bên trái, và sau đó bằng những từ thích hợp. Với

đặt hàng này, chúng ta có thể dễ dàng phát hiện nếu tất cả các cặp kết hợp với các từ ngữ chúng tôi đều có điều trên (wi) đã gặp phải. Vào thời điểm đó chúng ta có thể quay trở lại thông qua bộ đệm trong bộ nhớ, tính toán tần số tương đối, và sau đó phát ra những kết quả trong cặp khóa-giá trị cuối cùng.

Có thêm một thay đổi cần thiết để làm cho công việc của thuật toán này. Chúng ta phải đảm bảo rằng tất cả các cặp với từ trái cùng được gửi đến giảm tương tự. Điều này, không may, không xảy ra tự động: nhớ lại rằng các phân vùng mặc định dựa trên giá trị băm của khóa trung gian, theo modulo số lượng gia giảm. Đối với một chìa khóa phức tạp, các đại diện byte liệu được sử dụng để tính toán các giá trị băm. Kết quả là, không có đảm bảo rằng, ví dụ, (chó, lợn đất) và (chó, ngựa vằn) được gán cho là sản phẩm giảm tương tự. Để sản xuất ra các hành vi mong muốn, chúng ta phải xác định một phân vùng tùy chỉnh mà chỉ chú ý đến từ bên trái. Đó là, các phân vùng cần phân vùng dựa trên các hash của chỉ từ bên trái.

Thuật toán này sẽ thực sự làm việc, nhưng nó bị những hạn chế tương tự như phương pháp Pairs: như kích thước của tập văn bản phát triển, do đó, không có kích thước từ vựng, và tại một số điểm sẽ không có đủ bộ nhớ để lưu trữ tất cả các đồng xảy ra từ và đếm của họ cho từ chúng tôi đang điều trên. Đối với việc tính toán ma trận đồng xảy ra, lợi thế của phương pháp tiếp cận cặp là nó không bị bất kỳ tắc nghẽn bộ nhớ. Có cách nào để thay đổi cách tiếp cận cặp cơ bản để lợi thế này được giữ lại?

Khi nó quay ra, một thuật toán như vậy là thực sự tốt, mặc dù nó đòi hỏi sự phối hợp của một số cơ chế trong MapReduce. Sự thấu hiểu nằm trong trình tự đúng liệu trình bày đến giảm tốc. Nếu nó đã có thể đôi khi cách tính (hoặc nếu không có được quyền truy cập vào) các biên trong giảm tốc trước khi xử lý số lượng doanh, bộ giảm chỉ có thể phân chia số lượng chung của các biên để tính toán tần số tương đối. Khái niệm "trước" và "sau" có thể bị bắt trong sự sắp đặt của cặp khóa-giá trị, có thể được kiểm soát một cách rõ ràng bởi các lập trình viên. Đó là, các lập trình viên có thể xác định thứ tự sắp xếp của các phím để các dữ liệu cần thiết trước đó được trình bày cho các dữ liệu giảm mui được- đó là cần thiết sau này. Tuy nhiên, chúng ta vẫn cần phải tính toán số lượng biên. Nhớ lại rằng trong thuật toán cặp căn bản, mỗi mapper phát ra một cặp khóa-giá trị với các cặp từ xảy ra đồng thời như là chìa khóa. Để tính toán tần số tương đối, chúng ta sửa đổi các mapper để nó thêm phát ra một "đặc biệt" quan trọng của hình thức (wi, *), với giá trị của một, đại diện cho sự đóng góp của các cặp từ để các biên. Với việc sử dụng các tổ hợp, các tính biên một phần sẽ được tổng hợp trước khi được gửi đến gia giảm. Ngoài ra, mô hình kết hợp trong mapper có thể được sử dụng để tổng hợp nhiều hơn hiệu quả đếm biên.

Trong giảm tốc, chúng ta phải đảm bảo rằng các cặp khóa-giá trị đặc biệt của đại diện resenting những đóng góp biên một phần được xử lý trước khi các cặp khóa- giá trị bình thường đại diện cho số lượng doanh. Điều này được thực hiện bằng cách

xác định thứ tự sắp xếp của các phím để cặp với các biểu tượng đặc biệt trong mẫu (wi, *) được đặt hàng trước bất kỳ cặp khóa-giá trị khác mà từ trái là wi. Ngoài ra, như với trước khi chúng ta cũng phải xác định đúng các phân vùng phải chú ý đến chỉ từ trái trong mỗi cặp. Với các dữ liệu trình tự đúng cách, giảm tốc có thể trực tiếp tính toán tần số tương đối.

Một ví dụ cụ thể được thể hiện trong hình, trong đó liệt kê trình tự các cặp giá trị Key-mà giảm có thể gặp. Thứ nhất, giảm được trình bày với các phím đặc biệt (dog, *) và một số các giá trị, mỗi trong số đó đại diện cho một biệt tiềm đóng góp biên từ giai đoạn bản đồ (giả sử ở đây, hoặc tổ hợp hoặc trong-mapper kết hợp, vì vậy các giá trị đại diện cho số lượng một phần tổng hợp). Việc giảm tích tụ các tính đến nơi ở biên,.wt N (dog, wr).

Việc giảm nắm giữ trên để giá trị này là nó xử lý các khóa tiếp theo. Sau (dog, *), là sản phẩm giảm sẽ gặp phải một loạt các phím đại diện cho số lượng doanh; hãy nói rằng người đầu tiên trong số này là khóa (dog, aarvark). Kết hợp với khóa này

Hình 2.4. Ví dụ minh họa cặp giá trị

Ví dụ về trình tự các cặp khóa-giá trị trình bày với Reducer trong thuật toán cặp để tính tần số tương đối. Điều này cho thấy việc áp dụng các mẫu thiết kế để đảo ngược. Sẽ có một danh sách các giá trị đại diện cho số lượng doanh một phần từ giai đoạn bản đồ (hai giá trị riêng biệt trong trường hợp này). Tổng hợp các tính sẽ mang tính liên kết, tức là, số lần con chó và lợn đất đồng xảy ra trong toàn bộ bộ sưu tập. Tại thời điểm này, kể từ khi giảm tốc đã biết biên, giản ple số học đủ để tính toán tần số tương đối. Tất cả các tính chung sau đó được xử lý một cách chính xác theo cách tương tự. Khi giảm tốc gặp sự đặc biệt tiếp theo cặp khóa-giá trị (doge, *), là sản phẩm giảm reset trạng thái nội bộ của mình và bắt đầu tích lũy biên trên một lần nữa. Nhận thấy rằng các yêu cầu bộ nhớ cho thuật toán này là rất ít, vì chỉ có biên (một số nguyên) cần phải được lưu trữ. Không đệm đếm từ xảy ra đồng cá nhân là cần thiết, và do đó chúng tôi đã loại bỏ các nút cổ chai khả năng mở rộng của thuật toán trước đó.

Mẫu thiết kế này, mà chúng ta gọi là "trật tự đảo ngược", xuất hiện đáng ngạc nhiên thường xuyên và trên các ứng dụng trong nhiều lĩnh vực. Nó như vậy được đặt tên vì thông qua sự phối hợp thích hợp, chúng ta có thể truy cập vào kết quả của một

phép tính trong giảm tốc (ví dụ, một số liệu thống kê tổng hợp) trước khi xử lý các dữ liệu cần thiết để tính toán đó. Sự thấu hiểu chính là chuyển đổi các trình tự tính toán vào một vấn đề phân loại. Trong hầu hết các trường hợp, một thuật toán đòi hỏi dữ liệu theo một trật tự nhất định: bằng cách kiểm soát cách các phím được sắp xếp và làm thế nào các không gian chính là phân vùng, chúng tôi có thể trình bày dữ liệu đến giảm theo thứ tự cần thiết để thực hiện các tính toán thích hợp. Điều này giúp giảm số lượng kết quả một phần là giảm tốc cần nắm giữ trong bộ nhớ.

Để tóm tắt, các ứng dụng cụ thể của các mẫu thiết kế để đảo ngược để tính toán

tần số tương đối yêu cầu sau đây:

1. Phát ra một cặp khóa-giá trị đặc biệt cho mỗi cặp từ đồng xảy ra trong

mapper để nắm bắt việc đóng góp cho biên.

2. Kiểm soát thứ tự sắp xếp của các chính trung gian để các cặp khóa-giá trị thể hiện sự đóng góp cận biên được xử lý bởi giảm tốc trước khi bất kỳ của các cặp đại diện từ doanh đếm đồng xảy ra.

3. Xác định một phân vùng tùy chỉnh để đảm bảo rằng tất cả các cặp cùng

bên trái từ được xáo trộn đến giảm tương tự.

4. Bảo tồn nhà nước trên nhiều phím trong bộ giảm đầu tiên tính toán biên dựa trên các cặp khóa-giá trị đặc biệt và sau đó chia cho số đếm chung của dữ liệu lề để đi đến các tần số tương đối.

Như chúng ta sẽ thấy, mẫu thiết kế này cũng được sử dụng trong xây dựng chỉ

số ngược để thiết lập đúng thông số nén cho các danh sách thông tin đăng.

2.1.4. Sắp xếp thứ cấp

MapReduce sắp xếp các cặp key-value theo keys trong pha Shuffle and Sort, sẽ rất thuận tiện nếu việc tính toán ở reducer dựa vào thứ tự sắp xếp. Tuy nhiên, làm cách nào để ngoài sắp xếp theo key, ta sắp theo theo value nữa? MapReduce của Google có tính năng secondary được xây dựng sẵn để đảm bảo các values được sắp xếp khi đến Reducer. Tuy nhiên, Hadoop chưa có tính năng này. Có 2 cách để dùng secondary sort trong Hadoop: một là lưu tạm trong bộ nhớ sau đó sắp xếp, tuy nhiên cách này sẽ bị giới hạn khi dữ liệu trong bộ nhớ quá lớn. Cách thứ hai là sử dụng mẫu thiết kế Value- to-key tạo nên các composite key (khóa kết hợp) (k,v1).

2.2 Thuật toán tính chỉ mục ngược để tìm kiếm dữ liệu văn bản

Tìm kiếm web là một vấn đề lớn về dữ liệu tinh túy. Việc đưa ra một thông tin cần thể hiện như một truy vấn ngắn bao gồm một vài điều khoản, nhiệm vụ của hệ thống là để lấy đối tượng web có liên quan và trình bày chúng cho người dùng. Trang web lớn như thế nào? Rất khó để tính toán chính xác, nhưng kể cả dự tính khái quát / ước lượng cũng sẽ ra kích thước ở vài chục tỷ trang, với tổng trị giá hàng trăm

terabytes (chỉ xét văn bản). Trong các ứng dụng thực tế, người sử dụng yêu cầu kết quả nhanh chóng từ một công cụ tìm kiếm truy vấn - thời gian trễ dài hơn một vài trăm mili giây sẽ thử thách sự kiên nhẫn của người dùng. Thực hiện các yêu cầu này là khá một kỳ công, lưu tâm đến các khoản dữ liệu liên quan!

Gần như tất cả các động cơ truy hồi/thu hồi cho tìm kiếm văn bản đầy đủ ngày hôm nay dựa trên một cấu trúc dữ liệu được gọi là chỉ số đảo ngược, mà cho một thuật ngữ, cung cấp truy cập vào danh sách các tài liệu có chứa thuật ngữ. Trong thông tin theo cách nói retrieval, đối tượng được lấy lại được gọi khái quát là "tài liệu", mặc dù trong thực tế chúng có thể là các trang web, các file PDF, hoặc thậm chí mảnh mã. Cho một truy vấn của người dùng, retrieval engines sử dụng inverted index để ghi tài liệu có chứa các thuật ngữ truy vấn liên quan tới một số mô hình xếp hạng, có tính đến tính năng tài khoản như thuật ngữ thích hợp, trạng thái thuật ngữ (term proximity), các thuộc tính của các điều khoản/thuật ngữ trong tài liệu.

Các vấn đề tìm kiếm web bị phân hủy thành ba thành phần: thu thập nội dung web, xây dựng các chỉ số và các văn bản xếp hạng cho một truy vấn. Crawling và indexing chia sẻ những đặc điểm và yêu cầu tương tự nhau, nhưng chúng rất khác với thu hồi. Thu thập nội dung trang web và xây dựng các chỉ số đảo ngược được cho hầu hết các vấn đề offline. Cả hai cần phải được mở rộng và hiệu quả, nhưng chúng không cần hoạt động trong thời gian thực. Indexing thường là một quá trình batch để chạy theo định kỳ: tần suất làm mới và cập nhật thường phụ thuộc vào thiết kế của bộ tìm kiếm. Một số trang web (ví dụ, các tổ chức tin tức) cập nhật nội dung của họ khá thường xuyên và cần phải được truy cập thường xuyên; các trang web khác (ví dụ, chính phủ quy định) là tương đối tĩnh. Tuy nhiên, ngay cả đối với các trang web hay cập nhật, thường thì có thể chấp nhận được việc chậm trễ một vài phút cho đến khi nội dung tìm được. Hơn nữa, vì số lượng nội dung thay đổi nhanh chóng là tương đối nhỏ, chạy cập nhật chỉ số quy mô nhỏ hơn ở tần số lớn hơn thường là một là giải pháp thỏa đáng. Tìm kiếm là một vấn đề trực tuyến đòi hỏi thời gian phản ứng phụ thứ hai (sub- second response time). Người dùng cá nhân mong đợi độ trễ truy vấn thấp, nhưng thông lượng truy vấn cũng không kém phần quan trọng vì retrieval engine thường phục vụ cho nhiều người sử dụng đồng thời. Hơn nữa, tải truy vấn được đánh giá cao biến, tùy thuộc vào thời gian trong ngày, và có thể triển lãm "Spikey" hành vi do trường hợp đặc biệt (ví dụ, một tin tức sự kiện mới gây ra một số lượng lớn tìm kiếm trên cùng một chủ đề). Mặt khác, tiêu thụ tài nguyên cho vấn đề indexing có thể dự đoán được hơn.

2.2.1. Dò tìm Web

Trước khi xây dựng chỉ số đảo ngược, đầu tiên chúng ta phải có được bộ sưu tập tài liệu qua đó xây dựng các chỉ số. Trong học viện và cho các mục đích nghiên cứu, điều này có thể tương đối đơn giản. Bộ sưu tập tiêu chuẩn cho thông tin nghiên cứu thu hồi được phổ biến rộng rãi cho nhiều thể loại khác nhau, từ các blog đến

newswire text. Đối với các nhà nghiên cứu, những người muốn khám phá web-scale retrieval, sẽ là bộ sưu tập ClueWeb09 có chứa một tỷ trang web trong mười ngôn ngữ (Tổng cộng 25 terabyte) được thu thập thông tin bởi Đại học Carnegie Mellon vào đầu năm 2009. Việc tiếp cận với những bộ sưu tập tiêu chuẩn thường là đơn giản như ký một giấy phép dữ liệu thích hợp từ các nhà phân phối của các bộ sưu tập, trả chi phí hợp lý, và sắp xếp cho nhận dữ liệu.

Đối với tìm kiếm web trong thực thế, tuy nhiên, có thể không chỉ đơn giản cho rằng dữ liệu là có sẵn. Tiếp thu nội dung trang web đòi hỏi phải crawling, là quá trình đi qua trang web theo các siêu liên kết liên tục và lưu trữ các trang được tải về cho lần xử lý tiếp theo. Về mặt khái niệm, quá trình này khá đơn giản để hiểu: chúng ta bắt đầu bằng cách gia tăng một hàng đợi với một "hạt giống" danh sách các trang. Crawler tải các trang trong hàng, trích xuất đường dẫn từ những trang đó để thêm vào hàng đợi, lưu trữ các trang để xử lý tiếp, và lặp đi lặp lại. Trong thực tế, trình thu thập web thô sơ có thể được viết bằng hàng trăm dòng mã.

Tuy nhiên, hiệu quả việc dò tìm web hiệu quả phức tạp hơn rất nhiều. Dưới đây liệt kê một số vấn đề mà trình thu thập thực tế (real-world crawlers) phải đấu tranh với:

 Một trình thu thập (crawler) web phải thực hành tốt "nghi thức" và không quá tải web server. Ví dụ, việc chờ đợi một số lượng thời gian cố định trước khi lặp lại yêu cầu đến cùng một server là một thực tế phổ biến. Để tôn trọng những hạn chế trong khi duy trì thông lượng tốt, một crawler thường giữ nhiều thread chạy song song và duy trì nhiều kết nối TCP (có lẽ hàng trăm) mở cùng một lúc.

 Khi một trình thu thập có băng thông hữu hạn và nguồn lực, nó phải ưu tiên thứ tự mà trong đó các trang chưa xem được tải xuống. Quyết định này phải được thực hiện trực tuyến và trong một môi trường thù địch (adversarial environment), có nghĩa là spammer chủ động tạo ra các trang đầy spam "trang trại liên kết" và "bẫy nhện" (“link farms” and “spider traps”) để lừa một trình thu thập vào nội dung overrepresenting từ một trang web cụ thể.

 Hầu hết các trình thu thập web thực tế được phân phối hệ thống chạy trên các cụm máy , thường phân bố cục bộ. Để tránh tải một trang nhiều lần và để đảm bảo tính nhất quán dữ liệu, các trình thu thập như một toàn thể cần cơ chế phối hợp và cân bằng tải. Nó cũng cần phải có sức mạnh (robust) đối với thất bại của máy, mất mạng, và các loại lỗi.

 Nội dung web thay đổi, nhưng với tần số khác nhau tùy thuộc vào cả hai trang web và bản chất của nội dung. Một trình thu thập web cần phải học những các mẫu cập nhật đó để đảm bảo nội dung đó là hợp lý trong hiện

tại. Lấy tần số thu thập lại thông đúng là khó khăn: quá thường xuyên có nghĩa là lãng phí nguồn lực, nhưng không đủ thường xuyên lại dẫn đến nội dung cũ.

 Các trang web có đầy các nội dung trùng lặp. Các ví dụ bao gồm nhiều bản sao của một bài viết hội nghị phổ biến, mẫu của các trang web thường xuyên được truy cập như Wikipedia, và nội dung newswire thường được nhân đôi. Vấn đề phức tạp bởi thực tế rằng các trang lặp đi lặp lại hầu hết đều không trùng lặp hoàn toàn mà gần như trùng lặp (có nghĩa là, về cơ bản các trang tương tự nhưng với quảng cáo khác nhau, các thanh menu, vv). Việc xác định gần bản sao và chọn mẫu mực tốt nhất để chỉ mục trong quá trình thu thập thông tin là một việc đáng kỳ vọng.

 Các trang web đa ngôn ngữ. Không có đảm bảo rằng các trang trong một ngôn ngữ chỉ liên kết đến các trang trong cùng một ngôn ngữ. Ví dụ, một giáo sư tại Châu Á có thể duy trì trang web của mình bằng ngôn ngữ địa phương, nhưng chứa các liên kết đến các ấn phẩm bằng tiếng Anh. Hơn nữa, có nhiều trang chứa một hỗn hợp văn bản trong các ngôn ngữ khác nhau. Kể từ khi các kỹ thuật xử lý tài liệu (ví dụ, tokenization, stemming) khác biệt bởi ngôn ngữ, Việc xác định ngôn ngữ (chi phối) trên một trang là rất quan trọng.

2.2.2 Thuật toán chỉ mục ngược

Trong hình thức cơ bản của nó, một chỉ mục ngược bao gồm danh sách tin đăng, một liên kết với từng kỳ hạn xuất hiện trong bộ sưu tập. Cấu trúc của một chỉ mục ngược được minh họa trong hình. Một danh sách đăng bao gồm những bài viết cá nhân, mỗi trong số đó bao gồm một id tài liệu và trọng số - thông tin về lần xuất hiện của thuật ngữ trong tài liệu. Trọng số đơn giản nhất là... không có gì! Với simple boolean retrieval, việc không có thêm thông tin là cần thiết trong việc đăng khác với id tài liệu; sự tồn tại của bản thân việc gửi bài cho thấy sự hiện diện của các thuật ngữ trong tài liệu. Trọng số phổ biến nhất, tuy nhiên, là tần số hạn (tf), hoặc số lần thuật ngữ xảy ra trong tài liệu. Trọng tải phức tạp hơn bao gồm các vị trí của mỗi sự xuất hiện của thuật ngữ trong tài liệu (để hỗ trợ cụm từ truy vấn và ghi tài liệu dựa trên term gần), tính chất của thuật ngữ (chẳng hạn như nếu nó xảy ra trong tiêu đề trang hay không, để hỗ trợ bảng xếp hạng tài liệu dựa trên khái niệm quan trọng), hoặc thậm chí kết quả xử lý ngôn ngữ bổ sung (ví dụ, chỉ ra rằng term là một phần của tên địa điểm, để hỗ trợ tìm kiếm địa chỉ). Trong bối cảnh web, thông tin văn bản (anchor text information) (văn bản liên quan đến các siêu liên kết từ các trang khác trang trong câu hỏi) là hữu ích trong việc làm phong phú thêm các đại diện của tài liệu nội dung (ví dụ, thông tin này thường cũng được lưu trữ trong các chỉ số. Trong ví dụ thể hiện trong hình 4.1, chúng ta thấy rằng:

term 1 occurs in {d1, d5, d6, d11,...}, term 2 occurs in {d11, d23, d59, d84,...}, and term 3 occurs in {d1, d4, d11, d19,...}.

Trong thực tế thực hiện, chúng tôi giả định rằng các tài liệu có thể được xác định bởi một số nguyên duy nhất từ 1 đến n, trong đó n là tổng số tài liệu. Nói chung, thông tin đăng được sắp xếp theo id tài liệu, mặc dù cũng có các cách sắp xếp khác. Id tài liệu không có ý nghĩa ngữ nghĩa vốn có, mặc dù việc chuyển nhượng id số đến các văn bản không cần phải được tùy ý. Ví dụ, các trang từ cùng một tên miền có thể được đánh số liên tục. Hoặc là, theo một cách khác, những trang có chất lượng cao hơn (có cơ sở, ví dụ, trên các giá trị PageRank) có thể được gán giá trị số nhỏ hơn để chúng xuất hiện trước danh sách tin đăng. Dù bằng cách nào, một cấu trúc dữ liệu phụ trợ là cần thiết để duy trì mapping từ id tài liệu số nguyên cho một số xử lý khác có ý nghĩa hơn, chẳng hạn như một URL.

Hình 2.5. Minh họa đơn giản của một chỉ mục ngược.

Mỗi term có liên quan với một danh sách các thông tin đăng. Mỗi niêm yết bao gồm một id tài liệu và một trọng số, ký hiệu là p trong trường hợp này. Một chỉ số đảo ngược cung cấp truy cập nhanh đến tài liệu id có chứa một từ.

Cho một truy vấn, thu hồi liên quan đến danh sách đăng đem lại kết hợp với truy vấn điều khoản và vượt qua các tin đăng để tính toán kết quả. Trong trường hợp đơn giản nhất, boolean retrieval liên quan đến việc thiết lập hoạt động (hợp nhất cho boolean OR và giao cắt cho boolean AND) vào danh sách tin đăng, mà có thể được thực hiện rất hiệu quả từ các bài đăng được sắp xếp theo id tài liệu. Trong trường hợp tổng quát, tuy nhiên, điểm số truy vấn tài liệu phải được tính toán. Điểm số tài liệu một phần được lưu trữ trong các cấu trúc được gọi là tích lũy. Cuối cùng (tức là, một khi tất cả tin đăng đã được xử lý), các tài liệu đầu k được giải nén (extract) sau đó để mang lại một danh sách xếp hạng các kết quả cho người sử dụng. Tất nhiên, có rất nhiều

chiến lược tối ưu hóa để đánh giá truy vấn (cả hai gần đúng và chính xác) để giúp giảm số lượng đăng mà một động cơ thu hồi phải kiểm tra.

Kích thước của một chỉ số đảo ngược khác nhau, tùy thuộc vào trọng số lưu trữ trong mỗi bài gửi. Nếu tần số chỉ có hạn được lưu giữ, một chỉ số đảo ngược cũng được tối ưu hóa có thể là một phần mười kích thước của bộ sưu tập tài liệu gốc. Một chỉ số đảo ngược chứa đựng thông tin về vị trí sẽ dễ dàng lớn hơn nhiều lần chỉ số không chứa. Nói chung, có thể giữ toàn bộ từ vựng (tức là, Từ điển của tất cả các term) trong bộ nhớ, đặc biệt là với các kỹ thuật như rontcoding. Tuy nhiên, ngoại trừ có nguồn lực tốt, web thương mại công cụ tìm kiếm, danh sách đăng thường quá lớn để lưu trữ trong bộ nhớ và phải được tổ chức vào đĩa, thường ở dạng nén. Đánh giá truy vấn, do đó, nhất thiết phải liên quan đến việc truy cập đĩa ngẫu nhiên và "giải mã" các thông tin đăng. Một khía cạnh quan trọng của vấn đề thu hồi là tổ chức hoạt động của đĩa như giảm thiểu tìm kiếm ngẫu nhiên.

Một lần nữa, cuộc thảo luận ngắn gọn này bao quát nhiều phức tạp và tạo nên một sự bất bình đẳng to lớn đến một lượng lớn các nghiên cứu trong tìm kiếm thông tin. Tuy nhiên, mục tiêu của chúng tôi là cung cấp cho người đọc một cái nhìn tổng quan của các vấn đề quan trọng;

procedure Map (docid n, doc d)

for all term t ∈ doc d do H{t} ← H{t} + 1 for all term t ∈ H do Emit (term t, posting (n, H{t}))

1: class Mapper 2: 3: H ← new AssociativeArray 4: 5: 6: 7: 1: class Reducer 2: 3: 4: 5: 6: 7:

procedure Reduce (term t, postings [ (n1, f1), (n2, f2)...]) P ← new List for all posting (a, f) ∈ postings [ (n1, f1), (n2, f2)...] do Append (P, (a, f)) Sort (P ) Emit (term t, postings P )

Thuật toán lập chi mục ngược cơ bản (4)

2.2.3. Cài đặt theo cơ bản

4 Data-Intensive Text Processing with MapReduce - Jimmy Lin The iSchool University of Maryland

MapReduce được thiết kế ngay từ đầu để sản xuất các cấu trúc dữ liệu khác nhau liên quan đến tìm kiếm web, bao gồm các chỉ số ngược và web đồ thị. Chúng ta bắt đầu với các thuật toán lập chỉ mục ngược cơ bản thể hiện trong thuật toán.

Đầu vào cho các mapper gồm id tài liệu (key) kết hợp với thực tế nội dung (value). Tài liệu cá nhân được xử lý song song bởi mappers. Đầu tiên, mỗi tài liệu được phân tích và chia nhỏ thành các thành phần term của nó. Các đường ống xử lý khác nhau tùy theo ứng dụng và loại tài liệu, nhưng đối với các trang web thường liên quan đến việc stripping out các thẻ HTML và các yếu tố khác như mã JavaScript, tokenizing, case folding, removing stopwords (các từ phổ biến như 'the', 'a', 'của', vv), và stemming (loại bỏ sẽ gắn từ từ để 'những con chó' trở thành 'chó'). Một khi các tài liệu đã được phân tích, tần số hạn được tính bằng cách duyệt qua tất cả các điều khoản và theo dõi đếm. Dòng 4 và 5 trong mã giả phản ánh quá trình tính toán tần số hạn, nhưng ẩn chứa các chi tiết của tài liệu xử lý. Sau khi biểu đồ này đã được xây dựng, các mapper sau đó lặp lại trên tất cả các kỳ hạn. Đối với mỗi học kỳ, một cặp bao gồm id tài liệu và tần số hạn được tạo ra. Mỗi cặp, ký hiệu là hn, H {t} i trong mã giả, đại diện một đăng tải cá nhân. Mapper sau đó phát ra một cặp key-value trung gian với term như là key và posting là value, trong dòng 7 của mapper pseudo-code. Mặc dù như đã trình bày ở đây chỉ có tần số hạn được lưu trữ trong việc posting, thuật toán này có thể dễ dàng tăng cường để lưu trữ thông tin bổ sung (ví dụ, vị trí term) trong payload.

Trong giai đoạn shuffle và sắp xếp, thời gian chạy MapReduce về cơ bản thực hiện một nhóm lớn, phân phối bởi các tin đăng bởi term. Không có bất kỳ nỗ lực thêm vào nào của các lập trình viên, các framework thực hiện tập hợp tất cả các bài đăng thuộc trong cùng một danh sách tin đăng. Việc này đơn giản hóa rất nhiều nhiệm vụ của reducer, chỉ cần đơn giản tập hợp lại với nhau tất cả các bài đăng và ghi chúng vào đĩa. Reducer bắt đầu bằng việc khởi tạo một danh sách rỗng và sau đó gắn thêm tất cả các tin đăng liên quan cùng một key (term) vào danh sách. Các tin đăng này sau đó được sắp xếp theo id tài liệu, và toàn bộ danh sách thông tin đăng phát ra như là một value, với term như là key. Thông thường, danh sách đăng được nén đầu tiên, nhưng chúng ta sẽ tạm bỏ lại điều này bây giờ. Các cặp key-value cuối cùng được ghi vào đĩa và bao gồm các chỉ số ngược. Vì mỗi reducer viết ra nó trong một file riêng biệt trong hệ thống tập tin phân phối, chỉ số cuối cùng của chúng tôi sẽ được chia trên các tập tin r, trong đó r là số reducers. Không cần thiết củng cố thêm những tập tin này. Xét một cách riêng biệt, chúng tôi cũng phải xây dựng một chỉ số cho bản thân các danh sách bài đăng cho công cụ phục hồi: việc này là điển hình trong hình thức của việc mapping từ term đến pairs (tập tin, byte offset), để đưa ra một thuật ngữ, các công cụ phục hồi có thể lấy danh sách tin đăng của mình bằng cách mở các tập tin thích hợp và tìm đến đúng vị trí byte offset trong tập tin đó.

Thực hiện các thuật toán hoàn chỉnh được minh họa trong hình với một ví dụ đồ chơi gồm ba tài liệu, ba mapper, và hai reducer. Cặp key-value trung gian (từ mapper) và các cặp key-value cuối cùng bao gồm các chỉ số đảo ngược (từ reducer) được hiển thị trong các hộp với các đường chấm. Các bài đăng được hiển thị như các cặp hộp (pairs of boxes), với id tài liệu ở bên trái và tần số term ở bên phải.

Hình 2.6: Minh họa đơn giản cơ sở thuật toán lập chỉ mục ngược trong MapReduce với ba mapper và hai reducer

Mô hình lập trình MapReduce cung cấp một biểu hiện rất ngắn gọn về các thuật toán lập chỉ mục ngược. Thực hiện của nó ngắn gọn tương tự: các thuật toán cơ bản có thể được thực hiện với chỉ một vài chục dòng mã trong Hadoop (với xử lý tài liệu tối thiểu). Một thực hiện như vậy có thể hoàn thành một nhiệm vụ lập trình kéo dài một tuần trong một khóa học cho học viên cao học hoặc sinh viên năm thứ nhất tốt nghiệp đại học. Trong một phi MapReduce indexer (non- MapReduce indexer), một phần đáng kể của các mã được dành cho nhóm đăng bởi term, hạn chế được áp đặt bởi bộ nhớ và đĩa (ví dụ, dung lượng bộ nhớ bị hạn chế, đĩa tìm là chậm, vv). Trong MapReduce, các lập trình viên không cần phải lo lắng về bất cứ vấn đề này, hầu hết các nâng nặng được thực hiện bởi framework thực hiện.

2.2.4. Cài đặt thuật toán cải tiến

Các thuật toán lập chỉ mục ngược được trình bày trong phần trước phục vụ như

là một cơ sở hợp lý. Tuy nhiên, có một khả năng mở rộng ý nghĩa bottleneck (nghẽn cổ chai): thuật toán giả định rằng có đủ bộ nhớ để giữ tất cả các tin đăng liên quan cùng một term. Vì framework MapReduce cơ bản không đảm bảo về trật tự của các value liên quan đến cùng một key, reducer đầu tiên buffers tất cả các tin đăng và sau đó thực hiện một sắp xếp trong bộ nhớ trước khi ghi vào đĩa. Đối với phục hồi hiệu quả, thông tin đăng cần phải được sắp xếp theo id tài liệu. Tuy nhiên, khi bộ sưu tập trở nên lớn hơn, danh sách tin đăng trở nên dài hơn, và tại một số điểm trong thời gian, reducer sẽ hết bộ nhớ.

Có một giải pháp đơn giản cho vấn đề này. Kể từ khi framework thực hiện đảm

bảo rằng các key đến được với từng reducer trong thứ tự sắp xếp, một cách để vượt qua những khả năng mở rộng bottleneck là để cho thời gian chạy MapReduce làm các phân loại cho chúng ta. Thay vì phát ra cặp key-value của các loại sau đây:

(term t, posting )

Người ta phát ra cặp key-value trung bình của các loại thay vào đó:

(tuple , tf f)

Nói cách khác, key là một tuple chứa các thuật ngữ và các id tài liệu, trong khi value là tần số term. Đây chính là mẫu thiết kế chuyển đổi value-to-key chính xác được giới thiệu. Với thay đổi này, Mô hình lập trình đảm bảo rằng các thông tin đăng đến được theo thứ tự đúng. Điều này, kết hợp với thực tế mà reducer có thể giữ trạng thái trên nhiều key, cho phép danh sách tin đăng phải được tạo ra với việc sử dụng bộ nhớ tối thiểu. Một chi tiết là, hãy nhớ rằng chúng ta phải xác định một partitioner tùy chỉnh để đảm bảo rằng tất cả các tuples với cùng một term được xáo trộn đến cùng một reducer.

Các thuật toán MapReduce ngược lập chỉ mục sửa đổi (revised MapReduce inverted indexing algorithm) được thể hiện trong thuật toán Mapper vẫn không thay đổi đối với hầu hết các phần, khác hơn sự khác biệt trong các cặp key-value trung gian. Phương pháp Reduce được gọi cho mỗi key (tức là, ht, ni), và do thiết kế, sẽ chỉ có một value liên quan tới mỗi key. Đối với mỗi cặp key-value, một bài viết có thể được bổ sung trực tiếp vào danh sách tin đăng. Khi thông tin đăng được đảm bảo đến đúng thứ tự sắp xếp bởi id tài liệu, chúng có thể từng bước mã hóa trong hình thức nén - do đảm bảo một bộ nhớ nhỏ. Cuối cùng, khi tất cả các tin đăng liên quan đến cùng một term đã được xử lý (tức là, t 6 = tprev), toàn bộ danh sách thông tin đăng được phát ra. Danh sách đăng cuối cùng phải được viết ra trong phương thức Close. Với các thuật toán cơ bản, trọng tải có thể dễ dàng thay đổi: bằng việc đơn giản thay thế các giá trị trung gian f (tần số term) với bất cứ điều gì khác đang mong muốn (Ví dụ, thời hạn thông tin định vị).

Có một chi tiết mà ta phải nắm rõ khi xây dựng chỉ số đảo ngược. Vì gần như tất cả các mô hình retrieval đi vào chiều dài tài liệu tài khoản khi tính toán điểm số truy vấn tài liệu, thông tin này cũng phải được giải nén. Mặc dù việc thể hiện tính toán này là minh bạch như các job MapReduce khác, nhiệm vụ này thực sự có thể được xếp vào quá trình lập chỉ mục ngược. Khi xử lý các term trong mỗi tài liệu, chiều dài tài liệu được biết đến, và có thể được viết ra như "phụ liệu" trực tiếp để HDFS. Chúng ta có thể tận dụng lợi thế của các khả năng cho một mapper để giữ trạng thái qua xử lý nhiều tài liệu theo cách sau đây: một mảng kết hợp trong bộ nhớ (in-memory associative) được tạo ra để lưu trữ độ dài tài liệu, được phổ biến như mỗi tài liệu được xử lý. Khi mapper kết thúc xử lý hồ sơ đầu vào (input records), độ dài tài liệu được viết ra để HDFS (tức là, trong các phương thức Close). Cách tiếp cận này thực chất là một biến thể của trong-mapper kết hợp mô hình (in-mapper combining pattern). Dữ liệu chiều dài tài liệu (Document length data) kết thúc trong m file khác nhau, trong đó m là số mapper; những tập tin này sau đó được hợp nhất thành một đại diện nhỏ gọn hơn. Ngoài ra, thông tin chiều dài tài liệu có thể được phát ra trong cặp key-value đặc

biệt bởi các mapper. Một người sau đó phải viết partitioner tùy chỉnh để các cặp key- value đặc biệt được xáo trộn đến một reducer đơn, trong đó sẽ chịu trách nhiệm viết ra chiều dài dữ liệu tách biệt với danh mục tin đăng.

Thuật toán Tập chỉ mục ngược mở rộng (5)

method Map (docid n, doc d) H ← new AssociativeArray for all term t ∈ doc d do H{t} ← H{t} + 1 for all term t ∈ H do Emit (tuple (t, n), tf H{t})

1: class Mapper 2: 3: 4: 5: 6: 7: 1: class Reducer 2: method Initialize tprev ← ∅ 3: P ← new PostingsList 4: method Reduce (tuple (t, n), tf [f ]) 5: if t ƒ= tprev ∧ tprev ƒ= ∅ then 6: Emit (term tprev, postings P ) 7: P.Reset () 8: P.Add ( (n, f)) 9: 10: tprev ← t 11: method Close 12:

Emit (term t, postings P )

2.2.5. Nén chỉ mục

Chúng ta trở lại câu hỏi về việc làm thế nào để posting được thực sự nén và lưu trữ trên đĩa. Chương này dành một số lượng đáng kể không gian cho chủ đề này vì nén chỉ số là một trong những khác biệt chính giữa một "đồ chơi" indexer và một indexer hoạt động trên bộ sưu tập thực tế. Trái lại, thuật toán MapReduce inverted indexing khá đơn giản.

Chúng ta hãy xem xét các trường hợp kinh điển mà mỗi lần post bao gồm một tài liệu id và tần số term. Một thực hiện đơn giản (na¨ıve implementation) có thể biểu diễn đầu tiên như một số nguyên 32-bit và thứ hai là một số nguyên 16-bit. Do đó, một danh sách tin đăng có thể được mã hóa như sau:

5Data-Intensive Text Processing with MapReduce - Jimmy Lin The iSchool University of Maryland

[ (5, 2), (7, 3), (12, 1), (49, 1), (51, 2),...]

nơi từng posting được đại diện bởi một cặp trong ngoặc đơn. Lưu ý rằng tất cả các dấu ngoặc, dấu ngoặc đơn, dấu phẩy chỉ được bao gồm để tăng cường khả năng đọc; trong thực tế các thông tin đăng sẽ được biểu diễn như một dòng suối dài các số nguyên. Thực hiện đơn giản này sẽ yêu cầu sáu byte cho mỗi đăng tải. Sử dụng chương trình này, toàn bộ chỉ số đảo ngược sẽ lớn như chính bản thân bộ sưu tập. May mắn thay, chúng tôi có thể làm tốt hơn thế một cách đáng kể.

Bí quyết đầu tiên là để mã hóa sự khác nhau giữa id tài liệu, trái ngược với bản thân các tài liệu id. Khi thông tin đăng được sắp xếp theo id tài liệu, sự khác biệt (gọi là d -gaps) phải là số nguyên dương lớn hơn không. Danh sách tin đăng bên trên, đại diện với d -gaps, sẽ là:

[ (5, 2), (2, 3), (5, 1), (37, 1), (2, 2),...]

Tất nhiên, chúng tôi thực sự phải mã hóa các id tài liệu đầu tiên. Chúng tôi đã không bị mất bất kỳ thông tin nào, vì các id tài liệu gốc có thể dễ dàng xây dựng lại từ d -gaps. Tuy nhiên, không rõ ràng rằng chúng tôi cũng đã giảm yêu cầu không gian vì d -gap lớn nhất có thể nhỏ hơn số lượng tài liệu trong bộ sưu tập.

Đây là nơi mà bí quyết thứ hai xuất hiện, là đại diện cho các d –gaps theo cách mà mất ít không gian cho số nhỏ hơn. Tương tự như vậy, chúng tôi muốn áp dụng các kỹ thuật tương tự để nén các tần số hạn, vì đối với hầu hết các phần, chúng cũng là những giá trị nhỏ. Nhưng để hiểu làm thế nào điều này được thực hiện, chúng ta cần phải đi đường vòng vào các kỹ thuật nén, đặc biệt đối với mã hóa số nguyên.

Nén, nói chung, có thể được mô tả như là một trong hai lossless hay lossy: khá rõ ràng rằng nén loseless là cần thiết trong bối cảnh này. Để bắt đầu, quan trọng là phải hiểu rằng tất cả các kỹ thuật nén đại diện cho một thời gian không gian cân bằng. Đó là, chúng ta sẽ giảm số lượng của không gian trên đĩa cần thiết để lưu trữ dữ liệu, nhưng với chi phí của các chu trình xử lý bổ sung mà phải dành để mã hóa và giải mã dữ liệu. Do đó, có thể là nén làm giảm kích thước nhưng cũng làm chậm xử lý. Tuy nhiên, nếu hai yếu tố được cân đúng cách (ví dụ, tốc độ giải mã có thể theo kịp với băng thông đĩa), chúng ta có thể đạt được điều tốt nhất của cả hai thế giới: nhỏ hơn và nhanh hơn.

2.2.5.1. Dàn theo byte và dàn theo từ

Trong hầu hết các ngôn ngữ lập trình, một số nguyên được mã hóa trong bốn byte và giữ một giá trị giữa 0 và 232- 1, bao hàm. Chúng tôi giới hạn thảo luận để unsigned số nguyên, vì d -gaps luôn là số dương (và lớn hơn không). Điều này có nghĩa là rằng 1 và 4,294,967,295 đều chiếm bốn byte. Rõ ràng, mã hóa d –gaps cách này không mang lại bất kỳ việc giảm về kích thước nào.

Một phương pháp đơn giản để nén là để chỉ sử dụng như nhiều byte như là cần

thiết để đại diện cho các số nguyên. Điều này được gọi là chiều dài thay đổi số nguyên mã hóa (VarInt for short) và thực hiện bằng cách sử dụng các bit bậc cao của mỗi byte như các bit tiếp nối, được thiết lập để 1 trong byte cuối cùng và 0 ở nơi khác. Kết quả là, chúng tôi có 7 bit cho mỗi byte để mã hóa các giá trị, có nghĩa là 0 ≤ n <27 có thể được biểu diễn bằng 1 byte, 27≤ n <214 với 2 byte, 214≤ n <221 với 3 byte và 221≤ n <228 với 4 byte. Chương trình này có thể được mở rộng để mã số nguyên tùy tiện lớn (tức là, ngoài 4 byte). Là một ví dụ cụ thể, hai con số:

127, 128

sẽ được mã hóa như vậy:

1 1111111, 0 0000001 1 0000000

Đoạn mã trên có chứa hai từ mã, bao gồm đầu tiên là 1 byte, và thứ hai gồm 2 byte. Tất nhiên, dấu phẩy và không gian được xuất hiện chỉ để cho dễ đọc. Độ dài số nguyên (Variable-length integers) thay đổi được byte-aligned vì các từ mã luôn luôn rơi dọc theo ranh giới byte. Kết quả là, không có bất kỳ mơ hồ nào về nơi một từ mã số kết thúc và bắt đầu tiếp theo. Tuy nhiên, nhược điểm của varInt mã hóa là việc giải mã bao gồm rất nhiều hoạt động bit (masks, shifts). Hơn nữa, các bit tiếp tục đôi khi có kết quả trong mispredicts chi nhánh thường xuyên (frequent branch mispredicts) (phụ thuộc vào sự phân bố thực tế của d -gaps), làm chậm việc xử lý.

Một biến thể của sơ đồ varInt được mô tả bởi Jeff Dean trong một cuộc nói chuyện chủ đạo tại WSDM hội nghị năm 2009. Sự thấu hiểu là để code các nhóm bốn số nguyên tại một thời điểm. Mỗi nhóm bắt đầu với một byte tiền tố, chia thành bốn giá trị 2-bit, xác định độ dài byte của mỗi số nguyên theo sau. Ví dụ, các tiền tố byte sau:

00,00,01,10

chỉ ra rằng bốn số nguyên sau đây là một byte, một byte, hai byte, và ba byte, tương ứng. Do đó, mỗi nhóm bốn số nguyên sẽ tiêu thụ bất cứ nơi nào giữa 5 và 17 byte. Một bảng tra cứu đơn giản dựa trên các tiền tố byte hướng decoder tới việc làm thế nào để xử lý byte tiếp theo để thu hồi số nguyên được mã hóa. Ưu điểm của nhóm chương trình varInt mã hóa này là giá trị có thể được giải mã bằng mispredicts nhánh ít hơn và hoạt động trên bit. Các thí nghiệm báo cáo của Dean cho rằng giải mã số nguyên với chương trình này nhanh hơn gấp hai lần các chương trình varInt cơ bản.

Trong hầu hết các kiến trúc, truy cập toàn bộ từ máy hiệu quả hơn việc lấy tất cả các byte của nó một cách riêng biệt. Do đó, nó có ý nghĩa trong việc lưu trữ thông tin đăng trong gia số của 16-bit, 32-bit, hoặc 64-bit machine words. Anh và Moffat [8] trình bày một số phương pháp mã hóa word-aligned, một trong số đó được gọi là Simple-9, dựa trên các từ 32-bit. Trong lược đồ mã hóa này, bốn bit trong mỗi từ 32- bit được dành riêng như là một selector. 28 bit còn lại được sử dụng để mã thực tế các

giá trị số nguyên. Hiện giờ, có rất nhiều cách mà 28 bit này có thể được chia để mã hóa một hoặc nhiều số nguyên: 28 bit có thể được sử dụng để mã một số nguyên 28- bit, hai số nguyên 14-bit, ba số nguyên 9-bit (với một bit không sử dụng), vv, tất cả các cách lên đến hai mươi tám số nguyên 1-bit. Trong thực tế, có chín cách khác nhau 28 bit có thể được chia thành nhiều phần bằng nhau (do đó tên của kỹ thuật), một số với một vài bit chưa sử dụng còn sót lại. Chúng được lưu trữ trong các bit chọn. Vì thế, giải mã liên quan đến việc đọc một từ 32-bit, kiểm tra bộ chọn để xem như thế nào 28 bit còn lại được đóng gói, và sau đó giải mã mỗi số nguyên một cách thích hợp. Mã hóa các tác phẩm theo cách ngược lại: các thuật toán quét trước để xem có bao nhiêu số nguyên có thể được chia thành 28 bit, gói những số nguyên, và đặt các selector bit một cách thích hợp.

2.2.5.2. Mã theo bit

Ưu điểm của mã byte liên kết (byte-aligned) và từ canh (word-aligned) là chúng có thể được mã hoá và giải mã một cách nhanh chóng. Nhược điểm, tuy nhiên, là chúng phải tiêu thụ bội số của tám bit, ngay cả khi các bit ít hơn có thể suffice (sơ đồ Simple-9 nhận quanh điều này bằng cách đóng gói nhiều số nguyên vào một từ 32-bit, nhưng thậm chí sau đó, các bit thường bị lãng phí). Trong các mã bit-liên kết, mặt khác, các từ mã có thể chiếm bất kỳ số lượng bit nào, có nghĩa là ranh giới có thể rơi vào bất cứ nơi nào. Trong thực hành, mã hóa và giải mã các mã bit-canh yêu cầu xử lý byte và shifting hoặc masking bit một cách thích hợp (thường phức tạp hơn so varInt và nhóm varInt mã hóa).

Một thách thức nữa với mã byte-aligned là chúng ta cần một cơ chế để phân định từ mã, tức là, cho biết nơi kết thúc cuối cùng và bắt đầu tiếp theo, vì không có ranh giới byte để hướng dẫn chúng ta. Để giải quyết vấn đề này, hầu hết các bit liên kết mã được cái gọi là mã tiền tố (một cách dễ nhầm lẫn, chúng cũng được gọi là mã số tiền tố tự do - prefix-free codes), trong đó không có mã từ hợp lệ là một tiền tố của bất kỳ từ mã có giá trị khác nào. Ví dụ, mã hóa 0 ≤ x <3 với {0, 1, 01} không phải là mã tiền tố hợp lệ, vì 0 là một tiền tố của 01, và vì vậy chúng tôi không thể nói nếu 01 là hai từ mã hoặc một. Mặt khác, {00, 01, 1} là mã tiền tố hợp lệ, như vậy là một chuỗi các bit:

0001101001010100

có thể được tách ra rõ ràng thành:

00 01 1 01 00 1 01 01 00

và giải mã mà không cần bất kỳ ký tự phân cách bổ sung nào

Một trong những mã tiền tố đơn giản nhất là các mã nguyên phân. Một số nguyên x> 0 là ký hiệu là x - 1 một bit được theo sau bởi một zero bit. Lưu ý rằng mã

Golomb

unary 0

γ 0

x 1

b = 5 0:00

b = 10 0:000

10:0