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ả.
I got a round of applause for DJ Cash, thank you. How's your radio show going? I heard it's popping off. Do people call in for requests?
Cho một tràng pháo tay cho DJ Cash nào, cảm ơn em. Chương trình radio của em dạo này thế nào? Thầy nghe nói chương trình đang rất ăn khách. Có người gọi vào để yêu cầu bài hát không?
Okay, again, that's on Sundays at 1 p.m. It's streaming on the internet too, right? So if you're outside the university, you can check out DJ Cash's radio show every Sunday at 1 o'clock Eastern.
Được rồi, nhắc lại, chương trình phát vào Chủ nhật lúc 1 giờ chiều. Có phát trực tuyến trên internet nữa, đúng không? Vậy nếu các em đang ở ngoài trường, các em có thể nghe chương trình radio của DJ Cash vào mỗi Chủ nhật lúc 1 giờ theo giờ miền Đông.
All right, you guys in the class, we have a lot to cover today. Today's gonna be an awesome lecture. I say that every lecture, but this one's super, they're all fun.
Được rồi, các em trong lớp, hôm nay chúng ta có rất nhiều nội dung cần học. Hôm nay sẽ là một bài giảng tuyệt vời. Buổi nào thầy cũng nói vậy, nhưng buổi này thì cực kỳ hay, mà buổi nào cũng vui cả.
I like this one a lot, though. For you guys, again, homework, sorry, project one was due last night. I think we're missing about still maybe ten submissions from people.
Nhưng thầy rất thích buổi này. Về phía các em, nhắc lại, bài tập, xin lỗi, project một đã hết hạn vào tối qua. Thầy nghĩ vẫn còn thiếu khoảng mười bài nộp.
I haven't checked the leaderboard yet. They look, somebody is blowing everyone else out. We have to understand why. So if you haven't finished project one, please do that as soon as possible.
Thầy chưa xem bảng xếp hạng. Có vẻ có một bạn đang bỏ xa tất cả những người còn lại. Chúng ta phải tìm hiểu tại sao. Nếu em chưa hoàn thành project một thì hãy làm càng sớm càng tốt.
Project two is out live today. So if you want to pull down the latest code, the write-up is available on the website. Homework three came out last week.
Project hai được công bố hôm nay. Nếu muốn tải mã nguồn mới nhất về, phần mô tả đề bài có trên trang web. Bài tập ba đã được đưa ra từ tuần trước.
That'll be due this Sunday coming up, because the goal is to give you guys a great response on the following Monday, immediately afterwards, because it'll cover things that'll be on the exam coming up next week in class on Wednesday the 8th.
Hạn nộp là Chủ nhật tuần này, vì mục tiêu là để các em có phản hồi tốt vào thứ Hai kế tiếp, ngay sau đó, vì bài này bao gồm những nội dung sẽ có trong kỳ thi diễn ra vào tuần tới, trên lớp, thứ Tư ngày 8.
Okay, any questions about any of these? Homework three is due this Sunday.
Được rồi, có câu hỏi nào về những việc này không? Bài tập ba hết hạn vào Chủ nhật này.
Project two is due after the fall break, but the midterm will be next week, and I'll post the study guide and the practice exam after class later today.
Project hai hết hạn sau kỳ nghỉ thu, nhưng kỳ thi giữa kỳ sẽ diễn ra vào tuần tới, và thầy sẽ đăng đề cương ôn tập cùng đề thi thử sau buổi học hôm nay.
Everything's done. I just haven't posted it on Piazza yet, okay? And then the practice exam will look roughly like what the real exam will be.
Mọi thứ đã xong hết. Chỉ là thầy chưa đăng lên Piazza thôi, nhé? Còn đề thi thử sẽ có dạng gần giống đề thi thật.
A little bit longer though than what the live one will be, okay?
Nhưng sẽ dài hơn một chút so với đề thi thật, nhé?
All right, so again, for additional database talks, if you can't get enough of databases, Today we have the creator of Apache Hudi giving a talk with us after class at 4:30 over Zoom.
Được rồi, nhắc lại, về các buổi nói chuyện thêm về cơ sở dữ liệu, nếu các em vẫn chưa thấy đủ về cơ sở dữ liệu. Hôm nay chúng ta có người sáng lập Apache Hudi sẽ nói chuyện với chúng ta sau giờ học, lúc 4:30 qua Zoom.
And then next week we have the MotherDuck guys giving a talk about DuckLake, which is an alternative to Hudi and Iceberg.
Rồi tuần sau có nhóm MotherDuck nói về DuckLake, một giải pháp thay thế cho Hudi và Iceberg.
And then in two weeks after that, we'll have the SpiralDB guys doing a talk about a new file format that they've created to replace Parquet and ORC called Vortex.
Và hai tuần sau đó, nhóm SpiralDB sẽ nói về một định dạng tệp mới mà họ tạo ra để thay thế Parquet và ORC, gọi là Vortex.
If you're familiar with Parquet, it's from 2013, developed by, I think, Dremio and Cloudera. It might be Twitter, it might be a part of that too. And then ORC came out of Facebook.
Nếu các em quen với Parquet, nó ra đời năm 2013, do Dremio và Cloudera phát triển, thầy nghĩ vậy. Có thể là Twitter, có thể họ cũng tham gia. Còn ORC xuất phát từ Facebook.
And so these are sort of columnar-based file formats to follow the PAX format, stuff we've talked about before, but it's like an open-source library you can use to read and write these things.
Đây đều là các định dạng tệp theo cột, tuân theo định dạng PAX, những thứ chúng ta đã nói trước đây, nhưng nó là một thư viện mã nguồn mở mà các em có thể dùng để đọc và ghi các tệp này.
So Vortex is a modern version of all this, using sort of the state-of-the-art encoding techniques. Again, this is optional.
Vortex là phiên bản hiện đại của tất cả những thứ này, sử dụng các kỹ thuật mã hóa tiên tiến nhất. Nhắc lại, phần này là tùy chọn.
These are the things, if you want to go beyond the course, please feel free to join us.
Đây là những thứ dành cho các em nếu muốn học vượt ra ngoài môn học, cứ thoải mái tham gia cùng chúng ta.
All right, so for the last two classes, we've talked about data structures, again in the context of table indexes or being used in internal structures like a page table for your database system.
Được rồi, trong hai buổi học vừa rồi, chúng ta đã nói về các cấu trúc dữ liệu, một lần nữa trong ngữ cảnh các chỉ mục của bảng hoặc được dùng trong các cấu trúc nội bộ như bảng trang (page table) của hệ cơ sở dữ liệu.
We made a pretty big assumption that when we discuss these data structures and the algorithms we've used to interact with them or manipulate them, we assumed that we were going to have a single thread, a single worker accessing the database at any given time, because this makes a whole bunch of things a lot easier, because you're not worried about concurrency control issues of multiple threads coming in and touching the data structure at the same time.
Chúng ta đã đưa ra một giả định khá lớn khi bàn về các cấu trúc dữ liệu này và các thuật toán dùng để tương tác hay thao tác với chúng, đó là chúng ta giả định chỉ có một luồng duy nhất, một worker duy nhất truy cập cơ sở dữ liệu tại bất kỳ thời điểm nào, vì điều này làm cho rất nhiều thứ dễ dàng hơn nhiều, bởi bạn không phải lo về các vấn đề điều khiển đồng thời khi nhiều luồng cùng lúc đi vào và chạm đến cấu trúc dữ liệu.
So now in today's class, we need to go sort of break that assumption and say, okay, well if you do have multiple workers accessing these data structures, how are we going to protect them?
Vì vậy trong buổi học hôm nay, chúng ta cần phá bỏ giả định đó và nói rằng, được rồi, nếu có nhiều worker truy cập các cấu trúc dữ liệu này, thì chúng ta sẽ bảo vệ chúng như thế nào?
And it should be sort of obvious why you want to do this, because in modern architectures, The clock speed of a single core is not really going up that much.
Và lý do muốn làm điều này khá hiển nhiên, bởi vì trong các kiến trúc hiện đại, tốc độ xung nhịp của một lõi đơn không tăng lên nhiều nữa.
Instead, you're getting a lot more cores. And now in actually modern systems, you get a variety of heterogeneous cores.
Thay vào đó, bạn có nhiều lõi hơn rất nhiều. Và trong các hệ thống hiện đại ngày nay, bạn có nhiều loại lõi không đồng nhất.
You'll have some performance ones and low-power ones that have different clock speeds and different performance capabilities.
Sẽ có các lõi hiệu năng cao và các lõi tiết kiệm điện với tốc độ xung nhịp và khả năng hiệu năng khác nhau.
Nonetheless, we need to take care of using all these cores that are available to us, because then that'll help us maximize the performance of the system.
Dù vậy, chúng ta cần chú ý tận dụng tất cả các lõi hiện có, vì điều đó giúp tối đa hóa hiệu năng của hệ thống.
And as we see later on, we'll be able to use these extra workers or extra cores to hide disk stalls.
Và như chúng ta sẽ thấy sau này, chúng ta có thể dùng các worker hay lõi bổ sung này để che giấu các độ trễ do đĩa.
It's like, as you sort of did in Project 1, you could have one thread block while it was trying to go fetch some disk, and then another thread can run and make use of the system and still make forward progress.
Giống như bạn đã làm trong Project 1, một luồng có thể bị chặn khi đang cố lấy dữ liệu từ đĩa, và khi đó một luồng khác có thể chạy và tận dụng hệ thống, vẫn tiếp tục tiến triển.
So pretty much what we're talking about today is how almost every single data system that's out there is going to be implemented.
Vậy về cơ bản, những gì chúng ta nói hôm nay là cách mà hầu như mọi hệ thống dữ liệu ngoài kia được triển khai.
There is a small subset of these systems that don't actually do any of the stuff that we're talking about today, and instead have what are called single-threaded execution engines, meaning they assume that there is one and only one thread accessing these data structures at any time.
Có một tập con nhỏ các hệ thống không làm bất cứ điều gì chúng ta bàn hôm nay, mà thay vào đó có cái gọi là engine thực thi đơn luồng, nghĩa là chúng giả định chỉ có một và duy nhất một luồng truy cập các cấu trúc dữ liệu này tại mọi thời điểm.
So therefore, they could do all the stuff we were basically talking about before without bringing in the latching stuff that we'll talk about today.
Do đó, chúng có thể làm mọi thứ mà chúng ta đã nói trước đây mà không cần đưa vào cơ chế latch mà hôm nay chúng ta sẽ bàn.
Most famous of these is Redis. It's a single-threaded execution engine. There's only one thread that can do anything in the system at any given time.
Nổi tiếng nhất trong số này là Redis. Nó là một engine thực thi đơn luồng. Chỉ có một luồng duy nhất có thể làm bất cứ việc gì trong hệ thống tại một thời điểm.
There's a fork of Redis called Valkey from Amazon, because Redis got a little frisky with their licensing.
Có một bản fork của Redis tên là Valkey từ Amazon, vì Redis đã hơi "nghịch ngợm" với giấy phép của họ.
And so now there is actually multiple threads to handle networking, and then you can hand that off to then a single-threaded execution engine thread, which still doesn't have the latching stuff we're talking about here today.
Và giờ đây thực sự có nhiều luồng để xử lý mạng, rồi bạn chuyển giao việc đó cho một luồng engine thực thi đơn luồng, mà vẫn không có cơ chế latch như chúng ta đang nói hôm nay.
But the basic idea is, again, if you assume there's only one thread, you don't have to worry about another thread touching the data structure at the same time as you.
Nhưng ý tưởng cơ bản là, nếu bạn giả định chỉ có một luồng, bạn không phải lo một luồng khác chạm vào cấu trúc dữ liệu cùng lúc với bạn.
So some systems do this. They do mostly do it for performance reasons and engineering reasons.
Vậy nên một số hệ thống làm như thế. Họ làm vậy chủ yếu vì lý do hiệu năng và kỹ thuật.
It simplifies the implementation, but most of the systems we'll talk about in this class aren't going to do this. I just want to bring it up to say these things do exist.
Nó đơn giản hóa việc triển khai, nhưng hầu hết các hệ thống mà chúng ta sẽ nói đến trong môn này sẽ không làm như vậy. Tôi chỉ muốn nhắc đến để các em biết là những thứ này có tồn tại.
So now the thing we need to introduce in our database system is what is called a concurrency control protocol.
Vậy bây giờ, thứ chúng ta cần đưa vào hệ thống cơ sở dữ liệu của mình được gọi là giao thức điều khiển đồng thời (concurrency control protocol).
You sort of think of this as like the rules of the road, the traffic laws, for how workers can access parts of our system at the same time.
Các em có thể hình dung nó như luật đi đường, các quy tắc giao thông, cho việc các worker truy cập các phần của hệ thống cùng một lúc.
I'm using the term worker instead of a thread or process, because different systems will do different things. Like Postgres has multi-process. Most other systems are multi-threaded.
Tôi dùng thuật ngữ worker thay vì thread hay process, vì mỗi hệ thống sẽ làm một kiểu khác nhau. Ví dụ Postgres dùng đa tiến trình (multi-process). Hầu hết các hệ thống khác dùng đa luồng (multi-threaded).
But the high-level concept is still the same: you'd want to protect these data structures using a concurrency protocol.
Nhưng khái niệm ở mức cao vẫn như nhau: các em muốn bảo vệ những cấu trúc dữ liệu này bằng một giao thức đồng thời.
The basic idea is that this is how the system is going to guarantee that any changes that we're going to make to a shared object in our system will be "correct".
Ý tưởng cơ bản là đây là cách hệ thống đảm bảo rằng mọi thay đổi mà chúng ta thực hiện trên một đối tượng dùng chung trong hệ thống sẽ là "đúng đắn".
And I'm putting the word correct in quotes here because it can mean different things to different parts of the system, depending on who's doing what. So one notion of correctness will be logical correctness.
Và tôi đặt từ "đúng đắn" trong dấu ngoặc kép ở đây vì nó có thể mang những ý nghĩa khác nhau với các phần khác nhau của hệ thống, tùy vào việc ai đang làm gì. Một khái niệm về tính đúng đắn là tính đúng đắn logic.
And this just means: can I see the data that I should see?
Điều này chỉ có nghĩa là: tôi có thấy được dữ liệu mà tôi lẽ ra phải thấy không?
Like if I have a query that inserts a record, you know, ABC, if I come back and try to read that ABC, should I be able to see it?
Ví dụ nếu tôi có một truy vấn chèn một bản ghi, chẳng hạn ABC, nếu tôi quay lại và cố đọc ABC đó, tôi có nên thấy được nó không?
Sometimes yes, right? And if somebody else deletes it, then sometimes no. And so with that, those terms of correctness we'll cover after the midterm.
Đôi khi là có, đúng không? Và nếu ai đó khác xóa nó đi thì đôi khi là không. Và về những khái niệm đúng đắn này, chúng ta sẽ học sau kỳ thi giữa kỳ.
Just have this notion that there's a higher-level criteria we may want to use to determine whether something is actually correct or not.
Các em chỉ cần biết rằng có một tiêu chí ở mức cao hơn mà chúng ta có thể dùng để xác định một thứ có thực sự đúng hay không.
The thing that we care about in this lecture is physical correctness, meaning the internal representation of whatever data structure we're using and manipulating in our system will be, I'll use the term sound, meaning if I follow a node in my B+tree and has a pointer to some other node, that pointer better go to actually what I expected to go to it, not some random location in memory
Thứ mà chúng ta quan tâm trong bài giảng này là tính đúng đắn vật lý, nghĩa là biểu diễn bên trong của cấu trúc dữ liệu nào đó mà chúng ta đang dùng và thao tác trong hệ thống sẽ phải tôi sẽ dùng từ "vững chắc" (sound), nghĩa là nếu tôi đi theo một nút trong B+tree và nó có con trỏ tới một nút khác, thì con trỏ đó phải trỏ đúng tới thứ mà tôi mong đợi, chứ không phải một vị trí ngẫu nhiên trong bộ nhớ
where I would have a segfault or read some part of memory that I shouldn't be reading.
nơi tôi sẽ gặp segfault hoặc đọc một phần bộ nhớ mà lẽ ra tôi không được đọc.
So this is what we care about today: how to make sure that the data structure itself is correct, even though the contents of the data structure may have a different notion of correctness, like if I insert my record, can I see my own record, right?
Đây là điều chúng ta quan tâm hôm nay: làm sao đảm bảo bản thân cấu trúc dữ liệu là đúng, dù cho nội dung của cấu trúc dữ liệu đó có thể có một khái niệm đúng đắn khác, như là nếu tôi chèn bản ghi của mình, tôi có thấy bản ghi của mình không, đúng không?
That part we're not worrying about until later. This is like, how do we make sure that thing doesn't segfault as we're flipping bits and going down inside the data structure?
Phần đó chúng ta chưa lo đến cho tới sau này. Ở đây là làm sao đảm bảo thứ đó không bị segfault khi chúng ta đang lật các bit và đi xuống bên trong cấu trúc dữ liệu?
So to do this, we're first going to provide some overview about what the latching mechanisms look like.
Để làm điều này, trước tiên chúng ta sẽ có một cái nhìn tổng quan về các cơ chế latch trông như thế nào.
We don't really care about how, the low-level details of how all these are actually implemented, we maybe don't care so much, but at least it'd be good to be aware of what actually goes underneath the covers for these things.
Chúng ta không thực sự quan tâm đến việc chi tiết cấp thấp của cách chúng được cài đặt thực sự, có lẽ không quan tâm lắm, nhưng ít nhất cũng nên biết thực sự có những gì diễn ra bên dưới các cơ chế này.
We touched in the advanced class more sophisticated implementations, but I'll just highlight some of them.
Trong lớp nâng cao, chúng ta đã đề cập đến các cách triển khai tinh vi hơn, nhưng tôi sẽ chỉ nêu bật một vài cách trong số đó.
Then we'll talk about how to do hash table latching, which is the simplest protocol, and how to make sure our hash table is physically correct.
Sau đó chúng ta sẽ nói về cách thực hiện latching cho hash table, đây là giao thức đơn giản nhất, và cách đảm bảo hash table của chúng ta đúng đắn về mặt vật lý.
And then we'll spend a lot of time talking about how to handle this in B+trees.
Rồi chúng ta sẽ dành nhiều thời gian để nói về cách xử lý vấn đề này trong B+tree.
First we'll go with latching going from the top to the bottom, and then we'll deal with doing scans along the leaf nodes. And then we'll finish up with an announcement on project 2. Okay?
Đầu tiên chúng ta sẽ làm latching đi từ trên xuống dưới, và sau đó chúng ta sẽ xử lý việc quét dọc theo các nút lá. Cuối cùng chúng ta sẽ kết thúc bằng một thông báo về project 2. Được chứ?
All right, so I sort of alluded to this early in the semester about this notion of locks and latches, and the OSP people are gonna call what we call latches, they're gonna call them locks.
Được rồi, tôi đã nhắc sơ qua từ sớm trong học kỳ về khái niệm lock và latch, và những người làm OSP sẽ gọi cái mà chúng ta gọi là latch là lock.
The reason why we're not gonna use the term locks for latches and keep them separate is because these locks are gonna represent higher level protection mechanisms for, again, for logical concepts or logical entities in our database system.
Lý do chúng ta không dùng thuật ngữ lock cho latch mà tách riêng chúng ra là vì các lock này sẽ đại diện cho các cơ chế bảo vệ ở mức cao hơn, dành cho một lần nữa, các khái niệm logic hay các thực thể logic trong hệ cơ sở dữ liệu của chúng ta.
So locks are going to be used to control transactions, and think of a transaction as like a, I want to run multiple queries in my application, and I want all those queries to be atomic.
Vậy lock sẽ được dùng để điều khiển các transaction, và hãy hình dung một transaction như là, tôi muốn chạy nhiều truy vấn trong ứng dụng của mình, và tôi muốn tất cả các truy vấn đó mang tính nguyên tử.
Okay, we'll cover this later in the semester, but just think of like, it's a high-level thing where the application is trying to do multiple operations that has to define across multiple queries, and you make sure those multiple queries occur in some improper, some proper ordering, so that we produce correct results.
Được rồi, chúng ta sẽ học phần này sau trong học kỳ, nhưng cứ nghĩ đó là một khái niệm ở mức cao khi ứng dụng đang cố thực hiện nhiều thao tác phải được xác định trải dài qua nhiều truy vấn, và bạn đảm bảo những truy vấn đó xảy ra theo một thứ tự đúng đắn, một thứ tự thích hợp, để chúng ta cho ra kết quả chính xác.
And for this, for transactions, we're gonna hold these locks for the length of the transaction, typically, if you care about strict correctness.
Và với các transaction này, chúng ta sẽ giữ các lock trong suốt thời gian của transaction, thường là vậy, nếu bạn quan tâm đến tính đúng đắn nghiêm ngặt.
And then the database system itself is also responsible for rolling back any changes from queries that got executed on behalf of a transaction, if that transaction ends up having to abort.
Và bản thân hệ cơ sở dữ liệu cũng chịu trách nhiệm hoàn tác mọi thay đổi từ các truy vấn đã được thực thi thay mặt cho một transaction, nếu transaction đó cuối cùng phải hủy bỏ.
I mean, if I insert 10 records, and then I try to insert an 11th record, and I violate some integrity constraint that's defined in my table, then my transaction has to abort, and the database system is responsible for rolling back any of those first 10 things I inserted.
Ý tôi là, nếu tôi chèn 10 bản ghi, rồi cố chèn bản ghi thứ 11, và vi phạm một ràng buộc toàn vẹn nào đó được định nghĩa trong bảng của tôi, thì transaction của tôi phải hủy bỏ, và hệ cơ sở dữ liệu chịu trách nhiệm hoàn tác 10 thứ đầu tiên mà tôi đã chèn.
Not the application. So everything sort of happens transparently.
Không phải ứng dụng. Vậy nên mọi thứ diễn ra một cách trong suốt.
Again, the details of this we'll work out later, just be aware that the rollback mechanism is implemented by the system, because we're dealing with crappy JavaScript code, we don't want to rely on people to do that rollback for us, we have to do everything ourselves.
Một lần nữa, chi tiết phần này chúng ta sẽ tìm hiểu sau, chỉ cần biết rằng cơ chế rollback do hệ thống triển khai, vì chúng ta đang phải làm việc với đống mã JavaScript tồi, chúng ta không muốn trông cậy vào người khác để rollback giúp mình, chúng ta phải tự làm mọi thứ.
The thing we're talking about in this class today is the latches.
Thứ chúng ta nói đến trong lớp hôm nay là các latch.
We're protecting the internal workers of the database system that, again, are manipulating the low-level data structures we're using to run our actual system and store data.
Chúng ta đang bảo vệ các hoạt động nội bộ của hệ cơ sở dữ liệu mà, một lần nữa, đang thao tác trên các cấu trúc dữ liệu cấp thấp mà chúng ta dùng để chạy hệ thống thực sự và lưu trữ dữ liệu.
So the way to think of it is that we want to protect the critical sections of the data structures we have using these latches.
Vậy cách để hình dung là chúng ta muốn bảo vệ các phần găng của các cấu trúc dữ liệu mình có bằng những latch này.
And because these are meant to be really fast operations, like go and change some node then pop out right away, you're not going to hold them for long periods of time.
Và vì đây là những thao tác phải thật nhanh, kiểu vào sửa một nút nào đó rồi thoát ra ngay, nên bạn sẽ không giữ chúng trong thời gian dài.
We're going to hold them for nanoseconds or microseconds in some cases. And because now these are all internal operations, we want to be...
Có khi chỉ giữ trong vài nano giây hoặc micro giây. Và vì đây đều là các thao tác nội bộ, nên chúng ta muốn...
we're responsible for making sure that if we can't do something, we don't put the data structure in an invalid state or partial state. That's actually a mistake. Do not need better rollback changes.
chúng ta có trách nhiệm đảm bảo rằng nếu không làm được việc gì đó, thì không để cấu trúc dữ liệu rơi vào trạng thái không hợp lệ hoặc trạng thái dở dang. Thực ra đó là một sai sót. Không cần hoàn tác thay đổi tốt hơn.
Actually, we do need better rollback changes.
Thực ra là chúng ta cần hoàn tác thay đổi tốt hơn.
The worker itself is responsible for keeping track of what changes it made, and then it's the one that has to go and rollback things if it can't do everything that it wants to do.
Bản thân worker có trách nhiệm theo dõi những thay đổi nó đã thực hiện, và chính nó là bên phải đi hoàn tác mọi thứ nếu không làm được hết những gì nó muốn làm.
Yeah, that should be... do need rollback changes. So there's this great table from the book I mentioned before about...
Đúng rồi, phải là... cần hoàn tác thay đổi. Có một bảng rất hay trong cuốn sách tôi đã nhắc trước đó, về...
from this guy, Goetz Graefe, about modern B+tree techniques, and he has this distinction between the locks and the latches and what they're actually used for.
của ông Goetz Graefe, về các kỹ thuật B+tree hiện đại, và ông ấy phân biệt giữa lock và latch cùng mục đích sử dụng thực sự của chúng.
So a way to sort of read this is going from the top to the bottom.
Cách đọc bảng này là đi từ trên xuống dưới.
You would say, like, latches are some kind of primitive we're going to use to protect workers, threads, or processes from the in-memory data structures during the critical sections, and the only two modes we're going to have are read and write, whereas in locks for transactions, we'll have shared...
Bạn sẽ nói rằng, latch là một dạng nguyên thủy dùng để bảo vệ các worker, luồng, hoặc tiến trình khỏi các cấu trúc dữ liệu trong bộ nhớ trong các miền găng, và chỉ có hai chế độ là đọc và ghi, trong khi với lock cho giao dịch, ta sẽ có shared...
we'll have these intention locks and shared locks, higher-level concepts. Again, we'll worry about all that later.
ta sẽ có intention lock và shared lock, những khái niệm ở mức cao hơn. Một lần nữa, những việc đó để sau hãy lo.
And the only way we're going to be able to handle deadlocks with latches is through coding discipline and through avoidance, meaning that there isn't going to be some high-level coordinator understanding what all the different threads are doing in these critical sections and saying, "Oh, you got a deadlock.
Và cách duy nhất để xử lý bế tắc với latch là thông qua kỷ luật lập trình và sự phòng tránh, nghĩa là sẽ không có một bộ điều phối cấp cao nào hiểu các luồng khác nhau đang làm gì trong các miền găng này rồi nói: "Ồ, bạn bị bế tắc rồi.
Let me go ahead and break it apart," right? It's up to us in our code to make sure we don't have deadlocks.
Để tôi gỡ ra cho," đúng không? Việc đảm bảo không có bế tắc là trách nhiệm của chúng ta trong mã.
I'll show how we do that, to avoid any problems, because there isn't someone going to come along and fix it for us.
Tôi sẽ chỉ cách làm để tránh mọi vấn đề, vì sẽ không có ai đến sửa giúp chúng ta.
Whereas in locks for transactions, if you have two transactions try to acquire locks that the other guy holds, the database system is responsible for figuring out there's a deadlock and go ahead and use killing transactions to free up...
Còn với lock cho giao dịch, nếu có hai giao dịch cố lấy các lock mà bên kia đang giữ, thì hệ quản trị cơ sở dữ liệu có trách nhiệm phát hiện ra có bế tắc và tiến hành hủy giao dịch để giải phóng...
break the deadlock. Because again, we're assuming the transactions are coming from queries from the outside world, external to the system.
phá vỡ bế tắc. Vì một lần nữa, ta giả định các giao dịch đến từ các truy vấn của thế giới bên ngoài, bên ngoài hệ thống.
It's some JavaScript program that is poorly written, maybe doing bad things, and it's our job to make sure that we don't let them cause too many problems.
Đó có thể là một chương trình JavaScript viết kém, có thể làm những việc xấu, và nhiệm vụ của ta là đảm bảo không để chúng gây ra quá nhiều vấn đề.
So again, for this class today, we're worried about latches and therefore we have to do all of this. When we talk about locks, that'll be later in the semester.
Vậy nên, với buổi học hôm nay, chúng ta quan tâm đến latch và do đó phải làm tất cả những điều này. Khi nói về lock, đó sẽ là phần sau của học kỳ.
When we talk about concurrency control protocols at a higher level, in lecture 15, okay?
Khi nói về các giao thức điều khiển đồng thời ở cấp độ cao hơn, ở bài giảng 15, được chứ?
Alright, so our latches, since again there's these low-level protection primitives, synchronization primitives, only have two modes: read mode and write mode.
Được rồi, các latch của chúng ta, vì đây là những nguyên thủy bảo vệ mức thấp, những nguyên thủy đồng bộ hóa, nên chỉ có hai chế độ: chế độ đọc và chế độ ghi.
And it should be sort of obvious if you've taken any OS class or systems class, in read mode you can allow multiple threads or workers to access whatever this critical section is you're trying to protect at the same time, as long as they don't make any changes to it.
Và điều này khá hiển nhiên nếu các em đã học môn hệ điều hành hay hệ thống nào đó: ở chế độ đọc, ta cho phép nhiều thread hay worker cùng truy cập vào vùng găng mà ta đang cố bảo vệ này tại cùng một thời điểm, miễn là chúng không thay đổi gì trong đó.
So they can read the contents and be guaranteed that there won't be intermittent changes while this occurs, but it can't change anything.
Vì vậy chúng có thể đọc nội dung và được đảm bảo rằng sẽ không có thay đổi xen ngang trong lúc này, nhưng chúng không thể thay đổi bất cứ thứ gì.
Write mode basically puts whatever the critical section is into single-threaded mode, because only one worker can hold a latch in write mode at any given time, and it's allowed to make any changes that it wants.
Chế độ ghi về cơ bản đưa vùng găng, dù nó là gì, vào chế độ đơn luồng, vì tại một thời điểm chỉ một worker có thể giữ latch ở chế độ ghi, và worker đó được phép thực hiện mọi thay đổi mà nó muốn.
And it can guarantee that there's no other reader or writer thread or worker inside that critical section at the same time. So the compatibility matrix is pretty simple, right?
Và nó có thể đảm bảo rằng không có thread đọc hay ghi nào khác hay worker nào khác ở trong vùng găng đó cùng lúc. Vậy ma trận tương thích khá đơn giản, đúng không?
If I have a read latch and somebody else wants to acquire the read latch, those are compatible, you allow the other thread to acquire that latch at the same time.
Nếu tôi đang giữ một read latch và người khác muốn lấy read latch, thì hai cái đó tương thích, bạn cho phép thread kia lấy latch đó cùng lúc.
But if at least one of the latches is a write latch, then they're incompatible, and you have to deny the request for the other worker to acquire the latch.
Nhưng nếu ít nhất một trong các latch là write latch thì chúng không tương thích, và bạn phải từ chối yêu cầu lấy latch của worker còn lại.
And then we'll talk about in a second what do we do when that request is denied, what should that worker do if it says, I try to get a latch and I can't get it.
Lát nữa ta sẽ bàn xem làm gì khi yêu cầu đó bị từ chối, worker đó nên làm gì nếu nó nói: tôi cố lấy latch mà không lấy được.
So in our implementation of a latch, we have sort of four main goals.
Vậy khi cài đặt một latch, ta có bốn mục tiêu chính.
We, one, want our latch to have a small memory footprint, I think like in bytes, if possible, because again we're going to store these now inside the data structures that we're implementing.
Thứ nhất, ta muốn latch có dung lượng bộ nhớ nhỏ, nếu được thì tính theo byte, vì ta sẽ lưu các latch này bên trong các cấu trúc dữ liệu mà ta đang cài đặt.
Like in every page for a B+tree, we're going to put our latches inside of that page.
Chẳng hạn trong mỗi page của B+tree, ta sẽ đặt các latch bên trong page đó.
So we don't want this, you know, a 10 kilobyte data structure to maintain a latch inside of our page, because it's space we could be using for storing keys and values, right?
Nên ta không muốn một cấu trúc dữ liệu 10 kilobyte để duy trì một latch trong page, vì đó là không gian lẽ ra ta dùng để lưu khóa và giá trị, đúng không?
We want our latch to have a fast execution path when there's no contention, meaning I don't have to go through a bunch of, jump through a bunch of hoops in order to acquire a latch if nobody else is trying to acquire that latch at the same time or nobody else holds the latch at the same time.
Ta muốn latch có đường thực thi nhanh khi không có tranh chấp, nghĩa là tôi không phải trải qua hàng loạt bước, vượt qua hàng loạt rào cản để lấy latch nếu không ai khác đang cố lấy latch đó cùng lúc hoặc không ai khác đang giữ latch đó cùng lúc.
I also want to make sure that the management of my latches is completely decentralized, because again, I don't want to have to build a centralized coordinator that's keeping track of all the different workers I have running my system and what latches they hold and what they're doing, because that's going to be really expensive for me now to go update that information anytime I want to acquire a latch.
Tôi cũng muốn đảm bảo việc quản lý các latch hoàn toàn phi tập trung, vì tôi không muốn phải xây dựng một bộ điều phối tập trung để theo dõi tất cả các worker khác nhau đang chạy trong hệ thống của tôi và chúng giữ latch nào, đang làm gì, vì việc cập nhật thông tin đó mỗi lần muốn lấy latch sẽ rất tốn kém.
Think of it like the page table in your buffer pool.
Hãy nghĩ nó giống như page table trong buffer pool của các em.
It's a centralized data structure that everyone has to go to in order to get pages, and that can become a hotspot in our system.
Nó là một cấu trúc dữ liệu tập trung mà ai cũng phải truy cập để lấy các trang, và điều đó có thể trở thành điểm nghẽn (hotspot) trong hệ thống của chúng ta.
So that's why we want our latch management to be completely decentralized, and we're going to store the latches inside, directly inside our data structure at the different locations of the critical sections we want to protect.
Đó là lý do chúng ta muốn việc quản lý latch hoàn toàn phi tập trung, và chúng ta sẽ lưu các latch ngay bên trong, trực tiếp bên trong cấu trúc dữ liệu của mình, tại các vị trí của những critical section mà chúng ta muốn bảo vệ.
And last but not least, which goes, again, the major theme throughout the entire semester: at all costs, we want to avoid having to talk to the operating system.
Và cuối cùng nhưng không kém phần quan trọng, điều này một lần nữa lại là chủ đề xuyên suốt cả học kỳ: bằng mọi giá, chúng ta muốn tránh phải làm việc với hệ điều hành.
As soon as you have to make a syscall, now it's going to the kernel, it's going into protective mode, there's a bunch of security mechanisms that have to make sure you're not doing malicious things.
Ngay khi bạn phải gọi một syscall, thì nó sẽ đi vào kernel, chuyển sang chế độ bảo vệ, và có hàng loạt cơ chế bảo mật phải đảm bảo rằng bạn không làm những điều độc hại.
Going to the operating system is always going to be more expensive, and ideally we want to do as much as we can in user space. So if we can, we want to avoid syscalls.
Đi xuống hệ điều hành luôn tốn kém hơn, và lý tưởng nhất là chúng ta làm càng nhiều càng tốt trong user space. Vì vậy, nếu có thể, chúng ta muốn tránh syscall.
So now, everything I'm telling you here seems reasonable, again, if you come from a database systems perspective, like people actually building the actual system, we care about all of these things.
Bây giờ, mọi điều tôi nói ở đây nghe có vẻ hợp lý, một lần nữa, nếu bạn xuất phát từ góc nhìn của hệ cơ sở dữ liệu, tức là những người thực sự xây dựng hệ thống, chúng ta quan tâm đến tất cả những điều này.
You talk to the assholes building operating systems and they think we're all idiots and they should not be doing any of these things.
Còn nếu bạn nói chuyện với mấy gã khó ưa chuyên xây dựng hệ điều hành, họ nghĩ chúng ta đều là đồ ngốc và rằng chúng ta không nên làm bất kỳ điều nào trong số này.
So this is a famous post from Linus in the mailing list.
Đây là một bài đăng nổi tiếng của Linus trên mailing list.
This is, what, this is 2020, so five years ago, and he's making a, He's banging on about people, particularly database people, running their own latches, which again he calls Spinbox, and he has this little blurb here that he says, "I repeat, do not use Spinbox in user space," which is what we're gonna do, "unless you know actually what you're doing, and be aware that the likelihood that you know what you're doing is basically nil,"
Đây là, à, năm 2020, tức là năm năm trước, và ông ấy đang chê trách những người, đặc biệt là dân cơ sở dữ liệu, tự cài đặt latch của riêng mình, mà ông ấy gọi là Spinbox, và ông ấy có đoạn ngắn này, nói rằng: "Tôi nhắc lại, đừng dùng Spinbox trong user space," đúng là điều chúng ta sắp làm, "trừ khi bạn thực sự biết mình đang làm gì, và hãy nhớ rằng khả năng bạn biết mình đang làm gì về cơ bản là bằng không."
right? He's wrong. We're right. Nobody in their right mind would do it the way he's proposing because you lose complete control over the system if you have to go down to the operating system.
Đúng không? Ông ấy sai. Chúng ta đúng. Không ai tỉnh táo lại làm theo cách ông ấy đề xuất vì bạn mất hoàn toàn quyền kiểm soát hệ thống nếu phải đi xuống hệ điều hành.
We'll see why this is gonna happen in a second.
Lát nữa chúng ta sẽ thấy vì sao điều này xảy ra.
So this is why most database systems will not do what he's proposing here, and will not rely on the operating system to manage our latches.
Đó là lý do hầu hết các hệ cơ sở dữ liệu sẽ không làm như ông ấy đề xuất ở đây, và sẽ không dựa vào hệ điều hành để quản lý latch của chúng ta.
Again, give me a few more slides and I'll explain why this is the case. Alright, so how can we implement our latches? So the most simple one can be a test-and-set Spinbox.
Một lần nữa, cho tôi thêm vài slide nữa và tôi sẽ giải thích vì sao lại như vậy. Được rồi, vậy chúng ta có thể cài đặt latch như thế nào? Cách đơn giản nhất có thể là test-and-set Spinbox.
It's basically what Linus is talking about, and is what actually is in the kernel now when you call pthread mutex, so we'll discuss that in a second.
Về cơ bản đó là điều Linus đang nói đến, và là thứ hiện đang có trong kernel khi bạn gọi pthread mutex, nên lát nữa chúng ta sẽ bàn.
But then we'll look at another mechanism using a blocking OS mutex, right? Spin, spin, spin, test-and-set Spinbox is what Linus says not to use.
Nhưng sau đó chúng ta sẽ xem một cơ chế khác dùng blocking OS mutex, đúng không? Spin, spin, spin, test-and-set Spinbox là thứ Linus bảo đừng dùng.
He says use a blocking OS mutex, but we'll see what that looks like, and then I'll talk about what a reader-writer lock is. Again, there's a bunch of more advanced techniques you can use.
Ông ấy bảo hãy dùng blocking OS mutex, nhưng chúng ta sẽ xem nó như thế nào, rồi tôi sẽ nói về reader-writer lock là gì. Một lần nữa, có rất nhiều kỹ thuật nâng cao hơn mà bạn có thể dùng.
People have been researching this kind of stuff for a long, long time. There's an adaptive Spinbox from Apple's parking lot API, or a library.
Người ta đã nghiên cứu những thứ kiểu này từ rất rất lâu rồi. Có một Spinbox thích ứng (adaptive) từ API parking lot của Apple, hoặc một thư viện.
There is MCS locks, Cubase Spinbox, there's optimistic lock coupling that's used in some of the German systems.
Có khóa MCS, Cubase Spinbox, có optimistic lock coupling được dùng trong một số hệ thống của Đức.
The latest one I'm aware of is one called Cosmopolitan that uses a library from Google called nsync, with the letter n, nsync, that has a bunch of internal synchronization primitives.
Cái mới nhất mà tôi biết là một thứ tên là Cosmopolitan dùng một thư viện của Google tên là nsync, với chữ n, nsync, trong đó có hàng loạt nguyên thủy đồng bộ hóa nội bộ.
Some of them rely on the OS stuff, some of them rely on The userspace stuff, but in general you don't want to have to write this yourself.
Một số dựa vào hệ điều hành, một số dựa vào không gian người dùng, nhưng nhìn chung bạn không nên tự viết những thứ này.
There's existing libraries you want to use, again, like the one from Apple, and then this is a blog article from almost a decade ago from a locking library, for now we're on a latching library, that they built for the Safari browser.
Đã có sẵn các thư viện để dùng, như cái của Apple chẳng hạn, và đây là một bài blog từ gần mười năm trước về một thư viện khóa (lock), còn bây giờ ta gọi là thư viện latch, mà họ xây dựng cho trình duyệt Safari.
But they had this little micro benchmark here just showing how in some workloads you can get about 10 to 5 percent improvement over the standard template library pthreads, and the metadata they're maintaining per latch is much smaller than it would be using pthread and utils.
Nhưng họ có một micro benchmark nhỏ ở đây cho thấy trong một số workload bạn có thể đạt cải thiện khoảng 5 đến 10 phần trăm so với pthreads của thư viện chuẩn, và siêu dữ liệu mà nó phải duy trì cho mỗi latch nhỏ hơn nhiều so với khi dùng pthread và utils.
So the most simple latch you can write is called a test-and-set spin latch, or test-and-set spin lock.
Latch đơn giản nhất bạn có thể viết gọi là test-and-set spin latch, hay test-and-set spin lock.
This is very, very efficient because you only need to store maybe 8 bits to keep track of the latch.
Cái này rất, rất hiệu quả vì bạn chỉ cần lưu có lẽ 8 bit để theo dõi latch.
The challenge, though, it's not gonna be very scalable and certainly not cache friendly, because our thread is just spinning on trying to acquire this latch over and over again, and the OS is gonna think, oh, you're doing useful work, let me keep scheduling you, but in actuality you're just burning cycles.
Tuy nhiên, thách thức là nó sẽ không mở rộng tốt và chắc chắn không thân thiện với cache, vì thread của ta cứ quay vòng để cố gắng giành latch này hết lần này đến lần khác, và hệ điều hành sẽ nghĩ, ồ, bạn đang làm việc có ích, để tôi cứ tiếp tục lập lịch cho bạn, nhưng thực ra bạn chỉ đang đốt chu kỳ CPU.
But in some cases this is okay, some cases it's not okay. So a realistic implementation will look like this.
Nhưng có trường hợp thế này là ổn, có trường hợp thì không. Vậy một cài đặt thực tế sẽ trông như thế này.
So in C++ we can use the standard template library, we have this atomic flag, this is just an alias for the atomic boolean, and it has a really simple API where if I want to acquire the latch, assuming if it's currently not set, then when I call test-and-set, try to set it to true, it's gonna return false because I haven't set it yet,
Trong C++ ta có thể dùng thư viện chuẩn, có atomic flag này, nó chỉ là một bí danh của atomic boolean, và có API rất đơn giản: nếu tôi muốn giành latch, giả sử hiện tại nó chưa được đặt, thì khi tôi gọi test-and-set, thử đặt nó thành true, nó sẽ trả về false vì tôi chưa đặt nó,
and so I'll just spin in this loop over and over again until I can then set it to true, in which case it comes back as false because that was the previous value, and then I pop out of this while loop.
và như vậy tôi sẽ cứ quay trong vòng lặp này hết lần này đến lần khác cho đến khi đặt được thành true, khi đó nó trả về false vì đó là giá trị trước đó, và tôi thoát khỏi vòng lặp while này.
So it's basically me trying to acquire a latch, and it's gonna spin this while loop infinitely until I can actually get it. So you can be a little more sophisticated inside your while loop.
Về cơ bản đó là tôi đang cố giành một latch, và nó sẽ quay vòng while này vô hạn cho đến khi thực sự giành được. Bạn có thể tinh vi hơn một chút bên trong vòng while.
You can say, "Oh, I've tried ten times, so let me yield to the OS, deschedule my thread, and then that way if I come back maybe it'll be available."
Bạn có thể nói: "À, tôi đã thử mười lần rồi, nên hãy nhường cho hệ điều hành, hủy lập lịch thread của tôi, và như vậy khi quay lại có thể nó đã sẵn sàng."
I could kill myself for a certain amount of time if I can't acquire it.
Tôi có thể tự dừng một khoảng thời gian nếu không giành được.
But there's some intelligence you can put in here, but at the end of the day the implementation is pretty basic.
Nhưng bạn có thể đưa thêm một chút thông minh vào đây, nhưng rốt cuộc thì cách triển khai vẫn khá cơ bản.
So the reason why this is not gonna be so great is, what I've already said, is that we're burning cycles here, because technically we're doing work, we're just not doing useful work in our database system, and the OS doesn't know that.
Lý do cách này sẽ không tốt lắm là, như tôi đã nói, chúng ta đang đốt chu kỳ CPU ở đây, vì về mặt kỹ thuật thì chúng ta đang làm việc, chỉ là không làm việc có ích trong hệ quản trị cơ sở dữ liệu của mình, và hệ điều hành thì không biết điều đó.
The other challenge is gonna be in non-uniform memory architectures, or NUMA architectures. Think of like a multi-CPU socket machine. Each of those sockets is gonna have its own local DRAM.
Thách thức khác nằm ở các kiến trúc bộ nhớ không đồng nhất, hay kiến trúc NUMA. Hãy hình dung một máy có nhiều socket CPU. Mỗi socket sẽ có DRAM cục bộ riêng.
So if the latch I want to acquire is over this DRAM here, then this worker running on this CPU is basically spinning and trying to read this memory address over and over again.
Nếu latch mà tôi muốn lấy nằm trên DRAM này, thì worker đang chạy trên CPU này về cơ bản là đang quay vòng và cố đọc đi đọc lại địa chỉ bộ nhớ này.
Because this memory is on another node inside, or socket, in my CPU, I got to go over this interconnect between the different sockets, and that's much slower than reading like local DRAM or local L3 cache.
Vì bộ nhớ này nằm ở một nút khác, hay socket khác, bên trong CPU của tôi, nên tôi phải đi qua đường kết nối giữa các socket khác nhau, và việc đó chậm hơn nhiều so với đọc DRAM cục bộ hay bộ nhớ đệm L3 cục bộ.
So in a multi-CPU architecture, this is actually terrible if you just do this incessantly. Does anyone know how test-and-set works?
Vì vậy trong kiến trúc nhiều CPU, nếu cứ làm thế này liên tục thì thực sự rất tệ. Có ai biết test-and-set hoạt động thế nào không?
Okay, so test-and-set, compare-and-swap, the idea is pretty basic.
Được rồi, test-and-set, compare-and-swap, ý tưởng khá cơ bản.
It's a specialized CPU instruction, it's been around I think since the 80s, that allows you to check the value of some memory address, and if it's a value expected to be, then you're allowed to update it and change it to a new value, And you can do this atomically.
Đó là một lệnh CPU chuyên dụng, tôi nghĩ đã có từ những năm 80, cho phép bạn kiểm tra giá trị của một địa chỉ bộ nhớ nào đó, và nếu nó là giá trị mà bạn mong đợi, thì bạn được phép cập nhật và đổi nó sang giá trị mới, và bạn làm được điều này một cách nguyên tử.
So you're not worried about, like, you know, think of, like, if you had to do, like, if the value equals this, then change it, right?
Nên bạn không phải lo, ví dụ, hãy nghĩ là nếu bạn phải viết kiểu: nếu giá trị bằng cái này, thì đổi nó, đúng không?
If you just write that C code, someone could come in between the if check and then the update, and modify the thing before you get to it, right?
Nếu bạn chỉ viết đoạn mã C như vậy, thì ai đó có thể chen vào giữa phép kiểm tra if và bước cập nhật, và sửa giá trị trước khi bạn kịp làm, đúng không?
So with a compare-and-swap instruction, or test-and-set instruction, it allows you to do all of that atomically, and you know that no one's gonna squeak in and change something before you do.
Còn với lệnh compare-and-swap, hay lệnh test-and-set, bạn có thể làm tất cả những việc đó một cách nguyên tử, và bạn biết sẽ không ai chen vào thay đổi gì trước khi bạn làm xong.
So this is a really simple notation to do a compare-and-swap on a single memory address. So this is for GCC running on x86.
Đây là một cách viết rất đơn giản để thực hiện compare-and-swap trên một địa chỉ bộ nhớ duy nhất. Đây là cho GCC chạy trên x86.
Anytime you see, like, a double underscore in front of a function name in C++ or C, it's called an intrinsic.
Bất cứ khi nào bạn thấy hai dấu gạch dưới phía trước tên hàm trong C++ hoặc C, thì đó gọi là intrinsic.
Think of it like a macro for the actual assembly instructions that'll do this for you, right?
Hãy xem nó như một macro cho các lệnh assembly thực sự sẽ làm việc này cho bạn, đúng không?
So it sort of fits in, it sort of looks more natural, like C code, but underneath the cover the compiler just converts this to assembly, to do exactly the assembly that does this.
Nên nó trông tự nhiên hơn, giống mã C hơn, nhưng bên dưới thì trình biên dịch chỉ chuyển nó thành assembly, đúng đoạn assembly thực hiện việc này.
All right, so here we're gonna pass in the memory address, we'll have the compare value, then we're gonna check to see whether this current value is what we expect it to be, and if it is, we check to see whether it's 20, and since it is 20, then within, again, the same instruction, we can then change it to 30.
Được rồi, ở đây ta truyền vào địa chỉ bộ nhớ, và có giá trị so sánh, rồi ta kiểm tra xem giá trị hiện tại có đúng là giá trị ta mong đợi không, và nếu đúng, ta kiểm tra xem nó có phải 20 không, mà nó đúng là 20, thì cũng trong cùng lệnh đó, ta có thể đổi nó thành 30.
So again, this guarantees that nobody else can squeak in before we do, after we do the check that it's 20, and change to some value before we do.
Một lần nữa, điều này đảm bảo không ai khác chen vào được trước khi ta làm xong, sau khi chúng ta kiểm tra giá trị đó là 20, và đổi sang một giá trị nào đó trước khi chúng ta kịp làm.
So this is the basic primitive that all these latching schemes are gonna use, that we can then build upon and do more sophisticated things.
Vậy đây là primitive cơ bản mà tất cả các cơ chế latch này sẽ sử dụng, để từ đó chúng ta có thể xây dựng thêm và làm những việc phức tạp hơn.
All right, so we talk about the issues with the spin latch. What Linus would say for you to use is a blocking OS mutex, and this is what you get basically with std::mutex.
Được rồi, vậy chúng ta đã nói về các vấn đề của spin latch. Điều mà Linus sẽ bảo các bạn nên dùng là một blocking OS mutex, và về cơ bản đây là thứ các bạn có được khi dùng std::mutex.
And so the way this basically works is you declare a mutex, you call lock on it, do something in your critical section, and then when you're done with it, you can call unlock.
Cách nó hoạt động về cơ bản là bạn khai báo một mutex, gọi lock trên nó, làm việc gì đó trong critical section của bạn, rồi khi dùng xong, bạn có thể gọi unlock.
Right, the guards are basically doing the same thing. When they fall out of scope, then the lock gets released. So on Linux, if you call std::mutex, what do you actually get? Pthread mutex.
Đúng rồi, các guard về cơ bản cũng làm điều tương tự. Khi chúng ra khỏi phạm vi (scope), khóa sẽ được giải phóng. Vậy trên Linux, nếu bạn gọi std::mutex thì thực sự bạn nhận được gì? Pthread mutex.
Exactly right. What is a Pthread mutex? How's that actually implemented?
Chính xác. Pthread mutex là gì? Nó thực sự được cài đặt như thế nào?
You know, he says there's a fast path that's a spin lock, and then, so what is that called? Close. Futex. Fast user mutex. So he's right. So you have a...
Bạn biết đấy, anh ấy nói có một đường nhanh (fast path) là spin lock, và sau đó, vậy cái đó gọi là gì? Gần đúng. Futex. Fast user mutex. Vậy anh ấy nói đúng. Vậy bạn có một...
A futex is actually two data structures.
Một futex thực ra gồm hai cấu trúc dữ liệu.
You have a user space latch, it's just the spin latch that I showed in the last slide, where you just try to conditionally try to set something with an atomic compare and swap.
Bạn có một latch ở user space, nó chính là spin latch mà tôi đã trình bày ở slide trước, trong đó bạn chỉ thử đặt một cách có điều kiện một giá trị nào đó bằng phép compare and swap nguyên tử.
But then if you can't acquire it, then you fall back down to the OS and try to acquire a latch inside the operating system.
Nhưng nếu bạn không thể giành được nó, thì bạn lùi xuống hệ điều hành và thử giành một latch bên trong hệ điều hành.
And then if you can't acquire that latch, the OS is going to deschedule you in its own internal schedule table, and make sure that it can only notify you through a conditional variable when this thing actually becomes available.
Và nếu bạn cũng không giành được latch đó, hệ điều hành sẽ hủy lập lịch của bạn trong bảng lập lịch nội bộ của nó, và đảm bảo rằng nó chỉ thông báo cho bạn qua một biến điều kiện khi thứ này thực sự trở nên sẵn sàng.
So think of it like that. So I have my two workers, they're about to try to acquire this. The first thing they try to acquire is the user space latch.
Các bạn cứ hình dung như vậy. Giả sử tôi có hai worker, họ sắp thử giành cái này. Điều đầu tiên họ thử giành là latch ở user space.
The first guy gets it, the second guy can't get it.
Người đầu tiên giành được, người thứ hai thì không.
So then it falls down to the OS latch, and then it goes to sleep because the OS says, like, you can't run until this latch gets available.
Vậy nó lùi xuống latch của hệ điều hành, rồi đi ngủ vì hệ điều hành bảo rằng, bạn không thể chạy cho đến khi latch này sẵn sàng.
Then when it becomes available, it notifies it, and it wakes it up. So this is what Linus wants you to do.
Sau đó khi nó sẵn sàng, hệ điều hành thông báo và đánh thức nó dậy. Vậy đây là điều Linus muốn các bạn làm.
I've already said why it's a bad idea, because again, you're going down to the OS with a syscall. That sucks. There's one more reason why this sucks.
Tôi đã nói tại sao đó là ý tưởng tồi rồi, vì một lần nữa, bạn phải đi xuống hệ điều hành bằng một syscall. Điều đó tệ. Còn một lý do nữa khiến nó tệ.
How is the OS figuring out or maintaining the metadata, or keeping track of what threads it has to, should be descheduled, and what threads are waiting for this data structure?
Hệ điều hành xác định hay duy trì metadata như thế nào, hay theo dõi những thread nào nó phải hủy lập lịch, và những thread nào đang chờ cấu trúc dữ liệu này?
It has its own hash table down there. How is it protecting that? It has its own latches. Right?
Dưới đó nó có hash table riêng. Nó bảo vệ cái đó bằng cách nào? Nó có các latch riêng. Đúng không?
So in order for me to acquire this latch, I had to first try to acquire the first one. I can't get that.
Vậy để tôi giành được latch này, trước tiên tôi phải thử giành cái đầu tiên. Tôi không giành được.
Then I have to go down now into the scheduling table, acquire latches inside of that data structure, and then put myself to sleep inside that.
Rồi bây giờ tôi phải đi xuống bảng lập lịch, lấy các latch bên trong cấu trúc dữ liệu đó, rồi tự đưa mình vào trạng thái ngủ ở trong đó.
And then the OS has to then kick up, you know, the scheduling messes up, the thing's available, and then you start running.
Sau đó hệ điều hành lại phải kích hoạt, bạn biết đấy, việc lập lịch bị xáo trộn, tài nguyên đã sẵn sàng, và rồi bạn mới bắt đầu chạy.
So this is way more expensive to do because, again, we're relying on the OS mechanisms, and the OS has to protect its own data structures.
Vì vậy cách này tốn kém hơn rất nhiều, bởi vì, một lần nữa, chúng ta đang dựa vào các cơ chế của hệ điều hành, và hệ điều hành phải bảo vệ các cấu trúc dữ liệu của chính nó.
Well, we just want something more simple to protect ourselves. And the memory location for these things, with a few tags, that'll sit in user space, but the OS has its own data structures.
Trong khi đó, chúng ta chỉ muốn một thứ đơn giản hơn để tự bảo vệ mình. Còn vị trí bộ nhớ của những thứ này, cùng với vài thẻ đánh dấu, sẽ nằm trong không gian người dùng, nhưng hệ điều hành lại có các cấu trúc dữ liệu riêng.
That's somewhere else in kernel memory.
Chúng nằm ở một chỗ khác trong bộ nhớ nhân.
And now we're jumping around to different parts of memory, where if you keep everything co-located together, that's going to be much faster for our workers to rip through, for modern CPUs.
Và như vậy ta phải nhảy qua lại giữa các vùng bộ nhớ khác nhau, trong khi nếu bạn giữ mọi thứ nằm cùng một chỗ, thì các worker của chúng ta sẽ duyệt qua nhanh hơn nhiều, với các CPU hiện đại.
So a more sophisticated thing you can build on top of this, again, these two latches just have basically one mode. It's either write mode or read mode.
Vậy một thứ phức tạp hơn mà bạn có thể xây dựng trên nền tảng này, một lần nữa, hai loại latch này về cơ bản chỉ có một chế độ. Hoặc là chế độ ghi, hoặc là chế độ đọc.
If you want to be sophisticated and have what are called reader-writer latches, this allows us to have multiple concurrent readers access the critical section at the same time.
Nếu muốn tinh vi hơn và dùng cái gọi là reader-writer latch, thì nó cho phép nhiều reader đồng thời truy cập vào vùng găng cùng một lúc.
And then when a writer thread, a writer worker, shows up, it converts the latch into write mode, and that blocks everything else out. So this is what you get using standard shared mutex.
Và khi một writer thread, một writer worker, xuất hiện, nó chuyển latch sang chế độ ghi, và điều đó chặn tất cả những thứ khác. Đây là những gì bạn có được khi dùng shared mutex chuẩn.
And this is just a wrapper or an alias on Linux for pthread read-write lock, and then this is just a combination of a pthread mutex and a pthread conditional variable.
Và đây chỉ là một lớp bao hoặc bí danh trên Linux cho pthread read-write lock, còn cái này chỉ là sự kết hợp của một pthread mutex và một pthread conditional variable.
So the way it basically works is that your latch now has a mode, might be read mode or write mode, and then it has a queue for our counter, the number of threads that are accessing the critical section, holding the latch in this given mode at a given time, and then a counter for the number of threads that are waiting to acquire it.
Cách nó hoạt động về cơ bản là latch của bạn giờ có một chế độ, có thể là chế độ đọc hoặc chế độ ghi, và sau đó nó có một hàng đợi cho bộ đếm của chúng ta, số lượng thread đang truy cập vùng găng, đang giữ latch ở chế độ đó tại một thời điểm nhất định, và một bộ đếm cho số thread đang chờ để lấy nó.
So if the first worker shows up, wants to do a read on the data structure of the critical section, acquires the latch in read mode, we just update the counter by one, and then the thread can do whatever it wants.
Nếu worker đầu tiên xuất hiện, muốn đọc cấu trúc dữ liệu của vùng găng, lấy latch ở chế độ đọc, ta chỉ cần tăng bộ đếm lên một, và thread đó có thể làm bất cứ điều gì nó muốn.
Another thread comes along, tries to acquire the latch in read mode. We're already in read mode, so we can allow this, give it the latch, set the counter to two.
Một thread khác đến, cố lấy latch ở chế độ đọc. Ta đang ở chế độ đọc rồi, nên có thể cho phép, đưa latch cho nó, đặt bộ đếm là hai.
So then now, if this worker shows up, wants to acquire the latch in write mode, it would look in the counter and see that the read counter is set to two, or greater than zero.
Bây giờ, nếu worker này xuất hiện, muốn lấy latch ở chế độ ghi, nó sẽ nhìn vào bộ đếm và thấy bộ đếm đọc đang là hai, tức là lớn hơn không.
So it can't acquire the latch in write mode, because we don't want to go inside the critical section and start mucking around and changing bits of bytes to pointers or whatever, because these guys are reading it and are not expecting it to change underneath them.
Vì vậy nó không thể lấy latch ở chế độ ghi, vì ta không muốn đi vào vùng găng rồi bắt đầu táy máy và thay đổi các bit, byte, con trỏ hay gì đó, vì những thread này đang đọc nó và không mong đợi nó thay đổi ngay bên dưới mình.
So this thread has to pause and wait, and then for fairness, when the next thread comes along that wants to acquire the latch in read mode, since we know that this guy is waiting for it, we don't want to starve him out.
Vậy thread này phải tạm dừng và chờ, và để đảm bảo công bằng, khi luồng tiếp theo đến và muốn lấy latch ở chế độ đọc, vì ta biết luồng kia đang chờ nó, ta không muốn để nó bị bỏ đói.
So therefore, we're going to let that thread now go to sleep and wait to acquire the latch, either spin or sleep in the OS.
Do đó, ta sẽ cho luồng đó đi ngủ và chờ để lấy latch, hoặc là quay vòng (spin) hoặc là ngủ trong hệ điều hành.
And then at some point, when the two readers are done, the latch will switch to write mode, and then the next thread can start running.
Và rồi đến một lúc nào đó, khi hai luồng đọc đã xong, latch sẽ chuyển sang chế độ ghi, và luồng tiếp theo có thể bắt đầu chạy.
So this is a bit more sophisticated, because now we have to maintain these data structures and these counters. So I'm saying, now we're sort of making this latch larger and larger.
Cách này phức tạp hơn một chút, vì giờ ta phải duy trì các cấu trúc dữ liệu và các bộ đếm này. Tức là bây giờ ta đang làm cho latch này ngày càng lớn hơn.
Still, it's not too bad for this, if we rely on the OS mechanisms for some things.
Dù vậy, vẫn không tệ lắm, nếu ta dựa vào các cơ chế của hệ điều hành cho một số việc.
But this can be actually, you know, if we have to store this now for every single record, in every single tuple, then this can start to add up and be kind of expensive.
Nhưng thực ra điều này có thể, nếu ta phải lưu cái này cho từng bản ghi một, trong từng tuple một, thì nó có thể cộng dồn lại và khá tốn kém.
Yes?
Vâng, bạn hỏi?
The question is, why does the OS not want to use spin locks in user space?
Câu hỏi là: tại sao hệ điều hành không muốn dùng spin lock trong không gian người dùng?
Because from his perspective, he's at the operating system, they're seeing a bunch of threads and they want to try to maximize the amount of useful work being done.
Vì từ góc nhìn của hệ điều hành, họ thấy một loạt luồng và họ muốn tối đa hóa lượng công việc hữu ích được thực hiện.
But if my thread is spinning on the spin lock, or spin latch, trying to acquire it, I'm not really doing any useful work.
Nhưng nếu luồng của tôi đang quay vòng trên spin lock, hay spin latch, để cố lấy nó, thì tôi không thực sự làm việc hữu ích nào.
I'm just trying to get, and get, and get, over and over again, I can't get it.
Tôi chỉ cứ cố lấy, lấy, lấy, lặp đi lặp lại mà không lấy được.
So from the OS perspective, the thread looks like it's doing something, it's executing instructions, but it's not actually doing any useful work.
Vậy nên theo góc nhìn của hệ điều hành, luồng trông như đang làm gì đó, nó đang thực thi lệnh, nhưng thực ra không làm công việc hữu ích nào.
So in the OS world, they would say, well, you can't do anything now, so let me actually deschedule you, and then some other thread can do something. Because that's their perspective.
Trong thế giới hệ điều hành, họ sẽ nói: bây giờ bạn không làm được gì cả, nên để tôi hủy lập lịch bạn, và để luồng khác làm việc. Vì đó là góc nhìn của họ.
And all I'm saying is, if I go back to, all I'm saying is, the data-driven people, we can be smarter about this middle part here. I can't acquire the latch, do something.
Còn điều tôi muốn nói là, nếu quay lại, điều tôi muốn nói là, với những người làm hệ thống dữ liệu, ta có thể thông minh hơn ở phần giữa này. Tôi không lấy được latch thì làm việc khác.
And we're not talking about coroutines, we're not talking about different architectures, but you can imagine in some systems where I try to acquire the latch, I can't get it, but I'm using non-preemptive scheduling, where I say, all right, I can't get this latch, let me go yield, The coroutine goes back,
Và ta không nói về coroutine, cũng không nói về các kiến trúc khác nhau, nhưng bạn có thể hình dung trong một số hệ thống nơi tôi cố lấy latch, không được, nhưng tôi dùng lập lịch không ưu tiên (non-preemptive), tức là tôi nói: được rồi, tôi không lấy được latch này, để tôi nhường (yield). Coroutine quay lại,
and the thread can then be handed off to some other coroutine to process work, right?
và luồng có thể được giao cho coroutine khác để xử lý công việc, đúng không?
I can't do that if I'm using the OS mutex, because as soon as I try to acquire the latch and I don't get it, I'm gonna fall down to the kernel and my thread gets scheduled, or descheduled.
Tôi không làm được vậy nếu dùng mutex của hệ điều hành, vì ngay khi tôi cố lấy latch mà không được, tôi sẽ rơi xuống kernel và luồng của tôi bị lập lịch, hay bị hủy lập lịch.
Whereas if I implement my data system correctly, then I could say, I can't get it, and I know that the thing I'm trying to get may take a long time, so you can't always know that.
Trong khi nếu tôi cài đặt hệ thống dữ liệu đúng cách, thì tôi có thể nói: tôi không lấy được, và tôi biết thứ tôi cố lấy có thể mất nhiều thời gian, dù không phải lúc nào cũng biết được điều đó.
But you can say, all right, let me go back and let my thread be used for something else.
Nhưng bạn có thể nói: được rồi, để tôi quay lại và để luồng của tôi được dùng cho việc khác.
Other questions? This question, what's a good option?
Còn câu hỏi nào khác không? Câu hỏi này, lựa chọn nào là tốt?
So again, I don't want to go too much deep in the details, but the, this thing from the parking lot stuff. I might have a slide on it.
Một lần nữa, tôi không muốn đi quá sâu vào chi tiết, nhưng cái này là từ phần parking lot. Có thể tôi có một slide về nó.
Yeah, I don't have slides here in this class. MCS is probably a little bit better.
À, trong lớp này tôi không có slide ở đây. MCS có lẽ tốt hơn một chút.
Basically, this thing maintains a linked list, and you can keep track of like, like, you're not, everyone's not waiting for the same lock. You can kind of put yourself in a queue.
Về cơ bản, nó duy trì một danh sách liên kết, và bạn có thể theo dõi, kiểu như, không phải tất cả mọi người đều chờ cùng một khóa. Bạn có thể tự xếp mình vào một hàng đợi.
This is actually what Linux uses on the inside, but you can then do something better in user space.
Thực ra đây là thứ Linux dùng bên trong, nhưng sau đó bạn có thể làm tốt hơn ở user space.
The parking lot one from Apple, they maintain their own, like, worker pools to keep track of like, this worker can't do anything, but, so in some cases, the thing it's waiting for, I know it's not gonna be available for a long time, so let me actually go yield it back to the OS.
Còn parking lot của Apple thì họ tự duy trì các worker pool để theo dõi xem worker này không làm được gì, nhưng, nên trong một số trường hợp, thứ mà nó đang chờ, tôi biết là sẽ lâu lắm mới có sẵn, vậy nên hãy trả quyền chạy lại cho hệ điều hành.
But other ones might be like a hot pool, like I think I need, I think I'm gonna get it back right away, so don't go to sleep.
Nhưng những trường hợp khác có thể giống như một hot pool, kiểu tôi nghĩ là tôi cần, tôi nghĩ là tôi sẽ lấy lại được ngay, nên đừng đi ngủ.
There's a bit more logic in there that they're doing.
Họ có thêm một chút logic trong đó.
The MCS one is another implementation to minimize the, Yeah, this is what the spin lock is from the parking lot one, but I don't want to, I don't, other than the description here, I don't have other slides on it that show demonstrations of it.
MCS là một cách triển khai khác để giảm thiểu, Vâng, đây là spin lock của parking lot, nhưng tôi không muốn, ngoài phần mô tả ở đây ra, tôi không có slide nào khác minh họa về nó.
Okay, all right, so we now basically, we know how to do basic latching.
Được rồi, vậy giờ về cơ bản chúng ta đã biết cách làm latching cơ bản.
Again, the exact implementation for what we'll talk about going forward doesn't matter, whether we yield it to the OS or not.
Một lần nữa, cách triển khai cụ thể cho những gì chúng ta sẽ nói tiếp theo không quan trọng, dù có trả quyền chạy cho hệ điều hành hay không.
Again, it's still about the, we're trying to maintain the physical correctness of the data structure.
Một lần nữa, vẫn là về việc chúng ta cố gắng duy trì tính đúng đắn vật lý của cấu trúc dữ liệu.
So the first one we'll talk about is hash table latching, because this one is, again, it's much more simple than the B+trees, because all the threads are gonna be going in the same direction, right?
Vậy cái đầu tiên chúng ta sẽ nói là hash table latching, vì cái này đơn giản hơn nhiều so với B+tree, vì tất cả các luồng đều đi cùng một hướng, đúng không?
Think of it like when I was doing linear probe hashing: I hash my key, I land somewhere on the hash table, and I always scan going down to try to find the key that I want, and therefore I can't have deadlocks, because I don't, I'm not worried about somebody else coming from the bottom going up, and I need their latch and they need my latch and get blocked.
Hãy nghĩ như khi tôi làm linear probe hashing: tôi băm khóa của mình, rơi vào một vị trí nào đó trên bảng băm, và tôi luôn quét xuống dưới để tìm khóa mình muốn, nên không thể có bế tắc, vì tôi không, tôi không lo có ai đó đi từ dưới lên, rồi tôi cần latch của họ và họ cần latch của tôi và cả hai bị chặn.
So in this case here, this is gonna be a lot easier to do, because we're always going in the same direction.
Vậy trong trường hợp này sẽ dễ làm hơn nhiều, vì chúng ta luôn đi cùng một hướng.
Now, if you have to resize the hash table, that's a bit more tricky, and so the simplest way to do this, you just maintain a latch for the entire data structure, and so anytime you do a read, anytime you want to do a read or write into it, it requires a latch for this, and then if you want to swap out the hash table by resizing it,
Còn nếu bạn phải thay đổi kích thước bảng băm thì phức tạp hơn một chút, và cách đơn giản nhất để làm việc này là bạn chỉ cần duy trì một latch cho toàn bộ cấu trúc dữ liệu, và vì vậy bất cứ khi nào bạn đọc, bất cứ khi nào bạn muốn đọc hoặc ghi vào nó, bạn cần một latch cho việc này, rồi nếu bạn muốn thay thế bảng băm bằng cách thay đổi kích thước,
just take a write latch on the entire thing, and that prevents anybody from coming along and reading it. Again, we can ignore that. But there's basically three approaches.
chỉ cần lấy một write latch trên toàn bộ nó, và điều đó ngăn bất kỳ ai xen vào đọc nó. Một lần nữa, chúng ta có thể bỏ qua điều đó. Nhưng về cơ bản có ba cách tiếp cận.
The first one is, as I already said, I can use a global latch that protects the entire data structure.
Cách đầu tiên, như tôi đã nói, là dùng một global latch bảo vệ toàn bộ cấu trúc dữ liệu.
The problem with this, again, it's simple to implement, but now it's basically making my data structure single-threaded, all right?
Vấn đề của cách này là, nó dễ cài đặt, nhưng lúc này nó biến cấu trúc dữ liệu của tôi thành đơn luồng, đúng không?
The next could be, I have the scope of the latch protect the page or block within my hash table.
Cách tiếp theo có thể là, phạm vi của latch bảo vệ một trang hoặc một khối trong hash table của tôi.
And that means anytime before I go look inside a page, I acquire the latch for it in whatever mode that I want.
Nghĩa là bất cứ khi nào trước khi tôi nhìn vào bên trong một trang, tôi lấy latch của nó ở chế độ nào mà tôi muốn.
And then before I go down, if I can't find anything I want, a free slot to put some data in, before I go to the next page, I release that latch on my page that I'm at right now, and then try to acquire it on the next one.
Và rồi trước khi đi tiếp, nếu tôi không tìm thấy thứ mình cần, chẳng hạn một slot trống để đặt dữ liệu vào, trước khi sang trang tiếp theo, tôi nhả latch trên trang hiện tại, rồi cố lấy latch của trang kế tiếp.
And then the alternative is to have more fine-grained latches, where every single slot in a page will have its own latch. Again, this thing is something I'm embedding inside of the header, right?
Và cách còn lại là dùng các latch mịn hơn, trong đó mỗi slot trong một trang có latch riêng của nó. Một lần nữa, thứ này tôi nhúng vào bên trong phần header, đúng không?
And so the advantage of this is that, since they're more fine-grained, I could have, in theory, two different threads touching different parts of the same page, and that's okay because the latches are, you know, at a slot level.
Và ưu điểm của cách này là, vì chúng mịn hơn, nên tôi có thể có, về lý thuyết, hai luồng khác nhau cùng truy cập các phần khác nhau của cùng một trang, và điều đó ổn vì các latch nằm ở mức slot.
Whereas if I have a page latch, then only one thread can make a modification to a page at a time.
Trong khi nếu tôi có latch trang, thì mỗi lúc chỉ một luồng được sửa đổi một trang.
So let's look at a real simple example here. We have our hash table. All right, first we'll do the page-based locks, or block-based locks, or latches. So I'm gonna find D.
Hãy xem một ví dụ thật đơn giản. Chúng ta có hash table. Trước hết ta làm với khóa theo trang, hay theo khối, tức là latch. Giả sử tôi sẽ tìm D.
So again, ignoring whatever sort of global latch I have to protect things or resizing, assuming that's already taken care of, I'm gonna land in this page here.
Một lần nữa, bỏ qua global latch nào đó mà tôi có để bảo vệ hay để thay đổi kích thước, giả sử việc đó đã được xử lý, tôi sẽ đến trang này.
So before I can start reading the contents, after I hash it and figure out what page I need to read, I have to put this latch in read mode.
Vậy trước khi bắt đầu đọc nội dung, sau khi băm và xác định trang cần đọc, tôi phải đặt latch này ở chế độ đọc.
Since there's no other threads right now, I can go ahead and do that.
Vì hiện không có luồng nào khác, tôi có thể làm ngay.
Now my thread can jump inside the page and actually start reading the contents of the slots to figure out whether the key D is there.
Bây giờ luồng của tôi có thể vào trong trang và bắt đầu đọc nội dung của các slot để xác định khóa D có ở đó không.
But then at the same time, T2 comes along, another thread, and it wants to find E, or sorry, insert E, and say it's gonna hash to this location here.
Nhưng đồng thời, T2, một luồng khác, xuất hiện và muốn tìm E, à xin lỗi, chèn E, và giả sử nó băm vào vị trí này đây.
So it wants to put the latch, the page latch, into write mode, but it can't because the first thread holds it in read mode, so it has to stall and has to wait.
Nên nó muốn đặt latch, latch của trang, ở chế độ ghi, nhưng không được vì luồng đầu tiên đang giữ nó ở chế độ đọc, nên nó phải dừng lại và chờ.
T1 then can resume, so it keeps scanning along, and then when it jumps to this next page here, since we know that the data structure can't be resized, or linear probing, not doing extendible hashing or linear hashing, then I can go ahead and actually release the latch on the page one, in the middle here, before I get the latch on page two.
Sau đó T1 có thể tiếp tục, nên nó quét tiếp, và khi nó nhảy sang trang kế tiếp này, vì ta biết cấu trúc dữ liệu không thể bị thay đổi kích thước, hay dùng linear probing, không phải extendible hashing hay linear hashing, thì tôi có thể nhả latch trên trang một, ở giữa đây, trước khi lấy latch của trang hai.
Right? Because again, I know the sequence of the pages I need to access, that isn't gonna get moved around because I'm not gonna reorder that.
Đúng không? Vì một lần nữa, tôi biết thứ tự các trang cần truy cập, nó sẽ không bị dời chỗ vì tôi không sắp xếp lại.
So then now I get the read latch on page two, the other thread can then wake up and now get the write latch on page one, look, scan all the slots, see that it can't insert E either way at once, so it has to go down here, and then the same thing, since the first thread holds the read latch on the page, this guy has to wait, the second one has to wait,
Vậy bây giờ tôi lấy read latch trên trang hai, luồng kia sau đó có thể thức dậy và lấy write latch trên trang một, nhìn, quét tất cả các slot, thấy rằng nó cũng không thể chèn E ngay được, nên nó phải đi xuống đây, và tương tự, vì luồng đầu tiên đang giữ read latch trên trang, luồng này phải chờ, luồng thứ hai phải chờ,
then when T1 is done, releases the read latch, T2 can then acquire the write latch, and then go ahead and make its change there.
rồi khi T1 xong, nhả read latch, T2 mới có thể lấy write latch, và tiến hành thực hiện thay đổi ở đó.
Alright, so this is page-based locking, see how, like, even though one was trying to do a read, one was trying to do a write, and they're looking at different things, I had to, you know, the second thread had to wait until the first thread finished reading or accessing whatever it was accessing.
Được rồi, đây là khóa theo trang, hãy xem này, dù một luồng đang cố đọc, một luồng đang cố ghi, và chúng nhìn vào những thứ khác nhau, tôi vẫn phải, luồng thứ hai vẫn phải đợi cho đến khi luồng đầu tiên đọc xong hoặc truy cập xong thứ nó đang truy cập.
If I have a slot per latch, then if I try to do that same operation I had before, When T1 hashes into the hash table, lands on the first slot here, it takes the read latch on it, goes, inspects the contents.
Nếu mỗi slot có một latch, thì khi tôi thử thực hiện cùng thao tác như trước, T1 băm vào bảng băm, rơi vào slot đầu tiên ở đây, nó lấy read latch trên slot đó, rồi kiểm tra nội dung.
T2 comes along, it hashes into the same thing, and now it's gonna take the write latch on this, because you don't know whether it's empty until you actually read it, so you take the write latch.
T2 đến, nó băm vào cùng vị trí đó, và giờ nó sẽ lấy write latch trên slot này, vì bạn không biết nó có trống hay không cho đến khi thực sự đọc nó, nên bạn lấy write latch.
Then now when T1 scans along, because it's trying to find D, it tries to get to the next slot, but the second thread holds the write latch on that, so it has to wait until that latch is released, so it stalls.
Rồi khi T1 quét tiếp, vì nó đang cố tìm D, nó cố sang slot kế tiếp, nhưng luồng thứ hai đang giữ write latch trên slot đó, nên nó phải đợi đến khi latch được nhả, vì vậy nó bị treo.
T2 comes along, scans along, takes the write latch on the next page.
T2 đến, quét tiếp, lấy write latch trên slot kế tiếp.
Then at this point here, T1 can take the read latch on that slot, doesn't find what it wants, scans along, has to wait for this guy to finish.
Đến lúc này, T1 có thể lấy read latch trên slot đó, không thấy thứ nó muốn, quét tiếp, và phải đợi luồng này xong.
This guy comes down here, says this slot is empty, let me go ahead and insert E, and then at the same time D could then do a read on the slot to find the thing that it wants.
Luồng này xuống đây, thấy slot này trống, nên chèn E vào, và đồng thời D có thể đọc slot đó để tìm thứ nó muốn.
Good question. What, sorry?
Câu hỏi hay. Sao cơ, xin lỗi?
Statement is, in this case here, wouldn't you have to take a latch on the page itself, assuming it's backed by disk, because you want to mark the dirty bit true?
Ý bạn là, trong trường hợp này, chẳng phải bạn phải lấy latch trên chính trang đó sao, giả sử nó được lưu trên đĩa, vì bạn muốn đặt dirty bit thành true?
Yeah, so, and for this one I'm assuming it's in memory, but yes, if it was a, no, because if I'm not writing to disk, I don't care if it's dirty.
Vâng, ở ví dụ này tôi giả sử nó nằm trong bộ nhớ, nhưng đúng, nếu là, không, vì nếu tôi không ghi xuống đĩa thì tôi không quan tâm nó có dirty hay không.
If it's not backed by the buffer pool manager, I don't, there's no concept of a dirty page, it's just memory, right?
Nếu nó không do buffer pool manager quản lý, thì không có khái niệm trang dirty, nó chỉ là bộ nhớ, đúng không?
But in the thing you're proposing, yes, you'd have to, but that one, you could do the update on the dirty bit, on the dirty flag, after the changes you made.
Nhưng với cách bạn đề xuất, đúng, bạn sẽ phải làm vậy, nhưng trường hợp đó, bạn có thể cập nhật dirty bit, tức cờ dirty, sau khi thực hiện các thay đổi.
You still want to pin it so it doesn't get swapped out, Right, but you don't have to take the latch on the whole page if you have different parts reading it, because then you just go flip the bit, because the, the first thread here, it doesn't care whether the page is marked dirty.
Bạn vẫn muốn pin nó để nó không bị đẩy ra ngoài, đúng không, nhưng bạn không phải lấy latch trên toàn bộ trang nếu có các phần khác nhau đang đọc nó, vì khi đó bạn chỉ việc đi lật bit, bởi vì luồng đầu tiên ở đây, nó không quan tâm trang có được đánh dấu dirty hay không.
I care that it stays in memory, so it's pinned, that's fine.
Tôi quan tâm là nó phải ở lại trong bộ nhớ, nên nó được pin, vậy là ổn.
But then setting that flag, since I'm not, the only, the buffer manager is the only one reading it, the different threads accessing it don't need to do that atomically.
Còn việc đặt cờ đó, vì tôi không, chỉ có buffer manager đọc nó, nên các luồng khác nhau truy cập nó không cần làm điều đó một cách nguyên tử.
Yes.
Vâng.
The question is, how much performance benefit do you get from having slot latches versus page latches? I mean, it's the classic storage versus compute, right?
Câu hỏi là: việc dùng slot latch so với page latch mang lại lợi ích hiệu năng bao nhiêu? Ý tôi là, đây là bài toán kinh điển giữa lưu trữ và tính toán, đúng không?
If my key value pairs are not that big, then I'm gonna have a lot of key values within a page, but every one now is gonna have its own memory location to keep track of the latches, right, and so I'm gonna maximize concurrency.
Nếu các cặp khóa-giá trị của tôi không lớn lắm, thì tôi sẽ có rất nhiều khóa-giá trị trong một trang, nhưng giờ mỗi cặp sẽ có vị trí bộ nhớ riêng để theo dõi các latch, đúng không, và như vậy tôi sẽ tối đa hóa tính đồng thời.
And again, it's a cop-out, it depends on the workload, depends on how fast you're, you know, how many cores you have, what they're actually trying to do, right?
Và một lần nữa, câu trả lời này hơi né tránh, nó phụ thuộc vào workload, phụ thuộc vào việc bạn, bạn biết đấy, có bao nhiêu lõi, chúng thực sự đang cố làm gì, đúng không?
So it could be a huge benefit, it could be a small benefit, depends on what the workload actually is.
Nên lợi ích có thể rất lớn, cũng có thể nhỏ, tùy vào workload thực sự là gì.
But the question, the statement is, it depends on how large each entry is, how large each slot is, relative to the size of the latch.
Nhưng câu hỏi, nhận định ở đây là, nó phụ thuộc vào mỗi mục lớn cỡ nào, mỗi slot lớn cỡ nào, so với kích thước của latch.
Same thing, right?
Cùng một ý, đúng không?
So if the key values are really small, your latches are always gonna be fixed size, so if the key value is really small, then the size of the key value could be the same as the latch, so you're basically storing double the space to store this latch information.
Nếu các khóa-giá trị rất nhỏ, thì latch luôn có kích thước cố định, nên nếu khóa-giá trị rất nhỏ, thì kích thước của khóa-giá trị có thể bằng kích thước latch, nghĩa là về cơ bản bạn tốn gấp đôi dung lượng để lưu thông tin latch này.
So is that a good trade-off? I mean, again, it depends.
Vậy đó có phải là một sự đánh đổi tốt không? Một lần nữa, còn tùy.
There isn't, there's, so I'm not trying to like, I'm not trying to be evasive, but there isn't a number I can give you and say, oh, it's always gonna be 10x, it depends.
Tôi không cố tình né tránh đâu, nhưng tôi không thể đưa ra một con số rồi nói: ồ, lúc nào cũng nhanh gấp 10 lần; còn tùy.
Alright, latching for hash tables should be straightforward. The good stuff comes along when we start doing latching for B+trees, right?
Được rồi, việc latching cho bảng băm khá đơn giản. Phần hay ho bắt đầu khi ta làm latching cho B+tree, đúng không?
Again, so the idea is the same: we want to have multiple threads, we want to read and write to our B+tree at the same time, and we have to protect against the problem where we have two workers trying to modify the node at the same time.
Một lần nữa, ý tưởng vẫn vậy: ta muốn nhiều luồng đọc và ghi vào B+tree cùng lúc, và ta phải ngăn chặn vấn đề khi có hai worker cố sửa đổi cùng một nút tại cùng một thời điểm.
And then we have the other problem, which is we have nodes, or workers, traversing our data structure at the same time we're doing splits and merges, because then now we could have pointers going to nowhere, and we could get a segfault, right?
Rồi còn một vấn đề khác, là có các nút, hay các worker, đang duyệt cấu trúc dữ liệu trong lúc ta đang thực hiện tách và gộp nút, vì khi đó có thể có con trỏ trỏ tới chỗ không tồn tại, và ta có thể bị segfault, đúng không?
The statement is, the question is, when I'm talking about B+tree and hash table latching, is it using one of the latching implementations I showed before? Yes, but it doesn't matter.
Nhận định, câu hỏi ở đây là, khi tôi nói về latching cho B+tree và bảng băm, thì có dùng một trong các cách cài đặt latch tôi đã trình bày trước đó không? Có, nhưng không quan trọng.
For, like, we just have this notion of a protection mechanism that we can protect the critical section with, so whether it's spin latches, OS mutexes, parking lot thing, doesn't matter.
Ta chỉ có khái niệm về một cơ chế bảo vệ để bảo vệ vùng găng, nên dù là spin latch, OS mutex hay parking lot thì cũng không quan trọng.
Alright, so here's what we're trying to avoid. So we say we have our B+tree here, and we have this key 44 we want to do a delete on.
Được rồi, đây là điều ta đang cố tránh. Giả sử ta có B+tree ở đây, và ta muốn xóa khóa 44.
So when the thread starts, you know, it does the scan, looks at the guide post, figures out where to go, traverses down to the bottom, gets to this leaf node, and voila, there's key 44 that it wants to go ahead and delete.
Khi luồng bắt đầu, nó quét, nhìn các guide post, xác định cần đi đâu, duyệt xuống tận đáy, đến nút lá này, và kìa, có khóa 44 mà nó muốn xóa.
So it goes ahead and deletes that, but now we have the problem where the node is less than half full, so we've got to rebalance, which means we have to do a merge.
Vậy là nó tiến hành xóa khóa đó, nhưng bây giờ ta gặp vấn đề là nút này đầy chưa đến một nửa, nên ta phải cân bằng lại, nghĩa là phải thực hiện một phép gộp.
But then say, and say for this key here, we want to move 41 over, that'll keep us balanced.
Nhưng giả sử rằng, và giả sử với khóa này, ta muốn chuyển 41 sang, như vậy sẽ giữ được sự cân bằng.
And then say for whatever reason the thread gets, this worker gets descheduled by the OS, there's a pause, something, right? Doesn't matter.
Rồi giả sử vì lý do nào đó thread này bị worker này bị hệ điều hành hủy lập lịch, nó bị tạm dừng, hay chuyện gì đó, đúng không? Không quan trọng.
And then while it's paused, asleep, The other thread comes along and now wants to find 41, does the same thing, scans along, finds the guide post, comes along down here to D, looks at the keys inside there, figures out it needs to follow this pointer to get to this node here.
Và trong lúc nó đang tạm dừng, đang ngủ, thì thread kia xuất hiện và bây giờ muốn tìm 41, nó làm tương tự, quét dọc theo, tìm thấy guide post, đi xuống đây tới D, xem các khóa bên trong đó, và xác định rằng nó cần đi theo con trỏ này để đến nút này ở đây.
But then say now, for whatever reason, the OS deschedules this thread and it goes to sleep.
Nhưng rồi giả sử lúc này, vì lý do nào đó, hệ điều hành hủy lập lịch thread này và nó đi ngủ.
The first guy wakes up, then moves the, does the rebalancing, moves key 41 from H to I, then it's done.
Thread đầu tiên thức dậy, rồi thực hiện việc cân bằng lại, chuyển khóa 41 từ H sang I, xong việc.
The second thread then comes back awake, follows that pointer that I thought was correct before, gets down here, and now it sees that the key that I thought was gonna be there is no longer there.
Sau đó thread thứ hai thức dậy trở lại, đi theo con trỏ mà trước đó nó cho là đúng, xuống tới đây, và bây giờ nó thấy rằng khóa mà nó nghĩ sẽ nằm ở đó thì không còn ở đó nữa.
So this, this is what we're trying to avoid, right? This is a best-case scenario, because this will give us a false negative.
Vậy đây chính là điều ta đang cố tránh, đúng không? Đây còn là trường hợp tốt nhất, vì nó chỉ cho ta một kết quả âm tính giả.
It's better than following a pointer that takes it to a bad memory location, we get a segfault, right?
Vẫn còn hơn là đi theo một con trỏ dẫn tới một vị trí bộ nhớ sai, và ta bị segfault, đúng không?
But still, this is still bad, because if it's your bank account, we can't find it, or you're losing money, you would get pissed.
Nhưng như vậy vẫn là tệ, vì nếu đó là tài khoản ngân hàng của bạn mà không tìm thấy, hoặc bạn bị mất tiền, bạn sẽ rất bực.
So the way we're gonna, to, to avoid this problem is through a technique called latch coupling, or sometimes it's called latch crabbing.
Vậy cách mà ta sẽ tránh vấn đề này là dùng một kỹ thuật gọi là latch coupling, hay đôi khi còn gọi là latch crabbing.
I think the textbook calls it latch coupling, Wikipedia calls it latch coupling, but sometimes you'll see older references called latch crabbing.
Tôi nghĩ giáo trình gọi là latch coupling, Wikipedia cũng gọi là latch coupling, nhưng đôi khi bạn sẽ thấy các tài liệu cũ hơn gọi là latch crabbing.
And this is the protocol we're gonna use in our B+tree implementation that's gonna allow multiple threads to access, safely access the data structure at the same time.
Và đây là giao thức ta sẽ dùng trong phần cài đặt B+tree của mình, cho phép nhiều thread truy cập, truy cập an toàn vào cấu trúc dữ liệu cùng một lúc.
The basic idea is that as we do our traversals, for either a modification, modifying or read operation, a write, read or write, we're always gonna acquire a latch for some parent, or the root node that we start out with, then acquire the latch for the child that we need to go, we need to go down to next.
Ý tưởng cơ bản là khi ta thực hiện duyệt cây, dù cho thao tác sửa đổi hay đọc, ghi, đọc hoặc ghi, ta luôn lấy latch của một nút cha nào đó, hoặc nút gốc mà ta bắt đầu, rồi lấy latch của nút con mà ta cần đi xuống tiếp theo.
And then if the, if we know that based on whatever operation that we're trying to do, That the, the child is not gonna have to do a split or a merge, then the parent is deemed as safe, and we can go ahead and release the latch for anything we hold up above in the tree.
Và sau đó nếu ta biết rằng dựa trên thao tác mà ta đang thực hiện, nút con sẽ không phải tách hay gộp, thì nút cha được coi là an toàn, và ta có thể thả latch của mọi nút ta đang giữ ở phía trên cây.
And the reason it's called latch crabbing is just, it's like the way that a crab would walk, right? It moves one leg after another, right?
Còn lý do nó được gọi là latch crabbing chỉ là vì nó giống cách một con cua bò, đúng không? Nó di chuyển hết chân này đến chân khác, đúng không?
So again, we're gonna define a safe node is that we know that, based on what operation we're trying to do, that if we want to do an insert, that we know it's not full, therefore we're not gonna have to do a split if, you know, if we have to handle keys coming up.
Vậy nên một lần nữa, ta sẽ định nghĩa nút an toàn là nút mà ta biết rằng, dựa trên thao tác mà ta đang cố thực hiện, rằng nếu muốn thực hiện thao tác chèn, thì ta biết nó chưa đầy, do đó ta sẽ không phải thực hiện tách nút nếu ta phải xử lý các khóa được đẩy lên từ bên dưới.
And then if we're doing a delete, then we know it's at least more than half full, so we're not gonna have to do a merge if we had to start deleting things below us.
Còn nếu đang thực hiện xóa, thì ta biết nó đầy hơn một nửa, nên ta sẽ không phải gộp nút nếu phải xóa các phần tử bên dưới.
So the basic protocol is, again, for a search, or lookup, or get, which is: acquire read latches all the way down, and once we reach the child node, it's, you know, in taking that latch in read mode, we can then release its parent in read mode.
Vậy giao thức cơ bản là, một lần nữa, với thao tác search, lookup hay get, tức là: lấy read latch từ trên xuống dưới, và khi đã tới nút con, tức là khi đã giữ latch của nó ở chế độ đọc, thì ta có thể nhả latch của nút cha ở chế độ đọc.
Do that till we reach the leaf node, read whatever we want, and then we're done. For inserts and deletes, we start with taking write latches on the way down.
Cứ làm vậy cho tới khi tới nút lá, đọc những gì ta muốn, rồi xong. Với chèn và xóa, ta bắt đầu bằng việc lấy write latch trên đường đi xuống.
Again, as we go down from a parent to a child, we check whether the child will have to split or merge based on whatever the operation is that we're gonna do, or that it could have to do this, because we may not know what comes below us in the tree.
Một lần nữa, khi đi từ nút cha xuống nút con, ta kiểm tra xem nút con có phải tách hoặc gộp hay không, tùy theo thao tác ta sắp thực hiện, hoặc liệu nó có thể phải làm vậy hay không, vì ta có thể không biết bên dưới trong cây có gì.
And if we know it's safe, we can go ahead and release the latch for our parent, and actually any other latches we hold going back up to the root, right?
Và nếu biết nó an toàn, ta có thể nhả latch của nút cha, và thực ra là mọi latch khác ta đang giữ ngược lên tới nút gốc, đúng không?
And then once we reach the leaf node, we do whatever it is that we need to do.
Rồi khi tới nút lá, ta làm bất cứ việc gì cần làm.
So the idea is that we don't release our latches as soon as possible, because we want to let other threads or other workers run in our system. Yes.
Vậy ý tưởng là ta nhả latch càng sớm càng tốt, vì ta muốn để các luồng hay worker khác chạy trong hệ thống. Vâng, mời bạn.
His statement is, I keep saying we want to put things in write mode if we're doing updates, don't we need to do everything in read mode and then upgrade?
Ý của bạn ấy là, em cứ nói là ta muốn đặt ở chế độ ghi nếu đang cập nhật, vậy chẳng phải ta nên làm mọi thứ ở chế độ đọc rồi nâng cấp sao?
Few more slides. Yes. This is the basic protocol.
Còn vài slide nữa. Vâng. Đây là giao thức cơ bản.
All right, so let's see.
Được rồi, ta xem thử.
If I want to do a find on key 38, and so I started here, they're always gonna start at the root node, I put this in read mode, I come down to B, acquire B in read mode, right?
Nếu tôi muốn tìm khóa 38, thì tôi bắt đầu ở đây, luôn luôn bắt đầu từ nút gốc, tôi đặt nó ở chế độ đọc, đi xuống B, lấy B ở chế độ đọc, đúng không?
Because again, going back here, like, I know that these pointers are all gonna be correct at this point, because I have it in read mode, so I know nobody else is gonna swap them out and change it to something else, because you can't do that in read mode.
Vì một lần nữa, quay lại đây, tôi biết các con trỏ này đều đúng tại thời điểm này, vì tôi đang giữ nó ở chế độ đọc, nên tôi biết không ai khác có thể thay chúng và đổi thành thứ khác, vì không thể làm vậy ở chế độ đọc.
So it's safe for me to follow this pointer.
Nên tôi có thể an toàn đi theo con trỏ này.
I then land down here, put this page, or this node, in read mode, and at this point, I know it's safe to release A, the latch on A, because I'm at B, and I hold B's latch.
Rồi tôi xuống đây, đặt trang này, hay nút này, ở chế độ đọc, và lúc này tôi biết có thể an toàn nhả A, tức latch trên A, vì tôi đang ở B và giữ latch của B.
So I can go ahead and do that. Do the same thing.
Vậy tôi cứ nhả. Làm tương tự.
Scan down to D, put that in read mode, release the latch on B, scan down to H, put that in read mode, and then release the latch on D.
Quét xuống D, đặt ở chế độ đọc, nhả latch trên B, quét xuống H, đặt ở chế độ đọc, rồi nhả latch trên D.
Read what I want, and then I'm done. So this is pretty simple. Let's see what we have to do on delete.
Đọc những gì tôi muốn, rồi xong. Khá đơn giản. Giờ xem ta phải làm gì với thao tác xóa.
Start off with putting the parent in write mode, because again, at this point here, I don't know what's below me in the tree, so I don't know whether if I delete a key, I'm gonna have to do a merge, I might have to reorganize all the way up to the root.
Bắt đầu bằng việc đặt nút cha ở chế độ ghi, vì một lần nữa, tại thời điểm này tôi không biết bên dưới trong cây có gì, nên tôi không biết nếu xóa một khóa, liệu tôi có phải gộp nút không, có thể phải tổ chức lại cả đường lên tới nút gốc.
So I maintain the right latch on A, come down to B, same thing here.
Vậy tôi giữ write latch trên A, đi xuống B, ở đây cũng tương tự.
I don't know whether I'm gonna have to do a merge on B, because there's only got one key, and I can only store two keys, so if I delete something, and I delete the key here, I gotta do a merge, so I have to hold the write latch on this, and the write latch on A.
Tôi không biết liệu mình có phải thực hiện merge trên B hay không, vì nó chỉ có một khóa, và nó chỉ có thể chứa tối đa hai khóa, nên nếu tôi xóa một thứ gì đó, xóa khóa ở đây, tôi phải thực hiện merge, do đó tôi phải giữ write latch trên nút này, và write latch trên A.
But then when I get down to D, again, taking that latch in read-write mode, at this point here, I know that even if I delete a key below me, that then ends up deleting a key in D, since I'll be at least half full, I know I can absorb that delete in D, so therefore, I don't need the latch on A and B above me.
Nhưng sau đó khi xuống tới D, lại lấy latch ở chế độ đọc-ghi, tại thời điểm này, tôi biết rằng ngay cả khi tôi xóa một khóa bên dưới, dẫn đến việc xóa một khóa trong D, thì vì nó vẫn còn đầy ít nhất một nửa, tôi biết D có thể hấp thụ thao tác xóa đó, vì vậy, tôi không cần latch trên A và B ở phía trên nữa.
So it's safe for me to go ahead and delete those latches. What order do we want to release them?
Nên tôi có thể yên tâm giải phóng các latch đó. Chúng ta muốn giải phóng chúng theo thứ tự nào?
All right, go back here, do I want to release A, then B, or B, then A? Why? He says A, then B, then what? Why?
Được rồi, quay lại đây, tôi muốn giải phóng A rồi đến B, hay B rồi đến A? Tại sao? Bạn nói A, rồi B, sau đó thì sao? Tại sao?
He said, what he said is, he's correct, is that there's nothing to gain by releasing B first, because implicitly, the latch on B is being held by the latch on A.
Điều bạn ấy nói là đúng, là chẳng được lợi gì khi giải phóng B trước, vì ngầm định thì latch trên B đang được bảo vệ bởi latch trên A.
So I actually want to release A first, because if someone wants to go down to the other side of the tree, they can't do that from holding the latch on it, so if I release A first, and that sort of frees up that whole other side, and I want to do that before I release them on B.
Cho nên tôi thực sự muốn giải phóng A trước, vì nếu có ai muốn đi xuống phía bên kia của cây, họ không thể làm vậy khi tôi vẫn đang giữ latch trên nó, nên nếu tôi giải phóng A trước, điều đó giải phóng toàn bộ phía bên kia, và tôi muốn làm điều đó trước khi giải phóng các latch trên B.
So I want to release latches from top down, so roughly in the same order that I'm acquiring them, going top down, yes.
Vậy tôi muốn giải phóng latch từ trên xuống, tức là gần như theo cùng thứ tự mà tôi lấy chúng, từ trên xuống, đúng vậy.
Yeah, so the statement is, and it's correct, that the order in which we release them doesn't affect correctness, This is a performance optimization, because again, if I release the latch on B, nobody can do anything, nobody can get to B anyway, because I still hold the latch on its parent, on A.
Vâng, nhận định này là đúng, rằng thứ tự giải phóng không ảnh hưởng đến tính đúng đắn, Đây là một tối ưu hóa hiệu năng, vì một lần nữa, nếu tôi giải phóng latch trên B, thì không ai làm được gì, dù sao cũng không ai tới được B, vì tôi vẫn đang giữ latch trên nút cha của nó, tức A.
So I'm gonna release the most, sort of the, the latch that has the largest scope, or most, encompassing the most part of the tree, sooner rather than later.
Vì vậy tôi sẽ giải phóng latch có phạm vi lớn nhất, hay bao trùm phần lớn nhất của cây, càng sớm càng tốt.
Again, we're talking nanoseconds here, but you know, we'll take anything we can get.
Một lần nữa, ở đây chỉ là nano giây thôi, nhưng chúng ta cứ tận dụng mọi thứ có thể.
Alright, so now I get down to here, and again, same thing, I know that H can absorb a delete without rebalancing or attempting to merge, so it's safe for me to go ahead and release the latch on D, I do my delete, and I'm done.
Được rồi, bây giờ tôi xuống tới đây, và lại tương tự, tôi biết H có thể hấp thụ một thao tác xóa mà không cần cân bằng lại hay cố merge, nên tôi có thể yên tâm giải phóng latch trên D, tôi thực hiện xóa, và xong.
Alright, let's look at another approach where we do have to do a modification to the structure of the tree.
Được rồi, hãy xem một cách tiếp cận khác trong đó chúng ta phải sửa đổi cấu trúc của cây.
So I'm gonna do an insert on key 45, take the write latch on A, scan down, get the write latch on B, again at this point, I know that if I do a split, and a key comes up into B, then B can handle it, B has space for it, so I can release the latch on A.
Vậy tôi sẽ chèn khóa 45, lấy write latch trên A, duyệt xuống, lấy write latch trên B, một lần nữa tại thời điểm này, tôi biết nếu tôi thực hiện split, và một khóa được đẩy lên B, thì B xử lý được, B còn chỗ, nên tôi có thể giải phóng latch trên A.
I get down here to D, D isn't gonna have enough room for it, so I gotta keep the latch up on B, then I get down to the bottom, and then at I, then I see I can do an insert there, so I can release the latch on B and D, and I go ahead, then I'll insert my new key, and then I'm done.
Tôi xuống đây tới D, D sẽ không đủ chỗ cho nó, nên tôi phải giữ latch ở B phía trên, rồi tôi xuống tận đáy, và tại I, tôi thấy mình có thể chèn ở đó, nên tôi có thể giải phóng latch trên B và D, và tôi tiến hành chèn khóa mới, rồi xong.
Alright, last example, do an insert that isn't gonna require us to do a modification, I insert 25, same thing, take the latch on A, go down to B, take the latch on B, B can absorb any new key that comes up, so I can release the latch from A, follow B down, I go to C, C can do the same thing, can absorb any new insert that could happen,
Được rồi, ví dụ cuối cùng, thực hiện một thao tác chèn không đòi hỏi phải sửa đổi cấu trúc, Tôi chèn 25, cũng tương tự: lấy latch trên A, đi xuống B, lấy latch trên B, B có thể chứa thêm bất kỳ khóa mới nào được đẩy lên, nên tôi có thể nhả latch trên A, đi theo B xuống, rồi tới C, C cũng làm được như vậy, có thể chứa thêm bất kỳ lần chèn mới nào có thể xảy ra,
so I can release the latch on B.
nên tôi có thể nhả latch trên B.
Then I get down to F, I see that F is gonna have to do a split now, because there's no, there's no room for this, so I hold, maintain the latch I have on C, that's, that's its parent.
Sau đó tôi đi xuống F, và thấy rằng F bây giờ sẽ phải tách, vì không còn chỗ trống cho khóa này, nên tôi giữ nguyên latch đang có trên C, vì đó là nút cha của nó.
Again, if I put a new key into C, that's not gonna get pushed anything, push anything up to B, so that's why I don't need to maintain the latch on it.
Một lần nữa, nếu tôi đưa một khóa mới vào C, thì C sẽ không phải đẩy bất cứ thứ gì lên B, nên đó là lý do tôi không cần giữ latch trên B.
So again, now, I'll create a new node, move my keys around as needed, update the guide post up above in C, and point to the new page that I just created here, which, again, I can do, because I hold the right latch on, on C, and then now insert my new record, and I'm done.
Vậy bây giờ, tôi sẽ tạo một nút mới, di chuyển các khóa cho phù hợp, cập nhật khóa dẫn hướng ở phía trên trong C, và trỏ tới trang mới mà tôi vừa tạo ở đây, điều mà tôi làm được vì tôi đang giữ đúng latch ghi trên C, rồi chèn bản ghi mới của tôi vào, và xong.
In the back, yes, saving is, and we'll get, we'll get in a second, the question is, if I have to, if, since I have these pointers along the leaf nodes, do I have to take the latches on the siblings in order to update them?
Bạn ở phía sau, mời bạn, lưu lại thì, và chúng ta sẽ nói tới ngay, câu hỏi là, nếu tôi phải, vì tôi có các con trỏ dọc theo các nút lá, thì tôi có phải lấy latch trên các nút anh em để cập nhật chúng không?
So, in this example here, I wouldn't, when I'm at this point here, right, so for, for node C, its siblings are E and F, I implicitly have the latch on E, because I have the latch on C, so nobody can get to it.
Trong ví dụ này, tôi sẽ không cần, khi tôi đang ở điểm này, đúng không, với nút C, các nút anh em của nó là E và F, tôi mặc nhiên có latch trên E, vì tôi có latch trên C, nên không ai có thể vào được nó.
We'll talk about leaf node scans in a few more slides, but to your point, yes, if I'm here, and now I have to update G, because this guy is now the new sibling, I will have to keep scanning across this, not go back up, and just scan along leaf nodes, and update G, now point back to J.
Chúng ta sẽ nói về việc quét nút lá trong vài slide nữa, nhưng theo ý bạn, đúng vậy, nếu tôi đang ở đây, và bây giờ tôi phải cập nhật G, vì nút này giờ là nút anh em mới, tôi sẽ phải tiếp tục quét ngang qua đây, không quay lên trên, mà chỉ quét dọc các nút lá, và cập nhật G, giờ trỏ ngược về J.
I'll show how to do that in a second.
Tôi sẽ chỉ cách làm việc đó ngay sau đây.
Alright, so for all my examples, what's the very first thing I did anytime I want to update the data structure? He sort of alluded to this before.
Được rồi, vậy trong tất cả các ví dụ của tôi, việc đầu tiên tôi làm mỗi khi muốn cập nhật cấu trúc dữ liệu là gì? Bạn ấy đã nhắc đến điều này trước đó.
What's the very first thing you always have to do in order to make a change to a B+tree? Exactly, take a write latch, a write latch on the root, right?
Việc đầu tiên bạn luôn phải làm để thay đổi một B+tree là gì? Chính xác, lấy một latch ghi, latch ghi trên nút gốc, đúng không?
Even though, again, in some of these operations, like for the inserts, even if a key came up, I would have to, you know, I could, A, have an extra free slot for it, I could insert something into it.
Mặc dù, một lần nữa, trong một số thao tác này, như các lần chèn, ngay cả khi có một khóa được đẩy lên, tôi sẽ phải, bạn biết đấy, có thể là, A, có thêm một chỗ trống cho nó, và tôi có thể chèn một thứ gì đó vào.
So this is basically making our data structure single-threaded, because everybody's coming in and trying to do the same thing, trying to take a write latch on the, on the root, and that'll become a bottleneck for us.
Vì vậy điều này về cơ bản biến cấu trúc dữ liệu của chúng ta thành đơn luồng, vì mọi người đều đi vào và cố làm cùng một việc, cố lấy latch ghi trên nút gốc, và điều đó sẽ trở thành nút thắt cổ chai của chúng ta.
So the optimization that we can do to this, so what he alluded to, is instead of taking a write latch, because we're gonna assume that we may have to do a split and merge, we're gonna be optimistic and assume that we're not gonna have to split and merge, and therefore we're gonna take read latches all the way down until we reach the,
Vậy tối ưu hóa mà chúng ta có thể làm cho việc này, tức là điều bạn ấy đã nhắc tới, là thay vì lấy latch ghi, vì chúng ta giả định rằng có thể phải tách và gộp, chúng ta sẽ lạc quan và giả định rằng sẽ không phải tách và gộp, và do đó chúng ta sẽ lấy latch đọc suốt đường đi xuống cho tới khi
to reach a leaf node, and then we check to see whether our assumption was correct or not, whether we are going to do a split and merge based on our operation.
tới được một nút lá, rồi sau đó chúng ta kiểm tra xem giả định của mình có đúng hay không, tức là liệu thao tác của chúng ta có phải thực hiện tách hoặc gộp nút hay không.
And if we're, if we were correct that we're not gonna split and merge, then we just take the write latch on the, on the leaf node, and poof, we're done, our change is just fine.
Và nếu giả định đúng, tức là sẽ không phải tách hay gộp, thì chúng ta chỉ cần lấy write latch trên nút lá đó, và xong ngay, thay đổi của chúng ta hoàn toàn ổn.
If we are incorrect about our assumption, then we release any latches that we have, just do the whole thing again, taking write latches in the more pessimistic approach.
Nếu giả định sai, thì chúng ta nhả mọi latch đang giữ, rồi làm lại toàn bộ từ đầu, lần này lấy write latch theo cách bi quan hơn.
So this technique was, it's sometimes called the Bayer-Schkolnick algorithm. Bayer was the guy that invented the B+tree with the other guy from CMU at Boeing in the, early 1970s or 1960s.
Kỹ thuật này đôi khi được gọi là thuật toán Bayer-Schkolnick. Bayer là người đã phát minh ra B+tree cùng với một người khác từ CMU, tại Boeing vào đầu những năm 1970 hoặc 1960.
So this is an optimistic algorithm that they developed A few years later.
Đây là một thuật toán lạc quan mà họ phát triển vài năm sau đó.
And we'll see this idea again when we talk about optimistic concurrency control; it's another technique invented here at CMU in the 1980s, of how we handle transactions, where, again, you assume that things are not going to conflict, and therefore you do the sort of the fast path, and if you get it wrong, you go back and clean things up.
Và chúng ta sẽ gặp lại ý tưởng này khi nói về điều khiển đồng thời lạc quan; đó là một kỹ thuật khác được phát minh ngay tại CMU vào những năm 1980, về cách chúng ta xử lý các giao dịch, trong đó, một lần nữa, bạn giả định rằng các thao tác sẽ không xung đột, và do đó bạn đi theo đường nhanh, còn nếu sai thì bạn quay lại và dọn dẹp.
Question is, the question is, is there an upgrade mechanism in latches where you can, if you hold a read latch, upgrade it to a write latch?
Câu hỏi là, câu hỏi là liệu latch có cơ chế nâng cấp không, tức là bạn có thể, nếu đang giữ read latch thì nâng cấp nó thành write latch?
If you don't know who the other threads are, and whether, how many other threads have it in read mode, no.
Nếu bạn không biết các thread khác là những thread nào, và có bao nhiêu thread khác đang giữ nó ở chế độ đọc thì không.
If you know there's nobody else holding it in read mode right now, you could do that, yes.
Nếu bạn biết hiện không có ai khác giữ nó ở chế độ đọc, thì bạn có thể làm vậy, đúng.
You said there's no, there's no, you used the word atomic for that, but I don't think you need that.
Bạn nói là không có, không có, bạn dùng từ nguyên tử cho việc đó, nhưng tôi nghĩ bạn không cần điều đó.
You said there's no way to just wait until all the other threads that have it in read mode finish.
Bạn nói là không có cách nào để chỉ chờ cho đến khi tất cả các thread khác đang giữ nó ở chế độ đọc kết thúc.
So again, if you have a counter for a number of threads currently holding it in read mode, you could do that sort of queue lock thing before, where, like, you put yourself in a queue and say, okay, I actually want this in write mode now.
Vậy nên, nếu bạn có một bộ đếm số thread hiện đang giữ nó ở chế độ đọc, bạn có thể làm kiểu khóa hàng đợi như lúc trước, tức là bạn tự đưa mình vào một hàng đợi và nói rằng, được rồi, giờ tôi thực sự muốn có nó ở chế độ ghi.
And then when that's free, you go ahead and get it. You could do that. But that's actually, it's more machinery. It may not be worth it.
Và khi nó rảnh thì bạn lấy nó. Bạn có thể làm vậy. Nhưng thực ra, nó cần thêm nhiều cơ chế hơn. Có thể không đáng.
Say it again?
Bạn nói lại được không?
So let me come back to your question. He's basically asking, do I always have to start from the root again? Can I just start halfway through?
Vậy để tôi quay lại câu hỏi của bạn. Về cơ bản bạn ấy hỏi là, liệu tôi có luôn phải bắt đầu lại từ gốc không? Tôi có thể bắt đầu từ giữa chừng được không?
He's saying doing a latch upgrade. You're saying do what? Do the same thing? Or, yeah, let's go through the table.
Bạn ấy nói về việc nâng cấp latch. Bạn nói là làm gì? Làm điều tương tự? Hoặc, vâng, hãy xem qua bảng.
It may work, but, like, the point of being changed, and that's the tricky part. It depends on whether you still hold a read latch or not.
Có thể nó sẽ hiệu quả, nhưng vấn đề là điểm bị thay đổi, và đó là phần khó. Nó phụ thuộc vào việc bạn có còn giữ read latch hay không.
All right, so search the same as before. Insert, delete.
Được rồi, vậy tìm kiếm thì giống như trước. Chèn, xóa.
Again, you treat it as if you're doing a search, take read latches, and once you get to the level right above the leaf node, because again, you maintain in every node what level you're at.
Một lần nữa, bạn xử lý nó như thể đang tìm kiếm, lấy read latch, và khi bạn đến mức ngay phía trên nút lá, vì, một lần nữa, bạn lưu trong mỗi nút việc nó đang ở mức nào.
So you know the height of the tree. So you know when you're at height minus one. Then you try to acquire the write latch on that leaf node.
Vậy bạn biết chiều cao của cây. Nên bạn biết khi nào mình đang ở chiều cao trừ một. Sau đó bạn cố gắng lấy write latch trên nút lá đó.
If you got it wrong, when you actually then inspect it to see whether you have to do a split or merge, then you just restart and take write latches all the way down.
Nếu bạn đoán sai, khi bạn kiểm tra nó để xem có phải tách hay gộp hay không, thì bạn chỉ cần khởi động lại và lấy write latch trên suốt đường đi xuống.
And in some cases, as he said, you may be able to not have to do the full traversal, but it's a bit more complicated.
Và trong một số trường hợp, như bạn ấy nói, bạn có thể không cần phải duyệt toàn bộ, nhưng nó phức tạp hơn một chút.
So going back here, the same example we had before, I want to delete key 38.
Quay lại đây, với cùng ví dụ trước, tôi muốn xóa khóa 38.
So instead of taking the write latch in the root, I'm going to take the read latch, go all the way down, just do the latch coupling technique as we did before, releasing the latch on my parent once I acquire the latch below me.
Vì vậy thay vì lấy write latch trên gốc, tôi sẽ lấy read latch, đi xuống tận dưới, dùng kỹ thuật latch coupling như trước, nhả latch trên nút cha khi tôi đã lấy được latch của nút bên dưới.
I now get the write latch on H. At this point here, I know that this node can absorb a deleted key.
Bây giờ tôi lấy write latch trên H. Tại thời điểm này, tôi biết nút này có thể chịu được việc xóa một khóa.
So I can go ahead and release the read latch above me on D, make my change to H at the bottom, and I know it can absorb that.
Nên tôi có thể nhả read latch ở phía trên trên D, thực hiện thay đổi trên H ở dưới cùng, và tôi biết nó chịu được.
And we're not going to do a merge, so we're fine there.
Và chúng ta sẽ không phải gộp, nên ổn ở đó.
In my example here, I have to insert 25. Same thing, start at the root, scan down, taking the read latches as I go along, and releasing up above me when I know it's safe.
Trong ví dụ này, tôi phải chèn 25. Tương tự, bắt đầu từ gốc, quét xuống, lấy các read latch trên đường đi, và nhả các latch phía trên khi biết là an toàn.
Then I get the write latch on this guy here, see that I am going to have to do a split on node F.
Rồi tôi lấy write latch trên nút này đây, và thấy rằng tôi sẽ phải tách nút F.
So in this case here, I'll just have to restart my search, taking write latches all the way down.
Vậy trong trường hợp này, tôi chỉ phải khởi động lại việc tìm kiếm, lấy write latch trên suốt đường đi xuống.
So now his comment is, could I be clever about this and keep track of the nodes I visited, figure out where could a new key come up where I have to do a split up above?
Vậy nhận xét của bạn ấy là, liệu tôi có thể khéo léo theo dõi các nút đã đi qua, để tìm ra nơi nào một khóa mới có thể đẩy lên khiến tôi phải tách ở phía trên không?
You could do that.
Bạn có thể làm vậy.
The challenge is that there's no guarantee by the time you get here, since you release all the read latches up above you, that if I then try to come back and say, "Oh, I was at B, and I know B could absorb anything that came up from C," or sorry, C can absorb anything that comes up from F, therefore I don't have to acquire read latches on B.
Thách thức là không có gì đảm bảo rằng khi bạn đến đây, vì bạn đã nhả tất cả read latch phía trên, rồi quay lại và nói: "Ồ, tôi đã ở B, và tôi biết B có thể chịu được bất cứ thứ gì đẩy lên từ C", hoặc xin lỗi, C có thể chịu được bất cứ thứ gì đẩy lên từ F, do đó tôi không cần lấy read latch trên B.
But you don't know whether somebody else has come along by the time you restarted, changed B's layout, and now C's some results. So you could do it.
Nhưng bạn không biết liệu người khác có chen vào trong lúc bạn khởi động lại hay không, làm thay đổi bố cục của B, và giờ C bị ảnh hưởng. Nên bạn có thể làm được.
It's just more tricky because there's no guarantee, because otherwise you're just holding latches on everything, and then it defeats the whole purpose of any of this.
Chỉ là phức tạp hơn vì không có gì đảm bảo, vì nếu không thì bạn sẽ giữ latch trên mọi thứ, và điều đó làm mất toàn bộ mục đích của việc này.
Oftentimes the simplest thing is the easiest thing to do, or the best thing to do.
Thường thì cách đơn giản nhất lại là cách dễ làm nhất, hoặc là cách tốt nhất.
All right, so now let's get to the last problem that he brought up in the back, where in all my examples here, I was just doing, like, point query lookups.
Được rồi, giờ đến vấn đề cuối cùng mà bạn ở phía sau đã nêu, là trong tất cả ví dụ ở đây, tôi chỉ làm các truy vấn điểm.
Go insert this one key. Go find this one key.
Đi chèn khóa này. Đi tìm khóa này.
But when I have to start doing range scans along leaf nodes, then this becomes more tricky, because assuming I have now sibling pointers that can go both directions, now I can have deadlocks.
Nhưng khi tôi phải bắt đầu quét phạm vi dọc theo các nút lá, thì việc này trở nên phức tạp hơn, vì giả sử bây giờ tôi có các con trỏ anh em đi được cả hai hướng, thì giờ tôi có thể gặp bế tắc.
Again, in the hash heap, I'm going from top to the bottom. In the B+tree coupling, I'm going from the top to the bottom.
Một lần nữa, trong hash heap, tôi đi từ trên xuống dưới. Trong kỹ thuật latch coupling của B+tree, tôi đi từ trên xuống dưới.
Nobody else is coming up in the other direction. I can't have a deadlock.
Không ai khác đi lên theo hướng ngược lại. Tôi không thể bị bế tắc.
But now if I have leaf node scans, I could have this problem, because there are people might be coming from different directions.
Nhưng bây giờ nếu có các lần quét nút lá, tôi có thể gặp vấn đề này, vì có những luồng có thể đến từ các hướng khác nhau.
So now we may come to a possibility where I need to acquire a latch on the next node I want to scan along, and somebody else holds it, and now I got to figure out what do I need to do.
Vậy bây giờ ta có thể gặp trường hợp tôi cần lấy latch trên nút kế tiếp mà tôi muốn quét tới, và người khác đang giữ nó, và giờ tôi phải tìm cách xử lý.
So say my first thread here wants to find all keys greater than 4. Again, I start at the root node. It's a really simple B+tree.
Giả sử luồng đầu tiên ở đây muốn tìm tất cả các khóa lớn hơn 4. Một lần nữa, tôi bắt đầu từ nút gốc. Đây là một B+tree rất đơn giản.
It only has two levels. I take this one in read mode. I scan along down here.
Nó chỉ có hai tầng. Tôi lấy nút này ở chế độ đọc. Tôi quét xuống đây.
Take this node C in read mode, and I'm fine, because I can find all the data I want.
Lấy nút C này ở chế độ đọc, và ổn, vì tôi tìm được tất cả dữ liệu mình cần.
But now when I want to come along here and go from C to B, because I'm scanning all values less than 4, I don't want to release the latch on C until I acquire the latch on B, because I don't know whether this thing will get swapped out by the time I'm following the pointer to B.
Nhưng bây giờ khi tôi muốn đi từ C sang B, vì tôi đang quét tất cả các giá trị nhỏ hơn 4, tôi không muốn nhả latch trên C cho đến khi lấy được latch trên B, vì tôi không biết nút này có bị thay đổi khi tôi đang đi theo con trỏ tới B hay không.
Because if I release the latch on C, some other thread might come in, do an update, and now the location of where C should be and what it's pointing to, or where B is now as well, could change, and then I could have out of bound memory access or follow a bad pointer.
Vì nếu tôi nhả latch trên C, một luồng khác có thể chen vào, thực hiện cập nhật, và khi đó vị trí của C cũng như nơi nó trỏ tới, hoặc vị trí của B lúc này, có thể thay đổi, và tôi có thể truy cập bộ nhớ ngoài phạm vi hoặc đi theo một con trỏ sai.
So once I know it's safe, I can get over to B, then I can go ahead and release the latch I have on C.
Vì vậy khi biết là an toàn, tôi có thể sang B, rồi tôi mới nhả latch đang giữ trên C.
All right, so look at another one. Find all keys greater than 1.
Được rồi, hãy xem một ví dụ khác. Tìm tất cả các khóa lớn hơn 1.
So now I have the blue thread wants to go down from the root node to B, and the red thread wants to go down from A to C.
Bây giờ luồng màu xanh muốn đi từ nút gốc xuống B, còn luồng màu đỏ muốn đi từ A xuống C.
So they both acquire the read latch on the root, that's fine. Then they get down to their leaf nodes.
Cả hai đều lấy read latch trên nút gốc, không sao. Sau đó họ xuống tới các nút lá của mình.
Now they're scanning along, they read all the data that they want, and then they want to swap sides, because the red thread wants to go over to B and the blue thread wants to go over to C.
Giờ họ quét dọc theo, đọc tất cả dữ liệu cần thiết, rồi họ muốn đổi bên, vì luồng đỏ muốn sang B và luồng xanh muốn sang C.
In this case here, both nodes are latched in read mode, so those are commutative.
Trong trường hợp này, cả hai nút đều được latch ở chế độ đọc, nên chúng tương thích với nhau.
It's okay for both of them to share these latches, so they just sort of swap sides and read the data they want, and that's just fine.
Cả hai có thể cùng chia sẻ các latch này, nên họ chỉ việc đổi bên và đọc dữ liệu mình muốn, và như vậy là ổn.
And then at this point here, they're both releasing the latches that are being held, that they're holding on the other nodes.
Rồi đến đây, cả hai đều nhả các latch đang giữ, các latch họ đang giữ trên những nút kia.
So at this final stage here, only T1 holds the read latch on B, and only T2 holds the read latch on C.
Vậy ở giai đoạn cuối này, chỉ T1 giữ read latch trên B, và chỉ T2 giữ read latch trên C.
All right, that's pretty straightforward. So now let's look at the case where we have modification. T1 wants to delete T4, and T2 wants to find all keys greater than 1.
Được rồi, khá đơn giản. Bây giờ hãy xem trường hợp có sửa đổi. T1 muốn xóa 4, và T2 muốn tìm tất cả các khóa lớn hơn 1.
So at the very beginning, they're assuming they're doing optimistic latch coupling, so they're gonna both acquire the root node in, the latch on the root node in read mode.
Ngay từ đầu, giả sử họ dùng optimistic latch coupling, nên cả hai sẽ cùng lấy nút gốc, lấy latch trên nút gốc ở chế độ đọc.
That's fine, that's commutative. T2 comes down here to B, gets the read latch on B.
Không sao, chúng tương thích. T2 đi xuống B, lấy read latch trên B.
T1 gets then the write latch on C, and wants to go ahead, because it wants to delete that key right there.
Sau đó T1 lấy write latch trên C, và muốn tiến hành, vì nó muốn xóa khóa ngay tại đó.
So let's say that T2 reads all it wants from B, and now wants to follow the sibling pointer to come over and read the contents on C.
Giả sử T2 đọc xong mọi thứ nó muốn từ B, và bây giờ muốn đi theo con trỏ anh em (sibling pointer) để sang và đọc nội dung của C.
And so again, we know it's doing a read operation, so once acquired the latch on C in read mode, but it's already being held in write mode, that's not compatible, so it can't acquire that latch.
Một lần nữa, chúng ta biết nó đang thực hiện thao tác đọc, nên nó sẽ lấy latch trên C ở chế độ đọc, nhưng latch đó đã bị giữ ở chế độ ghi rồi, hai chế độ này không tương thích, nên nó không thể lấy được latch đó.
So now the question is, what should happen here? Because T2 doesn't know what T1 is doing.
Vậy câu hỏi bây giờ là: chuyện gì nên xảy ra ở đây? Vì T2 không biết T1 đang làm gì.
T1 doesn't know that there's another thread trying to acquire the latch, because it acquired the latch in write mode, and it's off doing whatever the write that it wants to do.
T1 cũng không biết có một thread khác đang cố lấy latch, vì nó đã lấy latch ở chế độ ghi, và nó cứ đi làm bất cứ thao tác ghi nào nó muốn.
It's not checking to see who else is waiting for it, because that would be slow. Why would you do that?
Nó không kiểm tra xem ai khác đang chờ mình, vì làm vậy sẽ chậm. Tại sao bạn lại làm thế?
So T2 already knows that there's some other thread that holds this latch in write mode, that it's not compatible with what it wants to do.
Vậy T2 đã biết rằng có một thread khác đang giữ latch này ở chế độ ghi, và nó không tương thích với việc T2 muốn làm.
So now we have to make a decision of what we want to do with T2. So there's three choices. One is you just wait.
Giờ chúng ta phải quyết định sẽ làm gì với T2. Có ba lựa chọn. Một là cứ chờ.
Two, you could just kill yourself, release whatever latches you have, and then just try it again.
Hai là tự hủy chính mình, nhả mọi latch đang giữ, rồi thử lại.
And then three is, you kill the other thread, take its latch, steal its keys, whatever you want, and then do whatever it is that you want to do.
Ba là hủy thread kia, lấy latch của nó, cướp chìa khóa của nó, tùy bạn, rồi làm điều bạn muốn làm.
What's that? The statement is, you can't just wait. No, it's not a deadlock, because T1 only wants to delete T4.
Gì vậy? Ý bạn là không thể chỉ chờ. Không, đây không phải bế tắc, vì T1 chỉ muốn xóa T4.
It's not going to acquire any latches on B. It's not a deadlock.
Nó sẽ không lấy latch nào trên B. Đây không phải bế tắc.
The statement is, the question is, how would T2 know that it would find what it needs in that other node?
Câu hỏi là, làm sao T2 biết được rằng nó sẽ tìm thấy thứ cần thiết trong node kia?
The question is, is it possible that the pointer on where the location is C would...
Câu hỏi là, liệu có thể xảy ra việc con trỏ chỉ tới vị trí của C sẽ...
No, the statement is, is it possible where, say, the physical location of C would change, therefore the pointer on B would no longer be valid?
Không, ý bạn là, liệu có khả năng vị trí vật lý của C thay đổi, và do đó con trỏ trên B không còn hợp lệ nữa?
No, because I wouldn't be allowed to change that location without updating all the sibling pointers. And if I can't acquire the latch on B, then I can't make that change.
Không, vì tôi sẽ không được phép thay đổi vị trí đó mà không cập nhật tất cả các con trỏ anh em. Và nếu tôi không lấy được latch trên B thì tôi không thể thực hiện thay đổi đó.
Very clear. So T1, since it's deleting that one key, it doesn't have to update any sibling pointers, because it's not doing a merge, okay?
Rất rõ ràng. Vậy T1, vì chỉ xóa một khóa đó, nên không phải cập nhật con trỏ anh em nào, vì nó không thực hiện thao tác gộp (merge), được chứ?
Yep, sure. Yes, in that case you would have a deadlock, yes. That's not this example. And the protocol, the answer to this will roughly be the same. Say that again?
Vâng, đúng. Có, trong trường hợp đó thì sẽ có bế tắc. Nhưng đó không phải ví dụ này. Và với giao thức này, câu trả lời gần như giống nhau. Bạn nói lại được không?
T2 does not know that it's in deadlock. Correct. And it actually would never know.
T2 không biết là đang bế tắc. Đúng. Và thực tế nó sẽ không bao giờ biết.
The option is to wait. Okay, how long? What's that?
Lựa chọn là chờ. Được, chờ bao lâu? Gì vậy?
All right, so you said T1 would have to adjust its speed?
Được rồi, bạn nói T1 sẽ phải điều chỉnh tốc độ của nó?
Yes. Okay, so he said T2 should optimistically keep waiting until it acquires the latch. My question would be, how long?
Vâng. Được, vậy bạn ấy nói T2 nên lạc quan tiếp tục chờ cho đến khi lấy được latch. Câu hỏi của tôi là, chờ bao lâu?
All right, don't do that. We're not trying to do deadlock here. All we know here is T2 wants to acquire the latch on C. T1 holds that.
Thôi, đừng làm vậy. Ở đây chúng ta không cố tạo ra bế tắc. Tất cả những gì ta biết ở đây là T2 muốn lấy latch trên C. T1 đang giữ nó.
He said just kill yourself and try again later. Do you think it's a good idea? All right, raise your hand if you say you should wait.
Bạn ấy nói cứ tự kết liễu rồi thử lại sau. Các bạn thấy đó có phải ý hay không? Nào, ai cho rằng nên chờ thì giơ tay.
All right, one less than half. Raise your hand if you want to kill yourself. All right, you want to kill your thread. If you're the thread, you're gonna kill yourself. Sorry.
Được, ít hơn một nửa một người. Ai muốn tự kết liễu thì giơ tay. Được rồi, các bạn muốn kết liễu thread của mình. Nếu bạn là thread thì bạn sẽ tự kết liễu mình. Xin lỗi nhé.
Raise your hand if you want to kill yourself. Raise your hand if you want to kill the other thread.
Ai muốn tự kết liễu thì giơ tay. Ai muốn kết liễu thread kia thì giơ tay.
Nobody wants to kill the other thread. Oh, you do. Gangster. How would you do it?
Không ai muốn kết liễu thread kia. À, bạn có. Dân anh chị đấy. Bạn sẽ làm thế nào?
What's that? Not sure. Can we do it?
Gì cơ? Không chắc. Mình làm được không?
See if it is, it'd be hard to know which latch is being held by which thread. Yes.
Nếu vậy thì sẽ khó biết latch nào đang bị thread nào giữ. Đúng.
Yes. Remember we said before, there is no centralized data structure keeping track of what thread holds what latch. So all I know is that there's this latch I want.
Đúng. Nhớ là trước đó ta đã nói, không có cấu trúc dữ liệu tập trung nào theo dõi thread nào đang giữ latch nào. Nên tất cả những gì tôi biết là có một latch mà tôi muốn.
All T2 knows is that there's some latch I want. It's being held by this other thread. I can't talk to it.
Tất cả những gì T2 biết là có một latch nào đó mà nó muốn. Nó đang bị thread khác giữ. Tôi không thể nói chuyện với nó.
All right, so then maybe I could store within the latch the list of the threads that hold it. But then how am I going to kill them, right?
Vậy có lẽ tôi có thể lưu bên trong latch danh sách các thread đang giữ nó. Nhưng rồi làm sao tôi kết liễu chúng được?
Well, if you used pthread mutex and you send an interrupt, it wants to kill the whole thread. The thread wants to terminate.
Nếu bạn dùng pthread mutex và gửi một interrupt, nó sẽ muốn kết liễu cả thread. Thread sẽ muốn kết thúc.
Some of the user-based latches we talked about before, you can send interrupts and just kill the wait operation. That's more fine grain. That's what you want to do.
Với một số latch ở mức người dùng mà ta đã nói trước đó, bạn có thể gửi interrupt và chỉ hủy thao tác chờ. Cách đó mịn hơn. Đó là điều bạn muốn làm.
But like, if I want to basically, you know, I'd have to have a mechanism where I'm checking to see, hey, whether T1 would have to check to say, oh yeah, somebody wants this latch and I'm holding?
Nhưng nếu tôi muốn về cơ bản là, tôi phải có một cơ chế để kiểm tra xem, này, liệu T1 có phải kiểm tra để biết rằng, à, có người muốn latch này và mình đang giữ?
I should kill myself. But again, if I'm trying to do this as quickly, get in the critical section as quickly as possible and release it, Not always the case.
Mình nên tự kết liễu. Nhưng một lần nữa, nếu tôi cố làm việc này thật nhanh, vào critical section càng nhanh càng tốt rồi nhả ra, thì không phải lúc nào cũng vậy.
If I have to go get something from disk, yeah, I'm screwed because that's gonna take milliseconds. But in general, if I assume that everything's in memory, it'd be as fast as possible.
Nếu tôi phải lấy thứ gì đó từ đĩa thì đúng, tôi toi rồi vì việc đó mất hàng mili giây. Nhưng nhìn chung, nếu giả sử mọi thứ đều nằm trong bộ nhớ, nó sẽ nhanh nhất có thể.
I want to be in and out as quickly as I can. Because again, you can't just blindly kill the thread, like, you know, send a SIGTERM, because it's in your thread.
Tôi muốn vào và ra càng nhanh càng tốt. Bởi vì bạn không thể cứ thế kết liễu thread một cách mù quáng, chẳng hạn gửi SIGTERM, vì nó nằm trong thread của bạn.
It'll take down everything. But like, because if I have a large, my data structure is much larger, I may hold a bunch of latches up above and I got to unwind all that.
Nó sẽ làm sập mọi thứ. Hơn nữa, nếu cấu trúc dữ liệu của tôi lớn hơn nhiều, tôi có thể đang giữ hàng loạt latch ở phía trên và phải gỡ hết chúng.
Furthermore, I may have made a bunch of modifications in my data structure and I just want to, I can't just shoot it in the head and let it die.
Ngoài ra, tôi có thể đã thực hiện nhiều thay đổi trong cấu trúc dữ liệu và tôi chỉ muốn, tôi không thể cứ bắn vào đầu rồi để nó chết.
It has to roll back all its changes. Because again, as I said, there isn't a decentralized thing that's gonna keep track of what changes I made.
Nó phải rollback mọi thay đổi của mình. Bởi vì như tôi đã nói, không có thành phần tập trung nào theo dõi những thay đổi mà tôi đã thực hiện.
Every thread is responsible for cleaning itself up if it can't do what it needs to do when it rolls back. So the correct answer is kill ourselves.
Mỗi thread tự chịu trách nhiệm dọn dẹp cho chính nó nếu nó không thể làm được việc cần làm khi rollback. Vậy đáp án đúng là tự kết liễu mình.
We can be a little more, you know, graceful about it and wait a little bit. But in general, this is the easiest thing to do. And sometimes it's the fastest thing to do.
Chúng ta có thể làm mềm mỏng hơn một chút, kiểu chờ thêm một lúc. Nhưng nhìn chung, đây là cách dễ làm nhất. Và đôi khi nó cũng là cách nhanh nhất.
Now, when we talk about locking, and in that world where you want to break deadlocks, you want to kill yourself, there's a bunch more metadata we're gonna have about what we did in our transaction that we can make better decisions of whether we should kill ourselves or not.
Bây giờ, khi nói về locking, trong thế giới mà bạn muốn phá bế tắc, bạn muốn tự kết liễu mình, chúng ta sẽ có thêm nhiều metadata về những gì mình đã làm trong transaction, để có thể quyết định tốt hơn xem có nên tự kết liễu mình hay không.
In that case, also with locks, we can go kill the people too. Because I, in this simple example here, I only have three nodes in my entire data structure.
Trong trường hợp đó, với lock, chúng ta cũng có thể đi kết liễu người khác. Bởi vì trong ví dụ đơn giản này, tôi chỉ có ba node trong toàn bộ cấu trúc dữ liệu.
But let's say this T1 over here, it wants to delete a ton of keys.
Nhưng giả sử T1 ở đây muốn xóa rất nhiều key.
And let's say it started over this side, and it went in this direction, and did a bunch of deletes, did a million deletes, a billion deletes.
Và giả sử nó bắt đầu từ phía này, rồi đi theo hướng này, và xóa hàng loạt, một triệu lần xóa, một tỉ lần xóa.
I don't want to kill them because I, you know, the amount of work they have to then roll back is gonna be huge. Whereas all this guy is used to reading so much stuff.
Tôi không muốn kết liễu nó vì, lượng công việc mà nó phải rollback sau đó sẽ rất lớn. Trong khi anh chàng này chỉ quen đọc rất nhiều thứ.
So the best decision oftentimes is just kill yourself, because you don't have to reason about who's more important, me or you. Right?
Vì vậy quyết định tốt nhất thường là tự kết liễu mình, vì bạn không phải cân nhắc ai quan trọng hơn, tôi hay bạn. Đúng không?
And so that logic about when you decide, you know, how quickly you should kill yourself could be a little bit smarter based on what you've done.
Và logic quyết định như vậy, tức là nên tự kết liễu mình nhanh đến mức nào, có thể thông minh hơn một chút dựa trên những gì bạn đã làm.
Like if I've had to update a bunch of things, and I'll let myself maybe wait a millisecond or so before I kill myself.
Ví dụ nếu tôi đã phải cập nhật rất nhiều thứ, thì có thể tôi sẽ cho phép mình chờ khoảng một mili giây trước khi tự kết liễu.
Yeah, that's how I might kill myself faster. And then you come back and, I mean, in the end, like it's, there's no free lunch.
Vâng, đó là cách tôi có thể tự kết liễu nhanh hơn. Và rồi cuối cùng, không có bữa trưa nào miễn phí.
We can't just magically peer and say, oh, I know you're doing this. You got to make some decision. And the best you can do is based on what your own knowledge. Yes. Right?
Chúng ta không thể tự nhiên nhìn sang và nói, ồ, tôi biết bạn đang làm việc này. Bạn phải đưa ra một quyết định nào đó. Và điều tốt nhất bạn làm được là dựa trên hiểu biết của chính mình. Vâng, mời bạn.
In the back, behind you. Yes.
Ở phía sau, sau lưng bạn. Vâng.
The question is, why not just skip this node and go to one that doesn't have a latch? So this is, again, find all keys, going back here, find all keys greater than one.
Câu hỏi là, sao không bỏ qua node này và đi tới node không có latch? Đây lại là truy vấn tìm tất cả key, quay lại đây, tìm tất cả key lớn hơn một.
So you're right. There may be other nodes over here that, like, I could have accessed, but like I can't get to them without going through the leaf node.
Bạn nói đúng. Có thể có những node khác ở bên này mà tôi lẽ ra có thể truy cập, nhưng tôi không thể tới đó mà không đi qua leaf node.
I have to go back up and have to figure out how to jump back down to some middle point, keep track of the one I didn't see, then go read it.
Tôi phải quay lên trên và phải tìm cách nhảy xuống lại một điểm ở giữa, ghi nhớ node mình chưa thấy, rồi mới đọc nó.
This is way more complicated. Question? Yes.
Việc này phức tạp hơn nhiều. Câu hỏi nữa? Vâng.
Yes. You can't kill other threads. This is way too hard.
Vâng. Bạn không thể kết liễu các thread khác. Việc này quá khó.
All right. Hold up. So this gets into the logical correctness.
Được rồi, khoan đã. Điều này liên quan đến tính đúng đắn về mặt logic.
So his statement is, if I'm doing, what I thought you were going to say is, if I'm doing a write and I need to acquire a latch in write mode, but it's already in read mode, then it'd be nice if I can kill the other one.
Ý của bạn là, nếu tôi đang, điều tôi nghĩ bạn sắp nói là, nếu tôi đang ghi và cần lấy latch ở chế độ ghi, nhưng nó đã ở chế độ đọc rồi, thì sẽ rất tiện nếu em có thể giết luồng kia.
You can't.
Em không thể.
So what I thought you were going to say is, "Oh, I'll let myself sleep a little bit longer because I know what the work I've done is more, you know, I'm doing a write that's more important.
Thầy tưởng em định nói là: "Ồ, mình sẽ cho bản thân ngủ lâu hơn một chút vì mình biết công việc mình đang làm quan trọng hơn, tức là mình đang ghi, và việc ghi quan trọng hơn.
I'll let myself sleep more." You would do that? Yes. There's also other things you can do. Like if, basically, when I want to do it in any operation, there's a while around this.
Mình sẽ ngủ lâu hơn." Em sẽ làm vậy à? Vâng. Cũng còn những việc khác em có thể làm. Ví dụ, khi muốn thực hiện bất kỳ thao tác nào, ta có một vòng lặp while bao quanh.
So like if I try to do a write, I can't acquire the latch, I bail out, and then I'll just try to do that operation again.
Nên nếu em thử ghi mà không lấy được latch, em thoát ra, rồi em thử thực hiện lại thao tác đó.
And then now you can keep track of, oh, how many times have I tried this and it failed, because I don't want to starve myself forever.
Và lúc này em có thể theo dõi xem, mình đã thử bao nhiêu lần mà đều thất bại, vì em không muốn tự làm mình bị bỏ đói mãi mãi.
So then if I've tried a bunch of times, then maybe I'll sleep a little bit longer because I'm more likely to get to this.
Nên nếu đã thử nhiều lần, thì có thể em sẽ ngủ lâu hơn một chút vì khi đó khả năng em lấy được nó cao hơn.
Then there's a high-level mechanism to say, okay, if I really can never get to this write latch I need, there's a schedule up above and say, okay, well, pause any IELTS from accessing this data structure until this guy goes through and gets what he needs.
Rồi còn có một cơ chế ở mức cao hơn để nói rằng, nếu em thực sự không bao giờ lấy được write latch cần dùng, thì có một bộ lập lịch ở phía trên sẽ bảo, hãy tạm dừng mọi luồng truy cập cấu trúc dữ liệu này cho đến khi luồng kia xong việc và lấy được thứ nó cần.
All right. But then you were suggesting to do what again?
Được rồi. Nhưng vậy em đề xuất làm gì nhỉ?
Right.
Đúng rồi.
So he said, if the thread is trying to try the write latch and it's held in read mode, you're better off killing the reader because I'm going to update it now and whatever it read is now out of date.
Bạn ấy nói là, nếu luồng đang thử lấy write latch mà nó đang được giữ ở chế độ đọc, thì tốt hơn là giết bên đọc vì em sắp cập nhật nó và những gì bên đọc đã đọc giờ đã lỗi thời.
That's a logical correctness thing. Is that actually right or not? Depends on high-level concepts of the ordering of the transactions, which we're not talking about yet.
Đó là vấn đề về tính đúng đắn logic. Vậy điều đó có thực sự đúng không? Nó phụ thuộc vào các khái niệm mức cao về thứ tự của các giao dịch, mà chúng ta chưa bàn tới.
So for example, if I insert key five, then I go try it back and read key five, and in between that someone goes and deletes key five.
Ví dụ, nếu em chèn khóa năm, rồi quay lại thử đọc khóa năm, và ở giữa đó có ai đó xóa khóa năm.
Is that correct? It depends. What's that?
Như vậy có đúng không? Tùy. Em nói gì?
Yes, what I'm saying, ignore deadlocks, ignore all this trying to acquire latches. I have a data structure, it's single threaded. I insert something.
Vâng, ý thầy là hãy bỏ qua bế tắc, bỏ qua toàn bộ chuyện cố lấy latch. Ta có một cấu trúc dữ liệu đơn luồng. Em chèn một thứ.
I then go try to read it again, but before I can go read it again, someone else comes through and deletes it.
Rồi em thử đọc lại, nhưng trước khi em kịp đọc lại, có người khác tới và xóa nó.
Now I read it and I don't see it. Is that correct or not? Physically, it is. Logically, it may not be. That's this high-level concept of correctness for transactions, which we're not covering yet.
Giờ em đọc và không thấy nó. Vậy có đúng không? Về mặt vật lý thì đúng. Về mặt logic thì có thể không. Đó là khái niệm mức cao về tính đúng đắn của các giao dịch, mà chúng ta chưa đề cập.
In some cases, that may be okay. Other cases, no. Yes?
Có trường hợp thì ổn, có trường hợp thì không. Em hỏi gì?
So you can wait, but I'm saying you're not going to wait indefinitely. You abort whatever you've done, if you've updated things, or to read.
Em có thể chờ, nhưng ý thầy là em sẽ không chờ vô thời hạn. Em hủy bỏ mọi thứ đã làm, nếu em đã cập nhật hay đọc.
You just bounce out of the data structure and go back and try again.
Em chỉ cần thoát ra khỏi cấu trúc dữ liệu rồi quay lại thử lại.
Because the idea is that by the time you come back and try it another time, the latch you couldn't acquire before may now be available. And it's super simple to implement.
Vì ý tưởng là đến lúc em quay lại và thử lần nữa, thì latch mà trước đó em không lấy được có thể đã sẵn sàng. Và nó cực kỳ đơn giản để triển khai.
And it works in general practice, yes.
Và trong thực tế nói chung thì nó hoạt động tốt, vâng.
The statement is, in practice, are there starvation problems? Yes, absolutely could be. That's what I'm saying.
Câu hỏi là, trong thực tế, liệu có vấn đề starvation không? Có, hoàn toàn có thể xảy ra. Đó là điều tôi đang nói.
That's why you have a higher-level mechanism in your system keeping track of like, oh, I've tried to do this a bunch of times and I can't do it.
Đó là lý do bạn cần một cơ chế ở mức cao hơn trong hệ thống để theo dõi, kiểu như, ồ, mình đã thử làm việc này nhiều lần rồi mà không làm được.
Let me pause all the workers and prevent them from getting in this data structure until you go do what you need to do.
Hãy tạm dừng tất cả các worker và ngăn chúng đi vào cấu trúc dữ liệu này cho đến khi bạn làm xong việc cần làm.
Now, if everybody's trying to update the exact same key, then you're basically single-threaded. There's nothing you can do.
Còn nếu mọi người đều cố cập nhật đúng cùng một khóa, thì về cơ bản bạn chỉ chạy đơn luồng. Bạn không thể làm gì được.
If everyone's trying to update, I don't know, reads are easy, but everyone's trying to update Taylor Swift's message board or something like that. I'm trying to write this one record over and over again.
Nếu mọi người đều cố cập nhật, ví dụ, đọc thì dễ, nhưng mọi người đều cố cập nhật bảng tin của Taylor Swift chẳng hạn. Tôi cứ ghi đi ghi lại cùng một bản ghi này.
That's basically, you're just lined up single-threaded. Nothing you can do. All right, so everything I've said so far is basically reiterated in the slide. The simplest thing is again, just killing yourself.
Về cơ bản là mọi người xếp hàng chạy đơn luồng. Không làm gì được. Được rồi, mọi thứ tôi nói cho đến giờ về cơ bản được nhắc lại trên slide. Cách đơn giản nhất, một lần nữa, là tự hủy bản thân.
Because again, there isn't going to be any mechanism to handle deadlocks, to detect them and break them automatically. When we talk about transactions, it'll do that, right? The best protocol is this no-wait mode.
Vì một lần nữa, sẽ không có cơ chế nào để xử lý bế tắc, để phát hiện và tự động phá vỡ chúng. Khi nói về giao dịch, nó sẽ làm việc đó, đúng không? Giao thức tốt nhất là chế độ no-wait này.
Basically, Don't wait to try to acquire the latch. If I can't get it, immediately kill myself. Again, you can relax that a little bit. You wait a small amount and then try.
Về cơ bản là đừng chờ để cố lấy latch. Nếu không lấy được, lập tức tự hủy. Một lần nữa, bạn có thể nới lỏng một chút. Chờ một khoảng nhỏ rồi thử.
And then the amount you wait for every single high-level operation retry will be the same.
Và khoảng thời gian bạn chờ cho mỗi lần thử lại của một thao tác ở mức cao sẽ như nhau.
So for writes, we've talked about this sort of briefly, but anytime I make a change to a leaf node, I want to hold the write latch on that node.
Với các thao tác ghi, chúng ta đã nói sơ qua về điều này, nhưng bất cứ khi nào tôi thay đổi một nút lá, tôi muốn giữ write latch trên nút đó.
Because I don't know whether I'm going to have to roll back because I can't get a latch on some other node.
Vì tôi không biết liệu mình có phải rollback hay không do không lấy được latch trên một nút khác.
So to keep track of what changes I made is basically this thread local storage or worker local storage where I have what's called the write set.
Để theo dõi những thay đổi đã thực hiện, về cơ bản có thread local storage hay worker local storage, nơi tôi có cái gọi là write set.
But basically for every node that I've touched, I have the write latch on a leaf node. Here's the list of the keys I've inserted and deleted.
Về cơ bản, với mỗi nút mà tôi đã chạm tới, tôi giữ write latch trên một nút lá. Đây là danh sách các khóa tôi đã chèn và xóa.
Because now if I go ahead and do a, if I can't acquire the latch, I have to roll back, I basically want to undo all those changes and then jump out of the data structure.
Vì giờ nếu tôi tiếp tục làm, nếu không lấy được latch, tôi phải rollback, về cơ bản tôi muốn hoàn tác tất cả các thay đổi đó rồi thoát ra khỏi cấu trúc dữ liệu.
Now, split the merge is a bit more tricky because it may be the case that I did insert, delete, and I then reorganize the data structure.
Còn split và merge thì phức tạp hơn một chút vì có thể tôi đã chèn, xóa, rồi sau đó tổ chức lại cấu trúc dữ liệu.
It'd be kind of expensive to go ahead and undo all of that.
Hoàn tác tất cả những việc đó sẽ khá tốn kém.
So sometimes, this is what we said two lectures ago, sometimes it may be okay to be slightly unbalanced and not do a complete reversal of a split.
Vì vậy, đây là điều chúng ta đã nói cách đây hai bài giảng, đôi khi có thể chấp nhận để cây hơi mất cân bằng và không hoàn tác hoàn toàn một lần split.
The data structure still has the keys sort of pointing in the right direction, but it's really cheap for me then to undo any changes that I needed because I just removed maybe the key I inserted that caused the split.
Cấu trúc dữ liệu vẫn có các khóa trỏ đúng hướng, nhưng khi đó việc hoàn tác bất kỳ thay đổi nào tôi cần sẽ rất rẻ vì tôi chỉ vừa xóa khóa mà tôi đã chèn vào, thứ gây ra việc tách nút.
But it's still in the sort of that post split layout.
Nhưng cấu trúc vẫn giữ bố cục như sau khi đã tách.
And then at some later point, if I continue to insert and delete, all that will get washed away and put back in the correct order. And that's okay. Okay? All right.
Rồi đến một lúc nào đó về sau, nếu tôi tiếp tục chèn và xóa, tất cả những thứ đó sẽ bị xóa sạch và được đặt lại đúng thứ tự. Và như vậy là ổn. Được chứ? Được rồi.
We're out of time for going over project two, but I can cover that next class.
Chúng ta hết giờ để nói về project hai rồi, nhưng tôi sẽ nói trong buổi sau.
But again, the main takeaway from all this is the data structure, making them thread safe is super, super tricky. This is what you'll be doing in project two.
Nhưng một lần nữa, điều chính rút ra từ tất cả những điều này là với các cấu trúc dữ liệu, việc làm cho chúng an toàn đa luồng là cực kỳ khó. Đây là việc các bạn sẽ làm trong project hai.
And so the way to get started in project two is start with not making it multi-threaded. Just do single threaded first, because it'll make your life easier.
Và cách để bắt đầu project hai là bắt đầu bằng việc chưa làm nó đa luồng. Cứ làm đơn luồng trước, vì như vậy sẽ dễ hơn cho các bạn.
And then worry about adding those things later on.
Rồi sau đó hãy lo việc thêm những phần đó.
So next class, we're now going to talk about how to build all the stuff we've done, the things we've done so far, and start actually running real queries.
Vậy buổi sau, chúng ta sẽ nói về cách xây dựng trên tất cả những gì đã làm, những thứ chúng ta đã làm cho đến giờ, và bắt đầu chạy các truy vấn thực sự.
So we'll start with the algorithms run from operators and build from there to run complete query plans. Okay? All right. Hit it.
Chúng ta sẽ bắt đầu với các thuật toán chạy từ các toán tử và từ đó xây dựng để chạy các kế hoạch truy vấn hoàn chỉnh. Được chứ? Được rồi. Bắt đầu thôi.
Đă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.