Tìm hiểu về các hệ thống cơ sở dữ liệu lớn [phần 1], phần 2

Tìm hiểu về các hệ thống cơ sở dữ liệu lớn [phần 1]

n
Hôm vừa rồi có dịp lên lầu 2 siêu thị BigC đường Tô Hiến Thành, tán dóc với các anh Minh, Khải, Long, Tấn, Tiến của một cty rất trẻ và rất thành công. Trong vòng 5 năm họ đã xây dựng được một cơ đồ ấn tượng. Đố các bạn biết là cty nào? Tôi hiểu rằng họ đang phải giải quyết các vấn đề rất thú vị về các hệ thống CSDL khổng lồ và rất động. Điều này nằm ngoài tầm hiểu biết của tôi, vì thế tôi quyết định tìm hiểu thêm về các hệ thống CSDL lớn. Chuỗi bài này để bác Đoàn Ai Hải viết là thích hợp, nhưng chắc phải có mỹ nhân quân đội nhân dân Trung Của mới dụ được ẩn sĩ xuống núi.
Do nằm ngoài tầm hiểu biết, chuỗi bài này sẽ không tránh khỏi các sai sót cơ bản, mong các gurus góp ý thêm cho. Nhắc đến CSDL thì tôi lại nhớ đến đồ án tốt nghiệp đại học năm cuối ở ĐHBK của mình. Hồi đó tôi làm một CSDL quản lý cty du lịch dùng MS Access mà sau nghĩ lại thấy rất tầm thường. Được 7 hay 8 điểm gì đó là may lắm rồi mà vẫn nghĩ mình đáng lẽ phải được nhiều điểm hơn. Đến khi apply học sau đại học vẫn còn ghi trong statements of purpose là muốn làm về CSDL mà thật sự chẳng hiều là mình muốn làm gì.
Trước hết, phải xem là các CSDL cỡ nào thì gọi là lớn. Và người ta dùng cái gì để quản lý và phân tích chúng. Ở đây có một danh sách các CSDL khổng lồ. Nhớ rằng một petabyte bằng một triệu gigabyte.

• eBay có khoảng 6 1/2 petabyte dữ liệu, chạy trên Greenplum và một mớ 2 1/2 petabyte dữ liệu kinh doanh trong một data warehouse chạyTeradata. Greenplum là một hệ thống CSDL song song khổng lồ (MPP-DBMS hay massively parallel processing DBMS) dựa trên nềnPostgreSQL. Gần đây Greenplum còn thêm vào các mở rộng dựa trên MapReduce. Bài tới chúng ta sẽ tìm hiểu về MapReduce. Teradata là một MPP-DBMS khác.
• Facebook có datawarehouse cỡ 2 1/2 petabyte chạy trên nền Hadoop/Hive. Hadoop là một implementation của MapReduce.
• Wal-Mart, Bank of America, một công ty dịch vụ tài chính khác, và Dell cũng có các CSDL rất lớn chạy chạy trên Teradata.
• CSDL chứa web/network events của Yahoo chạy trên hệ thống họ tự phát triển, có lẽ bằng khoảng 1/6 kích thước của hệ thống Greenplum của eBay.
• Fox Interactive Media/MySpace có nhiều trăm terabytes chạy Greenplum và Aster Data nCluster.
• TEOCO có nhiều trăm terabytes chạy trên DATAllegro. Năm 2008 Microsoft mua DATAllegro, cho nên dù trước đó nó dựa trên Ingres nền Linux, bây giờ thì không biết có chuyển sang MS SQL Server không.
• Vertica có vài khách hàng với các CSDL cỡ 200 terabyte. Vertica do Michael Stonebraker đồng sáng lập.
• Sẽ rất thiếu sót khi nói về CSDL lớn mà không nói đến Google. Hệ thống phần mềm của Google quản trị dữ liệu bao gồm 4 thành phần chính:Chubby, Google File System, Bigtable và MapReduce. Chubby là một dịch vụ khóa cho một hệ thống phân bố. MapReduce ta sẽ tìm hiểu sau. Google File System là một distributed file system thiết kế cho scalability. Bigtable là một hệ thống CSDL phân bố gọn nhẹ. Chi tiết về phần cứng của Google nghe nói trong quyển sách của Stross là Google giấu giếm kỹ, dù ta http://research.google.com/archive/googlecluster.html là nó có vài chục đến vài trăm ngàn servers trên PC chạy một phiên bản đã chỉnh sửa của Linux. Tôi không tìm được nguồn đáng tin cậy, http://leekaikai.blogspot.com/2007/08/how-big-is-google-database.html Google chứa vài nghìn terabytes dữ liệu.

