Home > Programming > Hoạt động của MapReduce

Hoạt động của MapReduce

Map
Để thao tác Map có thể thực hiện song song, tập hợp các file input trước tiên được cắt thành nhiều phần gọi là FileSplits. Nếu 1 file quá lớn có thể ảnh hưởng đến thời gian tìm kiếm, nó sẽ được cắt thành nhiều phần nhỏ. Các phần này không biết gì về cấu trúc logic bên trong của file, nên 1 file có cấu trúc hàng cũng có thể bị cắt theo giới bạn byte. Sau đó, 1 nhiệm vụ map mới sẽ được tạo ứng với mỗi FileSplit.

Khi một nhiệm vụ map bắt đầu, nó sẽ mở ra một output writer cho mỗi nhiệm vụ reduce đã được cấu hình. Sau đó sẽ dùng RecordReader từ một InputFormat cụ thể để đọc FileSplit của nó. InputFormat phân tích input và sinh ra các cặp key-value. InputFormat cũng thụ lí các ghi chép nằm ngay đường biên của FileSplit. Ví dụ TextInputFormat đọc luôn dòng cuối cùng của FileSplit, và bỏ đi nội dung dòng đầu tiên của những FileSplit thứ 2 trở đi.

InputFormat không nhất thiết sinh ra những cặp key-value có nghĩa. Ví dụ output mặc định của TextInputFormat gồm value là hàng của input và key là độ dịch của hàng trong file, hầu hết các ứng dụng không quan tâm độ dịch này.

Khi được đọc từ RecordReader, các cặp key-value sẽ được truyền cho các mapper đã cấu hình. Mapper mà người dùng cung cấp có thể làm bất cứ điều gì họ muốn với các cặp key-value nhập vào và gọi OutputCollector.collect để thu thập các cặp key-value mà họ định nghĩa. Output nhất định phải sử dụng 1 lớp key và 1 lớp value. Chính là vì output của Map phải được viết vào SequenceFile có thông tin về loại file và ghi chép đều cùng 1 kiểu (sử dụng lớp con nếu muốn xuất ra cấu trúc dữ liệu khác). Input và output của Map không cần có quan hệ gì về kiểu hoặc về tập hợp.

Khi output của Mapper được thu thập, chúng sẽ được chia khu viết vào output theo chỉ định của Partitioner. HashPartitioner mặc định dùng hàm hashcode của lớp key (nên hàm hashcode cần phải ưu để cân bằng lượng công việc trên các nhiệm vụ reduce).

N files input sinh ra M nhiệm vụ map và mỗi map sẽ sinh ra số file output tương ứng với số nhiệm vụ reduce đã được cấu hình trong hệ thống. Mỗi file output đều cho 1 reduce nhất định và các cặp key-value của 1 key nhất định sinh ra từ tất cả các map sẽ được truyền cho một reduce nhất định.
Combine
Khi map sinh ra các cặp key-value thì những cặp này đã tồn tại trong bộ nhớ. Để tăng hiệu xuất, có thể cung cấp 1 lớp combiner để làm nhiệm vụ thu gọn trước. Nếu dùng lớp combiner thì các cặp key-value không viết liền vào output. Thay vào đó chúng được gom lại trong lists, mỗi key có 1 lists. Khi một lượng nhất định key-value đã được viết, buffer đó sẽ truyền hết cho thao tác thu gọn của combiner và xuất ra các cặp dạng tương tự như map xuất ra.

Ví dụ, trong ứng dụng word count của Hadoop, map xuất ra dạng các cặp (word, 1) đều có thể dùng combiner để xử lí nhanh hơn. Chức năng thu gọn sẽ thu gom output trong lists của bộ nhớ, mỗi từ 1 list. Khi có một lượng nhất định các cặp key-value được xuất vào bộ nhớ, chức năng thu gọn sẽ được gọi để gom lại mỗi word 1 list, và xuất ra dạng (word, số lượng word này trong phần này). Nhìn từ Reduce thì chức năng thu gọn cũng xuất ra giống như Map, nhưng số lượng các cặp đã giảm đi rất nhiều so với thao tác trên ổ cứng.
Reduce
Input của 1 nhiệm vụ reduce phân tán trong nhiều file khắp các node (vừa chạy map). Trong mô hình phân bố, trước tiên chúng cần được copy về local filesystem (copy phase).

Khi tất cả dữ liệu đã sẵn sàng trên node chạy reduce, chúng được lưu vào 1 file (append phase). Lúc đó, file này đã được sắp xếp để các cặp có key giống nhau nằm kề nhau. Do đó thao tác reduce trở nên đơn giản: file được đọc tuần tự vào, các value được tuần tự đưa vào cho đến khi gặp key kế tiếp.

Cuối cùng, mỗi nhiệm vụ reduce xuất ra 1 file output. Định dạng file có thể được JobConf.setOutputFormat chỉ định. Nếu dùng SequentialOutputFormat thì cần phải chỉ định lớp key và lớp value.

English version

Categories: Programming Tags: ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: