Blog Khoa Học Máy Tính

Trong chùa Vĩnh Nghiêm có cái phòng đựng cốt. Ai có tiền thì để cốt thân nhân vào đấy, đóng tiền hàng năm. Ít tiền thì cốt để lên cao, sâu bên trong. Nhiều tiền thì cốt ở ngoài, chỗ thấp dễ với. Chẳng hiểu dễ với để làm gì. Đến dịp lễ tết lại tốn tiền hương hoa, bốn năm anh đầu trọc béo tốt gõ mõ tụng kinh siêu độ điền vào khoảng trống: “Nam mô a di đà Phật, cầu cho thí chủ XYZ được siêu thoát”, trong đó XYZ là một dòng trong danh sách các thí chủ được tụng cho hôm đó. Các sư phụ giỏi thật, khói nhang nghi ngút mà không thấy chảy nước mắt bao giờ. Hay là có trang bị loại contact lense đặc dị.

Còn bọn nhà nghèo cho chúng chết không siêu thoát. Ai bảo nghèo! À, đúng ra thì cầu siêu sỉ: rằm tháng 7 hàng năm. Hồn nghèo nào thoát được thì thoát, không được thì cũng chẳng ai biết là ai.

Trên chính sảnh có một bảng đỏ to vật vã. Ý viết rằng chùa cần xây sửa, và đã được phép của Ủy Ban Nhân Dân P. x Q. y; mong thiện nam tín nữ giúp cho chùa một ít “công đức”.

Ở đâu công đức đo đếm thế nào không biết, ở xứ ta “công đức” nhét được vào một cái thùng trông như thùng phiếu. Nếu mà công đức nhiều, chắc chùa sẽ xây thêm một phòng để đựng cốt.

Khuôn viên ấy, diện tích ấy, “công đức” ấy mà xây một trại trẻ mồ côi, cái bệnh viện miễn phí hay một “trường quốc tế” cho con nhà nghèo, thì … công đức bút nào tả xiết.

Các chùa hẳn phải có một hệ thống tiêu thụ trái cây thừa hoạt động hiệu quả; nhỉ. Không biết có hòa thượng nào đi lấy lớp kiểm toán không. Rò rỉ công đức thì chỉ có Phật biết.

Cuối tháng 2 vừa rồi, khá nhiều công đức đã hao tổn khi mà “3 viên xá lợi Phật và 6 viên xá lợi thánh tăng sẽ được Giáo hội Phật giáo Việt Nam chuyển về từ Ấn Độ bằng một chuyên cơ riêng … Từ sân bay Nội Bài, Ngọc xá lợi phật được chuyên chở trên 5 chiếc xe Hammer H3 và Cadillac đặc dụng với sự tháp tùng của hàng trăm ôtô về chùa Bái Đính, Ninh Bình.”

Đi chuyên cơ, Hummer, với Cadillac thì khi nào mới thoát khỏi Vô Minh?

Hồi xưa đọc Tây Du Ký thấy có phép phân thân, tưởng là bịa, hóa ra có thật. Rằm tháng giêng và 24 tháng tư Âm Lịch ngày vía Bà thì người xe như nước, áo quần như nêm, hành hương về chùa bà Châu Đốc ở An Giang. Nay lại có thêm Châu Đốc 2 ở huyện Nhà Bè, và Châu Đốc 3 ở phường Phước Long quận 9. “Châu Đốc” biến thành cái franchise như gà rán KFC. Mà franchise thì “location” tuyệt đối quan trọng. Muốn “làm việc gì có ích cho những người khốn khó”, hãy mua tour đi chùa Phước Long, 250 nghìn một lượt.

Ở miền Tây có cái chùa gì đó cũng có tiếng, bạn kể mà quên mất rồi. Đường vào chùa bà con xây nhà lấn đường, dần dần biến thành cái hẻm nhỏ. Sư trụ trì tâm sự với khách thập phương: “thầy sắp bán đất này, rời chùa ra mặt tiền”. Công nhận thầy nhạy bén.

Mấy năm nay còn có thêm sáng kiến nhét thẳng tiền vào tay tượng Phật. Chắc sợ đưa tiền cho bọn “cò” béo tốt sẽ bị thất lạc, Phật không thấy tiền sẽ không biết lòng thành đến đâu.

Đi thì đại học thì bao sĩ tử vào Văn Miếu lạy lục. Có thai thì bắt bác sĩ mổ lấy con ra sớm (năm Sửu) vì sợ con gái sinh năm Dần. Lấy bê-tông bít cổng trường học vì Phong Thủy. Muốn khấn thì đã có khấn thuê. Quan chức thì đi “mua” ấn nhân lễ Khai Ấn ở đền Trần.

Thế kỷ thứ mấy rồi nhỉ?

Chuyên mục: Vượt định kiến | Bình luận (23) »

Chuyên mục: Vui - Giải Trí | Bình luận (4) »

• Một
• Hai
• Ba

Chuyên mục: Vui - Giải Trí | Bình luận »

Trường NTU có cơ sở vật chất thật ấn tượng. Thích nhất là có cái hồ bơi giống hồ bơi ở “nhà”. Kiến trúc hơi nhàm, nhưng các buildings đều rất hiện đại, sạch sẽ, thoáng mát.

Đảo quốc sư tử chưa từng có sư tử sống. Với dân số khoảng 5 triệu, già nửa Sài Gòn, mật độ dân số ở đây đặc thứ 2 trên thế giới, chỉ sau Monaco. Trưởng nam họ Lý vừa là chuẩn tướng trẻ nhất trong lịch sử quân đội Singapore, vừa là thủ tướng có mức lương cao nhất thế giới. Năm nay anh ấy cho cái này vào hoạt động (phần dưới đã xong, phần trên gần xong).

Ăn uống ở Boat Quay đắt quá đáng thể. Ăn trong căng tin trường hay ở các khu dân cư thì rất rẻ.

Khu Geylang có các phố đèn đỏ, ở các Lorongs số chẵn, rất nhiều gái điếm người Việt. Nghe bảo chính phủ Singapore nhận ra nhu cầu này của dân và của lao động ngoại quốc, cho nên không cấm nhưng cũng không cho mời chào lộ liễu.

Đảo quốc Temasek có mức sống đắt thứ 3 châu Á, chỉ sau Tokyo và Osaka. Kể ra sống chui rúc trong một trong cơ man nào là các chung cư ở đây lâu thì mất vui, sống như kiến. Đi vào các khu nhà HDB flats có cảm giác như vào một cái tủ chứa đồ bẩn và thừa trong một căn nhà được dọn dẹp bề ngoài rất cẩn thận. Được cái là có các quán dim-sum rất ngon.

Bọn expats thì có lẽ thường thuê condos, tùy theo vị trí, giá cả nằm trong khoảng 1000usd đến 3500usd một tháng. Các khu này nhà cửa hiện đại hơn, có hồ bơi và phòng tập.

Mua một cái xe ô tô ở Sing, đi 5, 7 năm, thì dùng số tiền đó mua một căn hộ ở Sài Gòn cũng được.

Sentosa là một cái nhà tù. Vào 3 bước là muốn đi ra. Sau 10 bước thì quay ra luôn.

Xuống Changi beach thấy các bạn Malay giăng lều võng ngủ đêm ở bờ biển rất vui; khác hẳn không khí ngột ngạt trong Orchard. Chắc tại mình già. Hay là mình trẻ hẳn ra?

Đại để là thế, cưỡi ngựa xem hoa.

Chuyên mục: Chưa phân loại | Bình luận (9) »

Hôm nay mùng một tết. Thay cho lời chúc, xin chôm bài của “người quen” để lên đây mời các bạn đọc.

TTXuân – Con gái thương, năm nay mẹ con mình đón tết ở Việt Nam, con nhé. Không như mẹ, con chưa biết nôn nao trước một hành trình. Nhưng con cũng đã biết hoan hỉ đón nhận nó. Con vào lớp dõng dạc thông báo với các cô và các bạn rằng “con sắp được đi Việt Nam”.

Việt Nam, với con, cũng giống như nhà hát, hứa hẹn những điều mới mẻ, khác nhịp sống ngày thường.

Cũng như con biết đi sở thú sẽ được xem hươu cao cổ, con biết về Việt Nam sẽ được ngồi xe gắn máy với ba mẹ, được đội mũ bảo hiểm (chứ không phải thắt dây an toàn) và được đi thăm ông bà. Con chưa biết vì sao mẹ nhẩm tính từng ngày, hay vì sao ba nói với bạn bè rằng trở về đón lại Tết Việt Nam là điều lẽ ra phải làm đã từ lâu lắm. Và con cũng không hiểu được vì sao khi các cô nhà trẻ hỏi có phải gia đình mình sắp đi Việt Nam không, thì mẹ đã “nhắc nhở” ngay rằng mình “về” chứ không phải “đi” Việt Nam.

Con mở lòng đón nhận mọi thứ trong cuộc sống ba năm tuổi như một mảng đất tơi khát nước, không phân biệt điều gì là nhỏ bé còn điều gì là lớn lao.

Con sẽ tròn xoe mắt nhìn nếu mẹ dùng những ngôn từ sách vở như cội nguồn, truyền thống, tổ tông. Với con, gần nhất và thật nhất là ba, là mẹ, là ngôi nhà nằm cạnh vạt rừng, là chiếc giường màu trắng và cái chăn màu xanh mà con ôm ngủ hằng đêm. Con cũng sẽ ngơ ngác nếu mẹ nói với con về khoảng cách. Con biết ông bà sinh ra ba mẹ, biết ba mẹ sinh ra ở Việt Nam.

Con không biết Việt Nam và nơi con sinh ra cách nhau nửa vòng trái đất, nên cũng không thể biết được các bạn của con đón lễ Tạ ơn cùng ông bà ở cách nhà các bạn một tiểu bang thì có khác gì ngày Tết, con thăm ông bà ở cách nhà mình hàng chục nghìn cây số.

Con cũng không biết thế giới đã đổi thay nhiều và nhanh đến thế nào. Nhiều chục năm trước, ông bà rời quê đi lập nghiệp cách vài trăm cây số mà đã thấy thăm thẳm xa. Giờ thì ba mẹ, cũng như hàng triệu gia đình trẻ, đang học hành và làm việc cách nơi sinh thành hai ba chặng máy bay vượt đại dương.

Ngày xưa, ông ngoại thèm nước mắm Phan Thiết phải chờ người nhà đi xe đò chở vào, ròng rã cả ngày đêm mới đến. Bây giờ, bà nội ở Sài Gòn đã nhìn thấy con tập ngồi tập đứng qua những cuộc điện thoại kèm hình ảnh hằng ngày, còn ba mẹ thì luôn sẵn đậu hũ mắm tôm và rau kinh giới trong bếp. Những khoảng cách tưởng chừng bất tận đều đã được nối liền, những điều dường như không thể đã trở thành một phần của cuộc sống trong thời đại mới.

Con đang lớn lên trong cuộc sống ấy, thời đại ấy. Con thích Bạch Tuyết và bảy chú lùn, thích chuột Mickey, con cũng thích sự tích Lang Liêu gói bánh, và thích xem đĩa phim ca nhạc có bài “bà còng đi chợ…”. Con đến trường, học nói tiếng Anh, học trang trí cây thông, ăn gà tây và mì ống.