Về phần giá cả thì làm chủ một datawarehouse bao gồm giá ban đầu, giá bảo trì, và giá upgrade. Giá ban đầu nghe đâu từ 10K đến 150K đô la cho mỗi terabyte. Giá bảo trì chiếm đến khoảng 80% tổng chi phí.
Rất tình cờ là tờ CACM số 1 năm 2010 lại đăng một cuộc “cãi vã” nho nhỏ về MapReduce vs. MPP-DBMS. Có vẻ như hai phe ủng hộ MapReduce/Hadoop và phe ủng hộ MPP-RDBMS đã tranh luận và, quan trọng hơn, tranh thị trường từ vài năm đổ lại đây. Xem các bài này, vàbài này, bắt đầu từ một bài blog của Stonebreaker và DeWitt mà bây giờ không còn tìm thấy nguyên bản ở website của họ (có hai bài: bài 1, bài 2), và sau đó bị phê phán nhiều. Có vài myths về MapReduce có thể xem ở đây.
Lần tới (không biết khi nào vì sắp Tết đến nơi) chúng ta sẽ tìm hiểu về MapReduce, sau đó tìm hiểu về MPP-DBMS, rồi bàn về cuộc chiến giữa chúng.


Tìm hiểu về các hệ thống cơ sở dữ liệu lớn [phần 2]

in
Bài này tìm hiểu sơ lược về MapReduce (viết tắt là MR). MR là một “mô hình lập trình” (programming model), lần đầu báo cáo trong bài báo của Jefferey Dean và Sanjay Ghemawat ở hội nghị OSDI 2004. MR chỉ là một ý tưởng, một abstraction. Để hiện thực nó thì cần một implementation cụ thể. Google có một implementation của MR bằng C++. Apache có Hadoop, một implementation mã nguồn mở khác trên Java thì phải (ít nhất người dùng dùng Hadoop qua một Java interface).
Thử tưởng tượng ta có nhiều terabytes dữ liệu phân bố trong một cluster của hàng ngàn máy PCs biệt lập (cấu hình share nothing), và ta có rất nhiều dự án khác nhau cần dùng và phân tích mớ dữ liệu này. Việc chứa dữ liệu (có replication) trong các data centers dùng commodity computers và commodity network devices là một chiến lược thành công của Google. Nghe đâu chiến lược này đã giúp họ tiết kiệm rất nhiều tiền thay vì dùng vài high-end servers. Khối dữ liệu này đại khái là một tập hợp của nhiều tỉ cặp (key, value). Với Google thì có thể key = file_name và value = file content, hoặc key = URL và value = URL content, vân vân. Do chúng ta không lường trước được các bài toán phân tích khối dữ liệu này trong tương lai là gì, độ phức tạp ra sao, dùng các kiểu hàm số gì, … cho nên việc đưa các cặp (key, value) này vào một MPP-DBMS sẵn “có thể” không phải là chiến lược tối ưu; tại vì khi đưa dữ liệu vào một MPP-DBMS thì ta cần thiết kế một schema, và các bài toán phân tích dữ liệu trong MPP-DBMS sẽ có thể bị ràng buộc bởi cái schema đó.
Vì thế, Google quyết định thiết kế MR để cung cấp chỉ một vài primitives thật đơn giản để truy cập và xử lý mớ dữ liệu này . Một implementation của MR sẽ tự động song song hóa quá trình tính toán, và bảo đảm tính chịu đựng lỗi, sao cho tính toán được chính xác và hiệu quả nhất. Như vậy, các primitives phải được thiết kế thế nào đó để cho (1) thật đơn giản, (2) có tính biểu cảm cao để người dùng có thể dùng chúng làm nhiều tác vụ tính toán khác nhau, (3) có thể song song hóa được. Ngoài ra, để cho MR thật sự hiệu quả, thường các implementation đòi hỏi một phải chạy MR trên với một distributed file system thích hợp, ví dụ như Google File System (GFS), Amazon S3, hoặc là Hadoop distributed file system (HDFS).
Lấy ý tưởng từ lập trình hàm, MR có hai primitives cơ bản là Map và Reduce. Đó là lý do tại sao mô hình lập trình này được gọi là MR. Map và Reduce là các combinators phổ dụng trong các ngôn ngữ lập trình hàm như Lisp.
Để xử lý khối dữ liệu bao gồm rất nhiều cặp (key, value), lập trình viên viết hai hàm map và reduce. Hàm map có input là một cặp (k1, v1) và output là một danh sách các cặp (k2, v2). Chú ý rằng các input và output keys và values có thể thuộc về các kiểu dữ liệu khác nhau, tùy hỉ. Như vập hàm map có thể được viết một cách hình thức như sau:
map(k1,v1) -> list(k2,v2)

