Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
Alright, G.G. Cash is not here, he's a tax accountant, so he's gone today. He should be back on Wednesday for the last class. So, a lot to cover.
Được rồi, G.G. Cash không có mặt ở đây, anh ấy là kế toán thuế nên hôm nay vắng. Anh ấy sẽ quay lại vào thứ Tư cho buổi học cuối cùng. Vậy nên hôm nay có rất nhiều nội dung cần nói.
Again, as a reminder, everything I'm talking about today is fair game on the final exam.
Một lần nữa, xin nhắc lại, mọi thứ tôi nói hôm nay đều có thể xuất hiện trong đề thi cuối kỳ.
Obviously, we've kind of covered this at the last minute, so we can't ask you too many details, but some of the questions are on the Homework 6, which is coming due this Wednesday.
Rõ ràng là chúng ta đề cập phần này vào phút chót, nên tôi không thể hỏi các em quá nhiều chi tiết, nhưng một số câu hỏi nằm trong Bài tập về nhà 6, hạn nộp là thứ Tư này.
Project 4 is also coming due this Sunday. Sorry, Sunday. Both are due on Sunday. And there's also, for the Project 4, the Saturday office hours coming up this Saturday on the 6th.
Dự án 4 cũng đến hạn vào Chủ nhật này. Xin lỗi, Chủ nhật. Cả hai đều hạn nộp vào Chủ nhật. Và còn có, cho Dự án 4, buổi office hours vào thứ Bảy sắp tới, ngày 6.
I'll post that on Piazza. That'll be 6th, 5th floor, and Gates, from 3 o'clock to 5 o'clock. And as always, post your questions on Piazza beforehand. The final exam, again, is Thursday, December 11th.
Tôi sẽ đăng thông tin đó trên Piazza. Là ngày 6, tầng 5 tòa Gates, từ 3 giờ đến 5 giờ. Và như mọi khi, hãy đăng câu hỏi của các em lên Piazza trước. Kỳ thi cuối kỳ, nhắc lại, là thứ Năm, ngày 11 tháng 12.
It's going to be over in the Student Center, in the Giant Auditorium. There is a final study guide I'm finishing up, also the practice final exam. I'll post that tonight.
Thi sẽ diễn ra ở Student Center, trong Giant Auditorium. Tôi đang hoàn thiện đề cương ôn tập cuối kỳ, cùng với đề thi thử cuối kỳ. Tối nay tôi sẽ đăng.
And then the next class, on Wednesday, will be a quick overview of the material we've covered so far that will be applicable to the final exam.
Và buổi học tiếp theo, vào thứ Tư, sẽ là phần tổng quan nhanh về nội dung chúng ta đã học cho đến nay mà sẽ áp dụng cho đề thi cuối kỳ.
I'll go over some of the questions people had about strict 2PL and some of the other things that came up during the lectures. I'll cover those again on Wednesday.
Tôi sẽ giải đáp một số câu hỏi của các em về strict 2PL và vài vấn đề khác xuất hiện trong các bài giảng. Tôi sẽ nói lại những phần đó vào thứ Tư.
And again, if you're interested in this kind of stuff and you're around for next semester and want to be a TA, please sign up here.
Và nhắc lại, nếu các em quan tâm đến những nội dung này và còn ở đây vào học kỳ sau và muốn làm TA, hãy đăng ký ở đây.
So, any questions about the final exam, Homework 6, or Project 4?
Vậy có câu hỏi nào về đề thi cuối kỳ, Bài tập về nhà 6 hay Dự án 4 không?
The question is, what's the maximum bonus you get for Project 4? It should be the same as the other ones. I think 25. Yeah, 25.
Câu hỏi là điểm thưởng tối đa của Dự án 4 là bao nhiêu? Nó sẽ giống các dự án khác. Tôi nghĩ là 25. Đúng, 25.
But I'll double check. It should be the same. Other questions? And then for the last two weeks of the semester, we have two remaining speakers.
Nhưng tôi sẽ kiểm tra lại. Chắc là giống nhau. Còn câu hỏi nào khác không? Và tiếp theo, trong hai tuần cuối của học kỳ, chúng ta còn hai diễn giả.
So the Snowflake guys are giving a talk tonight, or today, at 4:30 after class. That should be not 12 p.m., that should be 4:30. Both of these are at 4:30, not 12 p.m., sorry.
Các anh bên Snowflake sẽ có một buổi nói chuyện tối nay, à không, hôm nay, lúc 4:30 sau giờ học. Không phải 12 giờ trưa, mà là 4:30. Cả hai buổi đều lúc 4:30, không phải 12 giờ trưa, xin lỗi.
So that'll be the Polaris. It is the open source re-implementation of the Iceberg Catalog API.
Đó sẽ là Polaris. Đây là bản triển khai lại mã nguồn mở của Iceberg Catalog API.
Remember, Snowflake tried to buy the Iceberg people, a company called Tabular, for $600 million. Databricks came in and kicked their knees out and bought them for $1 billion.
Hãy nhớ, Snowflake từng cố mua những người làm Iceberg, một công ty tên là Tabular, với giá 600 triệu đô la. Databricks nhảy vào, phá đám và mua họ với giá 1 tỷ đô la.
So then Snowflake decided to write their own, and that's what Apache Polaris is. So they'll be talking about that today, again, at 4:30, not 12 p.m.
Thế là Snowflake quyết định tự viết một cái riêng, và đó là Apache Polaris. Họ sẽ nói về chuyện đó hôm nay, nhắc lại, lúc 4:30, không phải 12 giờ trưa.
And then next week, we have the guys from Apache Fluss. Again, I don't really know a lot about the system, but they've asked to give a talk.
Và tuần sau, chúng ta có các anh từ Apache Fluss. Một lần nữa, tôi không biết nhiều về hệ thống này, nhưng họ đã xin được trình bày.
And they'll be giving a talk about what they're running as well. So last class, we talked about distributed databases. It's sort of a quick introduction to the key ideas and key concepts behind them.
Và họ cũng sẽ nói về những gì họ đang vận hành. Vậy ở buổi trước, chúng ta đã nói về cơ sở dữ liệu phân tán. Đó là phần giới thiệu nhanh về các ý tưởng và khái niệm chính đằng sau chúng.
We spent most of our time talking about the difference between shared-nothing and shared-disk architectures. Shared-nothing is when every single node has some partition or piece of the database, and it's a local disk.
Chúng ta dành phần lớn thời gian để nói về sự khác biệt giữa kiến trúc shared-nothing và shared-disk. Shared-nothing là khi mỗi nút đều có một phân vùng hay một phần của cơ sở dữ liệu, và đó là một đĩa cục bộ.
And any time you want to communicate between the nodes, you're going through regular TCP/IP, typically, connections. You can do UDP.
Và bất cứ khi nào bạn muốn giao tiếp giữa các nút, bạn sẽ đi qua các kết nối TCP/IP thông thường, thường là vậy. Bạn cũng có thể dùng UDP.
And then shared-disk is where the primary storage location of the database was an external storage system, like an Amazon S3 or GCS or distributed file system.
Còn shared-disk là khi nơi lưu trữ chính của cơ sở dữ liệu là một hệ thống lưu trữ bên ngoài, như Amazon S3, GCS hoặc một hệ thống tệp phân tán.
And then all the databases would retrieve pages or receive data from that shared storage and then bring them into their own local memory.
Rồi tất cả các cơ sở dữ liệu sẽ lấy các trang hoặc nhận dữ liệu từ nơi lưu trữ dùng chung đó và đưa chúng vào bộ nhớ cục bộ của riêng mình.
We talked about how to do partitioning on the data to split it up into disjoint subsets, or usually disjoint subsets. And this is the technique called horizontal partitioning.
Chúng ta đã nói về cách phân vùng dữ liệu để chia nó thành các tập con rời nhau, hoặc thường là các tập con rời nhau. Và đây là kỹ thuật gọi là phân vùng ngang (horizontal partitioning).
People say sharding. It's essentially the same idea. And you can usually pick a set of keys that you would then hash or generate the ranges on.
Người ta còn gọi là sharding. Về cơ bản là cùng một ý tưởng. Và thường bạn có thể chọn một tập các khóa để băm hoặc để tạo các khoảng giá trị.
So you divide things up in such a way that when queries run, all the data they need is on a single node or single partition.
Vậy bạn chia mọi thứ sao cho khi các truy vấn chạy, toàn bộ dữ liệu chúng cần đều nằm trên một nút hoặc một phân vùng.
But we'll see later today how we're going to handle that when we want to do joins and the data is not partitioned in a way that we want for our join, and how we're going to handle that in our system.
Nhưng hôm nay chúng ta sẽ thấy cách xử lý khi muốn thực hiện phép nối (join) mà dữ liệu không được phân vùng theo cách ta cần cho phép nối, và hệ thống của chúng ta sẽ xử lý việc đó như thế nào.
We talked about how to do replication. So primary replica, multi-primary, the two basic setups. And then transaction coordination.
Chúng ta đã nói về cách thực hiện nhân bản (replication). Gồm primary replica và multi-primary, hai cách thiết lập cơ bản. Và sau đó là điều phối giao dịch.
We talked about having a centralized coordinator, either as an external third-party thing on the side, like a TP monitor, or a middleware sitting in between the application and the database system that is coordinating the transactions.
Chúng ta đã nói về việc có một bộ điều phối tập trung, hoặc là một thành phần bên thứ ba bên ngoài, đứng cạnh, như TP monitor, hoặc một middleware nằm giữa ứng dụng và hệ quản trị cơ sở dữ liệu để điều phối các giao dịch.
Or you have a decentralized model where all the nodes themselves are trying to decide whether transactions are allowed to commit. We'll spend more on that topic today.
Hoặc bạn có một mô hình phi tập trung trong đó chính tất cả các nút tự quyết định liệu các giao dịch có được phép commit hay không. Hôm nay chúng ta sẽ dành nhiều thời gian hơn cho chủ đề đó.
So today's class, again, I'm trying to condense down the two major concepts you need to be aware of in distributed systems.
Vậy buổi học hôm nay, một lần nữa, tôi đang cố cô đọng hai khái niệm chính mà bạn cần biết trong các hệ thống phân tán.
But we're going to distinguish: the first half of the lecture will be on OLTP systems and the second half will be on OLAP systems.
Nhưng chúng ta sẽ phân biệt: nửa đầu bài giảng sẽ nói về các hệ thống OLTP và nửa sau sẽ nói về các hệ thống OLAP.
And I think we talked about this earlier in the semester, but the way to think about OLTP is this is like what most websites are, when you buy things and place orders or do comments on Reddit or Hacker News.
Và tôi nghĩ chúng ta đã nói về điều này hồi đầu học kỳ, nhưng cách nghĩ về OLTP là nó giống như phần lớn các trang web, khi bạn mua hàng, đặt đơn hoặc bình luận trên Reddit hay Hacker News.
This is where the application is making a small number of updates at a time within transactions, and you want this to run as fast as possible because, again, this is something that's exposed to humans or other machines.
Đây là nơi ứng dụng thực hiện một số lượng nhỏ các cập nhật mỗi lần trong các giao dịch, và bạn muốn việc này chạy nhanh nhất có thể vì, một lần nữa, đây là thứ được đưa ra cho con người hoặc các máy khác sử dụng.
And then analytical workloads is where we would do exploratory analysis of the data to extrapolate new knowledge from the data we've already collected from an OLTP system.
Còn khối lượng công việc phân tích là nơi ta thực hiện phân tích khám phá trên dữ liệu để suy ra tri thức mới từ dữ liệu mà chúng ta đã thu thập từ một hệ thống OLTP.
So in this environment, we're running long-running queries that can take seconds Or even minutes or hours that will do a bunch of joins and try to aggregate a bunch of information together.
Vậy trong môi trường này, chúng ta chạy các truy vấn chạy lâu, có thể mất vài giây hoặc thậm chí vài phút, vài giờ, thực hiện hàng loạt phép join và cố gắng tổng hợp một lượng lớn thông tin lại với nhau.
So in the OLTP world, we want transactions to run less than 50 milliseconds. In an OLAP system, less than a second is usually good enough for most things.
Trong thế giới OLTP, ta muốn các giao dịch chạy dưới 50 mili giây. Còn trong một hệ thống OLAP, dưới một giây thường là đủ tốt cho hầu hết mọi việc.
So as I said, we're going to first talk about OLTP stuff, and then we'll talk about OLAP stuff. And again, it's not to say that these things are completely mutually exclusive to each other.
Như tôi đã nói, trước tiên ta sẽ nói về OLTP, rồi sau đó sẽ nói về OLAP. Và một lần nữa, không có nghĩa là những thứ này hoàn toàn loại trừ lẫn nhau.
If I'm building a distributed transactional database system, an OLTP database system, I may have to do joins in it, and therefore I'm going to need to do different distributed join algorithms.
Nếu tôi xây dựng một hệ cơ sở dữ liệu giao dịch phân tán, tức một hệ cơ sở dữ liệu OLTP, tôi vẫn có thể phải thực hiện join trong đó, và do đó tôi sẽ cần dùng các thuật toán join phân tán khác nhau.
But it may not be the main thing I'm going to focus on in my system.
Nhưng đó có thể không phải thứ chính mà tôi tập trung vào trong hệ thống của mình.
Likewise, in an analytical system, I still want to have transactions, and I still need to use a consistency protocol or atomic commit protocol to make sure this all works.
Tương tự, trong một hệ thống phân tích, tôi vẫn muốn có giao dịch, và tôi vẫn cần dùng một giao thức nhất quán hoặc giao thức atomic commit để bảo đảm mọi thứ hoạt động đúng.
But it's not the thing I'm trying to optimize for.
Nhưng đó không phải thứ tôi cố gắng tối ưu.
So again, whether or not you spend all your effort when you engineer a system to focus on one of these two category things depends on what the workload you're trying to target.
Vì vậy, việc bạn có dồn toàn bộ công sức khi thiết kế một hệ thống để tập trung vào một trong hai loại này hay không phụ thuộc vào khối lượng công việc mà bạn nhắm tới.
And this, again, there's a lot to cover here. I'm trying to condense what would have been, you know, if we had more faculty at CMU, we could teach a whole course on distributed databases.
Và một lần nữa, có rất nhiều thứ cần đề cập ở đây. Tôi đang cố cô đọng thứ mà lẽ ra, nếu CMU có nhiều giảng viên hơn, ta có thể dạy cả một môn riêng về cơ sở dữ liệu phân tán.
Trying to condense down the main things you need to understand so that when you go out in the real world, you'll be exposed to these concepts, exposed to these topics.
Tôi cố cô đọng những điều chính bạn cần hiểu để khi bạn bước ra thực tế, bạn đã được tiếp xúc với các khái niệm, các chủ đề này.
You may not be an expert in it, but you just be aware of it in some of the design decisions that you have to make when you start evaluating systems or try to build your own.
Bạn có thể không phải là chuyên gia, nhưng bạn sẽ biết đến nó trong một số quyết định thiết kế mà bạn phải đưa ra khi bắt đầu đánh giá các hệ thống hoặc thử tự xây dựng hệ thống của riêng mình.
So remember that last class, we talked about how the whole goal of a distributed database system is that we want it to appear to the application as if it's a single logical database.
Hãy nhớ rằng ở buổi trước, ta đã nói về việc toàn bộ mục tiêu của một hệ cơ sở dữ liệu phân tán là ta muốn nó hiện ra với ứng dụng như thể là một cơ sở dữ liệu logic duy nhất.
So again, ideally, the same query I could run on a single node Postgres database instance could run if I had a sharded or partitioned or distributed system.
Vậy lý tưởng nhất, cùng một truy vấn mà tôi có thể chạy trên một phiên bản cơ sở dữ liệu Postgres đơn nút cũng có thể chạy được nếu tôi có một hệ thống được shard, phân vùng hoặc phân tán.
But then now we've got to worry about, if now my data is broken up across, or resides in, a bunch of these different nodes, whether it's shared disk or a shared nothing system, when we start making changes to data that maybe reside on different nodes and we want to go commit a transaction, how are we going to make sure that all the same ACID properties we had
Nhưng giờ ta phải lo lắng, nếu dữ liệu của tôi giờ bị chia nhỏ ra, hoặc nằm trên, nhiều nút khác nhau như vậy, dù là hệ thống shared disk hay shared nothing, khi ta bắt đầu thay đổi dữ liệu có thể nằm trên các nút khác nhau và muốn commit một giao dịch, làm sao ta bảo đảm tất cả các tính chất ACID mà ta có
when we were doing transactions on a single node system are still going to work for us in a distributed environment?
khi thực hiện giao dịch trên hệ thống đơn nút vẫn sẽ hoạt động đúng trong môi trường phân tán?
Again, distributed doesn't mean it's a completely radical way of thinking about how to build the system.
Một lần nữa, phân tán không có nghĩa là một cách suy nghĩ hoàn toàn khác về cách xây dựng hệ thống.
It's just doing all the same stuff we were doing before, but now just in hard mode, because we have to worry about a bunch of things we didn't worry about before when we were on a single node.
Đó chỉ là làm tất cả những việc ta đã làm trước đây, nhưng giờ ở chế độ khó, vì ta phải lo lắng về hàng loạt thứ mà trước đây ta không phải lo khi chỉ có một node duy nhất.
So say we want to do a commit for a transaction that touches multiple nodes, but one of those nodes goes down. What should happen to that transaction?
Ví dụ, ta muốn commit một transaction có liên quan đến nhiều node, nhưng một trong số các node đó bị sập. Transaction đó nên được xử lý như thế nào?
What happens if the messages that we're sending for a commit transaction show up late or somehow get dropped along the way because of a weird network hiccup? What should happen?
Điều gì xảy ra nếu các thông điệp mà ta gửi đi để commit transaction đến muộn hoặc bằng cách nào đó bị mất giữa đường vì một trục trặc mạng kỳ lạ? Lúc đó nên làm gì?
And then what happens if we are doing a large distributed transaction on, like, a hundred machines?
Rồi điều gì xảy ra nếu ta đang chạy một transaction phân tán lớn trên khoảng một trăm máy?
Should we wait for every single one to agree that we should commit, or can we look at something less than that? Right?
Ta có nên chờ từng máy một đồng ý commit, hay có thể chỉ cần ít hơn thế? Đúng không?
So one important assumption we're going to make throughout this lecture today, actually going on the real world, you should make this assumption as well, is that we're going to assume all the nodes that are participating in our distributed DBMS system are controlled by us and therefore are well-behaved.
Vậy có một giả định quan trọng mà ta sẽ đặt ra xuyên suốt bài giảng hôm nay, thực ra ngoài đời thật các em cũng nên đặt giả định này, đó là ta giả định tất cả các node tham gia vào hệ DBMS phân tán của ta đều do ta kiểm soát và do đó đều hoạt động đúng mực.
Well-behaved in quotes, obviously, if, like, the hardware crashes, That's, you know, that's, we can't prevent that.
"Đúng mực" trong ngoặc kép, dĩ nhiên nếu phần cứng bị hỏng thì, ừ, ta không thể ngăn được điều đó.
But what we mean is that it's not like we're worried about someone running a malicious version of our database system, so that when we go to commit a transaction, they start messing around with us and causing, you know, weird states.
Nhưng ý ta là ta không lo có ai đó chạy một phiên bản độc hại của hệ cơ sở dữ liệu của ta, để rồi khi ta commit một transaction, họ bắt đầu giở trò với ta và gây ra những trạng thái kỳ quặc.
Right?
Đúng không?
So we assume that we control everything, even if we don't control the hardware, we're at least controlling the software, and that if a node tells us, "Yeah, let's go ahead and commit," they're not going to like change their mind or try to screw around with the decisions that are being made in our system.
Nên ta giả định rằng ta kiểm soát mọi thứ, dù không kiểm soát phần cứng thì ít nhất ta cũng kiểm soát phần mềm, và nếu một node nói với ta: "Ừ, cứ commit đi," thì họ sẽ không đổi ý hay giở trò với các quyết định được đưa ra trong hệ thống của ta.
Right? What kind of protocol would you want to use if you don't trust the other nodes? Byzantine, yes.
Đúng không? Nếu không tin các node khác thì em sẽ muốn dùng loại giao thức nào? Byzantine, đúng rồi.
So if you don't trust the other nodes and you assume they could be malicious actors, you need what is called a Byzantine fault tolerant protocol, the BFT protocol.
Nếu không tin các node khác và giả định chúng có thể là kẻ xấu, thì ta cần cái gọi là giao thức chịu lỗi Byzantine, giao thức BFT.
If you know what, I'm sure everyone heard of blockchains, but this is basically how blockchains work.
Tôi chắc ai cũng từng nghe về blockchain, và về cơ bản blockchain hoạt động như vậy.
Blockchains are just running transactions like we normally would in our beautiful database system, except those guys don't trust the other nodes.
Blockchain cũng chỉ chạy các transaction giống như ta vẫn làm trong hệ cơ sở dữ liệu tuyệt đẹp của mình, chỉ khác là họ không tin các node khác.
So therefore they have to run a BFT protocol to get everyone, the majority, to agree that this is what's going to happen.
Vì vậy họ phải chạy giao thức BFT để khiến mọi người, tức đa số, đồng ý rằng đây là điều sẽ xảy ra.
Right? And they use like the Merkle tree stuff, which I'm not going to talk about.
Và họ dùng cả mấy thứ như Merkle tree, mà tôi sẽ không nói tới.
They use an immutable ledger, immutable write-ahead log, keep track of here's all the changes that get made, and then you can't go back and reverse things.
Họ dùng một sổ cái bất biến, một write-ahead log bất biến, ghi lại tất cả các thay đổi được thực hiện, và sau đó không thể quay lại đảo ngược mọi thứ.
And they do all this extra stuff because they're, you know, it's a bunch of randos and crypto bros mining things and you can't trust them. Right?
Họ làm tất cả những việc thêm này vì, em biết đấy, đó là một đám người ất ơ và dân crypto đi đào coin, và không thể tin họ được. Đúng không?
You never want to do this in a real system running real transactions that isn't crypto. There really isn't a good practical use case for blockchains other than crypto.
Em không bao giờ muốn làm vậy trong một hệ thống thực tế hệ thống chạy các giao dịch thực mà không phải là crypto. Thực sự không có trường hợp sử dụng thực tế nào tốt cho blockchain ngoài crypto.
Like if you're money laundering stuff, then you want to use that. But like Amazon's not going to run off this, right?
Ví dụ nếu bạn rửa tiền, thì bạn sẽ muốn dùng nó. Nhưng Amazon sẽ không chạy trên thứ này, đúng không?
Blockchain, Any real system is not going to run on blockchain because it's going to be five to 10x slower than the stuff we're talking about today. Okay?
Blockchain, bất kỳ hệ thống thực nào cũng sẽ không chạy trên blockchain vì nó sẽ chậm hơn từ năm đến 10 lần so với những thứ chúng ta nói đến hôm nay. Được chứ?
So again, if you remember only two things from this class: never use mmap in your data system, and then don't use blockchain databases, right? Use the transactional stuff we'll talk about today.
Vậy nhắc lại, nếu các em chỉ nhớ hai điều từ lớp này: đừng bao giờ dùng mmap trong hệ thống dữ liệu của mình, và đừng dùng cơ sở dữ liệu blockchain, nhé? Hãy dùng các cơ chế giao dịch mà hôm nay chúng ta sẽ nói.
Because we're already struggling with the speed of light issues to do our atomic commit protocols, we'll see in a second.
Bởi vì chúng ta vốn đã vất vả với các vấn đề về tốc độ ánh sáng khi chạy các giao thức atomic commit, lát nữa sẽ thấy.
And now I've got to run a bunch of BFT stuff for it. You know, it's a waste. All right.
Giờ lại còn phải chạy cả một đống thứ BFT cho nó. Thật là lãng phí. Được rồi.
So how are we going to make sure that everyone can agree that in our distributed database, when we want to commit, that we can all go ahead and agree that we're going to commit?
Vậy làm sao đảm bảo mọi người có thể đồng ý rằng trong cơ sở dữ liệu phân tán của mình, khi muốn commit, tất cả có thể cùng thống nhất là sẽ commit?
So this is what's been called an atomic commit protocol. If you're coming from the distributed systems world, they would call this a consensus protocol. They are the same thing, right?
Đây là cái được gọi là giao thức atomic commit. Nếu các em đến từ thế giới hệ thống phân tán, họ sẽ gọi đây là giao thức đồng thuận (consensus). Chúng là một, đúng không?
And in the distributed systems world, they would call these things state machines. The thing that we care about is the order in which transactions are going to get committed.
Và trong thế giới hệ thống phân tán, họ gọi những thứ này là máy trạng thái (state machine). Điều chúng ta quan tâm là thứ tự mà các giao dịch sẽ được commit.
Guess what? That's the state of the system. It's the same thing. So we're going to use our atomic commit protocol to decide what is the order that transactions will be allowed to commit.
Đoán xem? Đó chính là trạng thái của hệ thống. Cũng là một thứ thôi. Vì vậy chúng ta sẽ dùng giao thức atomic commit để quyết định thứ tự mà các giao dịch được phép commit.
And then once we know they've been committed, we want to write them out in such a way, a ledger or a log, so that we recorded that this is the order that they were then committed.
Và khi đã biết chúng được commit rồi, ta muốn ghi chúng ra theo cách một sổ cái hoặc một log, để ghi lại rằng đây là thứ tự mà chúng đã được commit.
So if anybody comes back and tries to read, you know, to replay the transactions in that same order, you know, we guarantee to put it back in the same state.
Như vậy nếu ai đó quay lại và cố đọc, tức là phát lại các giao dịch theo đúng thứ tự đó, ta đảm bảo đưa hệ thống về đúng trạng thái cũ.
Okay? And we're going to want to do this, use our atomic commit protocol, no matter how the database is divided or split across the nodes in our system.
Được chứ? Và ta muốn làm điều này, dùng giao thức atomic commit, bất kể cơ sở dữ liệu được chia hay phân tách trên các nút của hệ thống như thế nào.
So whether a piece of data has been replicated across multiple machines or it's been partitioned and there's only one location of that data in our distributed system cluster, we're still going to run this atomic commit protocol.
Dù một phần dữ liệu được nhân bản trên nhiều máy hay được phân vùng và chỉ có một vị trí chứa dữ liệu đó trong cụm hệ thống phân tán, chúng ta vẫn sẽ chạy giao thức atomic commit này.
So the very first one that people sort of developed to solve this problem is two-phase commit. Who here has heard of two-phase commit? All right, less than half.
Giao thức đầu tiên mà người ta phát triển để giải quyết vấn đề này là two-phase commit. Ai ở đây đã nghe về two-phase commit? Được rồi, chưa đến một nửa.
And then it'll have one problem we'll see in a second.
Và nó sẽ có một vấn đề mà lát nữa chúng ta sẽ thấy.
And then there was a Stonebraker, the guy who invented Postgres, came up with another version called three-phase commit to solve some of the problems that two-phase commit does, but that's overly complicated.
Rồi sau đó có Stonebraker, người phát minh ra Postgres, đưa ra một phiên bản khác gọi là three-phase commit để giải quyết một số vấn đề của two-phase commit, nhưng nó quá phức tạp.
So nobody does three-phase commit. There's a four-phase commit from Microsoft for specialized hardware. But again, that's a research system, not a real system.
Nên không ai dùng three-phase commit cả. Có một bản four-phase commit của Microsoft dành cho phần cứng chuyên dụng. Nhưng lại một lần nữa, đó là một hệ thống nghiên cứu, không phải hệ thống thực tế.
But the problem we're trying to solve is basically get everyone to agree that this thing is, when we say transactions are allowed to commit, that we can go ahead and commit.
Nhưng vấn đề chúng ta đang cố giải quyết về cơ bản là làm cho mọi bên đồng ý rằng thứ này, khi ta nói các giao dịch được phép commit, thì ta có thể tiến hành commit.
And then we don't, ideally, not to block the entire system until everyone agrees. Two-phase commit is going to have that problem.
Và lý tưởng là ta không chặn toàn bộ hệ thống cho đến khi mọi bên đồng ý. Two-phase commit sẽ gặp vấn đề đó.
But the newer protocols like Paxos, that probably everyone is familiar with, they're going to get around this because they'll take majorities. So two-phase commit will block everyone until everyone agrees to commit.
Nhưng các giao thức mới hơn như Paxos, mà có lẽ ai cũng đã biết, sẽ tránh được vì chúng lấy theo đa số. Còn two-phase commit sẽ chặn tất cả cho đến khi mọi bên đồng ý commit.
There's a protocol developed at MIT called Viewstamped Replication that came out in 1988. This predates Paxos by a year, but it's essentially solving the same problem.
Có một giao thức được phát triển tại MIT gọi là Viewstamped Replication ra đời năm 1988. Nó có trước Paxos một năm, nhưng về cơ bản giải quyết cùng một vấn đề.
Paxos came out in '89. Again, it solves the same things. ZAB is the Zookeeper Atomic Broadcast protocol. That's only used in Zookeeper.
Paxos ra đời năm 1989. Một lần nữa, nó giải quyết những vấn đề tương tự. ZAB là Zookeeper Atomic Broadcast. Giao thức đó chỉ được dùng trong Zookeeper.
And then Raft is another one probably everyone is familiar with as well. It's a simplification of Paxos in a certain way. But it's designed to be more easily understood.
Và Raft là một giao thức khác mà có lẽ ai cũng đã biết. Theo một cách nào đó, nó là bản đơn giản hóa của Paxos. Nhưng nó được thiết kế để dễ hiểu hơn.
But at a high level, they're all the same thing. So we're going to focus on these two because in databases, most systems are going to do two-phase commit.
Nhưng ở mức tổng quát, chúng đều giống nhau. Vì vậy chúng ta sẽ tập trung vào hai giao thức này, vì trong cơ sở dữ liệu, hầu hết các hệ thống sẽ dùng two-phase commit.
And then a lot of them are also going to be doing Paxos as well. Sometimes they'll do both in a single system. Raft, again, if you understand Paxos, you'll be able to understand Raft.
Và nhiều hệ thống cũng sẽ dùng cả Paxos. Đôi khi chúng dùng cả hai trong một hệ thống. Còn Raft, nếu hiểu Paxos thì bạn sẽ hiểu được Raft.
And again, this is not a distributed systems class. You take, in, what is it, 440? They cover this as well.
Và đây không phải là lớp về hệ thống phân tán. Các bạn học môn, gì nhỉ, 440? Họ cũng có đề cập đến nội dung này.
But we'll go at a high level and talk about the things we care about in our databases. So two-phase commit is, again, one of the first ones that was developed.
Nhưng chúng ta sẽ đi ở mức tổng quát và nói về những điều chúng ta quan tâm trong cơ sở dữ liệu. Two-phase commit là một trong những giao thức đầu tiên được phát triển.
It's originally attributed to Jim Gray, the guy who invented two-phase locking and a bunch of other stuff, who won the Turing Award in databases in the 1990s.
Ban đầu nó được cho là của Jim Gray, người đã phát minh ra two-phase locking và nhiều thứ khác, và đã nhận giải Turing về cơ sở dữ liệu vào thập niên 1990.
But in interviews with him, he says that he got the idea from some Italian programmer in the 1970s.
Nhưng trong các cuộc phỏng vấn với ông, ông nói rằng ông lấy ý tưởng từ một lập trình viên người Ý vào thập niên 1970.
And when they talked to that guy, he said, oh, it's actually based on how people did contract law on pencil and paper.
Và khi họ hỏi người đó, ông ấy nói, ồ, thực ra nó dựa trên cách người ta làm luật hợp đồng bằng giấy và bút chì.
So it's an application of ideas that were in the physical world applied to the digital world with databases.
Vậy đây là việc áp dụng những ý tưởng từ thế giới vật lý vào thế giới số với cơ sở dữ liệu.
All right, so our atomic commit protocol, again, the idea is that we want to coordinate across multiple nodes or resources in our system that a transaction is allowed to commit, and that everyone's going to agree at the same time that this transaction has successfully committed, or a batch of transactions.
Được rồi, vậy giao thức atomic commit của chúng ta, ý tưởng là chúng ta muốn điều phối giữa nhiều nút hoặc tài nguyên trong hệ thống rằng một giao dịch được phép commit, và mọi bên sẽ đồng ý cùng một lúc rằng giao dịch này đã commit thành công, hoặc một loạt giao dịch.
And you can sort of think of the state machine for a transaction we're trying to follow is like this.
Và bạn có thể hình dung máy trạng thái cho một giao dịch mà chúng ta đang cố tuân theo là như thế này.
So while a transaction is executing queries and reading data, modifying the database, it's in the working state. And then it says, all right, I'm done with my changes.
Vậy khi một giao dịch đang thực thi các truy vấn và đọc dữ liệu, hay sửa đổi cơ sở dữ liệu, nó đang ở trạng thái working. Rồi nó nói: được rồi, tôi đã xong các thay đổi.
I want to go ahead and commit. And then the application sends a commit request. And then there's some work to be done to figure out, should we allow this guy, this transaction, to commit?
Tôi muốn commit. Và ứng dụng gửi một yêu cầu commit. Sau đó có một số công việc cần làm để xác định liệu có nên cho phép giao dịch này commit hay không?
Or is it not allowed to commit? And then we get everyone to agree that it can't commit, and we want to abort and roll back these changes.
Hay là nó không được phép commit? Rồi ta để mọi nút đồng ý rằng nó không thể commit, và ta muốn hủy bỏ (abort) và rollback các thay đổi này.
And then the property of our commit protocol is that once we decide that this transaction has successfully committed, we can't revert that decision.
Và tính chất của giao thức commit của ta là một khi ta đã quyết định rằng giao dịch này đã commit thành công, thì ta không thể đảo ngược quyết định đó.
Once all the nodes agree that this transaction is allowed to commit, one of them can't come back and say, "I changed my mind."
Một khi tất cả các nút đồng ý rằng giao dịch này được phép commit, thì không nút nào được quay lại và nói: "Tôi đổi ý rồi."
And then when we finally reach the end state, either committed or aborted, everyone is simultaneously in agreement that this is the right thing to happen. And this is the current state of the system.
Và cuối cùng khi ta đạt trạng thái kết thúc, hoặc committed hoặc aborted, mọi nút đồng thời đều nhất trí rằng đó là điều đúng đắn cần xảy ra. Và đây là trạng thái hiện tại của hệ thống.
So we're going to assume that has to be, we'll assume a liveness property, meaning that there's always going to be some number of nodes available for us to keep making forward progress in our system.
Vậy ta sẽ giả định rằng, ta sẽ giả định một tính chất liveness, nghĩa là luôn có một số nút khả dụng để hệ thống của ta tiếp tục tiến triển.
That doesn't mean that transactions will be allowed to commit.
Điều đó không có nghĩa là các giao dịch sẽ được phép commit.
It may be the case that we keep losing nodes before we get everyone to agree that we can commit and transactions keep getting aborted, but it's still moving forward in time.
Có thể ta liên tục mất các nút trước khi kịp để mọi nút đồng ý rằng có thể commit, và các giao dịch cứ bị abort, nhưng hệ thống vẫn tiến về phía trước theo thời gian.
All right, so let's look at the basic one, two-phase commit. So assume the application server has committed, did some reason right operations on these nodes here in our distributed data system.
Được rồi, ta hãy xem giao thức cơ bản nhất, two-phase commit. Giả sử máy chủ ứng dụng đã commit, vì lý do nào đó đã thực hiện các thao tác ghi trên những nút này trong hệ dữ liệu phân tán của ta.
And then it's going to go to this first one here. I'm not going to say how it decides to do that, but we'll cover that in a second.
Và rồi nó sẽ đến nút đầu tiên này. Tôi sẽ không nói nó quyết định việc đó thế nào, nhưng ta sẽ bàn ngay sau đây.
But assume there's like a leader election, right? And they said, "This is the node that's going to be in charge of committing my transaction."
Nhưng giả sử có một cuộc bầu chọn leader, đúng không? Và họ nói: "Đây là nút sẽ chịu trách nhiệm commit giao dịch của tôi."
So under two-phase commit, you would call this node here the coordinator, because it's going to be responsible for coordinating the commit process for this transaction across the other nodes.
Trong two-phase commit, nút này được gọi là coordinator, vì nó sẽ chịu trách nhiệm điều phối quá trình commit cho giao dịch này trên các nút khác.
And then the other nodes would be the participants. And assume these are the nodes that the transaction read or wrote data from while it was running.
Còn các nút khác sẽ là các participant. Và giả sử đây là những nút mà giao dịch đã đọc hoặc ghi dữ liệu trong lúc nó chạy.
So you could have like 1,000 nodes in your cluster, although that's rare for transactional systems. But I only need to run two-phase commit on the ones that I've interacted with.
Vậy bạn có thể có chẳng hạn 1.000 nút trong cụm, dù điều đó hiếm với các hệ thống giao dịch. Nhưng tôi chỉ cần chạy two-phase commit trên những nút mà tôi đã tương tác.
So as it sounds, two-phase commit has two phases.
Đúng như tên gọi, two-phase commit có hai pha.
So in the first phase, you send a prepare message to all the nodes and say, "Hey, this transaction here with this ID that uniquely identifies it, it wants to commit."
Ở pha đầu tiên, bạn gửi một thông điệp prepare đến tất cả các nút và nói: "Này, giao dịch này với ID này định danh duy nhất cho nó, muốn commit."
And then all the nodes will decide on their own whether this transaction is allowed to commit. They have to know what it did.
Rồi mỗi nút sẽ tự quyết định xem giao dịch này có được phép commit hay không. Chúng phải biết giao dịch đã làm gì.
And they can run whatever validation process they want to run, based on what concurrency protocol they're using, to determine whether that transaction is allowed to commit.
Và chúng có thể chạy bất kỳ quy trình kiểm tra hợp lệ nào mà chúng muốn. dựa trên giao thức điều khiển đồng thời mà chúng đang dùng, để xác định xem giao dịch đó có được phép commit hay không.
And then they send back an acknowledgment. They send back an OK. They're voting yes: we want to commit this transaction.
Sau đó chúng gửi lại một xác nhận. Chúng gửi lại một OK. Chúng đang bỏ phiếu đồng ý: chúng ta muốn commit giao dịch này.
And then once the coordinator gets the acknowledgment back from all of the nodes that it sent out the first message to, then it can go ahead and switch to the second phase, the commit phase, where now it sends to everyone and says, "Hey, guess what?
Rồi khi bộ điều phối nhận lại xác nhận từ tất cả các nút mà nó đã gửi thông điệp đầu tiên tới, thì nó có thể chuyển sang giai đoạn thứ hai, giai đoạn commit, khi đó nó gửi tới mọi nút và nói: "Này, đoán xem nào?
Everyone said we're going to commit this. Go ahead and commit it." Then they come back and say, "OK, we did commit it."
Mọi người đều đồng ý commit giao dịch này. Cứ commit đi." Sau đó chúng quay lại và nói: "OK, chúng tôi đã commit rồi."
And then, and only then, under the sort of strict definition of two-phase commit, once you get back the acknowledgment from all the nodes participating in this transaction in the second phase, then you're allowed to tell the application your transaction has committed.
Và chỉ khi đó, theo định nghĩa chặt chẽ của two-phase commit, khi bạn nhận lại xác nhận từ tất cả các nút tham gia vào giao dịch này ở giai đoạn thứ hai, thì bạn mới được phép báo cho ứng dụng biết rằng giao dịch của bạn đã commit.
You're telling the outside world that this thing has committed successfully.
Bạn đang báo cho thế giới bên ngoài biết rằng giao dịch này đã commit thành công.
One thing I'm not showing here is that we're actually going to be writing all the messages we're passing around between the coordinator and the participants.
Có một điều tôi không thể hiện ở đây là thực tế chúng ta cũng sẽ ghi lại tất cả các thông điệp được truyền qua lại giữa bộ điều phối và các nút tham gia.
We're going to be storing them in the write-ahead log as well.
Chúng ta cũng sẽ lưu chúng trong write-ahead log.
It could either be in the write-ahead log with the regular data, or it could be a separate write-ahead log used for transactional coordination stuff.
Chúng có thể nằm trong write-ahead log cùng với dữ liệu thông thường, hoặc có thể là một write-ahead log riêng dùng cho việc điều phối giao dịch.
But all these nodes will be recording on disk what their votes are and what the outcomes are, so that when we crash and come back, we go look in that log and figure out, What was I doing at the moment of that crash, including if I was doing a two-phase commit process across multiple nodes?
Nhưng tất cả các nút này sẽ ghi xuống đĩa phiếu bầu của chúng là gì và kết quả là gì, để khi chúng ta bị sập rồi khởi động lại, chúng ta xem trong log đó và tìm ra lúc xảy ra sự cố tôi đang làm gì, kể cả việc tôi có đang thực hiện quy trình two-phase commit trên nhiều nút hay không?
All right, let's look at the abort case. Same thing. I get a commit message. First phase, you send out the prepare message to everyone. Say the first guy comes back at the bottom here.
Được rồi, hãy xem trường hợp abort. Tương tự thôi. Tôi nhận được một thông điệp commit. Giai đoạn đầu, bạn gửi thông điệp prepare tới mọi nút. Giả sử nút đầu tiên ở phía dưới này phản hồi.
He says, OK, yeah, we know to commit this. But the second one in the middle, for whatever reason, it decides this transaction is not allowed to commit.
Nó nói: OK, vâng, chúng tôi đồng ý commit giao dịch này. Nhưng nút thứ hai ở giữa, vì lý do nào đó, quyết định giao dịch này không được phép commit.
Like, say there's an integrity constraint violation or whatever. And so it sends back the abort message.
Ví dụ, giả sử có vi phạm ràng buộc toàn vẹn hay gì đó. Và vì vậy nó gửi lại thông điệp abort.
So as soon as the abort message shows up from any one of the participant nodes, then we automatically switch into the abort phase, the second phase.
Vậy ngay khi thông điệp abort đến từ bất kỳ một nút tham gia nào, chúng ta tự động chuyển sang giai đoạn abort, tức giai đoạn thứ hai.
So we're not even going to wait for the node two to come back with its vote. Because once we get one abort, because everyone has to agree that this transaction is allowed to commit.
Chúng ta thậm chí sẽ không chờ nút thứ hai gửi lại phiếu bầu của nó. Vì một khi chúng ta nhận được một abort, mà mọi nút đều phải đồng ý rằng giao dịch này được phép commit.
Once we get one denial vote, then we switch into the second phase. So we send out the abort message to everyone in the second phase.
Một khi có một phiếu phản đối, chúng ta chuyển sang giai đoạn thứ hai. Vậy chúng ta gửi thông điệp abort tới mọi nút trong giai đoạn thứ hai.
And then we also immediately tell the application that the transaction has aborted.
Và chúng ta cũng báo ngay cho ứng dụng rằng giao dịch đã bị abort.
So we don't need to wait to find out whether everyone is going to finally commit this or finally abort it and roll back all the changes.
Vậy chúng ta không cần chờ để biết liệu mọi nút cuối cùng sẽ commit hay abort giao dịch này và hoàn tác mọi thay đổi.
As soon as we get one notification that this transaction can't complete, we send back the abort message immediately to the application. We saw this before on a single node.
Ngay khi nhận được một thông báo rằng giao dịch này không thể hoàn tất, chúng ta gửi thông điệp abort về ngay cho ứng dụng. Chúng ta đã thấy điều này trước đây trên một nút đơn.
When a transaction aborted, because there was a deadlock or something like that, we would then immediately send back the response to the application that the transaction has aborted.
Khi một giao dịch bị abort, vì có bế tắc hoặc điều gì đó tương tự, thì chúng ta sẽ gửi ngay phản hồi về cho ứng dụng rằng giao dịch đã bị hủy bỏ.
And then later on, we go ahead and clean things up with the CLRs to reverse things in our log. The application doesn't need to wait for that cleanup process.
Và sau đó, chúng ta sẽ tiến hành dọn dẹp bằng các CLR để đảo ngược các thay đổi trong log của mình. Ứng dụng không cần phải chờ quá trình dọn dẹp đó.
And then eventually, they all come back and say, yes, The transaction has successfully been aborted.
Rồi cuối cùng, tất cả các nút phản hồi lại và nói rằng, vâng, giao dịch đã được hủy bỏ thành công.
And at that point, again, there should be no artifacts or no pending changes for that transaction in any of the nodes.
Và đến lúc đó, một lần nữa, sẽ không còn dấu vết nào hay thay đổi nào đang chờ xử lý của giao dịch đó trên bất kỳ nút nào.
Yes? The question is, what happens when one node dies? Boom. Next slide. So we send a commit message. First, the prepare messages go out.
Vâng? Câu hỏi là, chuyện gì xảy ra khi một nút chết? Bùm. Slide tiếp theo. Vậy là chúng ta gửi một thông điệp commit. Trước tiên, các thông điệp prepare được gửi đi.
Then the first two guys, the top and the bottom, they ack OK. The second one dies. This is the scenario you want, right?
Rồi hai nút đầu, nút trên và nút dưới, trả lời ack OK. Nút thứ hai thì chết. Đây chính là kịch bản mà các bạn muốn xét, đúng không?
So again, under two-phase commit, all the nodes have to agree that this transaction is allowed to commit.
Vậy nên, một lần nữa, theo two-phase commit, tất cả các nút phải đồng ý rằng giao dịch này được phép commit.
So that means the coordinator has to wait for some amount of time to find out what happened with the node in the middle here.
Điều đó có nghĩa là bộ điều phối phải chờ một khoảng thời gian để biết chuyện gì đã xảy ra với nút ở giữa này.
And again, if it crashes completely, then if you're pinging it on the network, you won't get a response. You'll know that it's dead.
Và một lần nữa, nếu nó sập hoàn toàn, thì khi bạn ping nó trên mạng, bạn sẽ không nhận được phản hồi. Bạn sẽ biết là nó đã chết.
But it may be the case that the database system software itself is bogged down for some reason.
Nhưng cũng có thể là phần mềm hệ quản trị cơ sở dữ liệu bản thân nó bị quá tải vì lý do nào đó.
Like if it's written in Java and the garbage collector fires up and the JVM fires up, it may do a 30-second pause where, again, you're not getting a response from the database server software itself.
Ví dụ nếu nó được viết bằng Java và bộ thu gom rác chạy lên, JVM chạy lên, nó có thể dừng 30 giây, trong lúc đó, một lần nữa, bạn không nhận được phản hồi từ chính phần mềm máy chủ cơ sở dữ liệu.
But if you ping the node, it's going to come back and say it's alive. So it's really about, sometimes there will also be heartbeats in these systems that sound like, hey, are you alive?
Nhưng nếu bạn ping nút đó, nó vẫn sẽ trả lời là còn sống. Nên thực ra vấn đề là, đôi khi trong các hệ thống này cũng có heartbeat kiểu như, này, bạn còn sống không?
And it can't be a ping, because the pings are at the hardware level. You've got to go up at the upper layers and actually touch the application.
Và đó không thể là ping, vì ping hoạt động ở mức phần cứng. Bạn phải đi lên các tầng trên và thực sự tương tác với ứng dụng.
So in this case here, we have to wait. The coordinator has to wait. At some point, there's a timeout. And it says, all right, well, node 3 is not coming back.
Vậy trong trường hợp này, chúng ta phải chờ. Bộ điều phối phải chờ. Đến một lúc nào đó, sẽ có timeout. Và nó nói, được rồi, nút 3 sẽ không phản hồi nữa.
It doesn't want to talk to me. So at that point, I automatically switch into the abort phase. And I send back the abort message to the application server.
Nó không muốn nói chuyện với tôi. Vậy nên lúc đó, tôi tự động chuyển sang pha hủy bỏ. Và tôi gửi thông điệp abort về cho máy chủ ứng dụng.
And eventually, these guys will come back and say, we've aborted as well. Yes?
Và cuối cùng, các nút kia sẽ phản hồi rằng chúng cũng đã hủy bỏ. Vâng?
The question is, can the application abort before, when? Sorry.
Câu hỏi là, ứng dụng có thể hủy bỏ trước không, khi nào? Xin lỗi.
The question is, going back here, I time out, I see I can't send it. When do I send the abort message back? You can send it before and after.
Câu hỏi là, quay lại đây, tôi bị timeout, tôi thấy mình không thể gửi nó. Khi nào tôi gửi thông điệp abort về? Bạn có thể gửi trước hoặc sau.
It doesn't matter. Typically, you want to send it sooner to the application first, because why wait?
Không quan trọng. Thông thường, bạn muốn gửi cho ứng dụng trước, vì sao phải chờ?
Because it's not like they're blocked waiting for a response from the commit request.
Bởi vì không phải là họ bị chặn để chờ phản hồi cho yêu cầu commit.
So if you can free them up and let them do whatever, prepare the retry, then they can go ahead and do that. But we're talking microseconds, nanoseconds difference between the two.
Nên nếu bạn có thể giải phóng họ và để họ làm việc khác, chuẩn bị thử lại, thì họ có thể tiến hành ngay. Nhưng chênh lệch giữa hai cách chỉ là micro giây, nano giây.
Because again, you're not going to wait for these guys to acknowledge that they've aborted. You just need to tell the outside world you aborted.
Bởi vì một lần nữa, bạn sẽ không chờ các node này xác nhận rằng chúng đã hủy giao dịch. Bạn chỉ cần báo cho thế giới bên ngoài biết là bạn đã hủy.
So whether you do one versus the other, it's not a correctness issue.
Vì vậy làm cách này hay cách kia thì cũng không phải là vấn đề về tính đúng đắn.
The question is, what's the point of this last OK for a node? Why does node one need to wait for it? Or why do they need to send it back?
Câu hỏi là: mục đích của lời OK cuối cùng này đối với một node là gì? Tại sao node một phải chờ nó? Hay tại sao họ phải gửi nó trở lại?
So the question is, why even bother sending back the acknowledgment that we've successfully aborted? Did we even record every step of the process of what happened?
Vậy câu hỏi là, tại sao còn phải bận tâm gửi lại xác nhận rằng chúng ta đã hủy thành công? Liệu chúng ta đã ghi lại mọi bước của quá trình đã xảy ra chưa?
So these nodes are recording their log, hey, we got an abort message for this transaction.
Các node này đang ghi vào log của chúng rằng, này, chúng tôi đã nhận được thông điệp hủy cho giao dịch này.
The coordinator is going to record in its own log that it got back the acknowledgment for that abort message.
Bộ điều phối sẽ ghi vào log của riêng nó rằng nó đã nhận lại xác nhận cho thông điệp hủy đó.
Because if the coordinator crashes, which we'll cover in the next slide, and I come back, I've got to know, what was I doing at the time?
Bởi vì nếu bộ điều phối bị sập, điều mà ta sẽ nói ở slide tiếp theo, và tôi khởi động lại, tôi phải biết lúc đó mình đang làm gì.
I don't know whether or not these guys have been told this transaction has been aborted or not, unless they get back the acknowledgment. So we're being overly cautious here. Yes?
Tôi không biết các node này đã được báo là giao dịch này bị hủy hay chưa, trừ khi chúng gửi lại xác nhận. Nên ở đây chúng ta đang thận trọng quá mức. Bạn hỏi à?
So your question is, what happens here? So if I go, everyone says we're going to go ahead and commit.
Câu hỏi của bạn là chuyện gì xảy ra ở đây? Giả sử mọi người đều nói là sẽ tiến hành commit.
And then all of a sudden, one of these nodes comes back on the second phase and says no. In that case, that's considered a failure on that node.
Rồi đột nhiên, một trong các node này ở pha thứ hai lại trả lời là không. Trường hợp đó được coi là lỗi trên node đó.
The transaction is still committed, because everyone agreed. Since you got past the first phase, everyone agreed that this transaction is going to commit.
Giao dịch vẫn được commit, vì mọi người đã đồng ý. Vì bạn đã qua được pha đầu tiên, mọi người đã đồng ý rằng giao dịch này sẽ commit.
So if the second phase does something weird, like doesn't send back a response, or sends back an OK, which it shouldn't, but it might, because of some bug, then that node is considered faulty.
Nên nếu pha thứ hai có điều gì kỳ lạ, như không gửi lại phản hồi, hoặc gửi lại một OK, điều mà lẽ ra không nên, nhưng có thể xảy ra vì một lỗi nào đó, thì node đó bị coi là bị lỗi.
And therefore, it should crash. The transaction is still committed.
Và do đó, nó nên bị sập. Giao dịch vẫn được commit.
And then the system has to bring up another node to replace it, and then replay the log to know that that transaction has successfully committed.
Sau đó hệ thống phải khởi động một node khác để thay thế nó, rồi phát lại log để biết rằng giao dịch đó đã commit thành công.
So his question is, if one guy goes down during the commit phase, can we still tell the outside world that you committed? Yes.
Vậy câu hỏi của bạn là, nếu một node bị sập trong pha commit, liệu ta vẫn có thể báo cho thế giới bên ngoài biết là đã commit không? Có.
So I've already said this, but again, we basically need to record in our log all the inbound, outbound messages we have for every step along the way.
Tôi đã nói điều này rồi, nhưng nhắc lại, về cơ bản ta cần ghi vào log tất cả các thông điệp đến và đi ở mỗi bước trong suốt quá trình.
And just like in the write-ahead log, ideally, I want to make sure I flush those messages to disk before I send out any acknowledgment.
Và cũng như trong write-ahead log, lý tưởng nhất, tôi muốn đảm bảo đã flush các thông điệp đó xuống đĩa trước khi gửi đi bất kỳ xác nhận nào.
If I get the inbound message, I'm going to say, hey, I'm going to send an outbound message that I'm OK with voting this.
Nếu tôi nhận được thông điệp đến, tôi sẽ nói, này, tôi sắp gửi một thông điệp đi rằng tôi đồng ý bỏ phiếu cho giao dịch này.
I want to flush that before maybe I send it out, before I can say my transaction is fully committed. Most systems don't do that. There's a small window.
Tôi muốn flush nó trước khi có thể gửi nó đi, trước khi tôi có thể nói giao dịch của mình đã commit hoàn toàn. Hầu hết các hệ thống không làm vậy. Có một khoảng hở nhỏ.
Again, you could potentially lose things. But it's not like you're going to lose the changes for a transaction, potentially, because someone's still going to be recording, here's all the events that occurred.
Một lần nữa, bạn có thể bị mất dữ liệu. Nhưng không phải là bạn sẽ mất các thay đổi của một giao dịch, về mặt khả năng, vì vẫn sẽ có ai đó ghi lại rằng đây là tất cả các sự kiện đã xảy ra.
And so therefore, it just makes recovery longer. And that's why most systems do this optimization.
Và do đó, nó chỉ làm cho việc khôi phục lâu hơn. Và đó là lý do hầu hết các hệ thống đều dùng tối ưu hóa này.
So now, if I crash, if a transaction was in a prepared state on my node when I wake up, then I've got to go talk to the coordinator and say, hey, I'm new to the game, or I crashed and came back.
Vậy bây giờ, nếu tôi bị sập, nếu một giao dịch đang ở trạng thái prepared trên nút của tôi khi tôi khởi động lại, thì tôi phải đi hỏi coordinator và nói: này, tôi mới vào cuộc, hoặc tôi vừa bị sập rồi quay lại.
What happened to this guy? And the coordinator would tell you what happened. If the transaction was still actively running and didn't actually begin the commit process, then you know it should be aborted.
Chuyện gì đã xảy ra với giao dịch này? Và coordinator sẽ cho bạn biết. Nếu giao dịch vẫn đang chạy và thực sự chưa bắt đầu quá trình commit, thì bạn biết là nó nên bị hủy bỏ.
But then if the coordinator crashes, then you basically have to figure out: did everyone agree that this transaction is allowed to commit, and did we send any outbound messages to the application that committed?
Nhưng nếu coordinator bị sập, thì về cơ bản bạn phải xác định: mọi bên có đồng ý rằng giao dịch này được phép commit không, và chúng ta có gửi thông điệp nào ra ngoài tới ứng dụng báo rằng đã commit không?
Actually, that one you can't check. But if everyone agreed that the thing was committed, then the transaction is considered committed.
Thật ra, điều đó thì bạn không thể kiểm tra được. Nhưng nếu mọi bên đều đồng ý rằng giao dịch đã được commit, thì giao dịch được coi là đã commit.
And you may not even get the acknowledgment to the application, but everyone agreed that the transaction committed. So you need to make sure that actually happens. So I think I've already said this.
Và có thể ứng dụng thậm chí không nhận được xác nhận, nhưng mọi bên đã đồng ý rằng giao dịch đã commit. Vì vậy bạn cần đảm bảo điều đó thực sự xảy ra. Tôi nghĩ tôi đã nói điều này rồi.
If the coordinator crashes, the participants basically figure out what should happen.
Nếu coordinator bị sập, thì các participant về cơ bản sẽ tự xác định điều gì nên xảy ra.
And the simplest thing to do is just say, hey, coordinator crashes, the transaction gets aborted, and then you elect a new coordinator if necessary.
Và cách đơn giản nhất là chỉ cần nói: này, coordinator bị sập thì giao dịch bị hủy bỏ, rồi bạn bầu một coordinator mới nếu cần.
If you want to be kind of clever, you could then get them to reorganize themselves and try to figure out whether the transaction is allowed to commit. But most systems don't do that.
Nếu bạn muốn khôn khéo hơn một chút, bạn có thể cho họ tự tổ chức lại và cố xác định xem giao dịch có được phép commit hay không. Nhưng hầu hết các hệ thống không làm vậy.
And again, while you're doing this reorganization process, you can't commit any other transactions because you need to find out whether the preceding transaction has successfully committed or not.
Và một lần nữa, trong lúc bạn thực hiện quá trình tổ chức lại này, bạn không thể commit bất kỳ giao dịch nào khác vì bạn cần biết giao dịch đứng trước đã commit thành công hay chưa.
So then I know that I'm always moving forward in time in my state machine.
Như vậy tôi biết rằng mình luôn tiến về phía trước theo thời gian trong máy trạng thái của mình.
So one participant goes down, and I can figure out how to be clever and try to reorganize things and allow the transaction to commit.
Vậy một participant bị sập, và tôi có thể tìm cách khôn khéo, thử tổ chức lại mọi thứ và cho phép giao dịch commit.
It may not be worth it because I'm blocking other transactions from committing.
Có thể không đáng, vì tôi đang chặn các giao dịch khác không được commit.
If the participant crashes, then we just assume that the coordinator assumed the participant was going to vote for abort, assuming we're still in the first phase. And then we just abort the transaction.
Nếu participant bị sập, thì chúng ta chỉ cần giả định rằng coordinator cho rằng participant sẽ bỏ phiếu hủy bỏ, giả sử chúng ta vẫn đang ở pha đầu tiên. Và rồi chúng ta chỉ việc hủy bỏ giao dịch.
Because there's no guarantee that the changes that they were going to make landed correctly on the participant. So we can't allow the transaction to commit.
Vì không có gì đảm bảo rằng các thay đổi mà họ định thực hiện đã được ghi đúng trên participant. Vì vậy chúng ta không thể cho phép giao dịch commit.
So there's two ways to make this a little faster. I mean, I've already talked about one, where you don't log everything on disk.
Có hai cách để làm cho việc này nhanh hơn một chút. Ý tôi là, tôi đã nói về một cách rồi, đó là không ghi mọi thứ xuống đĩa.
That's an obvious one. But you can do two slight modifications. One is very common. One is not that common.
Đó là cách hiển nhiên. Nhưng bạn có thể thực hiện hai điều chỉnh nhỏ. Một cái rất phổ biến. Một cái thì không phổ biến lắm.
So early prepare voting basically means that if I know that the query I'm going to be executing on a node is the last query I'm ever going to be executing for that transaction, then when I send my query request message, I also send along, or piggyback on that message, "Hey, by the way, I'm going to go ahead and commit after this query.
Vậy early prepare voting về cơ bản có nghĩa là nếu tôi biết rằng truy vấn mà tôi sắp thực thi trên một nút là truy vấn cuối cùng mà tôi từng thực thi cho giao dịch đó, thì khi gửi thông điệp yêu cầu truy vấn, tôi cũng gửi kèm, hay gói thêm vào thông điệp đó: "Này, nhân tiện, tôi sẽ commit ngay sau truy vấn này.
So give me back your vote for two-phase commit." This assumes that your application can expose in some way the logic that this is the last query for my transaction.
Vậy hãy trả lại phiếu bầu của bạn cho two-phase commit." Điều này giả định rằng ứng dụng của bạn có thể bằng cách nào đó cho biết rằng đây là truy vấn cuối cùng của giao dịch.
Because you don't want to, you know, this can't be like a guess. You can't say, "Oh, I'm going to run a query and go ahead and commit," and then come back with another query.
Vì bạn không muốn, bạn biết đấy, đây không thể là một phỏng đoán. Bạn không thể nói: "À, tôi sẽ chạy một truy vấn và commit luôn", rồi sau đó lại quay lại với một truy vấn khác.
You have to say, "I'm definitely done running this." So you can do that with stored procedures, where you have all the logic running inside, the application logic running inside the database server.
Bạn phải nói: "Chắc chắn là tôi đã chạy xong." Vì vậy bạn có thể làm điều đó với stored procedure, nơi toàn bộ logic chạy bên trong, tức là logic ứng dụng chạy bên trong máy chủ cơ sở dữ liệu.
I think of it like an RPC call. So that's pretty rare. But what's more common is to do early acknowledgement.
Tôi coi nó giống như một lời gọi RPC. Nên cái này khá hiếm. Nhưng phổ biến hơn là early acknowledgement.
And basically, when I go to commit the transaction, once the coordinator gets the acknowledgement from all the participants that the transaction is about to commit, rather than waiting for the second round trip for the second phase, or the commit phase, I immediately send back the acknowledgement that the transaction is committed.
Về cơ bản, khi tôi commit giao dịch, ngay khi coordinator nhận được xác nhận từ tất cả các participant rằng giao dịch sắp được commit, thay vì chờ vòng khứ hồi thứ hai cho giai đoạn thứ hai, hay giai đoạn commit, tôi gửi lại ngay xác nhận rằng giao dịch đã được commit.
So it looks like this. Commit request shows up. I do the first round. Prepare. Everyone votes. OK.
Nó trông thế này. Yêu cầu commit đến. Tôi thực hiện vòng đầu tiên. Prepare. Mọi nút bỏ phiếu. OK.
And again, at this point here, if I run the regular two-phase commit protocol, I've got to then switch into the second phase, do another round trip.
Và một lần nữa, đến đây, nếu tôi chạy giao thức two-phase commit thông thường, tôi phải chuyển sang giai đoạn thứ hai, thực hiện thêm một vòng khứ hồi.
And then once everyone agrees that this thing is committed, then send back the acknowledgement.
Và khi mọi nút đồng ý rằng giao dịch này đã được commit, thì mới gửi lại xác nhận.
But with early acknowledgement, Once I get back from the first phase that everyone agrees that this transaction is going to commit, then I can tell the application they've committed.
Nhưng với early acknowledgement, ngay khi tôi nhận lại từ giai đoạn đầu tiên rằng mọi nút đồng ý giao dịch này sẽ được commit, thì tôi có thể báo cho ứng dụng biết là nó đã commit.
And the idea is, again, that the likelihood that I'm going to fail and not be able to record my transaction is low, assuming I'm logging things in an appropriate manner.
Và ý tưởng là, một lần nữa, khả năng tôi gặp sự cố và không thể ghi lại giao dịch của mình là thấp, giả sử tôi ghi log một cách phù hợp.
But I still have to run the second phase. And I can't commit any other transaction until this transaction commits.
Nhưng tôi vẫn phải chạy giai đoạn thứ hai. Và tôi không thể commit bất kỳ giao dịch nào khác cho đến khi giao dịch này commit.
So two-phase commit was used in some of the first distributed databases in the late 1970s, early 1980s.
Two-phase commit đã được dùng trong một số cơ sở dữ liệu phân tán đầu tiên vào cuối những năm 1970, đầu những năm 1980.
But again, it has this problem that, again, if one of the nodes goes down during my transaction, I have to stall the entire system until that node recovers.
Nhưng nó có vấn đề là, nếu một trong các nút ngừng hoạt động trong lúc giao dịch của tôi chạy, tôi phải làm đình trệ toàn bộ hệ thống cho đến khi nút đó phục hồi.
And then we can then continue running.
Và sau đó hệ thống có thể tiếp tục chạy.
So what Paxos and Raft and ViewstampedReplication solve is the ability to not require all participants to acknowledge that a transaction is committed. And you only require a majority.
Vậy điều mà Paxos và Raft cùng ViewstampedReplication giải quyết được là khả năng không yêu cầu mọi bên tham gia phải xác nhận rằng một giao dịch đã được commit. Và bạn chỉ cần đa số.
So this gives you the guarantee that even if some of the nodes go down, you can still make forward progress as long as you have a majority of the nodes agree that a transaction is allowed to commit.
Như vậy bạn có được đảm bảo rằng dù một số nút bị sập, bạn vẫn có thể tiếp tục tiến triển miễn là có đa số các nút đồng ý rằng một giao dịch được phép commit.
So ViewstampedReplication was the first one that was provably correct to be resilient in asynchronous networks. And then Paxos came out a year later. Who here has read the Paxos paper? What do you think?
ViewstampedReplication là thuật toán đầu tiên được chứng minh là đúng đắn và có khả năng chịu lỗi trong các mạng bất đồng bộ. Rồi một năm sau Paxos ra đời. Ở đây ai đã đọc bài báo về Paxos rồi? Các bạn thấy sao?
It's a wild ride. So go read it tonight. You will not find any other paper written like this in computer science. So it's written by Leslie Lamport.
Đúng là một chuyến phiêu lưu điên rồ. Tối nay hãy đọc thử đi. Bạn sẽ không tìm thấy bài báo nào khác trong khoa học máy tính được viết như thế này. Bài báo do Leslie Lamport viết.
He won the Turing Award, oh, seven years ago or so, for seminal work in distributed systems. He's at Microsoft Research now. The paper, he originally wrote it in '89.
Ông ấy đã nhận giải Turing, ồ, khoảng bảy năm trước, nhờ công trình nền tảng về hệ phân tán. Hiện ông ở Microsoft Research. Ban đầu ông viết bài báo này vào năm 1989.
But it isn't like a computer science paper describing algorithms. It's written as if he's an archaeologist discovering this ancient Greek tribe on the island of Paxos.
Nhưng nó không giống một bài báo khoa học máy tính mô tả thuật toán. Nó được viết như thể ông là một nhà khảo cổ phát hiện ra một bộ tộc Hy Lạp cổ đại trên đảo Paxos.
And it talks about how they would do voting in an early democratic society by writing on stone tablets, throwing them into a hole.
Và bài báo kể về cách họ bỏ phiếu trong một xã hội dân chủ sơ khai bằng cách viết lên các bảng đá, rồi ném chúng vào một cái hố.
And then other people in the village or the town would come look through the hole and pull out the tablets and look at what happened.
Sau đó những người khác trong làng hay thị trấn sẽ đến nhìn qua cái hố và lấy các bảng đá ra xem chuyện gì đã xảy ra.
So you can't take this paper and actually implement anything from it. It's just inscrutable. It's hilarious. As he said, it's a lot.
Nên bạn không thể lấy bài báo này rồi cài đặt thực sự bất cứ thứ gì từ nó. Nó khó hiểu kinh khủng. Buồn cười thật. Như ông ấy nói, nó rất nhiều thứ.
It's very challenging. So the story goes, he wrote this paper in '89. It got rejected by whatever the peer review committee that he submitted to, the conference he submitted to.
Rất thách thức. Chuyện kể rằng ông viết bài này năm 1989. Nó bị từ chối bởi hội đồng phản biện của hội nghị mà ông đã gửi bài.
And then he put it in his filing cabinet and didn't touch it for years.
Rồi ông cất nó vào tủ hồ sơ và không đụng đến suốt nhiều năm.
And then a bunch of people were writing other papers that were kind of dancing around and trying to solve roughly the same idea that Paxos had already solved.
Sau đó có nhiều người viết các bài báo khác cứ loanh quanh và cố giải quyết gần như cùng ý tưởng mà Paxos đã giải quyết rồi.
So then he pulled it out and dusted it off and then resubmitted it.
Thế là ông lôi nó ra, phủi bụi rồi nộp lại.
So if you go read the paper here, there's this little gray box blurb that talks about how this submission was recently discovered behind a filing cabinet in the TOCS editorial office.
Nếu bạn đọc bài báo, sẽ thấy có một khung chú thích nhỏ màu xám nói rằng bản nộp này mới được phát hiện phía sau một tủ hồ sơ trong văn phòng biên tập của TOCS.
Despite its age, the editor-in-chief thought it would be worth publishing. Because this is the reissue for Leslie Lamport after it got rejected.
Dù đã cũ, tổng biên tập vẫn thấy nó đáng được xuất bản. Vì đây là bản phát hành lại cho Leslie Lamport sau khi bị từ chối.
And so if you go to Leslie Lamport's website, he's got this chronology that talks about all his papers and where he was living, who he was dating, or what he was eating for every single one of these papers.
Và nếu bạn vào trang web của Leslie Lamport, ông có một bản niên biểu kể về tất cả các bài báo của mình và lúc đó ông sống ở đâu, đang hẹn hò với ai, hay đã ăn gì cho từng bài báo một.
So for the Paxos paper, he talks about how he submitted it. He thought it was a genius work of art.
Với bài báo Paxos, ông kể về việc ông đã nộp nó như thế nào. Ông nghĩ đó là một tác phẩm nghệ thuật thiên tài.
And the reviewing committee, they were all idiots, and they couldn't see his brilliance of it.
Còn hội đồng phản biện thì toàn là lũ ngốc, và họ không nhìn ra sự xuất chúng của nó.
So when I was in grad school, I presented this paper in my distributed systems class, and I said basically the same thing. Oh, this paper is a work of art.
Hồi tôi còn học cao học, tôi đã thuyết trình bài báo này trong lớp hệ thống phân tán của mình, và về cơ bản tôi đã nói y như vậy. Ồ, bài báo này là một tác phẩm nghệ thuật.
Those reviewers were all stupid for rejecting it. It turns out, though, the professor in the class, for the class, was one of the reviewers for it, Maurice Herlihy.
Những người phản biện đó thật ngu ngốc khi từ chối nó. Nhưng hóa ra, giáo sư dạy lớp đó, của lớp đó, lại chính là một trong những người phản biện bài này, Maurice Herlihy.
He used to be at CMU, and now he's at Brown. And he says, which I believe him, not Leslie Lamport's retelling.
Ông ấy từng ở CMU, và bây giờ ở Brown. Và ông ấy nói, mà tôi tin ông ấy, chứ không phải bản kể lại của Leslie Lamport.
He said that they were OK with all this archaeology stuff, but they just wanted him to add an appendix with the algorithm to explain how to actually implement this thing.
Ông ấy nói rằng họ không phản đối mấy chuyện khảo cổ này, nhưng họ chỉ muốn ông ấy thêm một phụ lục trình bày thuật toán để giải thích cách thực sự triển khai thứ này.
And Leslie Lamport refused to make any change because he thought it was pristine, or thought it was perfect, the way it was submitted.
Và Leslie Lamport từ chối sửa bất cứ điều gì vì ông cho rằng nó hoàn hảo nguyên bản, hay nghĩ rằng nó hoàn hảo như cách ông đã nộp.
So that's why it was rejected. And then again, you can't read this. You can't implement anything. Then he did a follow-up paper called Paxos Made Simple.
Đó là lý do nó bị từ chối. Và đúng vậy, bạn không thể đọc nổi bài này. Bạn không thể triển khai được gì cả. Sau đó ông viết một bài tiếp theo tên là Paxos Made Simple.
That one is not simple either. That one you can't understand. The best paper to read to understand Paxos is Paxos Made Live from Google.
Bài đó cũng không đơn giản. Bài đó bạn cũng không hiểu nổi. Bài hay nhất để đọc và hiểu Paxos là Paxos Made Live của Google.
It was like 2004, because they implemented this in their Chubby Lock service and a bunch of other things.
Khoảng năm 2004, vì họ đã triển khai nó trong dịch vụ khóa Chubby và nhiều thứ khác.
So the thing to understand about the difference between Paxos and Two-Phase Commit: Two-Phase Commit is a degenerate case of Paxos.
Vậy điều cần hiểu về sự khác biệt giữa Paxos và Two-Phase Commit là: Two-Phase Commit là một trường hợp suy biến của Paxos.
And there's a paper in 2006 from Leslie Lamport, the author of Paxos, and Jim Gray, the guy that did early Two-Phase Commit work, where they prove that Two-Phase Commit is just a subset of Paxos.
Và có một bài báo năm 2006 của Leslie Lamport, tác giả của Paxos, và Jim Gray, người đã làm những công trình đầu tiên về Two-Phase Commit, trong đó họ chứng minh Two-Phase Commit chỉ là một tập con của Paxos.
And Raft came out later. But they're all basically the same thing.
Raft ra đời sau. Nhưng về cơ bản tất cả đều là một.
The key idea here is that in Paxos, we only need a majority of participants to agree that a transaction is allowed to commit, rather than a unanimous decision that you would in Two-Phase Commit.
Ý tưởng chính ở đây là trong Paxos, chúng ta chỉ cần đa số các bên tham gia đồng ý rằng một giao dịch được phép commit, thay vì quyết định nhất trí tuyệt đối như trong Two-Phase Commit.
So it looks like this. Same as I said before. I have four nodes. My application says I want to commit. Under Paxos, they don't call them coordinators or participants.
Nó trông như thế này. Giống như tôi đã nói trước đó. Tôi có bốn nút. Ứng dụng của tôi nói rằng tôi muốn commit. Trong Paxos, người ta không gọi chúng là coordinator hay participant.
They're going to call them proposers and acceptors.
Họ gọi chúng là proposer và acceptor.
There's a third category of nodes in Paxos called learners, which are basically things that observe the changes to the state machine or the commit order log, but aren't allowed to vote.
Có loại nút thứ ba trong Paxos gọi là learner, về cơ bản là những thứ quan sát các thay đổi đối với máy trạng thái hoặc nhật ký thứ tự commit, nhưng không được phép bỏ phiếu.
But we don't care about that. It's just an add-on.
Nhưng ta không quan tâm đến điều đó. Nó chỉ là phần bổ sung.
So now we're going to do the same thing. In the first round, we're going to send a propose message to all the nodes.
Bây giờ ta sẽ làm điều tương tự. Ở vòng đầu tiên, ta sẽ gửi một thông điệp propose đến tất cả các nút.
And they're all going to vote for whether a transaction is allowed to commit. And if they all agree, if a majority agrees, then we're going to do this.
Và tất cả sẽ bỏ phiếu xem giao dịch có được phép commit hay không. Và nếu tất cả đồng ý, nếu đa số đồng ý, thì ta sẽ làm như sau.
So let's say the case, though, the setup we had before, where the middle guy dies while this transaction runs.
Vậy giả sử trường hợp, với thiết lập trước đó, khi nút ở giữa chết trong lúc giao dịch này chạy.
So the bottom one and the top one say, yes, we can go ahead and agree to commit this transaction.
Thì nút dưới cùng và nút trên cùng nói rằng, vâng, chúng tôi đồng ý commit giao dịch này.
So under Paxos, this is still allowed now to proceed and do the commit, because a majority agrees that this transaction is allowed to commit. So two out of three.
Vậy trong Paxos, giao dịch này vẫn được phép tiến hành và commit, vì đa số đồng ý rằng giao dịch này được phép commit. Vậy là hai trên ba.
So then we go ahead and agree this transaction is allowed to commit. And then once they all come back and say, yeah, we got it, then we send back the acknowledgment to the application.
Thế là chúng ta thống nhất rằng giao dịch này được phép commit. Và khi tất cả các nút phản hồi lại, kiểu như "vâng, chúng tôi nhận được rồi", thì chúng ta gửi xác nhận về cho ứng dụng.
Now, when the middle guy who crashed comes back, again, they have to go look at the log and go figure out what they missed.
Bây giờ, khi nút ở giữa vừa bị sập hoạt động trở lại, một lần nữa, nó phải xem log và tìm hiểu xem mình đã bỏ lỡ những gì.
Or if I can failover to a replica of this node, then it has to then learn that this thing has been successfully committed.
Hoặc nếu tôi chuyển sang một bản sao của nút này (failover), thì bản sao đó phải biết được rằng giao dịch này đã được commit thành công.
So there's an extra step to reconcile the state machine when there's failure.
Vì vậy có thêm một bước để đối chiếu lại trạng thái của máy trạng thái khi có sự cố.
And again, because we are assuming that our nodes are not malicious actors, that when they read the log, and they'll do what the log says, rather than like, oh, I'm not going to do that and throw things away and end up with an inconsistent state across the nodes.
Và một lần nữa, vì chúng ta giả định các nút không phải là những tác nhân độc hại, nên khi chúng đọc log, chúng sẽ làm theo những gì log ghi, chứ không phải kiểu như, ồ, tôi sẽ không làm thế mà vứt hết mọi thứ đi và cuối cùng dẫn đến trạng thái không nhất quán giữa các nút.
The question is, if this guy says abort, yes? Yes. If we're going to use Paxos to commit transactions. I see. Yes.
Câu hỏi là, nếu nút này nói abort thì sao? Vâng. Nếu chúng ta dùng Paxos để commit giao dịch. Tôi hiểu rồi. Vâng.
Sorry. If we're using Paxos to commit transactions, yes. If one guy says abort, then you have to abort. Because again, to your point, there could be integrity rights issues.
Xin lỗi. Nếu chúng ta dùng Paxos để commit giao dịch, thì vâng. Nếu một nút nói abort, thì bạn phải abort. Bởi vì, đúng như ý bạn nói, có thể có các vấn đề về ràng buộc toàn vẹn.
For other types of things you want to use Paxos for, like leader election, then you ignore them. So some things yes, some things no.
Còn với những việc khác bạn muốn dùng Paxos, như bầu chọn leader, thì bạn bỏ qua chúng. Vậy nên có việc thì có, có việc thì không.
The question is, Paxos would not be suitable? Because the idea is that I still have to wait for this guy to come back to say what happened.
Câu hỏi là, Paxos sẽ không phù hợp phải không? Bởi vì ý tưởng là tôi vẫn phải chờ nút này quay lại để cho biết chuyện gì đã xảy ra.
But if there's a timeout, the same as two-phase commit, if I get a majority agree that things are allowed to commit, then that's enough for me.
Nhưng nếu có timeout, giống như two-phase commit, nếu tôi nhận được đa số đồng ý rằng giao dịch được phép commit, thì thế là đủ với tôi.
And then this thing has to deal with it.
Và nút kia phải tự xử lý phần của nó.
So the question is, what if it dies and comes back and it should have been aborted? How do I say this?
Vậy câu hỏi là, nếu nó sập rồi quay lại và lẽ ra giao dịch phải bị abort thì sao? Tôi nên nói thế nào nhỉ?
Depending on what concurrency protocol you want to do, if it's two-phase locking, you would do all your integrity checks as the thing's running. Or you do all your locking checks as the thing's running.
Tùy vào giao thức điều khiển đồng thời bạn dùng, nếu là two-phase locking, bạn sẽ thực hiện mọi kiểm tra tính toàn vẹn ngay trong lúc giao dịch chạy. Hoặc bạn thực hiện mọi kiểm tra khóa ngay trong lúc giao dịch chạy.
With OCC, the validation step, you'd have to figure that out.
Với OCC, ở bước validation, bạn sẽ phải xác định điều đó.
If this is the only copy, node 3 is the only copy of the data you have, and therefore this is the only source in which you could figure out whether this transaction is allowed to commit, then you're going to have this problem.
Nếu đây là bản sao duy nhất, nút 3 là nơi duy nhất có dữ liệu của bạn, và do đó đây là nguồn duy nhất mà từ đó bạn có thể xác định xem giao dịch này có được phép commit hay không, thì bạn sẽ gặp vấn đề này.
So assume that there could be a replica that also could be involved in the process, like a learner, to decide that this thing wasn't allowed to commit.
Vậy hãy giả sử có thể có một bản sao cũng có thể tham gia vào quá trình này, như một learner, để quyết định rằng giao dịch này không được phép commit.
The question is, MVCC and Paxos would not be a good fit? I'm not saying that at all. I'm saying assume that it's not a single version, it's a single copy.
Câu hỏi là, MVCC và Paxos sẽ không kết hợp tốt phải không? Tôi hoàn toàn không nói vậy. Tôi đang nói hãy giả sử rằng đó không phải là một phiên bản duy nhất, mà là một bản sao duy nhất.
If node 3 is the only location for tuple A, if that thing goes down, then my system's hosed.
Nếu nút 3 là nơi duy nhất chứa tuple A, thì nếu nó sập, hệ thống của tôi coi như hỏng.
In order to make sure you don't have integrity constraint violations that you can't reverse later on, I either have to do them while the transaction is running, or I have to have a replica be able to be involved and decide whether this transaction is allowed to commit or not.
Để đảm bảo rằng bạn không gặp các vi phạm ràng buộc toàn vẹn mà sau này không thể hoàn tác được, Hoặc là tôi phải kiểm tra chúng trong lúc giao dịch đang chạy, hoặc là phải để một bản sao tham gia vào quá trình và quyết định xem giao dịch này có được phép commit hay không.
If node 3 comes back and disagrees, it can't. Because we assume these are non-malicious actors. So they will do whatever the log tells them to do when they come back up.
Nếu node 3 hoạt động trở lại và không đồng ý, thì giao dịch không thể commit. Vì chúng ta giả định đây là những tác nhân không có ý đồ xấu. Nên khi chạy lại, chúng sẽ làm bất cứ điều gì mà log bảo chúng làm.
The question is, if the commit process includes checking integrity constraints, then this devolves into two-phase commit, because I have to wait for everyone to agree that some.
Câu hỏi là, nếu quy trình commit bao gồm việc kiểm tra các ràng buộc toàn vẹn, thì nó sẽ biến thành two-phase commit, vì tôi phải chờ tất cả mọi người đồng ý về việc đó.
So again, if you're running transactions that could cause integrity violations, you have to know that before you go ahead and commit process. Because otherwise, you can't.
Vậy nên, nếu bạn chạy những giao dịch có thể gây vi phạm toàn vẹn, bạn phải biết điều đó trước khi tiến hành quy trình commit. Vì nếu không thì bạn không thể làm được.
But if it's a leader election, there's not going to be integrity constraint violations.
Nhưng nếu là bầu chọn leader, thì sẽ không có vi phạm ràng buộc toàn vẹn nào.
Replication, again, assuming non-malicious actors, that the replicas are going to mirror the state of whatever they're replicating. They have to.
Với replication, một lần nữa giả định các tác nhân không có ý đồ xấu, thì các bản sao sẽ phản chiếu trạng thái của thứ mà chúng đang sao chép. Chúng buộc phải như vậy.
The question is, is sharding more problematic? No.
Câu hỏi là, sharding có nhiều vấn đề hơn không? Không.
Yeah, the statement is, if it's sharded data, you can have integrity violations more easily. No, it doesn't matter if it's sharded, a single node.
Vâng, ý bạn là nếu dữ liệu được shard, thì dễ xảy ra vi phạm toàn vẹn hơn. Không, có shard hay chỉ một node thì cũng không khác gì.
Not null is not null, whether it's one node or multiple nodes. But I'm saying you would check those things while the transaction is making the changes.
Not null vẫn là not null, dù là một node hay nhiều node. Nhưng tôi muốn nói là bạn sẽ kiểm tra những điều đó trong lúc giao dịch đang thực hiện các thay đổi.
If you start doing reconnaissance transactions, the way Dyno does transactions is you run all the queries. You don't actually do any changes. It's sort of like repeating that scan we did to avoid phantoms.
Nếu bạn bắt đầu dùng các giao dịch thăm dò, thì cách Dyno thực hiện giao dịch là chạy tất cả các truy vấn. Thực ra bạn chưa thực hiện thay đổi nào. Nó hơi giống việc lặp lại lần quét mà ta đã làm để tránh phantom.
So you run all the queries, record what they're going to do. At that point, you check to see whether they have any integrity constraint violations. But you didn't actually make any changes.
Vậy bạn chạy tất cả truy vấn, ghi lại những gì chúng sẽ làm. Tại thời điểm đó, bạn kiểm tra xem chúng có vi phạm ràng buộc toàn vẹn nào không. Nhưng bạn chưa thực sự thay đổi gì cả.
So I just know I'm trying to insert something that can't be null, and I'm trying to insert something null. So you would do that before it runs. And then you go to commit.
Nên tôi chỉ biết là mình đang cố chèn một giá trị không được phép null, mà lại đang chèn giá trị null. Vậy bạn sẽ kiểm tra điều đó trước khi chạy. Rồi sau đó mới commit.
And then that's when you apply all the changes. And therefore, you won't have any integrity constraint violations because you checked beforehand.
Và lúc đó mới áp dụng tất cả các thay đổi. Và do đó, bạn sẽ không có vi phạm ràng buộc toàn vẹn nào vì đã kiểm tra từ trước.
But whether or not you're running these queries one at a time or in a batch, you would check these things as they're running.
Nhưng dù bạn chạy các truy vấn này từng cái một hay theo lô, bạn vẫn sẽ kiểm tra những điều này khi chúng đang chạy.
The question is, if I try to insert something and it would duplicate the value, I could still have the integrity constraint violation. So again, that's if you're doing phantom checks. But hold up.
Câu hỏi là, nếu tôi cố chèn một thứ gì đó mà nó làm trùng giá trị, thì tôi vẫn có thể bị vi phạm ràng buộc toàn vẹn. Đúng, đó là khi bạn kiểm tra phantom. Nhưng khoan đã.
They're still doing two-phase locking. You're still doing all the other high-level things. So inserting, you wouldn't take locks on the inserts. How do I say this?
Họ vẫn đang dùng two-phase locking. Bạn vẫn làm tất cả những việc ở mức cao khác. Vậy với việc chèn, bạn sẽ không lấy khóa trên các lần chèn. Nói thế nào nhỉ?
You don't have to wait for impacts. You're not going to wait for everyone to come back. Actually, you just have to wait for everything. Yeah. This is hard. OK.
Bạn không phải chờ các xung đột. Bạn sẽ không chờ tất cả mọi người quay lại. Thực ra, bạn phải chờ tất cả mọi thứ. Ừ. Chỗ này khó. OK.
I'm trying to think of a concrete example of how this would work.
Tôi đang cố nghĩ ra một ví dụ cụ thể về cách việc này hoạt động.
Let me follow up on this next week or next class. Just in general, assume that by the time you go to commit, everyone has to agree that this is allowed to happen.
Để tôi trả lời tiếp vấn đề này vào tuần sau hoặc buổi học sau. Nói chung, hãy giả sử rằng đến lúc bạn thực hiện commit, mọi người đều phải đồng ý rằng việc này được phép xảy ra.
So you don't try to undo certain things. OK.
Nên bạn không cố hoàn tác một số thứ. OK.
So let me just plow through this. Again, if you're taking a distributed systems class, this is nothing new. Basically, you have these proposers. They say they want to commit.
Vậy để tôi lướt nhanh qua phần này. Một lần nữa, nếu bạn đang học môn hệ phân tán thì điều này không có gì mới. Về cơ bản, bạn có các proposer. Họ nói muốn commit.
And then they all agree. But then at any time, someone says, hey, I want to propose a new transaction. The way Paxos works, you ensure that you have liveness property.
Và sau đó tất cả đều đồng ý. Nhưng bất kỳ lúc nào, cũng có người nói: này, tôi muốn đề xuất một giao dịch mới. Cách Paxos hoạt động là đảm bảo bạn có tính chất liveness.
You're always moving forward in time.
Bạn luôn tiến về phía trước theo thời gian.
As soon as somebody else says, I want to go to commit a new transaction before the first one has finished, then immediately, the acceptors can't allow that transaction to commit because they've learned about a new one.
Ngay khi có người khác nói rằng họ muốn commit một giao dịch mới trước khi giao dịch đầu tiên kết thúc, thì lập tức, các acceptor không thể cho phép giao dịch đó commit vì họ đã biết về một giao dịch mới.
So they reject it and say, you told us about committing transaction n, but we now know about n plus 1, so we can't commit you.
Nên họ từ chối và nói: bạn đã báo cho chúng tôi về việc commit giao dịch n, nhưng giờ chúng tôi biết về n cộng 1, nên không thể commit giao dịch của bạn.
And then you go ahead and agree to this other one. And then they commit, say yes. And then the bottom guy has to then resubmit the transaction to get committed again.
Rồi bạn đồng ý với giao dịch kia. Và họ commit, nói là đồng ý. Và sau đó bên dưới phải gửi lại giao dịch để được commit lần nữa.
It's basically, again, avoiding this blocking forever. You allow transactions to always move forward in time. Of course, it's now problematic.
Về cơ bản, một lần nữa, điều này tránh bị chặn vĩnh viễn. Bạn cho phép các giao dịch luôn tiến về phía trước theo thời gian. Tất nhiên, giờ lại có vấn đề.
If you have proposers clobbering each other all the time, trying to commit new transactions, then you never get any work done. So this is where multipaxes comes in. And this is from Google.
Nếu các proposer liên tục đè lên nhau, cố commit các giao dịch mới, thì bạn sẽ không bao giờ hoàn thành được việc gì. Đây là lúc Multi-Paxos xuất hiện. Và cái này đến từ Google.
And basically, you just do leader election, which is another transaction on the state of the system: who's the leader? And the leader is only allowed to commit transactions, or propose that we commit transactions.
Về cơ bản, bạn chỉ cần bầu chọn leader, đó là một giao dịch khác trên trạng thái của hệ thống: ai là leader? Và leader là bên duy nhất được phép commit các giao dịch, hoặc đề xuất việc commit các giao dịch.
And any time the leader fails, then you just run leader election again and elect a new one.
Và bất cứ khi nào leader gặp sự cố, thì bạn chỉ cần chạy lại bầu chọn leader và bầu một leader mới.
So you're doing multiple rounds of Paxos to both commit transactions and decide who's the leader within a quorum.
Vậy bạn chạy nhiều vòng Paxos để vừa commit các giao dịch vừa quyết định ai là leader trong một quorum.
So how long you're going to wait, for how long the leases last, depends on the implementation. I think Spanner is 10 seconds. Cockroach is like five minutes.
Còn chờ bao lâu, các lease kéo dài bao lâu, thì tùy vào cách triển khai. Tôi nghĩ Spanner là 10 giây. Cockroach khoảng năm phút.
TiDB is 10, 15 seconds. I forget what YugabyteDB is. But different systems do different things.
TiDB là 10, 15 giây. Tôi quên YugabyteDB là bao nhiêu. Nhưng mỗi hệ thống làm một kiểu khác nhau.
The question is, why do you need to periodically ask if you knew the leader? Because how do I know it's alive? Right?
Câu hỏi là: tại sao cần định kỳ hỏi xem có biết leader không? Vì làm sao tôi biết nó còn sống? Đúng không?
And again, the idea is if I'm doing leader election all the time, over and over again, then I'm doing leader election instead of committing transactions.
Và một lần nữa, ý tưởng là nếu tôi cứ bầu chọn leader liên tục, lặp đi lặp lại, thì tôi đang bầu leader thay vì commit các giao dịch.
But then if I don't do it that often, then I may end up with the thing crashes and takes me a while. Then here's the new leader. And I'm stalling transactions until that happens.
Nhưng nếu tôi không làm thường xuyên như vậy, thì có thể nó bị sập và tôi mất một lúc mới xử lý được. Rồi đây là leader mới. Và tôi phải làm các giao dịch đứng chờ cho đến khi điều đó xảy ra.
You basically, again, Paxos will allow us to avoid, when the leader goes down, you have now two nodes say, I want to be the leader.
Về cơ bản, một lần nữa, Paxos sẽ cho phép chúng ta tránh được tình huống khi leader sập, lúc này có hai nút cùng nói: tôi muốn làm leader.
And then you do leader election to decide which one can be the leader. And it's sort of like, going back here, it's this clobbering thing.
Và khi đó bạn thực hiện bầu chọn leader để quyết định nút nào được làm leader. Và nó giống như, quay lại chỗ này, là kiểu chúng giẫm đè lên nhau.
So say the best thing, I want to be the leader. But the idea is that as soon as I see a new proposal from another node, I throw away any other outstanding proposals.
Giả sử nút tốt nhất nói: tôi muốn làm leader. Nhưng ý tưởng là ngay khi tôi thấy một đề xuất mới từ nút khác, tôi bỏ đi mọi đề xuất còn đang chờ khác.
So ideally, eventually, somebody will be able to get in and commit. And then they become the new leader. So you would just do a simple exponential backoff.
Vì vậy lý tưởng là cuối cùng sẽ có một nút chen vào được và commit. Và rồi nó trở thành leader mới. Vì vậy bạn chỉ cần dùng một cơ chế exponential backoff đơn giản.
If I try to propose something and I get denied because somebody else proposed something, then I'll wait 50 milliseconds, and then 100 milliseconds. And that way, eventually, somebody will commit. Again, they're not malicious.
Nếu tôi cố đề xuất một thứ gì đó và bị từ chối vì có nút khác đã đề xuất trước, thì tôi sẽ chờ 50 mili giây, rồi sau đó 100 mili giây. Như vậy, cuối cùng sẽ có một nút commit được. Một lần nữa, các nút không có ý đồ xấu.
They're all trying to work together on this. You just need a quick and easy way to get them to back off and not clobber each other.
Tất cả đều đang cố gắng phối hợp với nhau. Bạn chỉ cần một cách nhanh và dễ để khiến chúng lùi lại và không giẫm đè lên nhau.
So again, the main takeaways I understand from Paxos, two-phase commit, and Raft, again, they're all essentially the same thing.
Vậy một lần nữa, những điểm chính cần nắm về Paxos, two-phase commit và Raft là về cơ bản chúng đều giống nhau.
In two-phase commit, you have to block the coordinator until everyone comes back or can respond or a timeout. And if one node goes down, then the transaction can't commit.
Trong two-phase commit, bạn phải chặn coordinator cho đến khi mọi nút quay lại hoặc phản hồi được, hoặc hết thời gian chờ. Và nếu một nút sập thì giao dịch không thể commit.
In Paxos, it's non-blocking as long as the majority are alive. And then in Raft, it's basically the same thing.
Trong Paxos, nó không bị chặn miễn là đa số các nút còn hoạt động. Còn Raft thì về cơ bản cũng giống vậy.
But the way they do a leader election is based on who has the most up-to-date version of the log and therefore is in the best state to become the leader.
Nhưng cách chúng bầu chọn leader dựa trên việc nút nào có phiên bản log mới nhất và do đó ở trạng thái tốt nhất để trở thành leader.
But at a high level, it basically works the same way. Instead of calling them learners, they call them followers. But again, at a high level, it's the same thing.
Nhưng ở mức tổng quan, về cơ bản nó hoạt động theo cùng một cách. Thay vì gọi là learner, họ gọi là follower. Nhưng một lần nữa, ở mức tổng quan thì nó là một thứ như nhau.
All right, so we have like 30 minutes. Yeah, let's keep going. I want to get to distributed joins as well. All right.
Được rồi, vậy chúng ta còn khoảng 30 phút. Ừ, tiếp tục nào. Tôi cũng muốn nói đến distributed join. Được rồi.
And then if we run out of time, we can pick up on Wednesday at the end.
Và nếu hết thời gian, chúng ta có thể làm tiếp vào cuối buổi thứ Tư.
All right, so the atomic commit protocol, either two-phase commit, Paxos, or Raft, will provide us the guarantee that when a transaction goes ahead and commits, and everyone agrees that it commits, then it's committed.
Được rồi, vậy giao thức atomic commit, dù là two-phase commit, Paxos hay Raft, sẽ cho chúng ta sự đảm bảo rằng khi một giao dịch tiến hành và commit, và mọi nút đều đồng ý là nó commit, thì nó đã được commit.
But the challenge is going to be what happens when there's failures and the database system ends up in this state where the nodes can maybe not potentially communicate with each other.
Nhưng thách thức sẽ là chuyện gì xảy ra khi có lỗi và hệ quản trị cơ sở dữ liệu rơi vào trạng thái mà các nút có thể không giao tiếp được với nhau.
And we need to know what guarantees can we provide of whether the system can still be considered alive and actually running queries and running transactions.
Và chúng ta cần biết chúng ta có thể đảm bảo được gì về việc hệ thống vẫn còn được coi là hoạt động và thực sự đang chạy truy vấn và chạy giao dịch.
So this CAP theorem was proposed in the late 90s by Eric Brewer, who's a professor at Berkeley. And he had a startup at the time. I think, I forget what it was called.
Định lý CAP này được Eric Brewer đề xuất vào cuối những năm 90, ông là giáo sư ở Berkeley. Và lúc đó ông có một công ty khởi nghiệp. Tôi quên mất nó tên là gì.
But they basically were trying to reason about the different states of distributed systems at their startup.
Nhưng về cơ bản họ đang cố suy luận về các trạng thái khác nhau của hệ phân tán tại công ty khởi nghiệp của ông.
And the CAP theorem basically is trying to say that if you have a distributed system, a distributed database system, that there's these three properties you may want to have: consistency, always available, and network partition tolerance.
Và về cơ bản, định lý CAP muốn nói rằng nếu bạn có một hệ phân tán, một hệ cơ sở dữ liệu phân tán, thì có ba thuộc tính mà bạn có thể muốn có: tính nhất quán (consistency), luôn sẵn sàng (availability), và khả năng chịu phân mảnh mạng (partition tolerance).
I'll explain what they are, each of them. But you can only pick two out of three.
Tôi sẽ giải thích từng thuộc tính. Nhưng bạn chỉ có thể chọn hai trong ba.
Like, if you're trying to pick, sort of the same rule of thumb, if you're trying to pick a boyfriend or girlfriend, they're going to need to be really good looking, really smart, or not crazy.
Giống như một quy tắc ngón tay cái khi chọn người yêu, nếu bạn đang chọn bạn trai hoặc bạn gái, họ phải rất ưa nhìn, rất thông minh, hoặc không điên.
And you can only get two out of three. Right? So the basic idea here.
Và bạn chỉ có thể có hai trong ba. Đúng không? Đó là ý tưởng cơ bản.
So the question we're trying to answer here with the CAP theorem is, what happens when there is a network partition where the nodes can't communicate with each other?
Vậy câu hỏi mà định lý CAP cố gắng trả lời là, điều gì xảy ra khi có một phân mảnh mạng khiến các nút không thể liên lạc với nhau?
Can we still guarantee the consistency of the database? Or can we guarantee that it's still going to be available to run queries? And the NoSQL guys will choose availability over consistency.
Liệu chúng ta vẫn có thể đảm bảo tính nhất quán của cơ sở dữ liệu không? Hay chúng ta đảm bảo nó vẫn sẵn sàng để chạy truy vấn? Và những người làm NoSQL sẽ chọn tính sẵn sàng thay vì tính nhất quán.
But any sort of traditional relational database system, or even the newer distributed SQL database systems, they're going to choose consistency over availability.
Nhưng bất kỳ hệ cơ sở dữ liệu quan hệ truyền thống nào, hay thậm chí các hệ cơ sở dữ liệu SQL phân tán mới hơn, đều sẽ chọn tính nhất quán thay vì tính sẵn sàng.
So let's see what this looks like. So say that I have my database. I have a primary and a replica. And I have two application servers running in two different data centers.
Hãy xem điều này trông như thế nào. Giả sử tôi có cơ sở dữ liệu của mình. Tôi có một primary và một replica. Và tôi có hai máy chủ ứng dụng chạy ở hai trung tâm dữ liệu khác nhau.
So when the transaction over here wants to do a modification on A, it goes ahead and applies the change, and then we send the update to the replica.
Khi giao dịch ở bên này muốn sửa đổi A, nó tiến hành áp dụng thay đổi, rồi chúng ta gửi bản cập nhật đến replica.
And again, this is just sending over the write-ahead log message that we talked about before.
Và một lần nữa, đây chỉ là gửi thông điệp write-ahead log mà chúng ta đã nói trước đây.
And then once we know that the change has been applied, running two-phase commit, whatever you want, we can send back the acknowledgment to the application server saying, your change has successfully saved.
Và khi chúng ta biết thay đổi đã được áp dụng, chạy two-phase commit, hay gì cũng được, chúng ta có thể gửi lại xác nhận cho máy chủ ứng dụng, báo rằng thay đổi của bạn đã được lưu thành công.
And then now, if a transaction over here wants to read A, it could either go to the replica or the primary, and it's guaranteed to see the same result, because we've told the outside world that our transaction's committed.
Và bây giờ, nếu một giao dịch ở bên này muốn đọc A, nó có thể đến replica hoặc primary, và được đảm bảo thấy cùng một kết quả, vì chúng ta đã báo với thế giới bên ngoài rằng giao dịch của mình đã commit.
So if the primary says to the other transaction over there that you committed, then we can immediately see that change over on the replica.
Nên nếu primary báo với giao dịch kia ở đằng đó rằng bạn đã commit, thì chúng ta có thể thấy ngay thay đổi đó ở replica.
Availability says that now if the replica goes down, then I can still run queries on the primary and do whatever I need.
Tính sẵn sàng nghĩa là nếu bây giờ replica bị sập, thì tôi vẫn có thể chạy truy vấn trên primary và làm những gì cần thiết.
But I can also have my application server on the other side send queries to the primary and read data as I need over there. And all that's fine.
Nhưng tôi cũng có thể để máy chủ ứng dụng ở phía bên kia gửi truy vấn đến primary và đọc dữ liệu khi cần ở đó. Và tất cả đều ổn.
The problem's going to be now when I have a partition tolerance, or sorry, when I have a network partition.
Vấn đề sẽ xảy ra khi tôi có partition tolerance, à xin lỗi, khi tôi có một phân mảnh mạng.
So if the network goes down for whatever reason, now I have my primary and my replica over here. My primary's going to say, oh, well, I was the primary before.
Nếu mạng bị sập vì lý do nào đó, thì bây giờ tôi có primary và replica ở đây. Primary sẽ nói, ồ, trước đây tôi là primary.
I'm still the primary now. That's fine. I'll just run as I did before. But the replica can't talk to the primary because the network's down.
Bây giờ tôi vẫn là primary. Không sao. Tôi cứ chạy như trước. Nhưng replica không thể nói chuyện với primary vì mạng bị sập.
So it is going to assume that the other primary failed, has crashed. So now it's going to run leader election and decide that it's now the new primary.
Vì vậy nó sẽ cho rằng primary kia đã hỏng, đã bị crash. Nên bây giờ nó sẽ chạy bầu chọn leader và quyết định rằng mình là primary mới.
And then so now the application server on one side of the network can make changes to what it thinks is the primary.
Và như vậy, application server ở một phía của mạng có thể thay đổi dữ liệu trên cái mà nó cho là primary.
The other application server can make changes to what it thinks is the primary. And those can admit, all that's fine.
Application server còn lại cũng có thể thay đổi dữ liệu trên cái mà nó cho là primary. Và những thay đổi đó đều được chấp nhận, không vấn đề gì.
But now the problem's going to be when the network comes back online, these two primaries are going to think they have the latest version of the database.
Nhưng vấn đề sẽ xuất hiện khi mạng hoạt động trở lại, hai primary này sẽ đều nghĩ rằng mình có phiên bản mới nhất của cơ sở dữ liệu.
But we've already told the outside world that these two separate transactions committed. And now we've got to reconcile the differences.
Nhưng chúng ta đã báo với thế giới bên ngoài rằng hai transaction riêng biệt này đã commit. Và giờ chúng ta phải hòa giải những khác biệt đó.
So that's the question we're trying to deal with: what happens when the network goes down?
Vậy đó là câu hỏi chúng ta đang cố giải quyết: điều gì xảy ra khi mạng bị ngắt?
Should we stop everything and not run any queries until the network comes back up, So we know that we don't have this split brain issue?
Chúng ta có nên dừng mọi thứ và không chạy truy vấn nào cho đến khi mạng hoạt động lại, để biết rằng mình không gặp vấn đề split brain này không?
Or should we allow changes to still happen, but then we have to figure out how to reconcile them when we put it back together?
Hay là vẫn cho phép các thay đổi diễn ra, nhưng sau đó phải tìm cách hòa giải chúng khi ghép hệ thống lại với nhau?
So most distributed database systems that are doing transactions will do the first one.
Hầu hết các hệ cơ sở dữ liệu phân tán có xử lý transaction sẽ chọn cách đầu tiên.
If enough nodes go down where you no longer have a majority of the nodes, then you say the system is unavailable. You can still run read-only queries if you wanted.
Nếu đủ nhiều node ngừng hoạt động đến mức không còn đa số các node, thì bạn nói rằng hệ thống không khả dụng. Nếu muốn, bạn vẫn có thể chạy các truy vấn chỉ đọc.
But no one's allowed to modify anything. No transaction can modify the database. And then eventually, the other nodes will come up. And then now you have a majority.
Nhưng không ai được sửa đổi gì cả. Không transaction nào được sửa đổi cơ sở dữ liệu. Rồi cuối cùng, các node khác sẽ hoạt động trở lại. Và lúc đó bạn có đa số.
And then now you know you're in a correct state.
Và lúc đó bạn biết mình đang ở trạng thái đúng.
An alternative is that you allow both sides of the partition to still accept writes and reads.
Một cách khác là cho phép cả hai phía của phân vùng vẫn chấp nhận ghi và đọc.
And then when the system comes back online, then you just figure out how to merge those changes together.
Rồi khi hệ thống hoạt động trở lại, bạn chỉ cần tìm cách hợp nhất các thay đổi đó với nhau.
So a simple thing would be you just look at the timestamps of the records when they were modified and assume that the latest one is going to be the newest version.
Một cách đơn giản là xem timestamp của các bản ghi vào lúc chúng được sửa đổi và giả định rằng bản mới nhất sẽ là phiên bản mới nhất.
An alternative is what's called vector clocks. I don't know if they even teach that anymore in distributed systems. But this is something that Leslie Lamport invented.
Một cách khác là cái gọi là vector clock. Tôi không biết bây giờ họ còn dạy cái đó trong môn hệ phân tán nữa không. Nhưng đây là thứ do Leslie Lamport phát minh.
Remember how multi-versioning, every time I did an update, I created a new physical version of the tuple. But at the SQL level, I can't see any of those different versions.
Hãy nhớ lại multi-versioning, mỗi lần tôi cập nhật, tôi tạo ra một phiên bản vật lý mới của tuple. Nhưng ở mức SQL, tôi không thấy được những phiên bản khác nhau đó.
I only see the latest one or whatever they were allowed to see within my snapshot.
Tôi chỉ thấy phiên bản mới nhất hoặc phiên bản nào mà snapshot của tôi cho phép thấy.
But with the vector clocks, the idea is when I go read a tuple now, I'm going to get back the version chain of all the versions of that tuple that I'm trying to look up on.
Nhưng với vector clock, ý tưởng là khi tôi đọc một tuple, tôi sẽ nhận lại chuỗi phiên bản của tất cả các phiên bản của tuple mà tôi đang cố tra cứu.
And now it's my job and the client to figure out what is the right version I should be looking at.
Và bây giờ nhiệm vụ của tôi và của client là phải xác định phiên bản nào là đúng để xem.
And then most people just do the easiest thing, just pick whatever the latest version, assuming that's the one I want.
Và hầu hết mọi người chỉ làm cách dễ nhất, là chọn phiên bản mới nhất, cho rằng đó là phiên bản mình muốn.
But actually, that may not be the correct thing if you start doing multi-statement transactions. So most of the NoSQL systems will do last writer wins, last update wins.
Nhưng thực ra, có thể không phải là điều đúng đắn nếu bạn bắt đầu dùng các transaction nhiều câu lệnh. Vì vậy, hầu hết các hệ thống NoSQL sẽ dùng last writer wins, tức là bản cập nhật cuối cùng thắng.
I know one system that was doing vector clocks called Riak. Don't do this. This is super hard to do, because your average JavaScript programmer isn't going to know what a vector clock is.
Tôi biết một hệ thống từng dùng vector clock, tên là Riak. Đừng làm vậy. Việc này cực kỳ khó thực hiện, vì một lập trình viên JavaScript bình thường sẽ không biết vector clock là gì.
It doesn't know how to reason about the correctness of the state of the database system.
Họ không biết cách lập luận về tính đúng đắn của trạng thái hệ quản trị cơ sở dữ liệu.
You're just better off lying to them and saying, "All right, last update wins," and deal with those problems later on, or stop the system until you have all the nodes, enough to figure out what's going on.
Tốt hơn là bạn cứ nói dối họ rằng: "Được rồi, bản cập nhật cuối cùng thắng," rồi xử lý những vấn đề đó sau, hoặc dừng hệ thống cho đến khi có đủ các nút, đủ để biết chuyện gì đang xảy ra.
So the CAP theorem is a pretty simplistic idea, where it just assumes, oh, do I want to be able to handle things when there's a partition, let the system be available, or just guarantee that my database is going to be consistent?
Định lý CAP là một ý tưởng khá đơn giản hóa, nó chỉ giả định rằng, ồ, tôi có muốn xử lý được mọi thứ khi xảy ra phân vùng mạng không, để hệ thống luôn sẵn sàng, hay chỉ đảm bảo cơ sở dữ liệu của tôi nhất quán?
There was an extension to it called PACELC. It came out in 2010, which now includes the notion of consistency and latency.
Có một bản mở rộng của nó gọi là PACELC. Nó ra đời năm 2010, và bổ sung khái niệm về tính nhất quán và độ trễ.
Because there's actually a trade-off between the two of these things that the original CAP theorem doesn't cover. Right?
Vì thực ra có sự đánh đổi giữa hai thứ này mà định lý CAP ban đầu không đề cập tới. Đúng không?
Because I can wait forever until my system comes back up, and I'll guarantee consistency, but then my latency is going to be minutes or hours, which is not realistic.
Vì tôi có thể chờ mãi cho đến khi hệ thống hoạt động lại, và tôi sẽ đảm bảo tính nhất quán, nhưng khi đó độ trễ sẽ là hàng phút hoặc hàng giờ, điều này không thực tế.
So basically, I think about it like this. So I have my primary and two replicas, and say they're running in different data centers. Right? I do a set on A.
Về cơ bản, tôi nghĩ về nó như thế này. Tôi có một nút chính và hai bản sao, giả sử chúng chạy ở các trung tâm dữ liệu khác nhau. Đúng không? Tôi thực hiện một lệnh set trên A.
I go ahead and apply the change here, and then now I'll send those changes to the other nodes, to my replicas, apply the change.
Tôi áp dụng thay đổi ngay tại đây, rồi gửi các thay đổi đó đến các nút khác, đến các bản sao của tôi, để chúng áp dụng thay đổi.
And then now they're going to send me back an acknowledgment. But the question would be, how long should the primary wait to hear back to know whether they've accepted the change?
Sau đó chúng sẽ gửi lại cho tôi một xác nhận. Nhưng câu hỏi là, nút chính nên chờ phản hồi trong bao lâu để biết các bản sao đã chấp nhận thay đổi hay chưa?
Has it been successfully modified? Right? If I don't wait, if I don't wait a long time, then yeah, my latency will be low.
Nó đã được sửa đổi thành công chưa? Đúng không? Nếu tôi không chờ, không chờ lâu, thì đúng, độ trễ của tôi sẽ thấp.
But now I don't have any consistency guarantees because I don't know whether those changes actually made it. Right?
Nhưng khi đó tôi không có đảm bảo nhất quán nào vì tôi không biết những thay đổi đó thực sự đã đến nơi chưa. Đúng không?
So I can wait for one of them and then not know what happened to the other one because I'm going underneath the ocean to Europe.
Tôi có thể chờ một bản sao rồi không biết chuyện gì xảy ra với bản còn lại vì nó nằm bên kia đại dương, ở châu Âu.
So maybe I don't want to wait that long, and that's going to be bad for me.
Nên có thể tôi không muốn chờ lâu như vậy, và điều đó sẽ bất lợi cho tôi.
But again, there's no guarantee that when I go read the data, if I tell the outside world the transaction committed and I go read the data here, there's no guarantee that's going to be correct.
Nhưng một lần nữa, không có gì đảm bảo rằng khi tôi đọc dữ liệu, nếu tôi báo với bên ngoài rằng transaction đã commit rồi tôi đọc dữ liệu ở đây, thì kết quả đó sẽ đúng.
Right? So then eventually, again, if I care about consistency, then I would wait for everyone to come back and say, "I got your change."
Đúng không? Vậy nên cuối cùng, nếu tôi quan tâm đến tính nhất quán, thì tôi sẽ đợi mọi nút quay lại và nói: "Tôi đã nhận được thay đổi của bạn."
Then I tell the outside world that you successfully committed, your change is successfully modified.
Sau đó tôi mới báo cho thế giới bên ngoài rằng giao dịch đã commit thành công, thay đổi của bạn đã được cập nhật thành công.
So latency is an additional thing that the CAP theorem doesn't cover.
Vậy độ trễ là một yếu tố bổ sung mà định lý CAP không đề cập tới.
And again, usually there's a timeout to say how long I'm going to wait, and then you can decide whether to abort the transaction because you haven't heard back from the other nodes, or allow yourself to be in a sort of transient state.
Và thường sẽ có một timeout để quy định tôi sẽ chờ bao lâu, rồi bạn có thể quyết định hủy giao dịch (abort) vì bạn chưa nhận được phản hồi từ các nút khác, hoặc cho phép mình ở trong một trạng thái tạm thời.
But that's OK because the application's allowed to do that. Now that I think about it, it's the same way we talked about transactions.
Nhưng không sao, vì ứng dụng được phép làm vậy. Giờ nghĩ lại thì đây cũng giống cách chúng ta đã nói về giao dịch.
If it's your bank account and you're trying to count money stuff, you want to have consistency because you don't want to lose money.
Nếu đó là tài khoản ngân hàng và bạn đang tính toán tiền bạc, bạn muốn có tính nhất quán vì không muốn mất tiền.
But if it's a post on Reddit, who cares if it gets delayed by a couple seconds? No one's going to know or really care about these things.
Nhưng nếu là một bài đăng trên Reddit thì ai quan tâm nếu nó bị trễ vài giây? Sẽ chẳng ai biết hay thực sự để ý đến những chuyện này.
So it's OK for me to be not consistent for that, and eventually things will get propagated and updated correctly. Facebook used to do this.
Vì vậy với trường hợp đó, không nhất quán cũng không sao, và cuối cùng mọi thứ sẽ được lan truyền và cập nhật đúng. Facebook từng làm như vậy.
Facebook used to have a single primary data center for all their updates. That would be in the US.
Facebook từng có một trung tâm dữ liệu chính duy nhất cho mọi cập nhật. Nó nằm ở Mỹ.
And then they would have data centers that would have copies of the database, the giant MySQL fleet. They would have copied the database in different continents.
Và họ có các trung tâm dữ liệu khác chứa bản sao của cơ sở dữ liệu, một đội máy MySQL khổng lồ. Họ sao chép cơ sở dữ liệu sang các châu lục khác nhau.
But then all the writes had to go into the US. Then they would then get propagated out to the different continents. And obviously, that's a big round-trip time.
Nhưng mọi thao tác ghi đều phải đi về Mỹ. Sau đó chúng mới được lan truyền ra các châu lục khác. Và rõ ràng, đó là thời gian khứ hồi rất lớn.
So what would happen is people would post on their timeline. And then that write would have to go to the US. And eventually, it would get propagated to the South American data center.
Vậy điều xảy ra là người dùng đăng bài lên dòng thời gian của mình. Và thao tác ghi đó phải đi về Mỹ. Rồi cuối cùng nó mới được lan truyền đến trung tâm dữ liệu ở Nam Mỹ.
So that means if they refreshed the page, they wouldn't see their own update. They'd think something was broken, something's wrong.
Nghĩa là nếu họ làm mới trang, họ sẽ không thấy bài cập nhật của chính mình. Họ sẽ nghĩ có gì đó bị hỏng, có gì đó không ổn.
So what they did is they just put a little post in your cookie, in your browser, so that when they refreshed the page, it read it from the cookie and showed it back to you.
Nên họ đã làm thế này: đặt một bản nhỏ của bài đăng vào cookie trong trình duyệt của bạn, để khi bạn làm mới trang, nó đọc từ cookie và hiển thị lại cho bạn.
So you thought that things are fine, even though it hasn't successfully made it from the US data center and propagated to all the replicas. They switched now to be a multi-primary setup.
Thế là bạn nghĩ mọi thứ vẫn ổn, dù thực tế nó chưa hề đi thành công từ trung tâm dữ liệu ở Mỹ và lan truyền đến tất cả các bản sao. Giờ họ đã chuyển sang mô hình nhiều nút chính (multi-primary).
But that's a good trick where, again, it's OK for me to not have consistency guarantees, because I can hide that at the application level, because I want lower latency for these things.
Nhưng đó là một mẹo hay, ở đây, tôi có thể không cần đảm bảo tính nhất quán, vì tôi có thể che giấu điều đó ở tầng ứng dụng, vì tôi muốn độ trễ thấp hơn cho những thứ này.
OK. So again, that's the crash course of everything you need to know about for doing transactions in a distributed OLTP system.
Được rồi. Vậy đó là khóa học cấp tốc về mọi thứ bạn cần biết để thực hiện giao dịch trong một hệ thống OLTP phân tán.
So let's talk about now how we're going to do analytical queries in a distributed database system.
Giờ hãy nói về cách chúng ta thực hiện các truy vấn phân tích trong một hệ quản trị cơ sở dữ liệu phân tán.
So the most expensive operation in a distributed database system for analytical queries is going to be the joins.
Thao tác tốn kém nhất trong một hệ cơ sở dữ liệu phân tán đối với các truy vấn phân tích sẽ là các phép join.
And it's going to depend on how the data is being partitioned and stored across the different nodes. And whether it's shared-disk or shared-nothing, it doesn't matter.
Và điều đó sẽ phụ thuộc vào cách dữ liệu được phân vùng và lưu trữ trên các nút khác nhau. Và dù là shared-disk hay shared-nothing thì cũng không quan trọng.
It's how we're actually going to be able to do our joins.
Điều quan trọng là chúng ta thực sự sẽ thực hiện các phép join bằng cách nào.
And the stupidest thing, if you want to do a join across a distributed system, is to copy all the data you want that has crossed different nodes, Put it into a single node and just run all the join algorithms we talked about earlier in the semester on a single box.
Và cách ngớ ngẩn nhất, nếu muốn thực hiện phép join trên một hệ thống phân tán, là sao chép toàn bộ dữ liệu cần dùng nằm rải rác trên các nút khác nhau, đưa nó vào một nút duy nhất rồi chạy tất cả các thuật toán join mà chúng ta đã học hồi đầu học kỳ trên một máy đơn.
Of course, now you lose all the parallelism of a distributed system, and your data may not even fit on a single node to be able to do that.
Tất nhiên, như vậy bạn mất toàn bộ tính song song của một hệ thống phân tán, và thậm chí dữ liệu của bạn có thể không vừa trên một nút duy nhất để làm được điều đó.
So ideally, I want to reduce the amount of data transfer I have and run my join as efficiently as possible.
Vì vậy, lý tưởng nhất là tôi muốn giảm lượng dữ liệu phải truyền và chạy phép join hiệu quả nhất có thể.
So what I'm going to talk about now is the way we're going to organize data so that we can do our joins in a distributed database system.
Vậy bây giờ tôi sẽ nói về cách chúng ta tổ chức dữ liệu để có thể thực hiện các phép join trong một hệ cơ sở dữ liệu phân tán.
We're still going to be doing all the join algorithms we talked about before: nested loop join, hash join, and sort-merge join. Those are the basic three categories of joins.
Chúng ta vẫn sẽ dùng tất cả các thuật toán join đã nói trước đây: nested loop join, hash join và sort-merge join. Đó là ba loại join cơ bản.
So all that's still going to be applied here, and we're still going to do that on our local nodes.
Tất cả những điều đó vẫn được áp dụng ở đây, và chúng ta vẫn sẽ thực hiện chúng trên các nút cục bộ của mình.
So now what we're talking about is how we're going to move data, if we need to, across the nodes so that we can then compute those joins locally.
Vậy điều chúng ta đang bàn bây giờ là cách di chuyển dữ liệu, nếu cần, giữa các nút để sau đó có thể tính các phép join đó ở cục bộ.
Again, the goal is we want our join algorithm to produce the same logical result when it's running on a distributed system as it would on a single-node system.
Một lần nữa, mục tiêu là thuật toán join của chúng ta phải cho ra cùng một kết quả logic khi chạy trên một hệ thống phân tán như khi chạy trên hệ thống một nút.
SQL is unordered unless there's an ORDER BY, so it's OK that the ordering of the output is different, as long as the logical content should still be the same.
SQL không có thứ tự trừ khi có ORDER BY, nên thứ tự của kết quả đầu ra khác đi cũng không sao, miễn là nội dung logic vẫn phải giống nhau.
All right, so the first scenario would be the simplest thing.
Được rồi, kịch bản đầu tiên sẽ là đơn giản nhất.
This is where we want to do a join between tables R and S, and the table R has been partitioned on the ID column, which just happens to be our join key.
Ở đây chúng ta muốn join giữa các bảng R và S, và bảng R đã được phân vùng theo cột ID, vốn tình cờ chính là khóa join của chúng ta.
And then table S is replicated on every single node. So think of table R as a really big table, and we divided it up, partitioned it, and put it on different nodes.
Còn bảng S được sao chép trên mọi nút. Hãy coi bảng R là một bảng rất lớn, và chúng ta chia nó ra, phân vùng và đặt lên các nút khác nhau.
Table S is small. Think of a zip code table. It's like 35,000 records. That's going to be in megabytes. We can put that on every single node.
Bảng S thì nhỏ. Hãy nghĩ đến bảng mã bưu chính. Khoảng 35.000 bản ghi. Chỉ cỡ vài megabyte. Chúng ta có thể đặt nó trên mọi nút.
Now, if we update this, the replicated table, we've got to run two-phase commit, Paxos, and make sure they're all in sync from the stuff we just talked about.
Bây giờ, nếu chúng ta cập nhật bảng được sao chép này, chúng ta phải chạy two-phase commit, Paxos, và đảm bảo tất cả đồng bộ, theo những gì chúng ta vừa nói.
But for this, we can ignore that. So again, our data has been partitioned on this key here.
Nhưng với trường hợp này, ta có thể bỏ qua điều đó. Vậy dữ liệu của chúng ta đã được phân vùng theo khóa này.
So that means to do the join between R and S for this query here, we don't need to send data between the different nodes.
Nghĩa là để thực hiện phép join giữa R và S cho truy vấn này, chúng ta không cần gửi dữ liệu giữa các nút khác nhau.
Everything we have to do the join within one partition of R is available to us on our own node.
Mọi thứ cần có để join trong một phân vùng của R đều có sẵn trên chính nút của chúng ta.
So we'll run our own local nested loop join, hash join, sort-merge join, whatever you want. We run that locally here. We produce the result.
Vì vậy chúng ta sẽ chạy nested loop join cục bộ, hash join, sort-merge join, tùy bạn muốn. Chúng ta chạy nó cục bộ ở đây. Chúng ta tạo ra kết quả.
And then now, one of the nodes will be designated the coordinator or the leader or whoever's responsible for returning back the result to the application.
Và sau đó, một trong các nút sẽ được chỉ định làm coordinator hoặc leader hoặc bất kỳ nút nào chịu trách nhiệm trả kết quả về cho ứng dụng.
The other nodes will send the data for their local join to that other node. It just has a union on them, which is cheap to do because it's copying bytes or concatenating bytes together.
Các nút khác sẽ gửi dữ liệu của phép join cục bộ của chúng đến nút đó. Nó chỉ thực hiện một phép hợp (union) trên chúng, việc này rẻ vì chỉ là sao chép các byte hoặc nối các byte lại với nhau.
And then now, it produces the final result of the partition join from the two nodes to a single result.
Và sau đó, nó tạo ra kết quả cuối cùng của phép join theo phân vùng từ hai nút thành một kết quả duy nhất.
So this is easy to do because everything's all local.
Vậy việc này dễ làm vì mọi thứ đều nằm cục bộ.
Another easy case is when the data is partitioned on the join key. So in the last example, R was partitioned on ID. And that S was replicated.
Một trường hợp dễ khác là khi dữ liệu được phân vùng theo khóa join. Trong ví dụ trước, R được phân vùng theo ID. Còn S thì được nhân bản.
And now, in this example here, S is also partitioned on ID. And the range of values line up between R and S in each partition.
Còn trong ví dụ này, S cũng được phân vùng theo ID. Và khoảng giá trị của R và S khớp nhau ở mỗi phân vùng.
If it was hash partition, you wouldn't worry about the ranges. But it would work the same way.
Nếu là phân vùng băm, bạn sẽ không phải lo về các khoảng giá trị. Nhưng nó vẫn hoạt động theo cách tương tự.
So again, just like before, I don't have to move data between the different nodes to do my join.
Vậy, cũng giống như trước, tôi không phải di chuyển dữ liệu giữa các nút khác nhau để thực hiện join.
I do my local join at every single node, produce the portion of the result that I have for each node, Send that over the network, or however I want to get it to this other node, who then combines it together and produces the output we send to the application.
Tôi thực hiện join cục bộ tại từng nút một, tạo ra phần kết quả mà mỗi nút có, gửi nó qua mạng, hoặc bằng cách nào đó chuyển nó đến nút kia, nút này sẽ kết hợp chúng lại và tạo ra đầu ra mà ta gửi cho ứng dụng.
Now, where things get hard is when the data isn't partitioned on our join keys, which is common.
Còn chỗ khó là khi dữ liệu không được phân vùng theo khóa join của ta, điều này rất phổ biến.
Because sometimes it's obvious we would pick a partition key in the beginning when you load some data.
Bởi vì đôi khi, lúc nạp dữ liệu ban đầu, ta chọn một khóa phân vùng một cách hiển nhiên.
And then eventually, some people might want to start running queries and start joining in ways that you didn't expect. And now you have to account for that in your implementation.
Rồi sau đó, có người muốn bắt đầu chạy các truy vấn và join theo những cách mà bạn không lường trước. Và bây giờ bạn phải tính đến điều đó trong cài đặt của mình.
So the first approach is what is called a broadcast join.
Cách tiếp cận đầu tiên gọi là broadcast join.
And this is where you identify that one of the data sets, of one of the tables you're trying to join, is small enough that you could actually just broadcast and make a copy of it, send it to every single node that's going to be participating in the join, sending them whatever copy of the data they have.
Đây là khi bạn nhận ra rằng một trong các tập dữ liệu, của một trong các bảng bạn định join, đủ nhỏ để bạn có thể quảng bá và tạo một bản sao của nó, gửi đến từng nút sẽ tham gia vào phép join, gửi cho chúng bất kỳ bản sao dữ liệu nào mà chúng có.
So for example, I'm partitioning table S on value, but it needs to be partitioned on ID.
Ví dụ, tôi đang phân vùng bảng S theo value, nhưng nó cần được phân vùng theo ID.
So rather than partitioning on ID, what I'm doing is going to copy the range of the values, 1 to 50, from S over here to this node, and then just combine it together with 51 over 100.
Vậy thay vì phân vùng theo ID, tôi sẽ sao chép khoảng giá trị, từ 1 đến 50, từ S ở đây sang nút này, rồi kết hợp nó với phần 51 đến 100.
And I'll do the same thing on the other side. So now it's like my first case, where every node has a complete copy of the table S.
Và tôi làm điều tương tự ở phía bên kia. Như vậy giờ nó giống như trường hợp đầu tiên, khi mỗi nút có một bản sao đầy đủ của bảng S.
Then I do my local join, produce the result, send it over the wire, and combine it together.
Sau đó tôi thực hiện join cục bộ, tạo ra kết quả, gửi nó qua đường truyền, và kết hợp lại với nhau.
It's end-to-end, yes. The question is, if I have more than two nodes, do I do end-to-end? Every node has to send part of the data to every other node? Yes.
Đúng, là từ đầu đến cuối (mọi nút với mọi nút). Câu hỏi là, nếu có nhiều hơn hai nút thì có làm theo kiểu mọi nút với mọi nút không? Mỗi nút phải gửi một phần dữ liệu cho mọi nút khác? Đúng vậy.
And if it's shared disk, you could say, all right, well, just go fetch it from the shared disk.
Và nếu là đĩa dùng chung, bạn có thể nói, được rồi, cứ lấy nó từ đĩa dùng chung.
But then depending on whether you pay for those reads, Like S3, Amazon charges you every time you read something in S3.
Nhưng khi đó còn tùy việc bạn có phải trả tiền cho các lần đọc đó không. Như S3, Amazon tính phí bạn mỗi lần đọc thứ gì đó trong S3.
So you don't want to have, like, 50 nodes go read the same thing on S3. You have one node need it, read it, and then send it out.
Nên bạn không muốn có chẳng hạn 50 nút cùng đi đọc một thứ trên S3. Bạn cho một node cần dữ liệu đó đọc nó, rồi gửi nó đi.
That's usually a cheaper way to do it. Or you have, like, a local cache that's outside S3. But the basic idea still is you're copying partitions of the data to every other node.
Thường thì đó là cách rẻ hơn. Hoặc bạn có một bộ nhớ đệm cục bộ nằm bên ngoài S3. Nhưng ý tưởng cơ bản vẫn là bạn sao chép các phân vùng dữ liệu đến mọi node khác.
So now they have a complete copy of the data.
Như vậy bây giờ chúng có một bản sao đầy đủ của dữ liệu.
So sometimes you'll see systems refer to these as broadcast joins. But broadcast is just like a modifier for what these... There's still going to be a basic join algorithm underneath that.
Đôi khi bạn sẽ thấy các hệ thống gọi những phép này là broadcast join. Nhưng broadcast chỉ giống như một từ bổ nghĩa cho những... Bên dưới vẫn sẽ có một thuật toán join cơ bản.
So it'll be a broadcast hash join instead of a broadcast join, or broadcast sort-merge join instead of a, you know. But people might just call it a broadcast join.
Nên nó sẽ là broadcast hash join thay vì broadcast join, hoặc broadcast sort-merge join thay vì, bạn biết đấy. Nhưng người ta có thể chỉ gọi là broadcast join.
And typically, that means they're doing a hash join. All right, the last one is where both tables are too big to be broadcast and replicated around.
Và thường thì điều đó có nghĩa là họ đang dùng hash join. Được rồi, trường hợp cuối cùng là khi cả hai bảng đều quá lớn để broadcast và sao chép đi khắp nơi.
And they're also not partitioned on the join key.
Và chúng cũng không được phân vùng theo khóa join.
So I have to do what's called a shuffle to basically repartition the data on the fly based on my join key, so that now when I do my join on every single node, every node has all the data that it needs.
Vì vậy tôi phải làm cái gọi là shuffle để phân vùng lại dữ liệu ngay lúc chạy dựa trên khóa join của tôi, để khi tôi thực hiện join trên từng node, mỗi node đều có tất cả dữ liệu mà nó cần.
So in this case here, table R is partitioned on name, and it needs to be partitioned on RID.
Vậy trong trường hợp này, bảng R được phân vùng theo name, và nó cần được phân vùng theo RID.
So I'll decide what the partition boundaries are, either with range partitioning or using hash partitioning, where I hash the key that I'm trying to join on.
Tôi sẽ quyết định ranh giới các phân vùng là gì, hoặc bằng phân vùng theo khoảng, hoặc dùng phân vùng băm, trong đó tôi băm khóa mà tôi định dùng để join.
And every node is going to send their portion of the data to all other nodes. And then same thing for S.
Và mỗi node sẽ gửi phần dữ liệu của mình đến tất cả các node khác. Rồi làm tương tự với S.
And then now I'm in my second scenario, where the data is now on every single node, it's partitioned on that join key.
Và bây giờ tôi ở trong kịch bản thứ hai, nơi dữ liệu giờ nằm trên mọi node, được phân vùng theo khóa join đó.
I can do my local join, and then copy the result over and send it back to the application that way.
Tôi có thể thực hiện join cục bộ, rồi sao chép kết quả và gửi ngược về ứng dụng theo cách đó.
And just like in broadcast join, some systems will call these shuffle joins, but it's really shuffle hash joins, shuffle join. Yes. The question is, is this the same as MapReduce?
Và giống như broadcast join, một số hệ thống gọi những phép này là shuffle join, nhưng thực ra là shuffle hash join, shuffle join. Vâng. Câu hỏi là, cái này có giống MapReduce không?
Yes.
Có.
MapReduce is, so yes, it is the same as MapReduce, but distributed systems existed before MapReduce. So there's, you know, there's, when MapReduce came out, we were like, oh my god, this is groundbreaking.
MapReduce thì, vâng, nó giống MapReduce, nhưng các hệ thống phân tán đã tồn tại trước MapReduce. Nên là, bạn biết đấy, khi MapReduce ra đời, chúng tôi đã kiểu, trời ơi, cái này mang tính đột phá.
We've never seen it before. It's distributed data systems from the 80s and 90s. It's the same idea. The map function is basically a group by and a sort, in some cases.
Chúng tôi chưa từng thấy nó trước đây. Đó là các hệ thống dữ liệu phân tán từ những năm 80 và 90. Cùng một ý tưởng. Hàm map về cơ bản là một group by và một sắp xếp, trong một số trường hợp.
OK. So one digital optimization we can do is called a semi-join. And I know, I'll explain next class what fact tables and dimension tables are.
Được rồi. Một tối ưu hóa mà chúng ta có thể làm được gọi là semi-join. Và tôi biết, buổi sau tôi sẽ giải thích bảng sự kiện và bảng chiều là gì.
Just think of like fact tables like, I have a giant table of every single time someone bought something on Amazon. Like it's one row would be like, somebody bought this. Someone bought that.
Cứ nghĩ bảng sự kiện giống như, tôi có một bảng khổng lồ ghi lại mọi lần có người mua thứ gì đó trên Amazon. Mỗi hàng sẽ kiểu như, ai đó mua cái này. Ai đó mua cái kia.
And dimension table would be a side table that's usually read-only, but contains things like, you know, the item name, the item description. You wouldn't put that in the giant fact table.
Còn bảng chiều là một bảng phụ thường chỉ đọc, nhưng chứa những thứ như tên mặt hàng, mô tả mặt hàng. Bạn sẽ không đưa những thứ đó vào bảng sự kiện khổng lồ.
So dimension tables would be like the zip code, for example. I'll show what this looks like next class.
Vậy ví dụ, bảng chiều (dimension table) sẽ là bảng chứa mã bưu chính. Lớp sau tôi sẽ cho các em xem nó trông như thế nào.
But one optimization we can do is called a semi-join, where instead of sending around the entire data set between the different nodes when I do these shuffles of the broadcast, I'm going to send a summarization or the bare minimum information I need between the different nodes in order for me to compute the join.
Nhưng một tối ưu hóa chúng ta có thể làm là semi-join, trong đó thay vì gửi toàn bộ tập dữ liệu qua lại giữa các nút khác nhau khi tôi thực hiện các lần shuffle của broadcast, tôi sẽ gửi một bản tóm tắt, hay lượng thông tin tối thiểu mà tôi cần giữa các nút để tính được phép join.
So let's say that I have, I'm joining a fact table and dimension table. And the fact table is on one giant node. And then dimension table is on another node.
Giả sử tôi đang join một bảng sự kiện (fact table) với một bảng chiều. Bảng sự kiện nằm trên một nút khổng lồ. Còn bảng chiều nằm trên một nút khác.
So instead of moving the data around, what I'm going to do is run a subquery on this side table here to just get out all the records where the zip code equals 15213.
Vậy thay vì di chuyển dữ liệu đi lại, tôi sẽ chạy một truy vấn con trên bảng phụ này để lấy ra tất cả các bản ghi có mã bưu chính bằng 15213.
And then I'm going to send that over now to this node here. And I'm still not going to compute the join.
Rồi tôi sẽ gửi kết quả đó sang nút này. Và tôi vẫn chưa tính phép join.
Instead, what I'm going to do is apply this filter to strip out all the things I actually need, the actual records I want from the fact table, and then send that smaller portion over here to now compute my join.
Thay vào đó, tôi sẽ áp dụng bộ lọc này để lọc ra đúng những thứ tôi thật sự cần, tức các bản ghi tôi muốn từ bảng sự kiện, rồi gửi phần nhỏ hơn đó sang đây để tính phép join.
And the trick is, based on what the output of the query is, the projection output, for example, you notice I need all the elements from the dimension table, but I only need the price from the fact table.
Và mẹo ở chỗ, dựa vào đầu ra của truy vấn, ví dụ đầu ra của phép chiếu, các em thấy tôi cần mọi phần tử từ bảng chiều, nhưng từ bảng sự kiện tôi chỉ cần giá.
So I don't want to have to copy the entire tuple.
Nên tôi không muốn phải sao chép cả tuple.
I want to do my projection on that node here, scan the projection, predicate pushdown we talked about before, to filter out all the redundant or unnecessary information I need before I send that over the wire.
Tôi muốn thực hiện phép chiếu ngay trên nút này, quét và chiếu, predicate pushdown mà ta đã nói trước đây, để lọc bỏ mọi thông tin dư thừa hoặc không cần thiết trước khi gửi qua đường truyền.
Furthermore, I can optimize this even more by, over here, instead of actually sending maybe the list of the records here, I could send a Bloom filter, because that's super compact, to send that over the wire and then do the filtering on that side and then send my results later on.
Hơn nữa, tôi còn có thể tối ưu thêm ở bên này, thay vì gửi danh sách các bản ghi ở đây, tôi có thể gửi một Bloom filter, vì nó rất gọn nhẹ để gửi qua đường truyền, rồi lọc ở phía bên kia và sau đó gửi kết quả của tôi đi.
Yes? The question is, can this optimization be applied in the query optimizer?
Em hỏi? Câu hỏi là tối ưu hóa này có thể được áp dụng trong bộ tối ưu truy vấn không?
Yes. So some systems, I think, allow you to specify semi-join in SQL, but it's not in the standard. Yes. I think some systems have a semi-join operator in SQL.
Có. Một số hệ thống, tôi nghĩ, cho phép chỉ định semi-join trong SQL, nhưng nó không có trong chuẩn. Vâng. Tôi nghĩ một số hệ thống có toán tử semi-join trong SQL.
That's not in the standard. Underneath the covers, yes.
Cái đó không nằm trong chuẩn. Còn bên dưới thì có.
For the example here, I didn't write in my select query that I'm doing a semi-join.
Trong ví dụ này, tôi không viết trong câu truy vấn select rằng tôi đang dùng semi-join.
The optimizer figured it out that it could support that, and it does all that predicate projection pushdown when it runs it.
Bộ tối ưu tự nhận ra rằng nó có thể hỗ trợ điều đó, và nó thực hiện toàn bộ predicate projection pushdown khi chạy.
All right, so let me finish this last thing.
Được rồi, để tôi kết thúc phần cuối này.
So I sort of was lying when, not lying, but I sort of was not saying the entire truth when I said joins are the most expensive thing in a distributed OLAP system.
Lúc nãy tôi hơi nói dối, mà không hẳn là nói dối, chỉ là tôi chưa nói toàn bộ sự thật khi nói rằng join là thứ tốn kém nhất trong một hệ thống OLAP phân tán.
The most expensive thing is actually going to be shuffles.
Thứ tốn kém nhất thật ra là các lần shuffle.
That shuffle thing I showed in the distributed joins, that fourth phase of moving data around, if you have to do that, that's always going to be super slow.
Cái shuffle mà tôi đã cho xem trong các phép join phân tán, giai đoạn thứ tư là di chuyển dữ liệu đi khắp nơi, nếu bạn phải làm bước đó, thì nó luôn luôn cực kỳ chậm.
Now, why would you want to shuffle? Because you're using it for a join.
Vậy tại sao bạn lại muốn shuffle? Vì bạn dùng nó cho một phép join.
So technically, yes, the joins are an expensive thing, but within that join operation itself, the shuffle phase is usually going to be the biggest bottleneck for you, because you're copying data and moving across the network and have to send it somewhere else, right?
Nên về mặt kỹ thuật, đúng vậy, join là một thứ tốn kém, nhưng bên trong chính phép join đó, giai đoạn shuffle thường sẽ là nút thắt cổ chai lớn nhất, vì bạn đang sao chép dữ liệu và di chuyển qua mạng và phải gửi nó đến một nơi khác, đúng không?
So the challenge is going to be, how can we make that run efficiently?
Vậy thách thức là làm sao để nó chạy hiệu quả?
And furthermore, what if our data is highly skewed so that when we start doing the shuffle and the repartitioning things, or the data itself, when it originally resides without doing the shuffle, what if one node has a large majority of all the data when we're trying to do the join or any other query operation, and all our other machines are going to be idle while
Hơn nữa, nếu dữ liệu của chúng ta bị lệch nặng thì sao, khi chúng ta bắt đầu shuffle và phân vùng lại dữ liệu, hoặc bản thân dữ liệu, khi nó vốn nằm sẵn ở đó mà chưa shuffle, nếu một node nắm giữ phần lớn toàn bộ dữ liệu khi chúng ta đang cố thực hiện join hay bất kỳ thao tác truy vấn nào khác, và tất cả các máy còn lại đều rảnh rỗi trong khi
that one node is trying to crunch through the bulk of the data?
một node đó phải xử lý ngốn hết phần lớn dữ liệu?
So the shuffle phase is going to allow us to redistribute data across our distributed system in such a way that we can rebalance things and repartition it so that we can compute most of our operations we need for our query on the local nodes, right?
Vì vậy giai đoạn shuffle cho phép chúng ta phân phối lại dữ liệu trên hệ thống phân tán của mình theo cách mà ta có thể cân bằng lại và phân vùng lại để có thể tính toán hầu hết các thao tác cần cho truy vấn ngay trên các node cục bộ, đúng không?
We're only touching data that's local to us.
Chúng ta chỉ chạm vào dữ liệu nằm cục bộ.
So some systems will incorporate shuffle as it's sort of once in a while, like some queries you need, you're doing a shuffle join, then I have to have a shuffle operator.
Một số hệ thống đưa shuffle vào thỉnh thoảng mới dùng, như với một số truy vấn bạn cần, bạn làm shuffle join thì tôi phải có toán tử shuffle.
Other systems like BigQuery, for every single time I have a pipeline breaker, they're going to introduce a shuffle explicitly.
Các hệ thống khác như BigQuery, mỗi lần có một pipeline breaker, họ sẽ đưa vào một shuffle một cách tường minh.
And this allows them to do certain optimizations, like decide while the query is running whether they need more nodes or fewer nodes to compute whatever it is they want to compute.
Và điều này cho phép họ thực hiện một số tối ưu hóa nhất định, như quyết định ngay khi truy vấn đang chạy xem cần thêm node hay ít node hơn để tính toán bất cứ thứ gì họ muốn tính.
And they use the shuffle staging process as sort of an intermediate staging checkpoint, if you will, for the query to decide, okay, this is what I'm seeing in the data at this sort of pipeline breaker.
Và họ dùng quá trình staging của shuffle như một kiểu điểm kiểm tra (checkpoint) trung gian, nếu có thể nói vậy, để truy vấn quyết định, được rồi, đây là những gì tôi thấy trong dữ liệu tại pipeline breaker này.
I can then decide how to then reorganize the other parts of the query plan going up above.
Sau đó tôi có thể quyết định cách tổ chức lại các phần khác của kế hoạch truy vấn phía trên.
There are some systems where you can swap out what the sort of built-in shuffle implementation is, to switch it with one of these open source ones, Celeborn and Uniffle.
Có một số hệ thống mà bạn có thể thay thế phần triển khai shuffle tích hợp sẵn, bằng một trong các hệ thống mã nguồn mở này, Celeborn và Uniffle.
These came out of the Chinese companies, but these are like open source systems that only do a shuffle.
Chúng xuất phát từ các công ty Trung Quốc, nhưng đây là các hệ thống mã nguồn mở chỉ làm mỗi việc shuffle.
In the case of Google and BigQuery, shuffle is so important for them, they have specialized hardware to do in-memory shuffle that runs on like smart NICs, FPGAs, to make the shuffle phase go as fast as possible.
Với Google và BigQuery, shuffle quan trọng đến mức họ có phần cứng chuyên dụng để shuffle trong bộ nhớ chạy trên những thứ như smart NIC, FPGA, để giai đoạn shuffle chạy nhanh nhất có thể.
Because it's nice, it's sort of abstracting away the ideas like this sort of shuffle stage allows us to implement different operators up and down the query plan without worrying about how we're going to move things around.
Bởi vì nó rất tiện, nó trừu tượng hóa các ý tưởng, như giai đoạn shuffle này cho phép chúng ta triển khai các toán tử khác nhau ở phía trên và phía dưới kế hoạch truy vấn mà không phải lo lắng về cách chúng ta sẽ di chuyển dữ liệu.
The shuffle phase is going to do that for us. So I don't have to write a partition-aware hash join operator.
Giai đoạn shuffle sẽ lo việc đó cho chúng ta. Vì vậy tôi không phải viết một toán tử hash join nhận biết phân vùng.
If I just do my shuffle phase before I do a join, then every node can just have the local implementation of their hash join. So it basically looks like this.
Nếu tôi chỉ cần thực hiện giai đoạn shuffle trước khi thực hiện join, thì mỗi nút chỉ cần dùng cài đặt cục bộ của hash join. Về cơ bản nó trông như thế này.
So say I first stage my query, consider it like the first pipeline. It's almost like a producer-consumer model.
Giả sử đầu tiên tôi chia truy vấn thành các giai đoạn, coi đây là đường ống đầu tiên. Nó gần giống như mô hình producer-consumer.
So they're reading data up either from disk or from other nodes in the query plan, other workers. Actually, not other workers, like let's say from either local disk or a shared disk.
Các nút này đọc dữ liệu lên, hoặc từ đĩa hoặc từ các nút khác trong kế hoạch truy vấn, các worker khác. À mà không, không phải từ các worker khác, ví dụ như từ đĩa cục bộ hoặc đĩa dùng chung.
They're reading data in, producing some output, and then now they're going to take the output of the data and hash it on whatever partition key I care about.
Chúng đọc dữ liệu vào, tạo ra một số kết quả đầu ra, rồi sau đó lấy kết quả đầu ra của dữ liệu và băm nó theo khóa phân vùng nào mà tôi quan tâm.
And then modify the number of shuffle nodes that I have.
Và sau đó điều chỉnh số lượng nút shuffle mà tôi có.
And if these guys run out of memory, because I want to keep things in memory, then I can spill over to a shared disk.
Và nếu các nút này hết bộ nhớ, vì tôi muốn giữ dữ liệu trong bộ nhớ, thì tôi có thể ghi tràn sang một đĩa dùng chung.
Then now in the second stage that comes after this, I can decide, well, I don't have as much data as I thought I was going to have after I do whatever the first workers were doing to clean things up or process the queries.
Rồi ở giai đoạn thứ hai sau giai đoạn này, tôi có thể quyết định, à, mình không có nhiều dữ liệu như mình nghĩ là sẽ có sau khi thực hiện bất cứ việc gì mà các worker đầu tiên đã làm để làm sạch dữ liệu hoặc xử lý các truy vấn.
So therefore, I only need three workers.
Vì vậy, tôi chỉ cần ba worker.
I don't have to have a one-to-one correspondence between the workers in the first stage and the workers in the second stage, because the shuffle phase abstracts that away.
Tôi không cần có sự tương ứng một-một giữa các worker ở giai đoạn đầu và các worker ở giai đoạn thứ hai, vì giai đoạn shuffle đã trừu tượng hóa điều đó đi.
And then now these workers will then be reading data out from the shuffle nodes or reading it from the shared disk to then produce whatever the result they want and then send it off to the next stage or to the final result of the query.
Và bây giờ các worker này sẽ đọc dữ liệu ra từ các nút shuffle hoặc đọc từ đĩa dùng chung để tạo ra kết quả mà chúng muốn rồi gửi nó sang giai đoạn tiếp theo hoặc thành kết quả cuối cùng của truy vấn.
So what does this smell like when we talk about parallel query execution? It's not MapReduce. MapReduce has a shuffle phase, yes, but database is data first.
Vậy khi nói về thực thi truy vấn song song, việc này giống cái gì? Nó không phải MapReduce. MapReduce có giai đoạn shuffle, đúng, nhưng cơ sở dữ liệu thì ưu tiên dữ liệu trước.
It's the exchange operator, right? And in particular, it's this bottom one here, the repartition, right? I can have a bunch of operators feeding data up in parallel to some repartition box, right?
Đó là toán tử exchange, đúng không? Và cụ thể là cái ở dưới cùng này, repartition, đúng không? Tôi có thể có một loạt toán tử đẩy dữ liệu lên song song vào một khối repartition nào đó, đúng không?
So that red box that says repartition, that's that middle phase of the shuffle nodes. So it's the same idea, rather than running on a single box or distributed system, right?
Khối màu đỏ ghi repartition đó, chính là giai đoạn ở giữa của các nút shuffle. Vậy là cùng một ý tưởng, thay vì chạy trên một máy đơn hay hệ thống phân tán, đúng không?
It allows me to have these breakpoints in my query that can then decide how to reorganize things and then repartition it based on what my query wants to do.
Nó cho phép tôi có những điểm ngắt này trong truy vấn để từ đó quyết định cách tổ chức lại dữ liệu rồi phân vùng lại dựa trên việc truy vấn của tôi muốn làm gì.
All right, so, again, that's a crash course for distributed databases.
Được rồi, vậy đó là phần học nhanh về cơ sở dữ liệu phân tán.
The main takeaways should be that having strong consistency for distributed transactions is hard to do, but it's important and necessary because we can't assume the application developer is going to know how to reason about inconsistent data, right?
Những điều chính cần rút ra là việc có tính nhất quán mạnh cho các giao dịch phân tán là khó thực hiện, nhưng nó quan trọng và cần thiết vì chúng ta không thể giả định rằng nhà phát triển ứng dụng biết cách suy luận về dữ liệu không nhất quán, đúng không?
And then Paxos, two-phase commit, and Raft are the most common consensus protocols, or atomic commit protocols, that distributed data systems use.
Và rồi Paxos, two-phase commit, và Raft là những giao thức đồng thuận phổ biến nhất, hay còn gọi là giao thức atomic commit, mà các hệ thống dữ liệu phân tán sử dụng.
It's probably Raft outpaces Paxos now just because there's a lot of open-source implementations of Raft and Paxos wasn't really any.
Có lẽ bây giờ Raft đã vượt Paxos, chỉ vì có rất nhiều bản triển khai mã nguồn mở của Raft còn Paxos thì thực sự không có bản nào.
And when we do distributed joins, we want to minimize the data we have to move and we don't want any false negatives, so we need to make sure that in order to compute the data we want to, our local join on every single node, we have the data that we need because we repartition things and move things around ahead of time.
Và khi thực hiện distributed join, chúng ta muốn giảm thiểu lượng dữ liệu phải di chuyển và không muốn có bất kỳ false negative nào, nên chúng ta cần bảo đảm rằng, để tính được phép join cục bộ trên từng nút một, chúng ta có dữ liệu cần thiết, vì ta đã phân vùng lại dữ liệu và di chuyển chúng trước đó.
Okay? All right, so next class will be the last class. DJ Cash will be back. We will start off with a review for the final, cover over the main topics.
Được chứ? Được rồi, buổi tới sẽ là buổi cuối cùng. DJ Cash sẽ quay lại. Chúng ta sẽ bắt đầu bằng phần ôn tập cho kỳ thi cuối kỳ, điểm lại các chủ đề chính.
We can cover this atomic commit protocol and integrity constraint violation stuff we talked about before, and then I'm going to try to cram in what you would have learned in 721 into a single lecture.
Chúng ta có thể xem lại giao thức atomic commit này và phần vi phạm ràng buộc toàn vẹn mà ta đã nói trước đây, rồi tôi sẽ cố nhồi nhét vào một bài giảng duy nhất những gì mà các bạn sẽ học trong môn 721.
So we'll try to basically build up all the analytical stuff we talked about at the end here.
Về cơ bản, chúng ta sẽ cố xây dựng lại toàn bộ phần phân tích mà ta đã nói ở cuối phần này.
We'll try to talk about how to make the queries run fast, do vectorization, just-in-time compilation, how different data formats look like, how to do parallel hash joins, try to cram as much as I can, but obviously none of that will be on the final exam.
Chúng ta sẽ cố nói về cách làm cho truy vấn chạy nhanh, vectorization, biên dịch just-in-time, các định dạng dữ liệu khác nhau trông như thế nào, cách thực hiện parallel hash join, cố nhồi nhét càng nhiều càng tốt, nhưng tất nhiên không có phần nào trong đó nằm trong đề thi cuối kỳ.
Okay? So let's get started.
Được chứ? Vậy chúng ta bắt đầu thôi.
Thank you.
Cảm ơn các bạn.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.