Nhưng con cũng đang phả một phần đặc tính của gia đình mình vào lớp học – con mặc áo dài dự tiệc hóa trang làm các cô trầm trồ cả buổi, con hát “kìa chú là chú ếch con” vang lừng trong lớp, con đem mũ bảo hiểm xe máy vào cho các bạn thay phiên nhau đội cho vui. Nhờ con, cô giáo Ruth hào hứng chọn Sài Gòn làm địa điểm để thiết kế mô hình nhà trẻ quốc tế (cô rất chăm chú ghi nhận chuyện trẻ con Việt Nam bỏ tã sớm hơn trẻ con Mỹ đến cả năm!), còn ba mẹ của các bạn con thì được hướng dẫn làm món gỏi bưởi trong bữa ăn gia đình.

Nhìn con tung tăng trong cuộc sống tự nhiên như thở, đôi khi mẹ tự hỏi có cần phải áp đặt những thứ mẹ cho là quý giá vào trái tim hồn nhiên của con hay không. Mẹ chỉ muốn cùng con về Việt Nam đón Tết, để con hóa thân làm em bé phụ gói bánh như trong truyện Lang Liêu, ăn dưa hấu như truyện An Tiêm, sắp mâm ngũ quả và mặc váy mới đi chợ hoa như bài hát Tết trong phim ca nhạc.

Mẹ muốn con được sống trong thế giới mà có lẽ cho đến giờ này với con chỉ là một câu chuyện cổ tích như hàng trăm chuyện cổ tích khác mà con được nghe ba mẹ kể. Mẹ muốn con được làm tất cả những điều ấy dù mẹ biết với con gái ba tuổi, ấn tượng bánh chưng hay hoa đào Tết cũng không khác ấn tượng Lọ Lem hay Bạch Tuyết ở Disneyland.

Con chưa có trong vốn từ của mình những định nghĩa lớn lao, nhưng con đang đi tiếp con đường nối dài trong hành trình đến tương lai của tổ tiên, ông bà và ba mẹ – hành trình bắt đầu từ nghìn năm trước. Mẹ tin một ngày nào đó con sẽ tự mình khám phá những xúc cảm với cội nguồn theo cách của con, trong thời đại và thế giới của con. Con sẽ tự biết hương vị Tết có gì khác với sắc màu Disneyland. Còn lần này, mẹ con mình sẽ chỉ đón Tết và giành nhau miếng bánh chưng xanh thẳm – thế thôi, con gái nhé.

Chuyên mục: Chưa phân loại | Bình luận (15) »

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 reduce thuộ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!

Chuyên mục: Các hệ thống máy tính & Cơ sở dữ liệu | Bình luận (1) »

Điều gây ngạc nhiên là Google có một quảng cáo ở Superbowl năm nay, chôm ý tưởng của Thaidn:

Chuyên mục: Vui - Giải Trí | Bình luận (1) »

Trong bài “what should we teach new software Developers? why?“, cha đẻ của C++ viết:

Also, many students fail to connect what they learn in one class to what they learn in another. Thus, we often see students with high grades in algorithms, data structures, and software engineering who nevertheless hack solutions in an operating systems class with total dis- regard for data structures, algorithms, and the structure of the software. The result is a poorly performing unmain- tainable mess.

Có lẽ software engineering là lớp khó dạy và khó học nhất trong tất cả các lớp của KHMT. Mười mấy năm trước, tôi lấy 3 lớp SE, được A tất cả, mà vẫn không biết gì về SE. Lý do chính là trong khuôn khổ của một học kỳ, làm thế nào có thể truyền tải được việc xây dựng một hệ thống phần mềm lớn mà trên thực tế đa phần cần nhiều năm để hiện thực hóa. Trước hết, người thầy phải có kinh nghiệm này, nhưng những người có kinh nghiệm xây dựng các hệ thống phần mềm lớn thì họ sẽ đi … xây dựng các hệ thống phần mềm lớn chứ đâu có đi dạy! Các sinh viên thông minh và chịu khó mày mò, chơi và viết mã nguồn mở chẳng hạn, sẽ có nhiều kinh nghiệm SE hơn thầy!