MR sẽ áp dụng hàm map (mà người dùng MR viết) vào từng cặp (key, value) trong khối dữ liệu vào, chạy rất nhiều phiên bản của map song song với nhau trên các máy tính của cluster. Sau giai đoạn này thì chúng ta có một tập hợp rất nhiều cặp (key, value) thuộc kiểu (k2, v2) gọi là các cặp (key, value) trung gian. MR cũng sẽ nhóm các cặp này theo từng key, như vậy các cặp (key, value) trung gian có cùng k2 sẽ nằm cùng một nhóm trung gian.
Giai đoạn hai MR sẽ áp dụng hàm reduce (mà người dùng MR viết) vào từng nhóm trung gian. Một cách hình thức, hàm này có thể mô tả như sau:
reduce(k2, list (v2)) -> list(v3)Trong đó k2 là key chung của nhóm trung gian, list(v2) là tập các values trong nhóm, và list(v3) là một danh sách các giá trị trả về của reducethuộc kiểu dữ liệu v3. Do reduce được áp dụng vào nhiều nhóm trung gian độc lập nhau, chúng lại một lần nữa có thể được chạy song song với nhau.
Ví dụ cơ bản nhất của MR xuất hiện trong bài báo của Dean và Ghemawat: với mỗi từ (tiếng Anh chẳng hạn) xuất hiện trong một bộ rất nhiều files, đếm số lần xuất hiện của từ. Rõ ràng đây là một bài toán cơ bản và quan trọng mà một search engine phải làm. Nếu chỉ có vài chục files thì dễ rồi, nhưng nhớ rằng ta có nhiều triệu hay thậm chí nhiều tỉ files phân bố trong một cluster nhiều nghìn máy tính. Ta lập trình MR bằng cách viết 2 hàm cơ bản với pseudo-code như sau (copy từ bài báo):
void map(String name, String document): // name: document name // document: document contents for each word w in document: EmitIntermediate(w, "1"); void reduce(String word, Iterator partialCounts): // word: a word // partialCounts: a list of aggregated partial counts int result = 0; for each pc in partialCounts: result += ParseInt(pc); Emit(AsString(result));Chỉ với hai primitives này, lập trình viên có rất nhiều flexibility để phân tích và xử lý các khối dữ liệu khổng lồ. MR đã được dùng để làm rất nhiều việc khác nhau, ví dụ như distributed grep, distributed sort, web link-graph reversal, term-vector per host, web access log stats, inverted index construction, document clustering, machine learning, statistical machine translation, large-scale graph computation … Khi implementation của MR được hoàn tất ở Google, MR đã được dùng để tái tạo toàn bộ Google index của WWW. Có thể xem mấy lectures này để thấy làm thế nào dùng MR giải quyết các vấn đề như distributed PageRank, thuật toán tìm được đi ngắn nhất của Dijkstra, các thuật toán clustering như k-means và kanopy, vân vân.
Đến đây chúng ta có thể kết luận sơ bộ là MR là một mô hình hùng mạnh, các primitives đơn giản của nó có thể dùng đề làm nhiều việc phân tích và xử lý dữ liệu khổng lồ môt cách hiệu quả. Năm ngoái Hadoop lập kỷ lục thế giới về sorting khối dữ liệu lớn (sort một petabyte trong 16 tiếng, và một terabyte trong 1 phút). Nghe đâu mỗi ngày có đến vài nghìn hay vài chục nghìn chương trình MR được chạy ở Google, chưa tính đến biết bao cty khác trên thế giới. Tuy nhiên, MR hiển nhiên không phải là thuốc chữa bá bệnh. Tùy theo bản chất bài toán của mình là gì mà chúng ta sẽ phải quyết định xem MR có phải là một framework thích hợp hay không.
Có lẽ, một trong các dấu hiệu cho thấy MR là giải pháp tốt là phần đã víết ở trên: khối lượng dữ liệu khổng lồ và các tác vụ phân tích và tính toán phức tạp và không lường trước được (ví dụ như các tác vụ liên quan đến hiện thực hóa các mô hình thống kê, data mining, hay các mô hình vật lý cực kỳ phức tạp với dữ liệu từ các máy gia tốc hạt, hoặc các mô hình dự báo khí tượng thủy văn). Trong trường hợp đó, một MPP-DBMS có lẽ là hơi bị hạn chế. Ngoài ra, nếu có một tác vụ tính toán nào đó chỉ cần làm 1 hoặc 2 lần thì MR có lẽ cũng tốt hơn, vì thời gian thiết kế và load một khối DL khổng lồ vào một MPP-DBMS không nhỏ, chẳng kém thời gian chạy thẳng MR luôn. Như Dean và Ghemawat và nhiều người khác đã chỉ ra, MR là một công cụ rất tốt để biến dữ liệu thô thành dữ liệu sẵn sàng để load vào DBMS!
Theo: http://www.procul.org/blog/2010/02/0...l%E1%BB%9Bn-2/