Bài này Strousrup viết rất tốt.

Chuyên mục: Công nghệ phần mềm | Bình luận (2) »

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ạy Teradata. 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ền PostgreSQL. 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 biết sơ lược 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, có vẻ như 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.

Chuyên mục: Các hệ thống máy tính & Cơ sở dữ liệu | Bình luận (9) »

93. 100 hành khách lên xe lửa đi chuyến Bắc Nam. Xe lửa có 100 ghế. Tèo lên trước, thay vì ngồi đúng số ghế của mình thì Tèo ngồi vào một nghế ngẫu nhiên. Các hành khách sau đó, từng người một, ngồi vào đúng ghế trên vé nếu ghế trống, nếu không thì ngồi vào ghế trống ngẫu nhiên. Hỏi: xác suất mà hành khách cuối cùng ngồi đúng ghế là bao nhiêu?
94. Câu 94 lấy từ blog của giáo sư Gil Kallai.
    

Chuyên mục: Dành cho du học sinh & Vui - Giải Trí | Bình luận (6) »

Theo tờ Sunday Times, một tài liệu “bị lộ” của tổ chức phản gián MI5 của Anh cho biết nhiều doanh nhân Anh bị các bạn Trung Của gài bẫy bằng mỹ nhân kế và các phương tiện khác để phải tiết lộ bí mật kinh doanh. Một trong các bẫy khác là các bạn Trung Của tặng cho các doanh nhân các ổ USB có gài rệp, hoặc các máy chụp ảnh. Dùng các ổ USB này thì các con rệp sẽ cho phép các bạn Trung Của truy cập máy tính từ xa. Các “mỹ nhân” thì là gián điệp của quân đội nhân dân Trung Của. Các phòng khách sạn mà chính khách hay doanh nhân thường vãng lai cũng bị cài rệp.

Lần sau đi hội nghị nào do các bạn Trung Của tổ chức, gặp các em groupies, thì các bác cẩn thận, nhất là bác An Hải có nhiều groupies.

Chuyên mục: Bảo mật và mật mã học | Bình luận (5) »

6. Thử nhóm bất ứng biến giải mã nhanh

6.1. Ý tưởng của Kautz-Singleton

Hồi 1964, Kautz và Singleton đề xuất cách xây dựng ma trận -phân-cách dựa trên hai ý tưởng chính. Thứ nhất là nếu các cột của ma trận có “cân nặng” (số số trên cột) đủ lớn và nếu hai cột bất kỳ có phần giao đủ nhỏ thì ma trận sẽ là ma trận phân cách. Thứ hai là ta có thể dùng phương pháp nối mã (code concatenation) để xây dựng một ma trận thỏa tính chất thứ nhất. Chúng ta thảo luận ý tưởng của Kautz-Singleton trước, sau đó chỉ ra cách dùng ý tưởng này và một ý mới để xây dựng ma trận phân cách giải mã nhanh được.

Bổ đề 1 Gọi là một ma trận nhị phân mà mỗi cột có cân nặng ít nhất là , và phần giao của hai cột bất kỳ (các số chung của hai cột) có lực lượng nhiều nhất là . Thì, là ma trận -phân-cách với bất kỳ nào thỏa mãn . Cụ thể là sẽ là ma trận -phân-cách.

Bổ đề này dễ chứng minh. Ta nói tiếp ý tưởng thứ hai. Trước hết hãy định nghĩa phép nối mã.

Gọi là một mã , nghĩa là một ánh xạ từ vào , trong đó . (Phép nối mã có thể định nghĩa tổng quát hơn, nhưng ta không cần điều đó.) Như vậy, mỗi ký tự mã của là một thành viên của tập gồm phần tử, và vì thế cũng có thể xem như một thành viên của tập . Mỗi một từ mã của có vị trí. Mã sẽ được gọi là mã ngoài (outer code).

Đọc tiếp toàn bài »

Chuyên mục: Combinatorics & Lý thuyết mã hóa & Thuật Toán | Bình luận (2) »

5. Sơ lược lý thuyết mã hóa

Claude Shannon là cha đẻ của lý thuyết thông tin và lý thuyết mã hóa. Sẽ không có truyền thông hiện đại nếu không có Shannon. Nhà toán học lỗi lạc Kolmogorov từng nói về Shannon như sau: “Trong thời buổi mà kiến thức nhân loại càng lúc càng đuợc chuyên môn hóa, Claude Shannon là một nhà khoa học ngoại lệ. Shannon kết hợp các ý tưởng toán học sâu sắc với các hiểu biết rộng và cụ thể của các vấn đề quan trọng bậc nhất của công nghệ. Shannon là một trong những nhà toán học vĩ đại nhất đồng thời là một trong những kỹ sư giỏi nhất trong vài thập niên qua”. Nếu câu nói đó được phát biểu lúc này, thì phải thay “vài thập niên qua” bằng “thế kỷ 20″. Bài này duyệt qua một số kiến thức cơ bản về lý thuyết mã hóa cần cho thử nhóm.

5.1. Ý tưởng của Shannon (và Hamming)

Ý tưởng chính của lý thuyết mã hóa là thêm thông tin vào từng thông điệp trước khi gửi đi để bên nhận có thể tự phát hiện lỗi hoặc thậm chí tự sửa lỗi xảy ra trên đường truyền. Hai tham số chính của một mã là tỉ lệ (rate) của thông tin nguyên thủy trên thông tin gửi đi, và khả năng chịu đựng lỗi — số lỗi tối đa mà mã có thể dùng để kiểm tra hoặc sửa lỗi.

Cụ thể hơn, giả sử ta làm việc trên an-pha-bê . Trong truyền thông số thì thông thường với số tự nhiên nào đó vì thường chỉ có 2 bits và . Trong lý thuyết mã hóa thì có thể tổng quát hơn, là một trường chẳng hạn. Chuyển từ an-pha-bê sang an-pha-bê nhị phân không khó khăn gì. Nhưng ta cứ xét một an-pha-bê tổng quát trước đã. Giả sử mỗi thông điệp gửi đi có chiều dài , nghĩa là mỗi thông điệp gửi đi là một vector trong . Thay vì gửi một thông điệp , ta gửi là ảnh của dưới ánh xạ mã hóa . Chúng ta cần chứa nhiều thông tin hơn , để cho bên nhận — dù có nhận một bản bị lỗi của — thì vẫn có thể hồi phục lại . Do đó .

Đọc tiếp toàn bài »

Chuyên mục: Combinatorics & Lý thuyết mã hóa & Thuật Toán | Bình luận »

Trong lịch sử không có gì tệ hơn ý tưởng rằng mình có thể đi chỗ này ngồi nhìn lên cây

và chuẩn bị cho 2 buổi nói chuyện tuần sau đó. Tại vì bận làm mấy cái này:

Thế cho nên thân gửi các anh chị tôi hân hạnh được gặp tuần sau, xin thông cảm nếu tôi không “make sense”.

(Đừng thắc mắc, tôi hít đất có 1 cái thôi!)

Chuyên mục: Vui - Giải Trí | Bình luận (6) »

Giáo sư Sam Roweis, khoa KHMT của NYU, vừa nhảy từ tầng 16 tự tử hôm qua. Cách đây vài năm ông có buổi nói chuyện ở khoa tôi. Rất thông minh và energetic. Nghe nói gần đây ông có cặp con gái song sinh, sinh sớm, bị “severe disability”.

Chuyên mục: Tin tức đó đây | Bình luận (8) »