Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
Alright, again, give it up for DJ Cash, awesome.
Được rồi, một lần nữa, xin một tràng pháo tay cho DJ Cash, tuyệt vời.
Again, I apologize for being out of town last week. I was in London. If you watched the last video, it was bizarre.
Một lần nữa, tôi xin lỗi vì tuần trước đã đi vắng. Tôi đã ở London. Nếu các bạn đã xem video lần trước thì thấy nó rất kỳ quặc.
Your friend, so Cash is his old friend, Fat Miss Red, that owes you money. I was supposed to get your money. I did not get your money.
Bạn của các bạn, Cash là người bạn cũ của anh ta, Fat Miss Red, người nợ các bạn tiền. Tôi lẽ ra phải lấy tiền cho các bạn. Tôi đã không lấy được tiền của các bạn.
Like, he, like, whatever, took some drugs and then walking around like the bad parts of London and, like, got beat up by 12 year olds.
Kiểu như, anh ta, kiểu như, sao cũng được, dùng ma túy rồi đi lang thang ở những khu tồi tệ của London và, kiểu như, bị lũ nhóc 12 tuổi đánh.
So we had 12 year old kids. It was super bizarre. He was fucked up. What was I supposed to do? Alright, sorry.
Thế là có mấy đứa trẻ 12 tuổi. Cực kỳ kỳ quặc. Anh ta tơi tả luôn. Tôi biết làm gì được đây? Thôi, xin lỗi nhé.
Yeah, so I apologize for not being around. That was a weird one. That's a new one for me. Okay, so let's open this.
Vâng, nên tôi xin lỗi vì đã không có mặt. Chuyện đó thật kỳ lạ. Đây là chuyện mới với tôi. Được rồi, bắt đầu thôi.
So the, again, Project Zero and Homework One were due last night. Everyone should have completed Project Zero. We're going to go over the grades later today with the TAs.
Vậy, Project Zero và Homework One đã đến hạn vào tối qua. Mọi người đều phải hoàn thành Project Zero. Lát nữa hôm nay chúng ta sẽ xem điểm cùng các trợ giảng.
And again, you have to get 100 on this by last night in order to be allowed to take the class.
Và một lần nữa, các bạn phải đạt 100 điểm bài này trước tối qua thì mới được học lớp này.
Project One we hope to release later today and that will be due at the end of the month, and that's going to be related to what today's class will be about.
Project One chúng tôi hy vọng sẽ phát hành vào cuối ngày hôm nay và hạn nộp sẽ là cuối tháng, và nó sẽ liên quan đến nội dung của buổi học hôm nay.
Okay? The source code is not pushed yet. So everyone will have to sort of do a git pull and merge in the latest version of the main branch into your local code.
Được chứ? Mã nguồn vẫn chưa được đẩy lên. Vì vậy mọi người sẽ phải git pull và hợp nhất phiên bản mới nhất của nhánh main vào mã cục bộ của mình.
Okay? The other thing coming up next week on Monday and Tuesday is that we're having our visit day for all our friends in the database industry. So there's two days, Monday and Tuesday.
Được chứ? Việc khác sắp tới vào thứ Hai tuần sau và thứ Ba là chúng ta có ngày đón tiếp tất cả bạn bè của chúng ta trong ngành cơ sở dữ liệu. Vậy là có hai ngày, thứ Hai và thứ Ba.
Obviously the class is on Monday but we'll duck out and teach that and then we can always go back.
Rõ ràng thứ Hai có lớp, nhưng chúng ta sẽ lẻn ra để dạy xong rồi lúc nào cũng có thể quay lại.
So the first day was sort of research talks and some intro talks from the companies.
Ngày đầu tiên là các buổi báo cáo nghiên cứu và một số buổi giới thiệu từ các công ty.
And then on the Tuesday in the morning, that'll be these info sessions where each company will present for about an hour, talk about what their system is, what they're building, And they talk a little about internships and full-time positions as well.
Rồi vào sáng thứ Ba, sẽ có các buổi thông tin, mỗi công ty trình bày khoảng một giờ, nói về hệ thống của họ là gì, họ đang xây dựng gì. Họ cũng nói đôi chút về thực tập và vị trí toàn thời gian.
So that's why I posted on Piazza over the weekend or Friday, whatever that was.
Đó là lý do tôi đã đăng trên Piazza hồi cuối tuần hoặc thứ Sáu, không nhớ nữa.
So if you want to come to these sessions, since we're having, since we only have so many time slots, there'll be some overlap between two companies giving the same talk or giving different talks at the same time in different rooms.
Nên nếu các bạn muốn tham dự các buổi này, vì chúng ta có, vì chúng ta chỉ có số khung giờ nhất định, sẽ có một số trùng lặp giữa hai công ty trình bày cùng một nội dung hoặc trình bày các nội dung khác nhau cùng lúc ở các phòng khác nhau.
So just put down what your preference is, and then you just run whatever stable marriage algorithm generated by ChatGPT to figure out the best schedule for everyone.
Vậy hãy ghi lại lựa chọn ưu tiên của các bạn, rồi chỉ cần chạy một thuật toán stable marriage nào đó do ChatGPT tạo ra để tìm lịch tốt nhất cho mọi người.
And then if you want to, as I posted on this as well, if you want to get a database job, either internship or full-time position, go to that Piazza post there, and then there's a spreadsheet.
Và nếu muốn, như tôi cũng đã đăng về việc này, nếu các bạn muốn tìm việc về cơ sở dữ liệu, thực tập hoặc toàn thời gian, hãy vào bài đăng Piazza đó, có một bảng tính.
Just add yourself, what you're looking for, when you're available, and then we send that out to all our database friends, including the companies that are coming next week, so we want to get this out to them before they show up.
Chỉ cần thêm tên mình, bạn đang tìm gì, khi nào bạn rảnh, rồi chúng tôi sẽ gửi cho tất cả bạn bè trong ngành cơ sở dữ liệu, bao gồm cả các công ty sẽ đến vào tuần sau, nên chúng tôi muốn gửi danh sách này cho họ trước khi họ đến.
And then we have other database friends as well, we send it to everyone else. And again, this doesn't go to recruiters, except for some rare cases.
Và chúng tôi còn có những người bạn khác trong giới cơ sở dữ liệu, chúng tôi cũng gửi cho tất cả những người đó. Và một lần nữa, danh sách này không gửi cho nhà tuyển dụng, trừ một vài trường hợp hiếm.
This goes to the people that are like co-founders or like VP engineering, the hiring managers for the companies.
Nó được gửi cho những người như đồng sáng lập hoặc phó giám đốc kỹ thuật, tức là các quản lý tuyển dụng của các công ty.
So it's not like if you go to Microsoft's website, you fill out for an internship, that's just going in the pool with everyone else.
Vậy nên nó không giống như việc bạn vào trang web của Microsoft, nộp đơn xin thực tập, rồi hồ sơ của bạn chỉ nằm chung trong đống hồ sơ với mọi người khác.
We try to skip all that and go directly to the people that care about databases. They know what this course is. Yes.
Chúng tôi cố bỏ qua tất cả những bước đó và đến thẳng những người quan tâm đến cơ sở dữ liệu. Họ biết môn học này là gì. Vâng, mời em.
The statement is, we haven't learned that much about databases yet. Don't say that. Actually, here's the weirdest shit I've ever heard.
Ý em là chúng ta vẫn chưa học được bao nhiêu về cơ sở dữ liệu. Đừng nói vậy. Thật ra, đây là chuyện kỳ quặc nhất mà tôi từng nghe.
So I know that a bunch of database companies use this class for onboarding new employees.
Tôi biết có khá nhiều công ty cơ sở dữ liệu dùng lớp này để đào tạo nhân viên mới.
I had somebody tell me last week in London that they were not a database person, a company wanted to interview them for a database job, And he's like, he told them straight up, "I don't know anything about databases."
Tuần trước ở London, có một người nói với tôi rằng anh ấy vốn không phải dân cơ sở dữ liệu, một công ty muốn phỏng vấn anh ấy cho một vị trí về cơ sở dữ liệu, và anh ấy nói thẳng với họ: "Tôi không biết gì về cơ sở dữ liệu cả."
They sent him this class to prep for the job interview. I didn't know you could do that. And he got the job.
Họ gửi anh ấy lớp này để chuẩn bị cho buổi phỏng vấn. Tôi không biết là có thể làm vậy. Và anh ấy đã được nhận.
This, yes. Yeah. For the advanced class, one of our projects used to be another database company; basically, you took it, and that was the hacker challenge to hire you.
Đây, mời em. Vâng. Với lớp nâng cao, trước đây một trong các dự án của chúng tôi là của một công ty cơ sở dữ liệu khác; về cơ bản, bạn làm dự án đó, và đó chính là thử thách lập trình để họ tuyển bạn.
They would make you implement something that we were having you do in the class. So if you do the class, this is 721, you can show up and get hired easily.
Họ sẽ yêu cầu bạn cài đặt một thứ mà chúng tôi cũng cho bạn làm trong lớp. Vậy nên nếu bạn học lớp này, tức là 721, bạn có thể đến và được tuyển rất dễ dàng.
Anyway, so any questions about this, post on Piazza, and then please join us next week. Okay?
Dù sao thì, nếu có câu hỏi nào về việc này, hãy đăng lên Piazza, và xin mời các bạn tham gia cùng chúng tôi vào tuần sau. Được chứ?
All right, so last class, again, it was awkward because I had to teach it in the emergency room, but we spent time talking about what databases look like at the lowest level on disk.
Được rồi, buổi học trước, nhắc lại, hơi ngượng một chút vì tôi phải dạy ngay trong phòng cấp cứu, nhưng chúng ta đã dành thời gian nói về việc cơ sở dữ liệu trông như thế nào ở mức thấp nhất trên đĩa.
Again, at the end of the day, a database system, it's just the files on disk. There's nothing really special about them.
Rốt cuộc, một hệ cơ sở dữ liệu chỉ là các tệp trên đĩa. Chúng không có gì đặc biệt cả.
It's, from the OS's perspective, as if you open up VM or Emacs, whatever your favorite editor is, and create the file, start writing data into it. That's basically what the database system is doing.
Từ góc nhìn của hệ điều hành, nó giống như việc bạn mở VM hoặc Emacs, hay bất kỳ trình soạn thảo nào bạn thích, rồi tạo một tệp và bắt đầu ghi dữ liệu vào đó. Về cơ bản, đó là những gì hệ cơ sở dữ liệu đang làm.
And of course, how we layered the different concepts on top of each other, that sort of makes it so we can do more sophisticated things as we get further along in the semester.
Và tất nhiên, cách chúng ta xếp chồng các khái niệm khác nhau lên nhau giúp chúng ta có thể làm những việc phức tạp hơn khi chúng ta đi xa hơn trong học kỳ.
So today's class is now to jump ahead and say, okay, well, I have a bunch of files on disk.
Vậy buổi học hôm nay sẽ nhảy lên bước tiếp theo và nói rằng, được rồi, tôi có một loạt tệp trên đĩa.
In order for me to do anything with those files, I got to bring them into memory, right?
Để làm bất cứ điều gì với những tệp đó, tôi phải đưa chúng vào bộ nhớ, đúng không?
The classic Von Neumann architecture: I got to bring them to memory, and then I can manipulate them, serve queries, whatever I want.
Kiến trúc Von Neumann kinh điển: tôi phải đưa chúng vào bộ nhớ, rồi sau đó tôi có thể thao tác trên chúng, phục vụ truy vấn, hay làm bất cứ điều gì tôi muốn.
And so today's class is really about the management, or the movement, of data from disk into memory, and then back to disk again.
Và vì vậy buổi học hôm nay thực sự nói về việc quản lý, hay việc di chuyển, dữ liệu từ đĩa vào bộ nhớ, rồi lại từ bộ nhớ ghi về đĩa.
We'll talk a little bit about that, how we handle dirty writes, later in the semester.
Chúng ta sẽ nói một chút về điều đó, cách chúng ta xử lý các thao tác ghi dirty, ở phần sau của học kỳ.
Sorry, in this class, we'll go into more detail how we make sure we do things safely right back to disk later, after the midterm.
Xin lỗi, trong lớp này, chúng ta sẽ đi vào chi tiết hơn về cách bảo đảm làm mọi thứ an toàn khi ghi ngược trở lại đĩa, sau kỳ thi giữa kỳ.
But for now, we're just trying to say, can we copy things in, and then how do we serve them up?
Nhưng hiện tại, chúng ta chỉ đang tự hỏi: liệu có thể sao chép dữ liệu vào, rồi phục vụ chúng như thế nào?
And then next week, today's Monday, so starting Wednesday, we'll actually go back down, so back to problem number one, and talk about alternative approaches to storing data as files on disk.
Và tuần tới, hôm nay là thứ Hai, nên bắt đầu từ thứ Tư, chúng ta sẽ quay xuống tầng dưới, tức là quay lại vấn đề số một, và nói về các cách tiếp cận thay thế để lưu trữ dữ liệu dưới dạng tệp trên đĩa.
But the buffer pool stuff, the memory management stuff we're talking about today will still be relevant for those other design schemes.
Nhưng phần về buffer pool, phần quản lý bộ nhớ mà hôm nay chúng ta nói đến vẫn sẽ còn phù hợp với những mô hình thiết kế khác đó.
All right, so in databases, we care about, or data systems, we care about basically two ideas.
Được rồi, vậy trong cơ sở dữ liệu, chúng ta quan tâm đến, hay các hệ thống dữ liệu, về cơ bản chúng ta quan tâm đến hai ý tưởng.
There's two concepts that we need to be mindful of when we decide how we want to organize things on disk, how we want to bring things into memory, what algorithms we may want to use to process data or write to data, write data to disk, and so forth.
Có hai khái niệm chúng ta cần lưu ý khi quyết định muốn tổ chức dữ liệu trên đĩa như thế nào, muốn đưa dữ liệu vào bộ nhớ ra sao, có thể muốn dùng thuật toán nào để xử lý dữ liệu hoặc ghi dữ liệu, ghi dữ liệu xuống đĩa, v.v.
So the first idea is the notion of spatial control, and that's the idea of keeping track of, being mindful about, where we're going to write our data on disk so that when we have to read things again, we can do so, we can try to maximize the amount of sequential access that we have.
Ý tưởng đầu tiên là khái niệm kiểm soát không gian (spatial control), tức là ý tưởng theo dõi, lưu tâm đến việc chúng ta sẽ ghi dữ liệu ở đâu trên đĩa để khi phải đọc lại, chúng ta có thể làm được, và cố gắng tối đa hóa lượng truy cập tuần tự.
And I said last class that random I/O is much more expensive than sequential I/O.
Và tôi đã nói ở buổi trước rằng I/O ngẫu nhiên tốn kém hơn nhiều so với I/O tuần tự.
It's a little less of an issue in modern SSDs, but if you have any kind of rotating device, like a spinning disk hard drive, that is, there's a huge difference in the access times for sequential I/O versus random I/O, right?
Với SSD hiện đại thì vấn đề này nhẹ hơn một chút, nhưng nếu bạn có bất kỳ thiết bị quay nào, như ổ cứng đĩa quay, thì có sự chênh lệch rất lớn về thời gian truy cập giữa I/O tuần tự và I/O ngẫu nhiên, đúng không?
So that means that when we start having to write data to disk, we want to put things that are going to be used with each other very often close to each other.
Nghĩa là khi bắt đầu phải ghi dữ liệu xuống đĩa, chúng ta muốn đặt những thứ thường được dùng cùng nhau ở gần nhau.
The other idea is this notion of temporal control, And it's the idea here that when we bring something into memory from disk, since that's a very expensive operation, the thing we're trying to minimize or avoid as much as possible, when we bring something into memory, we want to do as much work as we can on that data that we brought into memory
Ý tưởng còn lại là khái niệm kiểm soát thời gian (temporal control), và ý tưởng ở đây là khi chúng ta đưa thứ gì đó từ đĩa vào bộ nhớ, vì đó là một thao tác rất tốn kém, thứ mà chúng ta cố gắng giảm thiểu hoặc tránh càng nhiều càng tốt, nên khi đưa thứ gì đó vào bộ nhớ, chúng ta muốn làm càng nhiều việc càng tốt trên dữ liệu vừa đưa vào bộ nhớ đó
before we give it up, before we release the memory or write some changes back to the disk, right?
trước khi bỏ nó đi, trước khi giải phóng bộ nhớ hoặc ghi một số thay đổi trở lại đĩa, đúng không?
Because the worst thing to do is, like, I've got to read three blocks, or say, I've got to read two blocks, and I can read the first one twice and the second one once.
Vì điều tệ nhất là, chẳng hạn, tôi phải đọc ba khối, hay nói là, tôi phải đọc hai khối, và tôi có thể đọc khối đầu hai lần và khối thứ hai một lần.
I don't want to read the first one, do some work on it, throw it away, read the second one, do some work on it, throw it away, and then go back and get the first one again, right?
Tôi không muốn đọc khối đầu, xử lý một chút, vứt nó đi, đọc khối thứ hai, xử lý một chút, vứt nó đi, rồi lại quay lại lấy khối đầu một lần nữa, đúng không?
I want to maximize the amount of work I can do for every single page I'm bringing in from disk.
Tôi muốn tối đa hóa lượng công việc có thể làm cho mỗi trang mà tôi đưa vào từ đĩa.
And we'll see alternative storage models next week, or Monday next week, how you can go to town on this and avoid reading things you don't even need for queries.
Và chúng ta sẽ thấy các mô hình lưu trữ thay thế vào tuần tới, hay thứ Hai tuần tới, bạn có thể tận dụng triệt để điều này như thế nào và tránh đọc những thứ mà truy vấn thậm chí không cần đến.
For today's class, we're going to mostly ignore that. So going back to that architecture I showed last class, right, at the lowest level you have the disk, and, again, this is the non-volatile storage.
Với buổi học hôm nay, chúng ta sẽ chủ yếu bỏ qua phần đó. Vậy quay lại kiến trúc mà tôi đã trình bày ở buổi trước, đúng không, ở tầng thấp nhất bạn có đĩa, và một lần nữa, đây là bộ nhớ lưu trữ không bay hơi.
This is considered the permanent location of the database, the resting point of it. And then we have some kind of database file that's going to be broken up into pages.
Đây được coi là nơi lưu trữ lâu dài của cơ sở dữ liệu, nơi nó nằm yên. Rồi chúng ta có một dạng tệp cơ sở dữ liệu nào đó sẽ được chia nhỏ thành các trang.
And then we said that at the beginning of the database file, or at some location that's special, we know where to find these things, we have a page directory.
Và chúng ta đã nói rằng ở đầu tệp cơ sở dữ liệu, hoặc ở một vị trí đặc biệt nào đó, mà ta biết tìm những thứ này ở đâu, có một page directory.
This is just a sort of a database of the database pages that I have.
Nó giống như một cơ sở dữ liệu của chính các trang cơ sở dữ liệu mà tôi có.
So keeping track of, like, I want this page for this data, or, sorry, for this database, for this table, for some file. Here's where to go find the offset where I need it.
Tức là theo dõi xem, chẳng hạn, tôi muốn trang này cho dữ liệu này, hoặc xin lỗi, cho cơ sở dữ liệu này, cho bảng này, cho tệp nào đó. Đây là nơi cần đến để tìm offset mà tôi cần.
This diagram here, I'm showing the database is comprised of one file. That's what SQLite does, and DuckDB does. It could be multiple files across multiple directories, or even across multiple machines.
Trong sơ đồ này, tôi đang minh họa cơ sở dữ liệu gồm một tệp. SQLite và DuckDB làm như vậy. Nó có thể là nhiều tệp trên nhiều thư mục, hoặc thậm chí trên nhiều máy.
But for now, we don't care about that. And then up above the disk, we have the volatile storage. We said this is just memory.
Nhưng hiện giờ chúng ta không quan tâm đến điều đó. Và phía trên đĩa, chúng ta có bộ nhớ bay hơi. Chúng ta đã nói đây chỉ là bộ nhớ.
And in this, now we're going to have, we're going to talk about today, the buffer pool.
Và trong đó, bây giờ chúng ta sẽ có, hôm nay chúng ta sẽ nói về buffer pool.
And this is going to be some region of memory that's been allocated that's in the address space of our database system that we can use to put pages that we fetch from disk into memory so that we can hand them off to other parts of the system.
Đây sẽ là một vùng bộ nhớ được cấp phát, nằm trong không gian địa chỉ của hệ quản trị cơ sở dữ liệu mà ta dùng để đặt các trang lấy từ đĩa vào bộ nhớ để có thể chuyển chúng cho các phần khác của hệ thống.
So in memory, we have our buffer pool. We're going to say that the placeholders, the locations where we can store pages from disk into memory, we're going to call these frames.
Vậy trong bộ nhớ, chúng ta có buffer pool. Chúng ta sẽ gọi các chỗ giữ chỗ, những vị trí mà ta có thể lưu các trang từ đĩa vào bộ nhớ, là các frame.
All right? And that's to say that this thing is a giant byte buffer, and we have some offsets where a frame starts, and we can put a page directly in there.
Được chứ? Nghĩa là thứ này là một bộ đệm byte khổng lồ, và có các offset nơi một frame bắt đầu, và ta có thể đặt trực tiếp một trang vào đó.
Because all the pages within a single file are going to be the same size, these frames can be reused, and we know how to easily jump to different offsets.
Vì mọi trang trong cùng một tệp có cùng kích thước, các frame này có thể tái sử dụng, và ta dễ dàng nhảy tới các offset khác nhau.
They're called frames because we're running out of words. We already have pages. Sometimes it's called blocks. We don't call them a buffer because the whole thing is called a buffer or cache.
Chúng được gọi là frame vì chúng ta sắp hết từ rồi. Đã có page rồi. Đôi khi còn gọi là block. Ta không gọi chúng là buffer vì cả thứ này đã được gọi là buffer hoặc cache.
So we're calling them frames because that's all we got. So then we have an execution engine. And again, this thing is where we're actually executing queries.
Nên ta gọi chúng là frame vì chỉ còn từ đó. Tiếp theo chúng ta có một execution engine. Và một lần nữa, đây là nơi thực sự thực thi các truy vấn.
And as it's running, somehow it says I want to read some data, and it's in page 2.
Khi nó đang chạy, bằng cách nào đó nó nói rằng tôi muốn đọc một số dữ liệu, và dữ liệu đó nằm ở trang 2.
It doesn't know where page 2 is, but it knows it can talk to the buffer pool manager, and it exposes an API that allows you to go get page 2.
Nó không biết trang 2 ở đâu, nhưng nó biết có thể trao đổi với buffer pool manager, và bộ quản lý này cung cấp một API cho phép bạn đi lấy trang 2.
So in order to figure out where page 2 is, we've got to bring the page directory in. I'm showing you this as a sort of separate step.
Vậy để biết trang 2 nằm ở đâu, chúng ta phải nạp page directory vào. Tôi chỉ cho các bạn thấy đây như một bước riêng biệt.
In actuality, when the system boots up, you usually load that in the very first thing you do because you need to know what's in there.
Thực tế, khi hệ thống khởi động, bạn thường nạp nó ngay từ đầu tiên, vì bạn cần biết bên trong đó có gì.
But for now, it's fine. We're just showing it as a separate step. So now we consult the page directory. And then that tells us where we want to find page 2.
Nhưng tạm thời thì không sao. Ta chỉ đang trình bày nó như một bước riêng. Bây giờ ta tra cứu page directory. Và nó cho ta biết cần tìm trang 2 ở đâu.
We find a free frame in our buffer pool where we just copy that page from disk into memory.
Ta tìm một frame trống trong buffer pool để sao chép trang đó từ đĩa vào bộ nhớ.
And then now we hand back the execution engine a pointer to that page in that frame.
Rồi sau đó ta trả lại cho execution engine một con trỏ tới trang đó trong frame ấy.
And the guarantee that the buffer pool manager is going to provide for the rest of our system is that if we go tell this execution engine, "Here's a pointer to the page that you wanted," that pointer will be valid until that execution engine, or whatever asks for that page, comes back and says, "I'm done with it."
Và đảm bảo mà buffer pool manager sẽ cung cấp cho phần còn lại của hệ thống là: nếu ta nói với execution engine này rằng "Đây là con trỏ tới trang mà bạn muốn," thì con trỏ đó sẽ còn hợp lệ cho đến khi execution engine đó, hoặc bất cứ thứ gì yêu cầu trang đó, quay lại và nói: "Tôi dùng xong rồi."
We'll talk about how we do that in a second.
Lát nữa ta sẽ nói về cách thực hiện điều đó.
Now, the cool thing about the buffer pool manager is that we can actually reorder and change the location of a page any way that we want if we have to bring it in multiple times.
Điều hay của buffer pool manager là ta thực sự có thể sắp xếp lại và thay đổi vị trí của một trang theo bất cứ cách nào ta muốn nếu phải nạp nó nhiều lần.
So let's say now we run some kind of eviction policy. We decide that we want to throw away page 2 to free memory.
Giả sử bây giờ ta chạy một chính sách loại bỏ (eviction) nào đó. Ta quyết định bỏ trang 2 để giải phóng bộ nhớ.
Realize we have a free space. We would have kept it, but we can ignore that. So then now the execution engine comes back and says, "Hey, I want page 2 again."
Lưu ý là ta còn chỗ trống. Lẽ ra ta sẽ giữ lại, nhưng cứ bỏ qua điều đó. Sau đó execution engine quay lại và nói: "Này, tôi muốn trang 2 một lần nữa."
The buffer pool manager would recognize that it doesn't have that page in memory. It's got to go back to disk and get it. But now it's going to copy into this frame.
Buffer pool manager sẽ nhận ra là nó không có trang đó trong bộ nhớ. Nó phải quay lại đĩa để lấy. Nhưng lần này nó sẽ sao chép vào frame này.
And it hands back that pointer to the database system or the execution engine. And that's perfectly fine.
Và nó trả lại con trỏ đó cho hệ cơ sở dữ liệu hay execution engine. Và như vậy hoàn toàn ổn.
It's just an address in memory telling you, here's where to go find the thing that you wanted. What's that? The question is, what about the previous pointer going back here?
Đó chỉ là một địa chỉ trong bộ nhớ cho bạn biết nơi cần đến để tìm thứ bạn muốn. Sao cơ? Câu hỏi là: còn con trỏ trước đó quay lại đây thì sao?
So at some point when we hand off this pointer, the contract is, I'm giving you this memory. You've got to tell me when you're done with it.
Thì tại một thời điểm nào đó khi ta trao con trỏ này đi, thỏa thuận là: tôi đưa bạn vùng bộ nhớ này. Bạn phải báo cho tôi khi dùng xong.
So at some point, the execution engine says, oh, I'm done with it. That's why we were allowed to then evict it. What's that?
Vậy đến một lúc nào đó, execution engine nói: à, tôi dùng xong rồi. Đó là lý do ta được phép loại bỏ nó. Sao cơ?
It's something like reference counting. Yes. But we'll get there in a second. But there's more. Yeah.
Nó giống như đếm tham chiếu. Đúng vậy. Nhưng lát nữa ta sẽ tới đó. Nhưng còn nhiều nữa. Vâng.
The question is, what if the execution engine asks for more frames than are in memory? We've got to throw things away. We'll handle that.
Câu hỏi là: nếu execution engine yêu cầu nhiều frame hơn số frame có trong bộ nhớ thì sao? Ta phải bỏ bớt đi. Ta sẽ xử lý việc đó.
The whole point is, like we said at the beginning, we want to give the illusion that we have more memory than we actually do. So we'll have to handle that ourselves. Other questions? Yes.
Mấu chốt là, như đã nói lúc đầu, ta muốn tạo ảo giác rằng mình có nhiều bộ nhớ hơn thực tế. Nên ta sẽ phải tự xử lý việc đó. Còn câu hỏi nào khác không? Vâng.
The question is, is it random how the frames are being selected by the execution engine or for eviction?
Câu hỏi là: các frame được execution engine chọn hay được chọn để loại bỏ có phải là ngẫu nhiên không?
How do we decide which frame? We'll cover that in a second.
Ta quyết định chọn frame nào? Lát nữa ta sẽ đề cập.
But we want to write the rest of the system, the execution engine, so that we don't actually care. It could be random. Who cares? Did you ask me for this page?
Nhưng ta muốn viết phần còn lại của hệ thống, tức execution engine, sao cho nó thực sự không cần quan tâm. Có thể là ngẫu nhiên. Ai quan tâm chứ? Em có hỏi tôi trang này không?
Here's the memory for it. Go for it. Yes.
Đây là vùng nhớ cho nó. Cứ dùng đi. Vâng.
The question is, is the size ratio from a page to a frame one-to-one? Yes, it has to be. And we'll talk about it.
Câu hỏi là: tỉ số kích thước giữa một trang và một frame có phải là một-một không? Có, bắt buộc phải như vậy. Và chúng ta sẽ nói về điều này.
There are some advanced systems like IBM DB2 where you can actually have a buffer pool that has different page sizes per table, per index.
Có một số hệ thống nâng cao như IBM DB2 mà ở đó bạn thực sự có thể có một buffer pool với kích thước trang khác nhau cho mỗi bảng, mỗi chỉ mục.
And you can even specify what the replacement policy should be per buffer pool instance. But in general, it has to be like, if I'm reading from this...
Và bạn thậm chí có thể chỉ định chính sách thay thế cho từng thể hiện buffer pool. Nhưng nhìn chung, nó phải như thế này: nếu tôi đọc từ cái này...
I know I'm reading from this database file on disk. It's organizing these database page sizes. My buffer pool has to have frames of those sizes. Okay.
Tôi biết mình đang đọc từ tệp cơ sở dữ liệu này trên đĩa. Nó tổ chức theo các kích thước trang cơ sở dữ liệu này. Buffer pool của tôi phải có các frame với những kích thước đó. Được chưa.
So I'm showing this example here that we're using the buffer pool to read disk pages or data pages for a database.
Ở đây tôi đang minh họa việc dùng buffer pool để đọc các trang đĩa hay trang dữ liệu của một cơ sở dữ liệu.
But actually, I'm going to be using these buffer pools for all the different parts of the database system.
Nhưng thực ra tôi sẽ dùng các buffer pool này cho tất cả các phần khác nhau của hệ cơ sở dữ liệu.
Basically, when the system boots up, when the database system boots up, you want to call malloc, get all the memory you're going to ever need to run queries, and then you're done.
Về cơ bản, khi hệ thống khởi động, khi hệ cơ sở dữ liệu khởi động, bạn muốn gọi malloc, lấy toàn bộ bộ nhớ bạn sẽ cần để chạy truy vấn, rồi xong.
You never want to have to go back to the OS and get more memory. Not every system does that. But in general, that's the ideal case.
Bạn không bao giờ muốn phải quay lại hệ điều hành để xin thêm bộ nhớ. Không phải hệ thống nào cũng làm vậy. Nhưng nhìn chung, đó là trường hợp lý tưởng.
Because the worst thing for me to do is start to try to do a malloc and get some memory I need for like a temp buffer, and then the OS says, "Look, I'm out."
Vì điều tệ nhất là tôi bắt đầu gọi malloc để lấy một ít bộ nhớ cần cho, chẳng hạn, một bộ đệm tạm, rồi hệ điều hành bảo: "Hết rồi nhé."
Right? You want to know that sooner rather than later.
Đúng không? Bạn muốn biết điều đó càng sớm càng tốt.
So in general, any time you're going to allocate memory, not from the stack, but anything from the heap for your application or your data system, you want that to come from one of these buffer pools.
Vì vậy nhìn chung, bất cứ khi nào bạn cấp phát bộ nhớ, không phải từ stack mà là bất cứ thứ gì từ heap cho ứng dụng hay hệ dữ liệu của bạn, bạn muốn nó đến từ một trong các buffer pool này.
Some of them will be backed by disk, meaning like if I, as you said, if I'm trying to allocate more memory than I actually have available to me, it can spill to disk.
Một số sẽ được hỗ trợ bởi đĩa, nghĩa là nếu tôi, như em nói, nếu tôi cố cấp phát nhiều bộ nhớ hơn mức tôi thực sự có, nó có thể tràn xuống đĩa.
Other times, you don't want to do that. Like if you just say, "I've run out of memory," then I almost killed the query. Right? So again, we won't really talk about these right now.
Những lúc khác, bạn không muốn làm vậy. Như nếu chỉ báo "hết bộ nhớ" thì coi như tôi suýt giết chết truy vấn. Đúng không? Nên bây giờ chúng ta sẽ chưa nói nhiều về những thứ này.
When we talk about join algorithms and sorting algorithms, that makes more sense, log buffers as well. Just be aware that there's memory being used for other things, other than just tuples for indexes.
Khi nói về các thuật toán join và thuật toán sắp xếp, chúng sẽ dễ hiểu hơn, cả log buffer nữa. Chỉ cần biết rằng bộ nhớ còn được dùng cho những thứ khác, chứ không chỉ cho các tuple của chỉ mục.
But the main one we want to focus on is those things. All right. So today, we're going to talk about the basics of what a buffer pool manager is.
Nhưng thứ chính chúng ta muốn tập trung là những cái đó. Được rồi. Hôm nay, chúng ta sẽ nói về những kiến thức cơ bản của buffer pool manager.
I think the textbook calls them a buffer cache, a buffer cache manager. Sometimes it's called a buffer manager. They're all basically the same thing.
Tôi nghĩ sách giáo trình gọi nó là buffer cache, buffer cache manager. Đôi khi nó được gọi là buffer manager. Về cơ bản chúng đều giống nhau.
It's managing the memory that the data system is going to use to run queries.
Nó quản lý bộ nhớ mà hệ dữ liệu sẽ dùng để chạy truy vấn.
Then we'll talk about my pet project, my pet topic, of why you don't want to use the operating system for any of this, because it's going to ruin your life.
Sau đó chúng ta sẽ nói về dự án tâm huyết của tôi, chủ đề tâm huyết của tôi, về lý do bạn không nên dùng hệ điều hành cho bất kỳ việc nào trong số này, vì nó sẽ phá hỏng cuộc đời bạn.
And then we'll talk about replacement policies: how to decide when we want to evict things, how to write things out to disk, and then do some additional optimizations.
Rồi chúng ta sẽ nói về các chính sách thay thế: cách quyết định khi nào muốn loại bỏ các trang, cách ghi dữ liệu ra đĩa, và sau đó là một số tối ưu hóa bổ sung.
All right. So the buffer pool, as I said, is just a bunch of memory that we've allocated in our data system that we're going to use to put in fixed-size pages.
Được rồi. Vậy buffer pool, như tôi đã nói, chỉ là một vùng bộ nhớ mà ta cấp phát trong hệ quản trị dữ liệu để chứa các trang có kích thước cố định.
And those locations within that giant array, each location where we could put a page in, we'll call that a frame.
Và những vị trí bên trong mảng khổng lồ đó, mỗi vị trí mà ta có thể đặt một trang vào, ta gọi là một frame.
So again, when other parts of the data system say, I want to get this page, they ask the buffer pool manager for it.
Vậy nên, khi các phần khác của hệ thống nói rằng họ muốn lấy trang này, họ sẽ hỏi buffer pool manager.
If it's available, if it's already in memory, then the buffer pool manager just hands back the pointer for it. If it's not available, then it has to decide what frame to put it in.
Nếu trang có sẵn, tức là đã nằm trong bộ nhớ, thì buffer pool manager chỉ cần trả về con trỏ tới nó. Nếu không có sẵn, thì nó phải quyết định đặt trang vào frame nào.
And if there's not a free frame, we'll have to handle that.
Và nếu không còn frame trống, ta sẽ phải xử lý tình huống đó.
And the page you're putting into memory that you're going to hand off to the other parts of the system, it'll be an exact copy of what is being read in from disk.
Còn trang mà bạn đưa vào bộ nhớ để chuyển giao cho các phần khác của hệ thống, sẽ là một bản sao chính xác của dữ liệu được đọc từ đĩa.
There isn't like... let me make sure this is true. If the low level, so you're using a storage appliance, it might do its own compression down below, actually at the hardware level.
Không có kiểu như... để tôi xác nhận lại điều này có đúng không. Nếu ở tầng thấp, tức là bạn dùng một thiết bị lưu trữ chuyên dụng, thì nó có thể tự nén dữ liệu ở bên dưới, thực ra là ở mức phần cứng.
But when you actually do a read against that file, you're going to get back the uncompressed bytes. And that's what the data system is going to hand back to the execution engine.
Nhưng khi bạn thực sự đọc từ tệp đó, bạn sẽ nhận lại các byte chưa nén. Và đó là thứ mà hệ quản trị dữ liệu sẽ trả lại cho execution engine.
Now, within that page, it actually may be compressed, and the data system knows how to interpret that compression. We'll see how we do that next week.
Còn bên trong trang đó, dữ liệu thực sự có thể đã được nén, và hệ quản trị dữ liệu biết cách diễn giải phần nén đó. Chúng ta sẽ xem cách làm điều đó vào tuần sau.
But in general, it's a one-to-one copy for whatever's on disk goes into memory. So if we look at an example like this, we have four pages on disk.
Nhưng nói chung, những gì có trên đĩa sẽ được sao chép một-một vào bộ nhớ. Vậy nếu xét một ví dụ như thế này, ta có bốn trang trên đĩa.
We want to read page one. The buffer pool manager is going to say, "All right, I got to put this somewhere."
Ta muốn đọc trang một. Buffer pool manager sẽ nói: "Được rồi, mình phải đặt nó ở đâu đó."
It picks the first frame, makes a copy into it, and that's it. All right? Now once we read page three, same thing, make a copy and go in there.
Nó chọn frame đầu tiên, sao chép vào đó, và xong. Đúng không? Tiếp theo khi đọc trang ba, cũng vậy, sao chép và đưa vào đó.
So the buffer pool is actually the memory location of where we actually store this.
Vậy buffer pool thực chất là vị trí bộ nhớ nơi ta lưu trữ các trang này.
There's an additional data structure called the page table that's going to sit in front of this memory, which is actually the entry point for how you find pages that are in memory or not, or check whether they're in memory or not.
Có thêm một cấu trúc dữ liệu gọi là page table nằm phía trước vùng bộ nhớ này, đây chính là điểm vào để tìm xem trang có nằm trong bộ nhớ hay không, hoặc để kiểm tra xem chúng có trong bộ nhớ hay không.
I think there's just another hash table where I do a lookup on the page ID, and then within that slot within that hash table, it's going to tell me whether the entry exists or not and where to go find it.
Tôi nghĩ đó chỉ là một hash table khác, nơi tôi tra cứu theo page ID, và sau đó trong ô đó của hash table, nó sẽ cho tôi biết mục đó có tồn tại hay không và tìm nó ở đâu.
So there's some additional metadata in here, sort of what they brought about, reference counting.
Ngoài ra còn có một số siêu dữ liệu bổ sung ở đây, kiểu như đếm tham chiếu.
I'm also going to keep track of how many times have I handed out this page to other parts of the system. It's called a pin counter, reference counter, same idea.
Tôi cũng sẽ theo dõi xem tôi đã giao trang này cho các phần khác của hệ thống bao nhiêu lần. Nó được gọi là pin counter, hay reference counter, cùng một ý tưởng.
And so you would say a page is pinned in memory means that some other part of the system currently has a pointer to that memory, and therefore I don't want to free that frame up and throw away whatever's in there, because I don't want some other part of the system to start reading and interpreting what's inside the page, and then I replace it with another page and now it starts getting garbage data or incorrect data.
Và ta nói một trang bị pin trong bộ nhớ nghĩa là có một phần khác của hệ thống hiện đang giữ con trỏ tới vùng nhớ đó, và do đó tôi không muốn giải phóng frame đó rồi vứt bỏ những gì đang có trong đó, vì tôi không muốn một phần khác của hệ thống đang đọc và diễn giải nội dung bên trong trang, rồi sau đó tôi thay nó bằng một trang khác và bây giờ nó bắt đầu nhận được dữ liệu rác hoặc dữ liệu sai.
So the pin counter is how we're going to avoid that problem.
Vì vậy, bộ đếm pin chính là cách chúng ta tránh vấn đề đó.
We also can maintain a latch inside our data structure to ensure that while we're doing a lookup in the page table to say, does this, yes, question, yes.
Chúng ta cũng có thể duy trì một latch bên trong cấu trúc dữ liệu để đảm bảo rằng trong lúc chúng ta tra cứu trong page table để xem liệu trang này có, vâng, câu hỏi, mời bạn.
The question is, what, sorry? The question is, what are page table entry sizes?
Câu hỏi là, gì cơ, xin lỗi? Câu hỏi là kích thước của một page table entry là bao nhiêu?
Less than a kilobyte? Because the big part is the actual frames, the actual memory.
Nhỏ hơn một kilobyte? Vì phần lớn dung lượng nằm ở các frame, tức là bộ nhớ thực sự.
The hash tables, the hash table can be large in terms of having a lot of entries, but each entry itself is not that big.
Còn bảng băm, bảng băm có thể lớn vì có rất nhiều entry, nhưng bản thân mỗi entry thì không lớn lắm.
Right? So there'll be a dirty flag where it's been modified. That's one byte. The reference counter, probably a single byte.
Đúng không? Sẽ có một cờ dirty cho biết trang đã bị sửa đổi. Cái đó là một byte. Bộ đếm tham chiếu, có lẽ cũng chỉ một byte.
Access tracking information, that would be like what transaction is actually is accessing this for me? Like who's actually, what is the thread or the worker ID that actually holds the pin for this?
Thông tin theo dõi truy cập, ví dụ như giao dịch nào đang thực sự truy cập trang này cho tôi? Kiểu như ai đang thực sự, thread hay worker ID nào đang thực sự giữ pin cho trang này?
Again, it's not that big.
Một lần nữa, nó không lớn lắm.
All right, so I need a latch within my page table as well, so that if I say, all right, well, I need to go get page two, I have a free location in my page table, let me protect this while I go then do the disk read to go put that into a frame, to ensure that nobody else comes along and tries to put something in my page table, that same slot, that same location.
Được rồi, vậy tôi cũng cần một latch trong page table của mình, để nếu tôi nói, được rồi, tôi cần lấy trang hai, tôi có một vị trí trống trong page table, hãy để tôi bảo vệ nó trong lúc tôi đọc đĩa để đưa trang đó vào một frame, nhằm đảm bảo không ai khác đến và cố đặt thứ gì đó vào page table của tôi, cùng cái ô đó, cùng vị trí đó.
Right? And then once I'm done, I can release the latch and throw away the pin. Anybody know what a latch is? Go for it. Mutex, perfect, yes.
Đúng không? Và khi xong việc, tôi có thể nhả latch và bỏ pin. Có ai biết latch là gì không? Mời bạn. Mutex, chính xác, đúng rồi.
So if you're coming from the OS world, what we call latches, they're called locks. And at the end of the day, it's a mutex. You could use the OS's mutex or the Pthread mutex.
Vậy nếu bạn đến từ thế giới hệ điều hành, cái mà chúng ta gọi là latch thì ở đó được gọi là lock. Và cuối cùng, nó là một mutex. Bạn có thể dùng mutex của hệ điều hành hoặc mutex của Pthread.
You shouldn't, but you could. We can always do better in the data system.
Bạn không nên dùng, nhưng bạn có thể. Trong hệ quản trị dữ liệu, chúng ta luôn có thể làm tốt hơn.
But the reason why we have this distinction between locks and latches is that locks in the database world is a separate concept that is about protecting higher level logical entities.
Nhưng lý do chúng ta phân biệt giữa lock và latch là vì lock trong thế giới cơ sở dữ liệu là một khái niệm riêng, dùng để bảo vệ các thực thể logic ở mức cao hơn.
Like I can lock a page, I can lock a tuple, I can lock an index. All right?
Chẳng hạn tôi có thể khóa một trang, một tuple, một chỉ mục. Được chứ?
And a latch is gonna be what you protect the internal critical section of any kind of data structure inside your database system from multiple threads or multiple workers accessing it at the same time.
Còn latch là thứ bạn dùng để bảo vệ vùng tới hạn bên trong của bất kỳ cấu trúc dữ liệu nào trong hệ cơ sở dữ liệu khỏi việc nhiều thread hoặc nhiều worker truy cập nó cùng lúc.
And the reason why we have to make this distinction is that in the lock case, we have to deal with stupid people on the outside of the database system.
Và lý do chúng ta phải phân biệt như vậy là, với lock, chúng ta phải đối phó với những người ngớ ngẩn bên ngoài hệ cơ sở dữ liệu.
Like someone starts a transaction and then decides to go out for a cup of coffee, and the transaction's still open.
Ví dụ có người bắt đầu một giao dịch rồi quyết định đi uống cà phê, và giao dịch vẫn còn mở.
So we as a database are gonna have to deal with somebody walking away from the computer and be able to rectify any issues like deadlocks or live locks and so forth.
Vì vậy, với tư cách là cơ sở dữ liệu, chúng ta phải xử lý việc ai đó bỏ đi khỏi máy tính và có khả năng khắc phục mọi vấn đề như bế tắc hay live lock, v.v.
A latch, since that's protecting internal data structure, that's us.
Còn latch, vì nó bảo vệ cấu trúc dữ liệu bên trong, nên đó là chính chúng ta.
Like, we're actually building the database system, we're paying a lot of money to do it, and therefore we won't be stupid, in theory, and therefore it's up for us to make sure that we don't have deadlocks or other problems.
Tức là chính chúng ta đang xây dựng hệ cơ sở dữ liệu, chúng ta được trả rất nhiều tiền để làm việc đó, nên về lý thuyết chúng ta sẽ không ngớ ngẩn, và do đó chúng ta có trách nhiệm đảm bảo rằng không có bế tắc hay các vấn đề khác.
Like, because there isn't gonna be this lock manager thing up above that's gonna kill us if we have deadlocks. So it's up for us to make sure we do this correctly.
Vì sẽ không có lock manager này ở phía trên sẽ giết chúng ta nếu ta gặp bế tắc. Nên chúng ta phải tự đảm bảo làm việc này cho đúng.
So this would be a low level mutex. You could use, again, pthread mutex, the Apple one called the parking mutex one or parking locks, that's better.
Vậy đây sẽ là một mutex mức thấp. Bạn có thể dùng, một lần nữa, pthread mutex, loại của Apple gọi là parking mutex hay parking lock, cái đó tốt hơn.
But we'll cover that in a few more weeks. But the main idea here is that, again, it's gonna protect the internal data structure of the system.
Nhưng chúng ta sẽ học phần đó trong vài tuần nữa. Nhưng ý chính ở đây, một lần nữa, là nó sẽ bảo vệ cấu trúc dữ liệu nội bộ của hệ thống.
And there isn't gonna be anybody that can make sure that we don't have problems. And there's not gonna be any way to roll back changes unless we do it ourselves.
Và sẽ không có ai đảm bảo giúp chúng ta rằng không có vấn đề gì xảy ra. Và cũng sẽ không có cách nào để hoàn tác các thay đổi trừ khi chúng ta tự làm.
In the case of a lock, if I open a transaction through SQL and then I make some changes and then my transaction gets killed, the database system won't clean up the mess afterwards for me.
Với lock, nếu tôi mở một giao dịch qua SQL rồi thực hiện một số thay đổi và sau đó giao dịch của tôi bị hủy, hệ quản trị cơ sở dữ liệu sẽ không dọn dẹp phần lộn xộn đó cho tôi.
It won't do that for a latch.
Nó sẽ không làm vậy với latch.
Again, also as a reminder, this is interpreted between the page table and the page directory.
Một lần nữa, xin nhắc lại, cái này được hiểu là nằm giữa page table và page directory.
Page directory is that thing I said in the beginning where I use that to find the pages I want on disk given an ID.
Page directory là thứ tôi đã nói ở đầu buổi, dùng để tìm các trang tôi muốn trên đĩa khi biết ID.
And the page table is this internal data structure that keeps track of, here's the location within frames of all the pages that I brought in from disk and where they reside in memory.
Còn page table là cấu trúc dữ liệu nội bộ theo dõi vị trí trong các frame của tất cả các trang mà tôi đã đưa vào từ đĩa và chúng nằm ở đâu trong bộ nhớ.
Again, you don't have to store that on disk. If you crash, you lose whatever's in memory anyway, so who cares?
Một lần nữa, bạn không cần lưu nó trên đĩa. Nếu hệ thống sập, dù sao bạn cũng mất mọi thứ trong bộ nhớ, nên có ai quan tâm đâu?
There are some systems that actually can, will write out what the contents of the page table is so that if I crash and come back, rather than organically populating the page table through whoever accesses what, I can actually preload or prefetch all the pages that I had in memory before after the crash and bring that back in.
Có một số hệ thống thực sự có thể ghi ra nội dung của page table để nếu tôi sập rồi khởi động lại, thay vì để page table được lấp đầy dần dần tùy theo ai truy cập cái gì, tôi có thể tải trước hoặc nạp trước tất cả các trang mà tôi từng có trong bộ nhớ trước khi sập và đưa chúng trở lại.
You see this in serverless systems. Again, we'll cover this later. In general, the page table does not need to be durable, does not need to be stored in disk.
Bạn thấy điều này trong các hệ thống serverless. Một lần nữa, chúng ta sẽ học sau. Nói chung, page table không cần phải bền vững, không cần được lưu trên đĩa.
All right, so what does this sound like, what I've been talking about so far?
Được rồi, vậy những gì tôi vừa nói nghe giống cái gì?
You sort of brought up the point before where, what happens if I have, you know, my database has a large amount of memory that I have?
Trước đó bạn có nêu một điểm, là điều gì xảy ra nếu cơ sở dữ liệu của tôi có một lượng bộ nhớ lớn?
We're basically, again, trying to provide the illusion that our system has more memory than it actually physically has. What does that sound like? Is it swapping?
Về cơ bản, một lần nữa, chúng ta đang cố tạo ra ảo giác rằng hệ thống có nhiều bộ nhớ hơn so với bộ nhớ vật lý thực sự có. Nghe giống cái gì? Có phải swapping không?
What is the higher level concept of that? Virtual memory, yes. All right, well, yeah, if you take an OS class, this is what the OS wants to do for you through virtual memory.
Khái niệm ở mức cao hơn là gì? Bộ nhớ ảo, đúng rồi. Được rồi, nếu bạn học môn hệ điều hành, đây chính là điều hệ điều hành muốn làm giúp bạn thông qua bộ nhớ ảo.
And it has a mechanism called memory map files that allows you to take a file that resides on disk, and you call mmap open on it, and it basically maps the contents of that file into the address space of your process.
Và nó có một cơ chế gọi là memory map file cho phép bạn lấy một tệp nằm trên đĩa, rồi gọi mmap để mở nó, và về cơ bản nó ánh xạ nội dung của tệp đó vào không gian địa chỉ của tiến trình của bạn.
All right, and obviously it doesn't do this eagerly, it does this lazily.
Và dĩ nhiên nó không làm việc này ngay lập tức, mà làm một cách lười (lazy).
So I call the open on the file, and it then gives me a starting point of the memory address, and any time I jump into an offset within that starting memory address, it will correspond to some offset within the pages of the file that I mapped in.
Vậy tôi gọi open trên tệp, và nó trả cho tôi một điểm bắt đầu là địa chỉ bộ nhớ, và bất cứ khi nào tôi nhảy tới một offset bên trong địa chỉ bộ nhớ bắt đầu đó, nó sẽ tương ứng với một offset nào đó trong các trang của tệp mà tôi đã ánh xạ vào.
So the OS was going to be trying to do this. Basically, it was trying to do the same thing we're talking about today, but it's going to do a terrible job at it.
Vậy là hệ điều hành sẽ cố gắng làm việc này. Về cơ bản, nó cố làm đúng điều mà hôm nay chúng ta đang nói đến, nhưng nó sẽ làm việc đó rất tệ.
I guess I'm sort of poisoning the well already, but trust me, you don't want to do this. All right, so here's that file we had on disk before, and we have virtual memory.
Tôi đoán là mình đang nói xấu trước rồi, nhưng hãy tin tôi, các bạn không muốn làm như vậy đâu. Được rồi, đây là tệp mà trước đó chúng ta có trên đĩa, và chúng ta có bộ nhớ ảo.
So again, I call mmap on it, and then in my address space of my process, it's going to say, all right, well, here's the four pages starting at some offset for the file that you mapped in.
Vậy, một lần nữa, tôi gọi mmap trên nó, và trong không gian địa chỉ của tiến trình, nó sẽ nói rằng, được rồi, đây là bốn trang bắt đầu từ một offset nào đó của tệp mà bạn đã ánh xạ vào.
So then now, when any thread or process accesses one of these pages, you try to, again, just read a memory address at one of these offsets.
Vậy bây giờ, khi bất kỳ luồng hay tiến trình nào truy cập một trong các trang này, tức là bạn lại chỉ đọc một địa chỉ bộ nhớ tại một trong các offset đó.
The OS says, oh, the thing you want isn't actually in memory.
Hệ điều hành sẽ nói: ồ, thứ bạn muốn thực ra không có trong bộ nhớ.
It's a major page fault, so it pauses your thread, go then fetches whatever the page you wanted, puts it into physical memory, and then wires up the virtual memory table to now point to that physical memory.
Đó là một major page fault, nên nó tạm dừng luồng của bạn, rồi đi lấy trang bạn cần, đưa vào bộ nhớ vật lý, và sau đó nối bảng bộ nhớ ảo để trỏ tới vùng bộ nhớ vật lý đó.
And then your process gets control back again, and you can do whatever you want with it.
Rồi tiến trình của bạn lại được trả quyền điều khiển, và bạn có thể làm gì tùy ý với nó.
All right, read another page, same thing, it's not memory, we get a major page fault, we block, fetches it in, we wire it up, and then our process can run again.
Đọc một trang khác, cũng như vậy, nó không có trong bộ nhớ, ta gặp major page fault, ta bị chặn, nó được nạp vào, ta nối lại, và rồi tiến trình của ta chạy tiếp được.
So now the challenge is going to be what happens when we try to access something again for this file, but now we're out of physical memory.
Vậy thách thức bây giờ là chuyện gì xảy ra khi ta lại cố truy cập một thứ gì đó của tệp này, nhưng lúc này ta đã hết bộ nhớ vật lý.
All right? What's going to happen? I've already said, right? It's going to block your process, then it's going to go decide now which page in physical memory to evict.
Được chứ? Chuyện gì sẽ xảy ra? Tôi đã nói rồi, đúng không? Nó sẽ chặn tiến trình của bạn, rồi quyết định trang nào trong bộ nhớ vật lý sẽ bị loại ra.
You know, if it's not dirty, it just throws it away.
Nếu trang không bị dirty thì nó chỉ việc bỏ đi.
If it is dirty, meaning it's been modified since you've read it in, it'll write it back out to disk, then copy whatever the page is that you want in, once it's put in the physical memory, and then hand you back control.
Nếu trang là dirty, nghĩa là nó đã bị sửa đổi kể từ khi bạn đọc vào, nó sẽ ghi trang đó ngược ra đĩa, rồi sao chép trang mà bạn muốn vào, khi đã đặt vào bộ nhớ vật lý, và trả lại quyền điều khiển cho bạn.
So again, this seems like exactly what you want in our database system, but because the operating system is doing it for us, it doesn't know anything about SQL, it doesn't know anything about queries or transactions or whatever we're trying to do, it doesn't know anything about what actually is in these files, and therefore, it's not in a good position to make decisions about what the right thing to evict is.
Vậy nên, điều này có vẻ đúng là thứ ta muốn trong hệ cơ sở dữ liệu, nhưng vì hệ điều hành làm việc đó thay cho ta, nó không biết gì về SQL, không biết gì về truy vấn hay giao dịch hay bất cứ thứ gì ta đang cố làm, nó không biết gì về nội dung thực sự trong các tệp này, và do đó, nó không ở vị trí tốt để đưa ra quyết định về việc loại trang nào là đúng đắn.
So, what are the problems? So, the first thing is that the OS can decide to swap out a dirty page any time that it wants, right?
Vậy các vấn đề là gì? Thứ nhất, hệ điều hành có thể quyết định đẩy một trang dirty ra bất cứ lúc nào nó muốn, đúng không?
The background writer can go through and says, "All right, you've modified this page, so let me go ahead and preemptively write it out for you, so that at some point, if I need to evict it, I don't have, and since I'm stalling your process, I don't have to block you for a long time while I write it out.
Tiến trình ghi nền có thể chạy qua và nói: "Được rồi, bạn đã sửa trang này, nên để tôi ghi nó ra trước cho bạn, để đến lúc nào đó nếu cần loại nó ra, tôi không phải, và vì tôi đang làm tiến trình của bạn bị đình trệ, tôi không phải chặn bạn lâu trong lúc ghi nó ra.
I can do this in the background, and that way, when you want to evict this, you just can throw it away because it's now been marked clean."
Tôi có thể làm việc này ở chế độ nền, và như vậy, khi bạn muốn loại trang này ra, bạn có thể bỏ nó đi luôn vì giờ nó đã được đánh dấu là sạch."
But the problem is, we have no control, we being the database system, have no control what it's going to write out, and when it's going to write it out.
Nhưng vấn đề là chúng ta, tức hệ quản trị cơ sở dữ liệu, không kiểm soát được nó sẽ ghi cái gì ra, và khi nào nó ghi ra.
Because, again, it doesn't know what's in these files, it doesn't know how the upper-level part of the transaction is actually modifying them, So there may be a case where there's a dependency between multiple pages, where I can't write out this dirty page until this other dirty page has been written out.
Bởi vì, một lần nữa, nó không biết bên trong các tệp này có gì, nó không biết phần ở tầng trên của giao dịch thực sự đang sửa đổi chúng như thế nào. Vì vậy có thể có trường hợp tồn tại sự phụ thuộc giữa nhiều trang, trong đó tôi không thể ghi trang bẩn này ra cho đến khi trang bẩn kia đã được ghi ra.
Okay, we'll see this when we talk about transactions later on, but, like, you basically, if I modify a page in the database system, I want to make sure I write a log record that says, here's the change I made to this page, before I write out that change.
Được rồi, chúng ta sẽ thấy điều này khi nói về giao dịch sau này, nhưng về cơ bản, nếu tôi sửa đổi một trang trong hệ quản trị cơ sở dữ liệu, tôi muốn đảm bảo mình ghi một bản ghi nhật ký nói rằng: đây là thay đổi tôi đã thực hiện trên trang này, trước khi ghi thay đổi đó ra.
But the OS doesn't know that, doesn't know that there's a write-ahead log or this other thing over here.
Nhưng hệ điều hành không biết điều đó, không biết có write-ahead log hay thứ khác ở bên này.
It says, all right, I got some dirty pages, let me go ahead and write them out.
Nó chỉ nói: được rồi, tôi có vài trang bẩn, cứ ghi chúng ra thôi.
You can prevent them from being evicted using mlock, which is basically the same thing as a pin for the pages, but that doesn't prevent it from writing it out.
Bạn có thể ngăn chúng bị loại ra bằng mlock, về cơ bản giống như việc pin các trang, nhưng nó không ngăn được việc ghi trang ra.
All right, so that's a problem for us. Then we have the stalling issue, where the database system doesn't know what pages are in memory.
Được rồi, vậy đó là một vấn đề đối với chúng ta. Tiếp theo là vấn đề bị treo (stall), khi hệ quản trị cơ sở dữ liệu không biết trang nào đang nằm trong bộ nhớ.
It tries to go and then access something, and if it's not in memory, then my worker, either a thread or process, will have to stall while the OS decides to go fetch it in.
Nó cố truy cập một thứ gì đó, và nếu không có trong bộ nhớ, thì worker của tôi, dù là luồng hay tiến trình, sẽ phải bị treo trong lúc hệ điều hành quyết định nạp nó vào.
So that means now my worker is not actually doing any useful, you know, any useful work that it could be doing while it's going and fetching something from the disk in the background, because it got blocked.
Điều đó nghĩa là worker của tôi lúc này không làm được việc gì hữu ích, tức là không làm được công việc hữu ích nào mà lẽ ra nó có thể làm trong lúc nó đang lấy dữ liệu từ đĩa ở chế độ nền, vì nó đã bị chặn.
Now, you could start, you know, doing a little, play a little game where you have a separate thread on the side that can go touch a page that you think you're going to need, and that way, if it gets blocked, the worker that's running the query can still do other stuff.
Giờ bạn có thể bắt đầu chơi một chút trò mà bạn có một luồng riêng bên cạnh để chạm vào một trang mà bạn nghĩ sẽ cần, và như vậy, nếu nó bị chặn, worker đang chạy truy vấn vẫn có thể làm việc khác.
But then you're actually, you're adding more complexity to your system when what the OS is trying to do, you know, trying to make it, you know, trying to do something simple for you, But now you're actually adding a bunch of stuff in order to deal with the OS doing stupid things for you.
Nhưng như vậy là bạn đang làm hệ thống phức tạp thêm trong khi điều hệ điều hành đang cố làm, là cố làm một thứ đơn giản cho bạn. Còn bây giờ bạn lại đang thêm cả đống thứ để xử lý những việc ngớ ngẩn mà hệ điều hành làm thay bạn.
Another problem that's actually more nuanced and not really obvious until you actually start building real systems is that error handling becomes more challenging now with the OS, with mmap, because a failure can occur at any time, anywhere, in your application or in your system.
Một vấn đề khác tinh vi hơn và không rõ ràng cho đến khi bạn thực sự xây dựng hệ thống thật là việc xử lý lỗi trở nên khó khăn hơn khi dùng hệ điều hành, với mmap, vì lỗi có thể xảy ra bất cứ lúc nào, ở bất kỳ đâu trong ứng dụng hay hệ thống của bạn.
That means that at any time I touch that memory, it might have got evicted, or it might been, there might be a problem in the actual underlying hardware, and I'm not getting an exception, I'm going to get an interruption or interrupt.
Nghĩa là bất cứ lúc nào tôi chạm vào vùng nhớ đó, nó có thể đã bị loại ra, hoặc có thể có sự cố ở phần cứng bên dưới, và tôi sẽ không nhận được một ngoại lệ, mà sẽ nhận một ngắt (interrupt).
So now I'm going to have interrupt handler code all throughout my system, whereas if I was managing disk and memory myself in my database system, at the time I try to go to read it, if I can't read it and I get an error, that's the only location where I need to handle that.
Thế là tôi sẽ có mã xử lý ngắt rải khắp hệ thống, trong khi nếu tôi tự quản lý đĩa và bộ nhớ trong hệ quản trị cơ sở dữ liệu của mình, vào lúc tôi cố đọc nó, nếu tôi không đọc được và nhận một lỗi, thì đó là nơi duy nhất tôi cần xử lý chuyện đó.
But if you use mmap, because it's, again, trying to be transparent to you, it's all over in your system. Yes?
Nhưng nếu bạn dùng mmap, vì nó, một lần nữa, cố tỏ ra trong suốt với bạn, nên lỗi có thể xuất hiện khắp nơi trong hệ thống của bạn. Bạn hỏi gì?
Is there a page fault? It's not a page fault. It'd be like an interrupt, like the disk is broken or something. Yeah.
Có phải là page fault không? Không phải page fault. Nó giống như một ngắt, kiểu như đĩa bị hỏng hay gì đó. Vâng.
So you try to read something and someone ripped the file out. It's gone. What do you do? Or rip the hardware out. You get an interrupt.
Tức là bạn cố đọc thứ gì đó mà có người đã rút tệp ra. Nó mất rồi. Bạn làm gì đây? Hoặc rút luôn phần cứng ra. Bạn sẽ nhận một ngắt.
The question is, statement is, and they're correct, like if someone screws around the system and starts breaking your files, but the point I'm trying to make is like, if I read something from disk, I put it into memory, and then I rip the hard drive out, then, in theory, the system can still run because it has it in memory.
Câu hỏi, à ý kiến của bạn là, và bạn nói đúng, nếu ai đó táy máy hệ thống và bắt đầu làm hỏng các tệp của bạn, nhưng điều tôi muốn nói là nếu tôi đọc thứ gì đó từ đĩa, đưa nó vào bộ nhớ, rồi tôi rút ổ cứng ra, thì về lý thuyết hệ thống vẫn chạy được vì dữ liệu đã nằm trong bộ nhớ.
Right? And so if I then try to read that page again, since the file is gone, I'll get a failure at that moment and I can handle it right there.
Đúng không? Và nếu sau đó tôi cố đọc lại trang đó, vì tệp đã mất, tôi sẽ gặp lỗi ngay lúc đó và có thể xử lý ngay tại chỗ.
Whereas with mmap, If some other part of the system tries to read it again, and it's saying it's trying to be transparent to me, I just do a memory access and it's like, it's non-deterministic, yes.
Trong khi với mmap, nếu một phần khác của hệ thống cố đọc lại nó, và vì nó cố tỏ ra trong suốt với tôi, tôi chỉ thực hiện một truy cập bộ nhớ và nó mang tính không tất định, vâng.
And there's a bunch more engineering work you have to do.
Và bạn còn phải làm thêm rất nhiều công việc kỹ thuật.
And the last one, I don't want to belabor this too much, but just to sort of take my word on this, it's going to be slower than doing everything ourselves, because what is the, how is the OS tracking virtual memory?
Và điểm cuối cùng, tôi không muốn nói dài dòng quá, mà cứ tin lời tôi về chuyện này, nó sẽ chậm hơn so với việc tự làm mọi thứ, vì hệ điều hành theo dõi bộ nhớ ảo bằng cách nào?
It's the same thing as the page table that we had before. So it's going to have its own internal data structures with its own latches that you use to protect those things.
Cũng giống như bảng trang (page table) mà chúng ta có trước đó. Nên nó sẽ có các cấu trúc dữ liệu nội bộ riêng với các latch riêng mà bạn dùng để bảo vệ chúng.
And we, in the data system world, we can always do a better job.
Và trong thế giới hệ quản trị dữ liệu, chúng ta luôn có thể làm tốt hơn.
So again, I don't want to go into this too much, but it's saying like, you can start tricking around the OS to make it look more like what we actually want to build in our database system, but it's just as much work, and in the end, you're relinquishing control to what's being brought into memory and when it's being written out, at what time and when.
Vậy nên, một lần nữa, tôi không muốn đi sâu quá, nhưng ý là bạn có thể bắt đầu dùng mẹo để qua mặt hệ điều hành để nó giống hơn với thứ chúng ta thực sự muốn xây dựng trong hệ quản trị cơ sở dữ liệu, nhưng công sức cũng nhiều như vậy, và rốt cuộc bạn đã nhường quyền kiểm soát việc thứ gì được đưa vào bộ nhớ và khi nào nó được ghi ra, vào lúc nào và như thế nào.
Like, all that is, you're giving up to the OS, and you're just better off just writing everything yourself, which is what this class is about.
Tất cả những thứ đó, bạn đều nhường cho hệ điều hành, và tốt hơn hết là bạn tự viết mọi thứ, đó chính là nội dung của môn học này.
So there's a bunch of systems that have tried to use mmap over the years. Probably the one that you're most familiar with is MongoDB.
Có khá nhiều hệ thống đã thử dùng mmap qua các năm. Có lẽ cái bạn quen thuộc nhất là MongoDB.
When MongoDB first started, they didn't have their own buffer pool, what we're talking about today. They relied on mmap. But since then, all these systems have gotten rid of it.
Khi MongoDB mới bắt đầu, họ không có buffer pool riêng, thứ mà hôm nay chúng ta đang nói tới. Họ dựa vào mmap. Nhưng từ đó, tất cả các hệ thống này đều đã bỏ nó.
They basically realized all the mistakes that I'm telling you here. They realized that over the years, this thing is just not maintainable. That you want to be doing everything yourself in your database system.
Về cơ bản họ nhận ra mọi sai lầm mà tôi đang nói với các bạn ở đây. Họ nhận ra qua nhiều năm rằng thứ này đơn giản là không thể bảo trì được. Rằng bạn nên tự làm mọi thứ trong hệ quản trị cơ sở dữ liệu của mình.
I like to point out Mongo because Mongo won IPO in 2018. They had a ton of money. You had a ton of top engineers.
Tôi hay nêu Mongo vì Mongo đã IPO vào năm 2018. Họ có rất nhiều tiền. Họ có cả một đội ngũ kỹ sư hàng đầu.
And if they couldn't make mmap work, be functional, then what hope does everyone else have? Instead, what MongoDB did was they bought WireTiger. WireTiger only uses mmap for one very small use case.
Và nếu họ còn không thể làm cho mmap hoạt động ổn, thì những người khác còn hy vọng gì nữa? Thay vào đó, MongoDB đã mua WireTiger. WireTiger chỉ dùng mmap cho một trường hợp rất nhỏ.
But the whole regular system is still based off buffer pools that we're talking about today. SQLite has mmap. It's for portability reasons.
Còn toàn bộ hệ thống thông thường vẫn dựa trên buffer pool mà hôm nay chúng ta sẽ nói đến. SQLite có mmap. Đó là vì lý do tính khả chuyển.
And by default, you don't get mmap. You have to tell it you want mmap. By default, you get the buffer pool stuff that we're talking about today.
Và theo mặc định thì bạn không có mmap. Bạn phải chỉ định là muốn dùng mmap. Theo mặc định, bạn có phần buffer pool mà hôm nay chúng ta sẽ nói đến.
This will be an overarching theme throughout the time semester is that the database system, meaning us actually building the system, we're always going to be in a better position to make decisions about anything, everything.
Một chủ đề xuyên suốt sẽ lặp lại trong cả học kỳ này là hệ quản trị cơ sở dữ liệu, tức là chúng ta, những người thực sự xây dựng hệ thống, luôn ở vị thế tốt hơn để đưa ra quyết định về bất cứ điều gì, mọi thứ.
Because we know what the queries are. We know what things we've executed in the past we're going to execute in the future.
Vì chúng ta biết các truy vấn là gì. Chúng ta biết những gì đã thực thi trong quá khứ và sẽ thực thi trong tương lai.
We know what our data looks like, what the dependencies are between them. Therefore, we're always going to make better decisions in the OS. And we'll talk about some of these tricks later on.
Chúng ta biết dữ liệu của mình trông như thế nào, các phụ thuộc giữa chúng ra sao. Do đó, chúng ta luôn đưa ra quyết định tốt hơn hệ điều hành. Và sau này chúng ta sẽ nói về một số mẹo trong đó.
But we'll have better prefetching than the OS. We'll have better policy than the OS. We can schedule things differently.
Nhưng chúng ta sẽ có prefetching tốt hơn hệ điều hành. Chúng ta sẽ có chính sách tốt hơn hệ điều hành. Chúng ta có thể lập lịch các thứ theo cách khác.
At the end of the day, we don't want to talk to the OS because it's not going to be our friend. It's always going to try to screw us over.
Rốt cuộc, chúng ta không muốn làm việc với hệ điều hành vì nó sẽ không phải là bạn của chúng ta. Nó luôn cố gắng gây khó dễ cho chúng ta.
If you don't believe me, go look up Linus's post on the mailing list about what he thinks about database people. He's always going to try to ruin our lives.
Nếu không tin tôi, hãy tìm bài đăng của Linus trên mailing list về việc ông ấy nghĩ gì về những người làm cơ sở dữ liệu. Nó luôn cố phá hỏng cuộc sống của chúng ta.
So we never want to talk to it as much as possible. So we actually ended up writing a paper a few years ago explicitly on this exact topic.
Vì vậy chúng ta không bao giờ muốn dựa vào nó, càng ít càng tốt. Thế nên cách đây vài năm chúng tôi đã viết một bài báo nói riêng về đúng chủ đề này.
It's my pet project. Because all these companies would come give talks at CMU and talk about how they're using mmap. And I was like, that seems like a bad idea.
Đó là dự án tâm huyết của tôi. Vì các công ty này thường đến CMU thuyết trình và nói về việc họ dùng mmap như thế nào. Và tôi nghĩ, có vẻ đó là ý tưởng tồi.
They're like, "Oh, what are you talking about? It's great." And then two years later, they were like, "Oh yeah, you were right. That was terrible." So we then wrote a paper about it.
Họ bảo: "Ồ, anh nói gì vậy? Nó tuyệt mà." Rồi hai năm sau, họ nói: "Ừ, anh đúng rồi. Nó tệ lắm." Thế là chúng tôi viết một bài báo về chuyện đó.
You can go to that link there. There's a video that summarizes the key things I'm talking about today as well.
Bạn có thể vào đường liên kết đó. Cũng có một video tóm tắt những điểm chính mà hôm nay tôi nói.
And then just a few weeks ago, yeah, a few weeks ago, somebody posted on Hacker News saying like, "Hey, I started building a database system using MMAP because I thought I could figure it out."
Rồi chỉ vài tuần trước, vâng, vài tuần trước, có người đăng trên Hacker News rằng: "Này, tôi bắt đầu xây dựng một hệ quản trị cơ sở dữ liệu bằng MMAP vì tôi nghĩ mình có thể làm được."
Nope. They were wrong. And then they were like, "Oh," because he knew about the paper that we wrote before. Then he realized, "Oh yeah, I guess I have to do what Andy said."
Không. Họ đã sai. Rồi họ nói: "Ồ," vì anh ấy biết bài báo mà chúng tôi đã viết trước đó. Rồi anh ấy nhận ra: "Ừ, chắc tôi phải làm theo những gì Andy nói."
So again, the rest of your life, never use MMAP in your database system.
Vậy nên, một lần nữa, cả đời bạn đừng bao giờ dùng MMAP trong hệ quản trị cơ sở dữ liệu của mình.
Okay, so if now we're responsible for memory and we're responsible for deciding what comes in and out, we have to decide what to evict when we run out of memory.
Được rồi, vậy nếu bây giờ chúng ta chịu trách nhiệm về bộ nhớ và chịu trách nhiệm quyết định cái gì được đưa vào và ra, chúng ta phải quyết định trang nào sẽ bị loại bỏ khi hết bộ nhớ.
Yes? The statement is, how do we bypass virtual memory?
Bạn có câu hỏi à? Câu hỏi là: làm sao để bỏ qua bộ nhớ ảo?
I mean, yes. So when you call malloc, yes, you get anonymous MMAP. The thing I care about is, I don't want the OS to decide how to flush pages out.
Ý tôi là, đúng vậy. Khi bạn gọi malloc, đúng, bạn nhận được anonymous MMAP. Điều tôi quan tâm là tôi không muốn hệ điều hành quyết định cách ghi các trang ra đĩa.
So it could start thrashing for us because we do anonymous MMAP and get a bunch of memory when you call malloc. And then it starts running and starts paging things out.
Nên nó có thể bắt đầu thrashing với chúng ta, vì chúng ta dùng anonymous MMAP và nhận một lượng lớn bộ nhớ khi gọi malloc. Rồi nó bắt đầu chạy và bắt đầu paging các thứ ra ngoài.
But in general, like I was saying, when the system boots up, you want to allocate all the memory you need ever at that moment.
Nhưng nhìn chung, như tôi đã nói, khi hệ thống khởi động, bạn muốn cấp phát toàn bộ bộ nhớ bạn cần ngay tại thời điểm đó.
And therefore, you have to tell it use exactly the amount of memory that's physically available.
Và do đó, bạn phải bảo nó dùng đúng lượng bộ nhớ vật lý đang có.
So if your system you're running on has 100 gigs, you would tell your database system, "Hey, you have 80 gigs, do whatever you want with it," and it mallocs whatever it wants.
Vậy nếu hệ thống bạn đang chạy có 100 gigabyte, bạn sẽ nói với hệ quản trị cơ sở dữ liệu: "Này, bạn có 80 gigabyte, muốn làm gì thì làm," và nó malloc bất cứ thứ gì nó muốn.
And that'll never get thrashed. Another user type, then there's going to be a statement that takes it out. The statement is, that's not true.
Và phần đó sẽ không bao giờ bị thrashing. Một bạn khác nêu ý kiến, rằng có một phát biểu phản bác lại. Ý kiến là: điều đó không đúng.
If another system running on the same box allocates a bunch of memory too, could you start thrashing? Yes. Don't do that.
Nếu một hệ thống khác chạy trên cùng máy cũng cấp phát nhiều bộ nhớ, thì có thể bắt đầu thrashing không? Có. Đừng làm vậy.
You never want to run another process or another system on your database system's same machine. That's considered the right way to do things.
Bạn không bao giờ nên chạy một tiến trình khác hay một hệ thống khác trên cùng máy với hệ quản trị cơ sở dữ liệu. Đó được coi là cách làm đúng.
If it's like a WordPress website, who cares, right? It's something real simple. But if it's anything mission critical, you don't run a Bitcoin miner in the same box as your database system.
Nếu chỉ là một trang WordPress thì ai quan tâm, đúng không? Nó rất đơn giản. Nhưng nếu là thứ gì quan trọng sống còn, thì bạn không chạy một chương trình đào Bitcoin trên cùng máy với hệ quản trị cơ sở dữ liệu.
Why would the OS want to page you out?
Tại sao hệ điều hành lại muốn page bạn ra ngoài?
The statement is, why would the OS page you out if you're saying that I'm running on a box that only has the memory that I need?
Câu hỏi là: tại sao hệ điều hành lại page bạn ra ngoài nếu bạn nói rằng bạn đang chạy trên máy chỉ có đúng lượng bộ nhớ bạn cần?
The only thing running is my database system, and it has all the memory that it could ever want. You're correct. It won't page you out. It could write out the dirty pages.
Thứ duy nhất đang chạy là hệ quản trị cơ sở dữ liệu của tôi, và nó có tất cả bộ nhớ mà nó có thể muốn. Bạn nói đúng. Nó sẽ không page bạn ra ngoài. Nhưng nó có thể ghi các dirty page ra đĩa.
And then you're screwed on that, as well as all the other stuff. There's other reporting issues too. You want to say, how much memory is my database system using?
Và khi đó bạn gặp rắc rối với việc đó, cùng mọi thứ khác. Còn có những vấn đề về báo cáo nữa. Bạn muốn biết hệ quản trị cơ sở dữ liệu của tôi đang dùng bao nhiêu bộ nhớ?
Well, now I've got to go look in whatever's in the page cache in a second. You can't just go to the OS and say, how much memory is this process using?
Thì giờ tôi phải đi xem trong page cache có gì. Bạn không thể chỉ hỏi hệ điều hành là tiến trình này đang dùng bao nhiêu bộ nhớ.
Because it's that plus the page cache or whatever. It becomes more complicated from reporting.
Vì nó là con số đó cộng với page cache hay gì đó. Việc báo cáo trở nên phức tạp hơn.
We have some fixed amount of memory that we can use to store data for the pages we bring into memory.
Chúng ta có một lượng bộ nhớ cố định để lưu dữ liệu cho các trang mà ta đưa vào bộ nhớ.
But then again, at some point, we're going to run out of memory, run out of free frames, and you have to decide how to make space.
Nhưng rồi, đến một lúc nào đó, ta sẽ hết bộ nhớ, hết các frame trống, và bạn phải quyết định cách tạo chỗ trống.
And this is going to be called the buffer replacement policy.
Và việc này được gọi là chính sách thay thế bộ đệm (buffer replacement policy).
And the idea is that we're going to run some algorithm that can choose which page we think we're least likely going to need in the future, The ideal scenario.
Ý tưởng là ta sẽ chạy một thuật toán nào đó có thể chọn ra trang mà ta cho là ít có khả năng cần đến nhất trong tương lai, đó là kịch bản lý tưởng.
And we're going to go ahead and evict it, free that frame up, and then now bring the new requested page into memory and reuse that frame.
Và chúng ta sẽ tiến hành loại bỏ (evict) nó, giải phóng frame đó, rồi đưa trang được yêu cầu mới vào bộ nhớ và tái sử dụng frame đó.
So this is an old problem in computer science in general, basically caching.
Đây là một bài toán cũ trong khoa học máy tính nói chung, về cơ bản là caching.
Because we have to deal with that memory hierarchy, where the things that have more space are going to be slower and farther away, but the fast stuff like DRAM is going to be much more limited in size.
Bởi vì chúng ta phải xử lý phân cấp bộ nhớ, trong đó những thứ có nhiều dung lượng hơn sẽ chậm hơn và ở xa hơn, còn những thứ nhanh như DRAM thì bị giới hạn nhiều hơn về kích thước.
So now when we run our replacement policy algorithm, we obviously want to be correct to the extent that we can, because we want to make sure that we throw things away that we're least likely going to need in the future.
Vậy bây giờ khi chạy thuật toán của chính sách thay thế, rõ ràng chúng ta muốn nó đúng ở mức tối đa có thể, vì chúng ta muốn chắc chắn rằng mình loại bỏ những thứ mà nhiều khả năng ít cần đến nhất trong tương lai.
And we want this to be as fast as possible, because again, if the cost of a disk IO is like one millisecond, but if our replacement algorithm takes 10 milliseconds to run, we're just better off just reading things from disk, because that's always going to be faster.
Và chúng ta muốn việc này nhanh nhất có thể, vì một lần nữa, nếu chi phí của một lần IO đĩa là khoảng một mili giây, mà thuật toán thay thế của chúng ta mất 10 mili giây để chạy, thì tốt hơn là cứ đọc thẳng dữ liệu từ đĩa, vì cách đó luôn nhanh hơn.
And the amount of memory we're going to use to store whatever metadata we have about what's in our buffer pool, we want that to be as small as possible, because if we're spending megabytes to store metadata about what's in the memory, then that's memory we can't be using to store more data.
Và lượng bộ nhớ chúng ta dùng để lưu trữ siêu dữ liệu (metadata) về những gì có trong buffer pool, chúng ta muốn nó nhỏ nhất có thể, vì nếu phải tốn hàng megabyte để lưu metadata về những gì đang có trong bộ nhớ, thì đó là phần bộ nhớ mà ta không thể dùng để lưu thêm dữ liệu.
So like I said, this is an old problem. One of those common solutions in systems goes back to 1965, LRU, least recently used.
Như tôi đã nói, đây là một bài toán cũ. Một trong những giải pháp phổ biến trong lĩnh vực hệ thống có từ năm 1965, LRU, tức là least recently used (ít được dùng gần đây nhất).
And the basic idea is that you just keep track of a timestamp for all the pages you have in memory based on when they were last accessed.
Ý tưởng cơ bản là bạn chỉ cần theo dõi một dấu thời gian cho tất cả các trang trong bộ nhớ, dựa trên lần truy cập gần nhất của chúng.
And then when it comes time to evict something, you just pick whatever one that was accessed the longest ago. And anytime you access something again, you just update that timestamp.
Và khi đến lúc cần loại bỏ một thứ gì đó, bạn chỉ cần chọn trang nào được truy cập cách đây lâu nhất. Và mỗi khi bạn truy cập lại một trang, bạn chỉ cần cập nhật dấu thời gian đó.
So say I have a database that has three pages, and my buffer pool has three pages. And so again, I can just maintain this linked list here. That's one way to do it.
Giả sử tôi có một cơ sở dữ liệu có ba trang, và buffer pool của tôi có ba trang. Và một lần nữa, tôi có thể duy trì danh sách liên kết này ở đây. Đó là một cách làm.
I could do a table where the order in which they exist in the linked list corresponds to the order in which they were last accessed. Yes? How do you store the metadata page tables?
Tôi cũng có thể dùng một bảng, trong đó thứ tự chúng xuất hiện trong danh sách liên kết tương ứng với thứ tự chúng được truy cập lần gần nhất. Vâng, bạn hỏi? Bạn lưu trữ bảng trang metadata như thế nào?
This question is, where would these timestamps be stored? Yeah, metadata page tables.
Câu hỏi là các dấu thời gian này sẽ được lưu ở đâu? Vâng, các bảng trang metadata.
The statement is, let me walk through this and I think it'll make sense. But yeah, when you go try to get a page, I want to get page one.
Ý là, để tôi đi qua từng bước và tôi nghĩ sẽ dễ hiểu hơn. Nhưng khi bạn cố lấy một trang, giả sử tôi muốn lấy trang một.
I go look at my buffer pool. I see that it exists there. So I don't have to go to disk and get it.
Tôi kiểm tra buffer pool của mình. Tôi thấy nó có ở đó. Vậy nên tôi không cần phải xuống đĩa để lấy nó.
But then I go find wherever it is in the LRU list. It could be a table. It doesn't matter. And I just move it to the front.
Nhưng sau đó tôi tìm xem nó nằm ở đâu trong danh sách LRU. Nó có thể là một bảng. Điều đó không quan trọng. Và tôi chỉ việc chuyển nó lên đầu.
And then I hand back the pointer to whoever wanted it. Yes?
Rồi tôi trả con trỏ lại cho bất kỳ ai cần nó. Vâng, bạn hỏi?
The statement is, if you have a list, why do you need the timestamp? You could store it as a list, but then you've got to search the list every time.
Câu hỏi là, nếu đã có danh sách thì tại sao cần dấu thời gian? Bạn có thể lưu dưới dạng danh sách, nhưng khi đó mỗi lần bạn phải tìm kiếm trong danh sách.
Or you have a table and you store the timestamp in the table. Effectively, the same way. This is just two representations. When I show LRU-K, I'll show the table.
Hoặc bạn dùng một bảng và lưu dấu thời gian trong bảng đó. Về cơ bản là như nhau. Đây chỉ là hai cách biểu diễn. Khi trình bày LRU-K, tôi sẽ cho các bạn xem bảng.
So then now, I want to attach something that I don't have memory in.
Vậy bây giờ, tôi muốn truy cập một trang mà tôi không còn chỗ trong bộ nhớ để chứa.
I pick whatever's on the last page at the end of the list and I go ahead and pick that and then free up space for the data that I want.
Tôi chọn trang nằm ở cuối danh sách và tiến hành chọn nó rồi giải phóng chỗ cho dữ liệu mà tôi muốn.
So again, this will give you the exact order in which the tables are being accessed. Maybe you actually don't need the exact order.
Vậy nên, một lần nữa, cách này sẽ cho bạn thứ tự chính xác mà các bảng được truy cập. Có thể thực ra bạn không cần thứ tự chính xác.
You can do a more simplified version called clock, which came out in 1969. And it's basically an approximate LRU.
Bạn có thể dùng một phiên bản đơn giản hơn gọi là clock, xuất hiện năm 1969. Về cơ bản nó là một dạng LRU xấp xỉ.
And the idea is now, instead of having a timestamp or a linked list to keep track of when things are accessed, I just have a simple reference counter, the single bit, for every single page.
Ý tưởng bây giờ là, thay vì dùng dấu thời gian hay danh sách liên kết để theo dõi thời điểm các trang được truy cập, tôi chỉ dùng một bộ đếm tham chiếu đơn giản, một bit duy nhất, cho mỗi trang.
And then now, all I need to do is check to see: has this bit been set? Has this page been accessed since the last time I checked it?
Và giờ tôi chỉ cần kiểm tra xem: bit này đã được đặt chưa? Trang này đã được truy cập kể từ lần cuối tôi kiểm tra nó chưa?
So at the very beginning, I would look at this one here. If I access page one, I'll set its reference count now to one. And then now there's this thing called the clock hand.
Vậy ngay từ đầu, tôi sẽ nhìn vào trang này ở đây. Nếu tôi truy cập trang một, tôi sẽ đặt bộ đếm tham chiếu của nó thành một. Và giờ có một thứ gọi là kim đồng hồ (clock hand).
I'm showing this in sort of a circling pattern, but obviously we store this in a list. It's just a cursor that goes through.
Tôi đang minh họa nó theo kiểu vòng tròn, nhưng tất nhiên ta lưu nó trong một danh sách. Nó chỉ là một con trỏ chạy qua các phần tử.
Anytime I want to evict something to free up a frame, I just go through and check to see whether the reference count is set to one.
Bất cứ khi nào tôi muốn loại bỏ một trang để giải phóng một frame, tôi chỉ việc duyệt qua và kiểm tra xem bộ đếm tham chiếu có bằng một không.
If it is, then I'd put it back to zero. And I keep scanning along until I find one where the reference count is zero.
Nếu có, tôi đặt nó về không. Và tôi tiếp tục quét cho đến khi tìm được trang có bộ đếm tham chiếu bằng không.
Meaning since the last time this algorithm ran, this page wasn't accessed, so therefore it's safe for me to go ahead and evict it. Yes?
Nghĩa là kể từ lần cuối thuật toán này chạy, trang này không được truy cập, nên tôi có thể yên tâm loại bỏ nó. Bạn hỏi à?
Statement is, I'm using the word page, but do I mean frames? So these are the pages that are in frames. So these are the pages that are in memory.
Ý bạn là, tôi dùng từ trang, nhưng có phải ý tôi là frame không? Đây là những trang nằm trong các frame. Tức là những trang đang nằm trong bộ nhớ.
A frame is a memory location where I can put a page in. So if you iterate over the memory, does the page ID matter?
Frame là một vị trí trong bộ nhớ nơi tôi có thể đặt một trang vào. Vậy nếu duyệt qua bộ nhớ, thì ID của trang có quan trọng không?
My statement is, am I iterating over the frame locations and not the page IDs? These are, it's a PowerPoint diagram, it doesn't matter.
Ý bạn là, tôi đang duyệt qua các vị trí frame chứ không phải các ID trang phải không? Đây chỉ là sơ đồ PowerPoint thôi, không quan trọng.
But in general, you would have the page table be the separate thing, you iterate over that. That's separate from the frames. Wait, no, sorry. Yes?
Nhưng nói chung, bạn sẽ có bảng trang (page table) là một thứ riêng, và bạn duyệt qua nó. Nó tách biệt với các frame. À không, xin lỗi. Bạn hỏi à?
So in the page table, you have all the possible page IDs, right? No, the page table is going to have what are pages that are in frames right now in memory.
Vậy trong bảng trang, bạn có tất cả các ID trang có thể có, đúng không? Không, bảng trang sẽ chứa những trang hiện đang nằm trong các frame trong bộ nhớ.
That's the page directory. The page directory is like, here's all the frames that exist. The page table says, here's the mapping from a page ID to a frame.
Đó là thư mục trang (page directory). Thư mục trang giống như: đây là tất cả các frame đang tồn tại. Bảng trang thì nói: đây là ánh xạ từ một ID trang tới một frame.
That are in memory. Yes.
Những trang đang ở trong bộ nhớ. Đúng vậy.
Because if I evict something, it's a hash map, but if I evict something, I evict, go back here, I evict page two, right?
Vì nếu tôi loại bỏ một trang, nó là một hash map, nhưng nếu tôi loại bỏ một trang, tôi loại bỏ, quay lại đây, tôi loại bỏ trang hai, đúng không?
In my page table, I'll have an entry for page two that's going to point to a frame where page two exists.
Trong bảng trang, tôi sẽ có một mục cho trang hai trỏ tới một frame nơi trang hai đang nằm.
So now when I want to go and evict it, I would say, assuming this algorithm runs, I said, "All right, I'm going to evict page two." I remove it from the page table.
Vậy khi tôi muốn loại bỏ nó, tôi sẽ nói, giả sử thuật toán này chạy, tôi nói: "Được rồi, tôi sẽ loại bỏ trang hai." Tôi xóa nó khỏi bảng trang.
So if anybody comes now looking for page two, they're not going to see it and they know they have a cache miss.
Vậy nếu giờ có ai tìm trang hai, họ sẽ không thấy nó và biết rằng đó là một cache miss.
So what's in the buffer pool, sorry, what's in the page table, is whatever's in the memory right now.
Vậy những gì có trong buffer pool, xin lỗi, những gì có trong bảng trang, là bất cứ thứ gì đang nằm trong bộ nhớ ngay lúc này.
We'll talk about ghost pages in a second, where you could keep track of all the pages. That's not this, though. That's later. I don't want to complicate things.
Lát nữa chúng ta sẽ nói về ghost page, nơi bạn có thể theo dõi tất cả các trang. Nhưng đó không phải cái này. Để sau. Tôi không muốn làm mọi thứ phức tạp thêm.
Other questions? Yes.
Còn câu hỏi nào khác không? Vâng, mời bạn.
This statement is, this is not a reference counter, it's just a bit. It's a reference count that goes up to one. Just one. That's it.
Câu này, đây không phải là bộ đếm tham chiếu, nó chỉ là một bit. Đó là một bộ đếm tham chiếu chỉ đếm tới một. Chỉ một thôi. Vậy thôi.
It's not a reference counter in terms of who has, yes, who's holding this page right now. It's just the same, because this thing references access.
Nó không phải bộ đếm tham chiếu theo nghĩa ai đang giữ, vâng, ai đang giữ trang này ngay lúc này. Nó chỉ như vậy thôi, vì cái này tham chiếu đến việc truy cập.
Yes, the terminology may be, it's hard to, they reuse a lot of these terms. It's called a reference bit, but it's really an access bit.
Vâng, thuật ngữ có thể hơi khó, họ tái sử dụng rất nhiều thuật ngữ này. Nó được gọi là reference bit, nhưng thực chất là access bit.
It was this thing accessed since the last time I checked.
Nó cho biết trang này có được truy cập kể từ lần cuối tôi kiểm tra hay không.
All right, and just looping through, set, bring in page five, set this reference count to zero, and I keep, say these other pages are accessed, so as I scan along, I change their reference bit to, back to zero, I come back up here, this guy's set to zero again, so I can go ahead, I can go ahead and evict it.
Được rồi, và cứ lặp qua các trang, đặt, nạp trang năm vào, đặt bộ đếm tham chiếu này về không, và giả sử các trang khác đang được truy cập, nên khi tôi quét dọc theo, tôi đổi reference bit của chúng về lại không, tôi quay lại đây, trang này lại bằng không, nên tôi có thể loại bỏ nó.
This is what basically Linux does, in its own internal page table. It's a multi-hand clock. The high-level idea is basically the same. Again, for some things this is okay.
Về cơ bản đây là điều Linux làm trong bảng trang nội bộ của nó. Đó là clock nhiều kim. Ý tưởng ở mức cao về cơ bản là giống nhau. Một lần nữa, với một số trường hợp thì thế này là ổn.
Again, we're not having exact listing, but this is probably good enough. Yes.
Chúng ta không có thứ tự chính xác, nhưng thế này có lẽ là đủ tốt. Vâng, mời bạn.
Yes, so he said, does this algorithm resume from the beginning, or where it left off last? That's where we left off last. Yes.
Vâng, bạn ấy hỏi, thuật toán này tiếp tục từ đầu, hay từ chỗ nó dừng lần trước? Là từ chỗ chúng ta dừng lần trước. Đúng vậy.
Yes, the statement is, and it's correct, this algorithm only runs when you need to evict something. Everything we're talking about today is how do you decide what to evict, when I need a frame.
Vâng, ý của bạn là, và điều đó đúng, thuật toán này chỉ chạy khi bạn cần loại bỏ thứ gì đó. Mọi thứ chúng ta nói hôm nay là làm sao quyết định loại bỏ cái gì, khi tôi cần một frame.
The clock's motion, does it only start when we're accessing through, that page five that wasn't evicted?
Kim đồng hồ chuyển động, nó chỉ bắt đầu khi chúng ta truy cập qua, trang năm mà không bị loại bỏ đó sao?
Is the clock constantly setting bits to one and zero, or does it only start when we're trying to access through? It's a question, when does the clock actually run?
Đồng hồ có liên tục đặt các bit thành một và không, hay nó chỉ bắt đầu khi chúng ta cố truy cập? Câu hỏi là khi nào đồng hồ thực sự chạy.
If I access a page, I set the bit to one. I have to.
Nếu tôi truy cập một trang, tôi đặt bit thành một. Bắt buộc phải vậy.
The clock sweep only occurs when someone says, I need a frame, I don't have any free ones, then it kicks in and runs, and it starts setting them back to zero.
Việc quét của kim đồng hồ chỉ xảy ra khi có ai đó nói, tôi cần một frame, tôi không còn frame trống nào, lúc đó nó mới khởi động và chạy, và bắt đầu đặt chúng về không.
The question is, why is this faster than LRU? Because the amount of metadata I have to recover for this is super simple. It's a bit.
Câu hỏi là, tại sao cách này nhanh hơn LRU? Vì lượng siêu dữ liệu tôi phải khôi phục cho việc này cực kỳ đơn giản. Chỉ là một bit.
Does this take longer? Is the computational complexity less than LRU? Again, it depends on how you...
Cách này có lâu hơn không? Độ phức tạp tính toán có thấp hơn LRU không? Một lần nữa, còn tùy bạn...
Sure, but when I...
Đúng, nhưng khi tôi...
It's like, it's O(1) to pop something off the end of the list, but when I have to update it, I got to go find it, and then put it to the front again.
Lấy một phần tử ra khỏi cuối danh sách là O(1), nhưng khi tôi phải cập nhật nó, tôi phải đi tìm nó, rồi đặt lại lên đầu.
Yeah. This is like, this is nothing. Right. I don't bring up this point yet. They bring up a very good point.
Vâng. Cái này thì chẳng đáng kể gì. Đúng vậy. Tôi chưa nêu điểm này ra. Bạn ấy đã nêu một điểm rất hay.
This is not your algorithms class, where like, oh, it's constant time, they're all the same. No, constants matter a lot. Like the difference between one millisecond and 10 milliseconds is a lot.
Đây không phải lớp thuật toán của các bạn, kiểu như "ồ, thời gian hằng số, nên tất cả đều như nhau". Không, các hằng số rất quan trọng. Chênh lệch giữa một mili giây và 10 mili giây là rất lớn.
That's an order of magnitude. So this isn't... I don't know who teaches algorithms. This isn't algorithms. We care about that. Right.
Đó là một bậc độ lớn. Nên đây không phải... Tôi không biết ai dạy thuật toán. Đây không phải thuật toán. Chúng ta quan tâm đến điều đó. Đúng.
So like, it is constant, but like, computation, the wall clock time is going to be significant. Yes. Does the clock start at the same point every time?
Nên nó là hằng số, nhưng về mặt tính toán, thời gian thực tế (wall clock time) sẽ đáng kể. Vâng. Kim đồng hồ có bắt đầu từ cùng một điểm mỗi lần không?
The question is, where does the clock start at the same point every time? No, because in that case, you'd be hammering whatever the first one is.
Câu hỏi là: kim đồng hồ có bắt đầu từ cùng một điểm mỗi lần không? Không, vì như vậy bạn sẽ liên tục dồn vào trang đầu tiên.
It's where you left off. So going back here. Right. So I flip this guy. Right. Say now the clock runs again. So these guys get access down below. Right. Set to one.
Nó bắt đầu từ chỗ đã dừng lại. Quay lại đây nhé. Tôi lật bit này. Đúng. Giả sử bây giờ đồng hồ chạy lại. Những trang này được truy cập ở bên dưới. Đặt thành một.
Then I got to evict something. When it starts, it starts where it left off. All right. I don't want to spend too much time on clock. Nodism does this.
Rồi tôi phải loại bỏ một trang. Khi bắt đầu, nó bắt đầu từ chỗ đã dừng lại. Được rồi. Tôi không muốn dành quá nhiều thời gian cho clock. Nodism làm như vậy.
It's just an approximation of LRU. LRU is actually common, but not in the simplified form that I showed before. And that's because both LRU and clock are susceptible to a problem called sequential flooding.
Nó chỉ là một phép xấp xỉ của LRU. LRU thực ra khá phổ biến, nhưng không phải ở dạng đơn giản hóa mà tôi đã trình bày trước đó. Đó là vì cả LRU và clock đều dễ gặp một vấn đề gọi là sequential flooding.
Basically means that if I have a query that comes along and does a sequential scan, which means I'm going to read the table from beginning to end, then that's going to blow away any recency information that I've been maintaining in my database system, these pages, because it's going to go through and rip out, throw away things, and put a bunch of pages into my buffer pool
Về cơ bản nghĩa là nếu có một truy vấn xuất hiện và thực hiện quét tuần tự, tức là tôi sẽ đọc bảng từ đầu đến cuối, thì điều đó sẽ xóa sạch thông tin về mức độ gần đây mà tôi vẫn duy trì trong hệ quản trị cơ sở dữ liệu, về các trang này, vì nó sẽ chạy qua, lôi ra, vứt bỏ mọi thứ, và đưa hàng loạt trang vào buffer pool của tôi
that maybe actually don't want to be in there. Because I only need it for that sequential scan. So I lose all sort of the information that I have about, again, the recency information.
mà có thể thực ra không nên nằm ở đó. Vì tôi chỉ cần chúng cho lần quét tuần tự đó. Vậy là tôi mất toàn bộ thông tin mà tôi có về một lần nữa, thông tin về mức độ gần đây.
It's basically polluting the buffer pool. And in some workloads, like OLAP for analytics, we'll talk about that next week, where you're not really doing single lookups on single keys.
Về cơ bản nó làm ô nhiễm buffer pool. Và trong một số khối lượng công việc, như OLAP cho phân tích, tuần sau chúng ta sẽ nói về nó, nơi bạn không thực sự tra cứu đơn lẻ trên từng khóa.
You're actually doing these scans over and over again. And you don't actually want least recency recently used. You actually want most recently used.
Bạn thực sự quét đi quét lại như vậy. Và bạn thực ra không muốn loại trang ít được dùng gần đây nhất. Bạn thực ra muốn trang được dùng gần đây nhất.
Because then you start playing games of, like, oh, I do my sequential scans, so I'll scan from beginning to end. Next query shows up.
Vì khi đó bạn bắt đầu chơi trò kiểu, ồ, tôi thực hiện quét tuần tự, nên tôi sẽ quét từ đầu đến cuối. Truy vấn tiếp theo xuất hiện.
Maybe I want to scan from the end to the beginning, because the pages that I just read are going to be in the buffer pool.
Có thể tôi muốn quét từ cuối về đầu, vì các trang tôi vừa đọc sẽ nằm sẵn trong buffer pool.
So what is sequential flooding? It looks like this. So say I have a query at the top. I'm doing a point query.
Vậy sequential flooding là gì? Nó trông như thế này. Giả sử tôi có một truy vấn ở trên cùng. Tôi thực hiện một truy vấn điểm.
I'm trying to find a single record where id equals 1, assuming id is the primary key. So somehow I figured out that id equals 1 is in page 0.
Tôi đang cố tìm một bản ghi duy nhất có id bằng 1, giả sử id là khóa chính. Bằng cách nào đó tôi xác định được id bằng 1 nằm ở trang 0.
So I go ahead and put that in my buffer pool. Then now a scan query comes along.
Thế là tôi đưa nó vào buffer pool. Rồi bây giờ có một truy vấn quét (scan) xuất hiện.
I want to compute the average from some column in the table, and that's going to go from beginning to end.
Tôi muốn tính giá trị trung bình của một cột nào đó trong bảng, và nó sẽ chạy từ đầu đến cuối.
And at some point, it's going to run, and it gets to this last page here, page 3. It doesn't have any more free space in the buffer pool.
Đến một lúc nào đó, nó chạy tới trang cuối cùng này, trang 3. Buffer pool không còn chỗ trống nào nữa.
So then it's got to run the LRU algorithm to decide what to kick out. Well, page 0 was the last thing that it read, the one that was least recently read.
Vậy nó phải chạy thuật toán LRU để quyết định đuổi trang nào ra. Trang 0 là trang được đọc gần nhất trước đó, và là trang được đọc cách đây lâu nhất.
I'm going to go ahead and evict that and put in page 3.
Tôi sẽ đuổi trang đó ra và đưa trang 3 vào.
But let's say this query at the top, where I'm doing these id lookups, that's actually super common, and I'm doing a bunch of lookups on this id equals 1.
Nhưng giả sử truy vấn ở trên cùng này, nơi tôi tra cứu theo id, thực ra rất phổ biến, và tôi thực hiện hàng loạt lần tra cứu với id bằng 1.
Workloads are very skewed, where people are always trying to read the same thing or write the same thing over and over. Like, Taylor Swift, she's on Instagram.
Khối lượng công việc rất lệch, tức là người ta luôn cố đọc cùng một thứ hoặc ghi cùng một thứ lặp đi lặp lại. Ví dụ Taylor Swift, cô ấy có trên Instagram.
Whenever her Instagram account versus some random guy's cat's Instagram account, there's more people reading Taylor Swift's thing rather than the cat guy's thing. So we want to keep the Taylor Swift thing in memory.
So tài khoản Instagram của cô ấy với tài khoản Instagram của con mèo nhà một anh chàng bình thường nào đó, thì có nhiều người đọc trang của Taylor Swift hơn là trang của anh chàng có con mèo. Vì vậy ta muốn giữ dữ liệu của Taylor Swift trong bộ nhớ.
But if we're just using LRU, we wouldn't be able to do that, because we would not know that Taylor Swift is popular.
Nhưng nếu chỉ dùng LRU thì ta không làm được điều đó, vì ta sẽ không biết Taylor Swift nổi tiếng.
And we would end up evicting her page if we use that basic LRU algorithm.
Và ta sẽ đuổi trang của cô ấy ra nếu dùng thuật toán LRU cơ bản đó.
So you say, "All right, well, what if I do something like keep track of how often these pages are being used?
Bạn sẽ nói: "Được rồi, nếu tôi theo dõi tần suất các trang được sử dụng thì sao?
And then when I want to run my eviction algorithm, I want to do the one that has been the least frequently accessed."
Và khi muốn chạy thuật toán đuổi trang, tôi sẽ chọn trang được truy cập ít thường xuyên nhất."
Just maintain a counter for every single page of how often they're being accessed and when they're in memory.
Chỉ cần duy trì một bộ đếm cho mỗi trang về việc chúng được truy cập bao nhiêu lần khi đang nằm trong bộ nhớ.
And then now when I want to evict something, I can pick whatever one that has the smallest count. Seems reasonable. Of course, there's a paper on this from 1971, two years after Clock.
Và khi muốn đuổi một trang ra, tôi có thể chọn trang có số đếm nhỏ nhất. Nghe có vẻ hợp lý. Tất nhiên, có một bài báo về cách này từ năm 1971, hai năm sau Clock.
Well, this causes more problems because now, to his point about the complexity, now it's logarithmic complexity maintaining this information for all the table.
Nhưng cách này gây ra nhiều vấn đề hơn, vì, theo ý của bạn ấy về độ phức tạp, giờ việc duy trì thông tin này có độ phức tạp logarit cho toàn bộ bảng.
And then furthermore, if I have someone that does something weird, like go look up the cat guy's Instagram account in the middle of the night a billion times, and then at no point did everyone go back and look at that cat guy's account, his counter's gonna be super high and I'm never gonna end up evicting it, even though it's not useful anymore at all,
Hơn nữa, nếu có ai đó làm điều kỳ quặc, như đi tra cứu tài khoản Instagram của anh chàng có con mèo vào giữa đêm cả tỉ lần, và sau đó không ai quay lại xem tài khoản của anh chàng đó nữa, thì bộ đếm của nó sẽ cực cao và tôi sẽ không bao giờ đuổi nó ra, dù nó hoàn toàn không còn hữu ích nữa,
because there's no information about time in this count. It's just like how many times was it accessed? Now, how long ago was it accessed?
vì số đếm này không có thông tin gì về thời gian. Nó chỉ cho biết trang được truy cập bao nhiêu lần. Chứ không cho biết nó được truy cập cách đây bao lâu.
So the solution to this is a simple enhancement that came out in the early 90s called LRU-K. And there's a great paper that talks about this.
Giải pháp cho vấn đề này là một cải tiến đơn giản xuất hiện vào đầu những năm 90 gọi là LRU-K. Và có một bài báo rất hay nói về nó.
And this is actually what's used in SQL Server. This is actually what Postgres implemented first in the late 90s, written by this guy Tom Lane, who did his PhD here at CMU.
Và đây thực sự là thứ được dùng trong SQL Server. Đây cũng là thứ Postgres cài đặt đầu tiên vào cuối những năm 90, do Tom Lane viết, người đã làm tiến sĩ ở đây tại CMU.
And the basic idea is that we're gonna maintain multiple LRU lists.
Ý tưởng cơ bản là chúng ta sẽ duy trì nhiều danh sách LRU.
And then when it comes time to evict something, we're going to calculate the length of time from when it was last accessed, or the oldest access, to the current time.
Và khi đến lúc cần loại bỏ một thứ gì đó, chúng ta sẽ tính khoảng thời gian từ lần truy cập gần nhất của nó, hoặc lần truy cập cũ nhất, đến thời điểm hiện tại.
And then that way we can decide who has been accessed the longest ago.
Nhờ vậy chúng ta có thể quyết định trang nào đã được truy cập cách đây lâu nhất.
And since now we're gonna have these multiple LRU lists, we would know whether someone just accessed something once and never accessed it again.
Và vì bây giờ chúng ta có nhiều danh sách LRU như thế này, chúng ta sẽ biết được liệu có ai đó chỉ truy cập một thứ gì đó một lần rồi không bao giờ truy cập lại nữa hay không.
And so therefore we don't have that blowout before where someone has a high count that never comes back.
Do đó chúng ta không gặp tình trạng bị lệch như trước, khi một trang có số đếm cao nhưng không bao giờ được truy cập lại.
So in order to make sure that if we evict something and then bring it back in, we don't have to learn from scratch all over again that this thing is a hot page or not, we can actually also maintain what are called ghost caches or ghost lists, where we can keep track of, even though something got evicted, we'll still keep in memory its access timestamps,
Vậy để đảm bảo rằng nếu chúng ta loại bỏ một thứ rồi đưa nó trở lại, chúng ta không phải học lại từ đầu xem trang này có phải là trang nóng hay không, chúng ta thực ra cũng có thể duy trì cái gọi là ghost cache hay ghost list, trong đó chúng ta theo dõi, dù một thứ đã bị loại bỏ, chúng ta vẫn giữ trong bộ nhớ các dấu thời gian truy cập của nó,
so that when we go fetch it back in the second time around, we can pre-populate our LRU lists or timestamps with what it was before it got written out to disk.
để khi chúng ta nạp nó lại lần thứ hai, chúng ta có thể điền sẵn vào các danh sách LRU hoặc các dấu thời gian giá trị mà nó có trước khi bị ghi ra đĩa.
So again, this now provides more persistence into our algorithms so that we write things out and we're not just learning from scratch all over again. So let's look at a simple example.
Một lần nữa, điều này giúp thuật toán của chúng ta có tính lưu giữ lâu hơn, để khi ghi dữ liệu ra ngoài, chúng ta không phải học lại từ đầu. Hãy xem một ví dụ đơn giản.
So now instead of using a linked list to keep track of the ordering, I'm going to maintain this separate table.
Bây giờ thay vì dùng danh sách liên kết để theo dõi thứ tự, tôi sẽ duy trì một bảng riêng này.
And you can think of this as like the page table where I'm just maintaining timestamps of things.
Bạn có thể xem nó giống như page table, trong đó tôi chỉ lưu các dấu thời gian của các trang.
So say that in the past I've accessed pages 0, 1, and 2, and that's what's in my buffer pool.
Giả sử trước đây tôi đã truy cập các trang 0, 1 và 2, và đó là những gì có trong buffer pool của tôi.
And assume the timestamp is just a monotonically increasing counter, like a 32-bit integer, like 1, 2, 3, 4, 5, 6, and so forth. So the query starts off here.
Và giả sử dấu thời gian chỉ là một bộ đếm tăng đơn điệu, như một số nguyên 32 bit, kiểu 1, 2, 3, 4, 5, 6, và cứ thế. Truy vấn bắt đầu ở đây.
I have an IN clause where I want to access four different values on four different pages. Now I'm going to show this in sort of the order that they're specified in the IN clause.
Tôi có một mệnh đề IN muốn truy cập bốn giá trị khác nhau trên bốn trang khác nhau. Bây giờ tôi sẽ trình bày theo thứ tự mà chúng được chỉ định trong mệnh đề IN.
But again, SQL is unordered.
Nhưng như đã nói, SQL không có thứ tự.
So in actuality, you would actually want the system to figure out what pages these records are on, like 1, 31, 11, and 41, and then do them in sequential order.
Nên thực tế, bạn sẽ muốn hệ thống tự xác định các bản ghi này nằm trên những trang nào, như 1, 31, 11 và 41, rồi xử lý chúng theo thứ tự tuần tự.
But for simplicity, or to show how the page history works, I'm going to have them jump around randomly.
Nhưng để cho đơn giản, hoặc để cho thấy lịch sử trang hoạt động thế nào, tôi sẽ cho chúng nhảy lung tung một cách ngẫu nhiên.
So when my query starts off, I want to read ID equals 1. That's in page 0.
Khi truy vấn bắt đầu, tôi muốn đọc ID bằng 1. Nó nằm ở trang 0.
So now because I already have this entry in my buffer pool, I'm going to have the two columns. One is going to be the last access, the most recent one.
Vì tôi đã có mục này trong buffer pool rồi, tôi sẽ có hai cột. Một cột là lần truy cập cuối, tức lần gần nhất.
And then the second access, since we're doing k equals 2 here, I'll have a second list and keep track of the oldest timestamp for this.
Và cột thứ hai là lần truy cập thứ hai, vì ở đây k bằng 2, tôi sẽ có danh sách thứ hai và theo dõi dấu thời gian cũ nhất cho nó.
So at the very beginning, if I access it once, there's nothing in that second column. And again, I'm showing k equals 2. You can go up to k equals 6.
Vậy ngay từ đầu, nếu tôi truy cập nó một lần, thì cột thứ hai đó sẽ không có gì. Và một lần nữa, ở đây tôi đang minh họa k bằng 2. Bạn có thể tăng lên đến k bằng 6.
Some systems can do that.
Một số hệ thống có thể làm được như vậy.
All right, so in this case here, because now I'm going to access it at timestamp 4, 1 gets slid over to the other column, and then I'm put timestamp 4 here.
Được rồi, vậy trong trường hợp này, vì bây giờ tôi sẽ truy cập nó tại dấu thời gian 4, 1 được đẩy sang cột bên kia, và sau đó tôi đặt dấu thời gian 4 vào đây.
Then now I jump down to access page 3. All right, so now this is not in memory in our page table.
Tiếp theo, tôi nhảy xuống để truy cập trang 3. Được rồi, bây giờ trang này không nằm trong bộ nhớ, tức là không có trong bảng trang của chúng ta.
So we've got to decide what we want to evict to free up space to put into memory. So the eviction policy is going to take whatever the current timestamp is for us.
Vì vậy chúng ta phải quyết định sẽ loại bỏ trang nào để giải phóng chỗ đưa vào bộ nhớ. Chính sách loại bỏ sẽ lấy dấu thời gian hiện tại của chúng ta.
Again, that's just a counter increasing. And then we look at the oldest last access timestamp, with the kth one.
Một lần nữa, đó chỉ là một bộ đếm tăng dần. Sau đó chúng ta xem dấu thời gian truy cập cuối cùng cũ nhất, tức là lần thứ k.
So in this case, k equals 2. We'll look at the last access number 2 column. And we'll just subtract that to figure out what the distance is between those two accesses.
Trong trường hợp này, k bằng 2. Chúng ta sẽ xem cột lần truy cập cuối thứ 2. Và chúng ta chỉ cần lấy hiệu để tìm ra khoảng cách giữa hai lần truy cập đó.
And then choose whatever one is the largest, meaning it's been the longest since it was last accessed before. If you don't have an entry in the second column, you just use infinity.
Sau đó chọn trang nào có giá trị lớn nhất, nghĩa là trang đó đã lâu nhất kể từ lần truy cập trước đó. Nếu không có giá trị ở cột thứ hai, bạn chỉ cần dùng vô cực.
And if you have ties, you just pick whatever one that has the oldest timestamp. So again, we're going to look at the second column here.
Và nếu có nhiều trang bằng nhau, bạn chỉ cần chọn trang có dấu thời gian cũ nhất. Vậy một lần nữa, chúng ta sẽ xem cột thứ hai ở đây.
You just go through, take the current timestamp, 5, subtract it by whatever's in the second column. In this case here, because it's time 5, subtract it by 1, you get 4.
Bạn duyệt qua, lấy dấu thời gian hiện tại, là 5, rồi trừ đi giá trị trong cột thứ hai. Ở đây, vì là thời điểm 5, trừ đi 1, bạn được 4.
But then the other two guys don't have entries there, so it's infinity. So then now, I would say, all right, well, both of these are infinity.
Nhưng hai trang còn lại không có giá trị ở đó, nên là vô cực. Vậy bây giờ, tôi sẽ nói, được rồi, cả hai trang này đều là vô cực.
I'm going to pick whatever one has the smallest timestamp, the oldest timestamp in the first column.
Tôi sẽ chọn trang có dấu thời gian nhỏ nhất, tức là dấu thời gian cũ nhất ở cột đầu tiên.
In this case here, it would be page 1. We go ahead and evict that and put that in. And then we update it to page 5. Do it again.
Trong trường hợp này, đó là trang 1. Chúng ta loại bỏ nó và đưa trang mới vào. Và sau đó chúng ta cập nhật thành trang 5. Làm lại lần nữa.
So now if I access page 1, that's the thing I just evicted. So it's not in memory.
Bây giờ nếu tôi truy cập trang 1, là trang tôi vừa loại bỏ. Vậy nó không nằm trong bộ nhớ.
So I've got to do that same algorithm that before, where I just subtract whatever the timestamp is with the last access one. In this case here, the two bottom ones are still infinity.
Nên tôi phải chạy lại đúng thuật toán như trước, trong đó tôi lấy dấu thời gian hiện tại trừ đi dấu thời gian của lần truy cập cuối. Trong trường hợp này, hai trang phía dưới vẫn là vô cực.
I pick page 2, because its timestamp is 3. It's less than 5. So that's where I'm going to go ahead and evict it. So that's where I'll put page 1.
Tôi chọn trang 2, vì dấu thời gian của nó là 3. Nó nhỏ hơn 5. Vậy tôi sẽ loại bỏ nó. Và đó là chỗ tôi sẽ đặt trang 1.
But now, again, remember, I can say I have that ghost list or ghost cache, where I keep track of the timestamps of pages I just evicted. So I just evicted page 1 from 4.
Nhưng bây giờ, hãy nhớ rằng tôi có thể có danh sách ma hay bộ nhớ đệm ma, nơi tôi theo dõi dấu thời gian của các trang vừa bị loại bỏ. Vậy tôi vừa loại bỏ trang 1 ở thời điểm 4.
So I can go ahead, if I have the ghost cache, I can put timestamp 2 in there.
Nên nếu có bộ nhớ đệm ma, tôi có thể đặt dấu thời gian 2 vào đó.
And that way, if the eviction policy runs again, this doesn't end up getting thrown out immediately all over again. I access the last page, page 4. Again, run the same algorithm.
Và như vậy, nếu chính sách loại bỏ chạy lại, trang này sẽ không bị loại bỏ ngay lập tức một lần nữa. Tôi truy cập trang cuối cùng, trang 4. Một lần nữa, chạy cùng thuật toán.
Run the same calculation. Now I get this middle guy here, because he hasn't been accessed twice. I'm going to go ahead and evict page 3 and put page 4 in there. Yes?
Chạy cùng phép tính. Bây giờ tôi chọn trang ở giữa này, vì nó chưa được truy cập hai lần. Tôi sẽ loại bỏ trang 3 và đưa trang 4 vào đó. Bạn hỏi gì?
The question is, is the ghost cache part of the page table, or is that a separate data structure? It's usually a separate data structure. It's not that big, so it's not a big deal.
Câu hỏi là bộ nhớ đệm ma có là một phần của bảng trang hay là một cấu trúc dữ liệu riêng biệt? Thường nó là một cấu trúc dữ liệu riêng. Nó không lớn lắm, nên không thành vấn đề.
Yes?
Bạn hỏi gì?
The question is, is this timestamp, is this, I'm assuming it's a logical counter. Would you do that in a real system, or would you use, like, hover clocks, like the wall clock time?
Câu hỏi là dấu thời gian này, thì tôi đoán đây là một bộ đếm logic. Trong một hệ thống thực tế thì bạn có làm như vậy không, hay bạn sẽ dùng kiểu đồng hồ treo, tức là thời gian đồng hồ treo tường?
You typically would use a logical one, because the wall clock time can change when there's, like, daylight savings and things like that. Time can go backwards.
Thông thường bạn sẽ dùng bộ đếm logic, vì thời gian đồng hồ có thể thay đổi khi có, ví dụ, giờ mùa hè và những thứ tương tự. Thời gian có thể đi lùi.
That's going to be a bigger problem when we talk about transactions later on, how to deal with that. Yeah. Oh, time is terrible. Yeah. Other questions?
Đó sẽ là vấn đề lớn hơn khi sau này chúng ta nói về giao dịch, về cách xử lý chuyện đó. Vâng. Ồ, thời gian thật là rắc rối. Vâng. Còn câu hỏi nào khác không?
OK, so let me show a sort of simplified version that MySQL uses called approximate LRU-K. And the basic idea is that they're still going to have one linked list.
Được rồi, giờ để tôi trình bày một phiên bản đơn giản hóa mà MySQL sử dụng, gọi là approximate LRU-K. Ý tưởng cơ bản là họ vẫn chỉ dùng một danh sách liên kết.
And again, it could be a table. It could be a linked list. It doesn't matter. But they're going to partition it into young and old regions.
Và một lần nữa, nó có thể là một bảng hoặc một danh sách liên kết. Không quan trọng. Nhưng họ sẽ chia nó thành vùng trẻ và vùng cũ.
And you're going to have two entry points into the linked list that allow you to find the beginning of the old region and the beginning of the new region, the young region.
Và bạn sẽ có hai điểm vào danh sách liên kết cho phép bạn tìm thấy phần đầu của vùng cũ và phần đầu của vùng mới, tức vùng trẻ.
So now when I access a page, say accessing page one here, I've got to evict something, because it's not in my buffer pool.
Bây giờ khi tôi truy cập một trang, ví dụ truy cập trang một ở đây, tôi phải loại bỏ một thứ gì đó, vì nó không có trong buffer pool của tôi.
So I'll pick whatever is a go into the old list, slide everything over by one. So I'm going to get rid of page eight.
Nên tôi sẽ chọn một trang vào danh sách cũ, dịch mọi thứ sang một vị trí. Vậy tôi sẽ loại bỏ trang tám.
These guys slide over, and that's where I'm going to put page one in.
Những trang này dịch sang, và đó là chỗ tôi đặt trang một vào.
And the reason I'm going to put it in the old list right at the beginning there is because if I never access page one again, then it'll just get sloughed off at the end.
Lý do tôi đặt nó vào ngay đầu danh sách cũ là vì nếu tôi không bao giờ truy cập trang một nữa, thì nó sẽ tự bị đẩy ra ở cuối.
No big deal.
Không có gì to tát.
But if I do now access page one again, Then what I want to do is now put it at the beginning of the young list, because I'm saying, oh, this clearly is important, because it keeps getting accessed again.
Nhưng nếu tôi truy cập lại trang một, thì lúc đó tôi muốn đặt nó vào đầu danh sách trẻ, vì tôi cho rằng, rõ ràng trang này quan trọng, vì nó cứ liên tục được truy cập lại.
So let me go improve its chance not to get evicted very soon while putting it to the front of the young list.
Vậy hãy tăng cơ hội để nó không bị loại bỏ quá sớm bằng cách đặt nó lên đầu danh sách trẻ.
Again, it's approximate. It's not exactly the way LRU-K did it, but it kind of gives you roughly the same benefits.
Một lần nữa, đây chỉ là xấp xỉ. Nó không đúng hệt cách LRU-K làm, nhưng nó mang lại những lợi ích gần tương tự.
All right, I want to talk about this ARC one, because this is what you have to implement in project one.
Được rồi, tôi muốn nói về ARC này, vì đây là thứ các bạn phải cài đặt trong project một.
And as I said, the projects this year are harder than the previous years, because you can, by all means, use LLMs to help you code. So this is called the adaptive replacement cache.
Và như tôi đã nói, các project năm nay khó hơn các năm trước, vì các bạn hoàn toàn có thể dùng LLM để hỗ trợ viết mã. Cái này gọi là adaptive replacement cache.
It was invented by IBM Research, actually, for the disk storage systems. But I think it went into IBM DB2. It's in ZFS as well.
Thực ra nó được IBM Research phát minh cho các hệ thống lưu trữ trên đĩa. Nhưng tôi nghĩ nó đã được đưa vào IBM DB2. Nó cũng có trong ZFS.
And it actually was in Postgres. It was added in Postgres 2004 or 2005. But IBM patented this, and the Postgres people were kind of worried about that.
Và nó từng có trong Postgres. Nó được thêm vào Postgres năm 2004 hoặc 2005. Nhưng IBM đã đăng ký bằng sáng chế, và những người làm Postgres khá lo ngại về điều đó.
So they made some little tweaks to the algorithm to make it look less like the patent, although IBM hasn't enforced it. And actually, I think it expires next year.
Nên họ đã chỉnh sửa đôi chút thuật toán để nó trông ít giống bằng sáng chế hơn, dù IBM chưa từng thực thi quyền đó. Và thực ra, tôi nghĩ nó sẽ hết hạn vào năm sau.
But this is roughly considered the state-of-the-art for buffer replacement algorithm.
Nhưng cái này đại khái được xem là hiện đại nhất cho thuật toán thay thế buffer.
But the basic idea is that we want to get all the benefit of something like least recently used, as well as the benefit of least frequently used.
Nhưng ý tưởng cơ bản là chúng ta muốn có được toàn bộ lợi ích của thứ như least recently used, cũng như lợi ích của least frequently used.
But instead of having to maintain separate lists, instead of having to balance how much we're going to depend on one list versus the other, and you have to manually tune that, we instead want to have this built-in policy that decides how to size up the different lists based on the access patterns of the query.
Nhưng thay vì phải duy trì các danh sách riêng biệt, thay vì phải cân bằng mức độ chúng ta dựa vào danh sách này so với danh sách kia, và phải tự tay tinh chỉnh điều đó, chúng ta muốn có một chính sách tích hợp sẵn để quyết định cách điều chỉnh kích thước các danh sách khác nhau dựa trên các mẫu truy cập của truy vấn.
And then, of course, we're going to maintain a ghost list to keep track of what things have been evicted recently, so that if we go fetch them back in, We can record that history and rely on that.
Và tất nhiên, chúng ta sẽ duy trì một ghost list để theo dõi những thứ vừa bị loại ra gần đây, để nếu chúng ta nạp chúng lại, chúng ta có thể ghi lại lịch sử đó và dựa vào nó.
So in the sake of time, I mean, I know we did this for the project, but you can follow up online to do a recitation of this separately.
Vì thời gian có hạn, tôi biết là chúng ta đã làm phần này trong project, nhưng các bạn có thể xem thêm trực tuyến để có một buổi thảo luận riêng về nó.
But basically, there's these multiple lists we're going to maintain.
Về cơ bản, có nhiều danh sách mà chúng ta sẽ duy trì.
There's this parameter P, where we keep track of how much we're going to favor putting things in the least recently used list, the recent list, or the frequent list.
Có tham số P này, dùng để theo dõi mức độ chúng ta ưu tiên đặt các thứ vào danh sách least recently used, tức danh sách recent, hay danh sách frequent.
And so if we find ourselves accessing the same things over and over again, then we'll allow the size of the pages we're tracking in the frequent list to grow and, of course, finally shrink the recent list.
Và nếu chúng ta thấy mình truy cập cùng những thứ đó lặp đi lặp lại, thì chúng ta sẽ cho phép số trang mà ta theo dõi trong danh sách frequent tăng lên và, tất nhiên, thu nhỏ danh sách recent lại.
So you sort of automatically get the best of both worlds, of both least recently used and least frequently used. And it can eventually narrow in on exactly what the workload actually wants.
Như vậy bạn tự động có được những điểm tốt nhất của cả hai, của cả least recently used lẫn least frequently used. Và cuối cùng nó có thể hội tụ về đúng thứ mà workload thực sự cần.
And because it's dynamic, if the workload changes over time and the access pattern changes over time, this thing can handle it.
Và vì nó mang tính động, nếu workload thay đổi theo thời gian và mẫu truy cập thay đổi theo thời gian, thì thứ này vẫn xử lý được.
So again, we'll follow up and do a separate recitation on the algorithm because you'll need it for the project. And there's a lot of videos online that show us how this works.
Vậy nên, chúng ta sẽ có một buổi thảo luận riêng về thuật toán này vì các bạn sẽ cần nó cho project. Và có rất nhiều video trực tuyến cho thấy nó hoạt động như thế nào.
But it's basically the same concepts we had before, except you have this P parameter that changes where things are going to go.
Nhưng về cơ bản vẫn là những khái niệm chúng ta đã có trước đây, chỉ khác là bạn có tham số P này làm thay đổi nơi các thứ sẽ được đặt vào.
Other tricks you can do to make things go better is to have information about how the page is actually going to be used.
Những mẹo khác để mọi thứ chạy tốt hơn là có thông tin về việc trang thực sự sẽ được sử dụng như thế nào.
Like, if I know that I'm doing a query, scanning a table for a sequential scan, and it's unlikely that this table is going to be used by other queries, then I don't want to put it into my global buffer pool.
Chẳng hạn, nếu tôi biết mình đang chạy một truy vấn, quét một bảng bằng sequential scan, và bảng này khó có khả năng được các truy vấn khác dùng, thì tôi không muốn đưa nó vào buffer pool toàn cục của mình.
I want to have a little separate side cache, a separate portion of the buffer pool, that's dedicated just for my one query that's running.
Tôi muốn có một cache phụ nhỏ riêng biệt, một phần riêng của buffer pool, được dành riêng cho một truy vấn đang chạy của tôi.
So then now, as I'm scanning through, I'm not putting things in the global buffer pool. ...and having that run into an additional policy.
Vậy là khi tôi quét qua, tôi không đưa các thứ vào buffer pool toàn cục. ...và phải chịu thêm một chính sách bổ sung.
I'm putting this in my own little buffer pool on the side. But it's really just a partition piece of the total amount of memory that's available for the system.
Tôi đưa nó vào buffer pool nhỏ riêng của mình ở bên cạnh. Nhưng thực chất nó chỉ là một phần được chia ra từ tổng dung lượng bộ nhớ có sẵn cho hệ thống.
So Postgres does this.
Postgres làm đúng như vậy.
They basically maintain a circular ring buffer for some portion of the buffer pool, so that every time I ask for a new page, I'm just appending to the end, and then eventually it'll wrap back around.
Về cơ bản, họ duy trì một vòng tròn đệm cho một phần của buffer pool, để mỗi khi tôi yêu cầu một trang mới, tôi chỉ việc nối thêm vào cuối, và cuối cùng nó sẽ quay vòng trở lại.
So it's really cheap to actually implement. And again, you minimize the effect of sequential scans, or sequential flooding, on the rest of the system.
Nên việc cài đặt nó thực sự rất rẻ. Và một lần nữa, bạn giảm thiểu ảnh hưởng của các lần quét tuần tự, hay sequential flooding, lên phần còn lại của hệ thống.
Another trick you can do is maintain priority hints about how the execution is using this data and what's actually in the pages, so that when the buffer pool replacement algorithm runs, it knows to avoid pages that it somehow thinks are more important than other pages.
Một mẹo khác là duy trì các gợi ý về mức ưu tiên về cách quá trình thực thi đang dùng dữ liệu này và về nội dung thực sự nằm trong các trang, để khi thuật toán thay thế của buffer pool chạy, nó biết cần tránh những trang mà nó cho là quan trọng hơn các trang khác.
So think of something like, I have an index. We haven't talked about B+trees yet, but assume it's a tree data structure.
Hãy nghĩ đến một ví dụ, tôi có một chỉ mục. Chúng ta chưa học về B+tree, nhưng cứ coi đó là một cấu trúc dữ liệu dạng cây.
And so I would have priority hints for my pages and say, the top of the index, the first page, that's super important, because that's where everyone has to go to in order to get inside the data structure and figure out where they need to go.
Và tôi sẽ có các gợi ý ưu tiên cho các trang, chẳng hạn đỉnh của chỉ mục, trang đầu tiên, là cực kỳ quan trọng, vì đó là nơi mọi người đều phải đi qua để vào cấu trúc dữ liệu và tìm ra chỗ cần đến.
So we think of, like, this is not valid in SQL, but assume I'm inserting values where I'm just incrementing some counter by one over and over again.
Giả sử, câu này không hợp lệ trong SQL, nhưng cứ giả sử tôi đang chèn các giá trị mà tôi chỉ tăng một bộ đếm lên một đơn vị lặp đi lặp lại.
Well, if I'm sorted along from min value to max value along the bottom, along my leaf nodes, then any time I want to insert something, I always got to go to the root.
Nếu tôi được sắp xếp từ giá trị nhỏ nhất đến lớn nhất ở phía dưới, dọc theo các nút lá, thì mỗi khi muốn chèn thứ gì, tôi luôn phải đi qua nút gốc.
And I'm always going to go down on this side of the tree. So therefore, I should tell my data system, hey, the index page 0, that's super important.
Và tôi luôn đi xuống về phía bên này của cây. Vì vậy, tôi nên nói với hệ quản trị dữ liệu rằng, trang chỉ mục 0 là cực kỳ quan trọng.
Yes, I would see that it's being accessed all the time as part of my frequency information. But maybe I want to make sure that the data system, no matter what, never pages it out.
Đúng, tôi sẽ thấy nó được truy cập liên tục trong thông tin về tần suất. Nhưng có thể tôi muốn đảm bảo rằng hệ thống dù thế nào cũng không bao giờ đẩy nó ra khỏi bộ nhớ.
Because the first thing I'm always going to do if I want to access the index is go to that root. And same thing if I want to do a lookup.
Vì việc đầu tiên tôi luôn làm nếu muốn truy cập chỉ mục là đi tới nút gốc đó. Và tương tự nếu tôi muốn thực hiện một lần tra cứu.
There's other tricks you can do about priorities.
Còn có những mẹo khác về mức ưu tiên.
Like if I know that there's a transaction that's running multiple queries, and the first thing it does is read some record and then immediately update that record, I don't want that to look like two separate unique accesses to my Buffer Pool Manager.
Ví dụ, nếu tôi biết có một transaction đang chạy nhiều truy vấn, và việc đầu tiên nó làm là đọc một bản ghi rồi lập tức cập nhật chính bản ghi đó, tôi không muốn điều đó trông như hai lần truy cập riêng biệt đối với Buffer Pool Manager.
I want to tell it, oh, by the way, this is part of the same transaction. Therefore, it only updates the access counter once.
Tôi muốn nói với nó rằng, nhân tiện, đây là một phần của cùng một transaction. Do đó, nó chỉ cập nhật bộ đếm truy cập một lần.
Because it didn't become more popular because everyone's trying to access it. It's just one transaction trying to access it multiple times. So SQL Server can do stuff like that.
Vì trang đó không trở nên phổ biến hơn do nhiều người cùng truy cập. Chỉ là một transaction truy cập nó nhiều lần. SQL Server có thể làm những việc như vậy.
So again, there's a bunch of hints and a bunch of information we can provide to the Buffer Pool Manager based on how we know queries are accessing this data.
Vậy nên, có rất nhiều gợi ý và nhiều thông tin mà chúng ta có thể cung cấp cho Buffer Pool Manager dựa trên việc chúng ta biết các truy vấn đang truy cập dữ liệu này như thế nào.
And I didn't say this at the beginning, but I'll say this multiple times throughout the semester: this is one of the things that's going to separate the expensive enterprise systems, like the Oracles, DB2s, the Teradatas, from the open source systems like Postgres, MySQL, and SQLite.
Và lúc đầu tôi chưa nói điều này, nhưng tôi sẽ nhắc lại nhiều lần trong suốt học kỳ: đây là một trong những điểm sẽ phân biệt các hệ thống doanh nghiệp đắt tiền như Oracle, DB2, Teradata với các hệ thống mã nguồn mở như Postgres, MySQL và SQLite.
They're going to have to spend a lot more time and a lot more money to make these Buffer Pool replacement algorithms as sophisticated as possible. Like the ARC thing is in IBM.
Họ sẽ phải bỏ ra nhiều thời gian hơn và nhiều tiền hơn rất nhiều để làm cho các thuật toán thay thế trong Buffer Pool này tinh vi nhất có thể. Ví dụ như ARC là của IBM.
That paper came out, and the Postgres has implemented it. But it's not public. But there's a bunch more things they've added since then in the DB2 version.
Bài báo đó được công bố, và Postgres đã cài đặt nó. Nhưng nó không công khai. Nhưng kể từ đó họ còn bổ sung thêm rất nhiều thứ nữa trong phiên bản DB2.
All right, so what happens now if we want to evict a page?
Được rồi, vậy điều gì xảy ra nếu bây giờ ta muốn loại bỏ một trang?
And we've identified this one we want to remove, but it's been marked dirty, meaning some part of the system has modified the changes since it was brought into memory.
Và ta đã xác định được trang muốn xóa, nhưng nó đã bị đánh dấu là dirty, nghĩa là một phần nào đó của hệ thống đã sửa đổi nó kể từ khi nó được đưa vào bộ nhớ.
And therefore, we can't just throw it away. We have to go write it back out the disk before we can reuse the frame.
Do đó, ta không thể cứ thế vứt nó đi. Ta phải ghi nó ngược ra đĩa trước khi có thể dùng lại frame.
So if the page has not been modified, then it's super easy for us, because again, we just drop the memory. No big deal.
Vậy nếu trang chưa bị sửa đổi, thì rất dễ cho ta, vì ta chỉ cần bỏ phần bộ nhớ đó đi. Không có gì to tát.
If it has been modified, then in order for us to use that frame, we have to wait until we write that data out the disk. It gets flushed.
Nếu nó đã bị sửa đổi, thì để dùng được frame đó, ta phải đợi cho đến khi ghi dữ liệu đó ra đĩa. Nó được flush.
In some cases, we have to write out another record or another page that tells us about what was modified in that page, like a log record. We have to flush that page.
Trong một số trường hợp, ta phải ghi ra thêm một bản ghi hoặc một trang khác cho biết những gì đã được sửa trong trang đó, chẳng hạn như một bản ghi log. Ta phải flush trang đó.
Then we flush the other page before we can free that frame up. And that's obviously going to be slow for us.
Rồi flush trang kia trước khi có thể giải phóng frame. Và rõ ràng điều đó sẽ làm ta chậm đi.
So what we want, ideally, is when our buffer replacement algorithm runs, we only want to consider clean pages.
Vì vậy, lý tưởng nhất là khi thuật toán thay thế trong buffer chạy, ta chỉ muốn xét các trang sạch.
The more clean pages that we have, the better chance we have of finding one that will be least likely be used in the future.
Càng có nhiều trang sạch, ta càng có nhiều cơ hội tìm được trang ít có khả năng được dùng nhất trong tương lai.
So similar to how the OS can do that preemptive background writing for pages in mmap, the data system can do the same thing.
Tương tự như cách hệ điều hành có thể thực hiện việc ghi nền chủ động cho các trang trong mmap, hệ quản trị dữ liệu cũng có thể làm như vậy.
Again, this is just walking through the page table, finding any pages that are marked as dirty, and going ahead and writing them out in a background thread.
Một lần nữa, việc này chỉ là duyệt qua page table, tìm các trang được đánh dấu là dirty, rồi ghi chúng ra trong một luồng nền.
So then the idea, again, by the time someone wants to go free that frame, the dirty data has been written out, and we don't have to block and wait for ourselves.
Ý tưởng là, đến lúc có ai đó muốn giải phóng frame đó, dữ liệu dirty đã được ghi ra rồi, và ta không phải chặn lại để tự chờ đợi.
This is sometimes called page cleaning or buffer flushing. The basic idea is the same thing.
Việc này đôi khi được gọi là page cleaning hay buffer flushing. Ý tưởng cơ bản thì giống nhau.
And then once we've written out the dirty page, we can go flip the dirty bit, and then it can be evicted easily.
Và khi đã ghi trang dirty ra, ta có thể bật lại dirty bit, rồi nó có thể bị loại bỏ dễ dàng.
Of course, now the challenge is going to be, if we spend all our time doing background writing, that's going to slow our system down, because now all our IOs are flushing out dirty pages when we could be using it for running other queries.
Tất nhiên, thách thức bây giờ sẽ là, nếu ta dành toàn bộ thời gian cho việc ghi nền, thì điều đó sẽ làm chậm hệ thống của ta, vì lúc này toàn bộ IO của chúng ta bị dùng để ghi các trang dirty xuống đĩa trong khi lẽ ra có thể dùng chúng để chạy các truy vấn khác.
So again, The high-end enterprise systems have all sorts of thresholds and other backup mechanisms you can put in place to say how aggressive you want it to be on background writing, where other systems might just run it periodically on a schedule, or if so many pages have been modified.
Một lần nữa, các hệ thống doanh nghiệp cao cấp có đủ loại ngưỡng và các cơ chế dự phòng khác mà bạn có thể thiết lập để quy định việc ghi nền được thực hiện quyết liệt đến mức nào, còn những hệ thống khác có thể chỉ chạy định kỳ theo lịch, hoặc khi có một số lượng trang nhất định đã bị sửa đổi.
I think Postgres, it'll do background writing if 30 pages in memory have been modified, and then it kicks in. There's simple things you can do like that, but the commercial systems are more sophisticated.
Tôi nghĩ Postgres sẽ ghi nền nếu có 30 trang trong bộ nhớ bị sửa đổi, và khi đó nó bắt đầu chạy. Có những việc đơn giản như vậy mà bạn có thể làm, nhưng các hệ thống thương mại thì tinh vi hơn.
So let me try to get through Disk IO quickly, and then we can pick back up on the optimizations you can have in your buffer pool next class.
Vậy hãy để tôi nói nhanh về Disk IO, rồi sau đó chúng ta có thể tiếp tục với các tối ưu hóa cho buffer pool của bạn vào buổi học tới.
So when we have to write pages out of the database, we're repaging from disk.
Khi phải ghi các trang ra khỏi cơ sở dữ liệu, chúng ta đang phân trang từ đĩa.
We want to do it in such a way that we can maximize the throughput or the bandwidth of the hardware, so that, again, for a certain amount of fetches and a certain amount of time, we can get as much data as we can from disk into memory.
Chúng ta muốn làm theo cách có thể tối đa hóa thông lượng hay băng thông của phần cứng, để, một lần nữa, với một số lần nạp nhất định trong một khoảng thời gian nhất định, chúng ta lấy được càng nhiều dữ liệu từ đĩa vào bộ nhớ càng tốt.
Disks have gotten a lot faster in recent years, but it still is a pretty significant bottleneck.
Những năm gần đây đĩa đã nhanh hơn rất nhiều, nhưng nó vẫn là một nút thắt cổ chai khá lớn.
So the way the operating system and hardware is going to try to do this in modern systems, like NVMe drives, is they want to maximize the amount of parallelism, and they try to be clever about reordering IO requests to make sure things are done and maximize the amount of sequential ordering.
Vì vậy, cách hệ điều hành và phần cứng cố gắng làm điều này trong các hệ thống hiện đại, như ổ NVMe, là tối đa hóa mức độ song song, và chúng khéo léo sắp xếp lại thứ tự các yêu cầu IO để đảm bảo mọi việc xong xuôi và tối đa hóa thứ tự tuần tự.
But the challenge is that it doesn't know which of these requests have a higher priority than other requests, because it doesn't see that information.
Nhưng thách thức là nó không biết yêu cầu nào có độ ưu tiên cao hơn các yêu cầu khác, vì nó không thấy thông tin đó.
So you can set the IO priority for doing disk reads and disk writes, but you can only do it at the process level in Linux.
Bạn có thể đặt độ ưu tiên IO cho việc đọc và ghi đĩa, nhưng trong Linux chỉ làm được ở mức tiến trình.
So if our single database system has two threads that want to read data, one is for a mission-critical query, and one's for a background thing.
Vậy nếu một hệ cơ sở dữ liệu của chúng ta có hai luồng muốn đọc dữ liệu, một cho truy vấn sống còn, và một cho việc chạy nền.
Who cares if it's slow? Linux doesn't know anything about those two requests. So this is, again, why we want to do all the scheduling in our own system.
Chậm thì ai quan tâm? Linux không biết gì về hai yêu cầu đó. Đây lại là lý do chúng ta muốn tự thực hiện toàn bộ việc lập lịch trong hệ thống của mình.
And a lot of the systems will tell you, turn off any kind of sophisticated scheduling policies in Linux.
Và nhiều hệ thống sẽ bảo bạn hãy tắt mọi chính sách lập lịch phức tạp trong Linux.
Go do the most simplest thing, because we're going to do everything better ourselves inside of our database system.
Cứ dùng cách đơn giản nhất, vì chúng ta sẽ làm mọi thứ tốt hơn ngay bên trong hệ cơ sở dữ liệu của mình.
And basically the way this works is that the database maintains its own internal queue of the IO requests that are coming from up above, from the buffer pool manager.
Về cơ bản, cách nó hoạt động là cơ sở dữ liệu duy trì hàng đợi nội bộ riêng của các yêu cầu IO đến từ phía trên, từ buffer pool manager.
And then it can reorder things based on how those queries are accessing the data, based on what it knows is the important things to consider.
Rồi nó có thể sắp xếp lại dựa trên cách các truy vấn đó truy cập dữ liệu, dựa trên những gì nó biết là quan trọng cần cân nhắc.
Again, the most simple thing is sequential IO versus random IO.
Một lần nữa, điều đơn giản nhất là IO tuần tự so với IO ngẫu nhiên.
If I have a bunch of requests from random pages, from multiple workers or multiple threads, then I can just look at all the requests, sort them by the page ID or the location on disk, and that way I can turn all these random IOs into a sequential IO.
Nếu tôi có một loạt yêu cầu đến từ các trang ngẫu nhiên, từ nhiều worker hoặc nhiều luồng, thì tôi có thể xem xét tất cả các yêu cầu, sắp xếp chúng theo ID trang hoặc vị trí trên đĩa, và bằng cách đó tôi có thể biến tất cả các IO ngẫu nhiên này thành IO tuần tự.
If, again, if it's a part of a query or a transaction that's important, I want to prioritize those versus random background tasks.
Một lần nữa, nếu đó là một phần của truy vấn hoặc giao dịch quan trọng, tôi muốn ưu tiên chúng hơn so với các tác vụ nền ngẫu nhiên.
If I know I'm writing out log data, that's really important to write that out first and make sure things are normal before I write out maybe other random dirty pages.
Nếu tôi biết mình đang ghi dữ liệu log, thì việc ghi nó ra trước là rất quan trọng và phải đảm bảo mọi thứ bình thường trước khi ghi ra các dirty page ngẫu nhiên khác.
There's a whole bunch of things we can consider that the OS is not going to know about, because it doesn't know what's inside of our application or system that's actually running.
Có cả một loạt điều chúng ta có thể cân nhắc mà hệ điều hành sẽ không biết, bởi vì nó không biết bên trong ứng dụng hay hệ thống đang chạy của chúng ta có gì.
I keep saying application, because from the OS perspective, the data system is just another application. So I don't mean your Node.js application over there. From the OS perspective, the data system is another application.
Tôi cứ nói là ứng dụng, vì theo góc nhìn của hệ điều hành, hệ quản trị dữ liệu chỉ là một ứng dụng khác. Nên tôi không nói đến ứng dụng Node.js của các bạn ở đằng kia. Theo góc nhìn của hệ điều hành, hệ quản trị dữ liệu là một ứng dụng khác.
So that's what I mean by that. But I really mean our system we're actually building. The OS doesn't know any of this, and it's just going to make things harder for us.
Đó là ý tôi muốn nói. Nhưng thực sự tôi muốn nói đến hệ thống mà chúng ta đang xây dựng. Hệ điều hành không biết gì về những điều này, và nó sẽ chỉ khiến mọi thứ khó khăn hơn cho chúng ta.
And so we want to try to avoid that as much as possible. Another thing we've got to be mindful about is the OS page cache.
Vì vậy chúng ta muốn cố tránh điều đó càng nhiều càng tốt. Một điều nữa chúng ta phải lưu ý là page cache của hệ điều hành.
So when I call fread or read using the libc POSIX syscall, that's going to go into the kernel, into the file system that's running in the kernel.
Khi tôi gọi fread hoặc read bằng syscall POSIX của libc, lời gọi đó sẽ đi vào kernel, vào hệ thống tệp đang chạy trong kernel.
And then it's going to consult its internal page cache in the OS.
Sau đó nó sẽ tra cứu page cache nội bộ của hệ điều hành.
And if it's not in the page cache, then it goes down to disk, copies it into the page cache, and then copies that again to a user space buffer that goes up to our database system up above.
Và nếu trang không có trong page cache, thì nó xuống đĩa, sao chép trang vào page cache, rồi lại sao chép thêm lần nữa vào một bộ đệm ở user space để đưa lên hệ quản trị cơ sở dữ liệu của chúng ta ở trên.
But now, if I'm maintaining my own buffer pool manager, that's another copy of pages that are out on disk.
Nhưng bây giờ, nếu tôi tự duy trì buffer pool manager, thì đó là một bản sao khác của các trang nằm trên đĩa.
So that's actually two copies now that are in memory in our OS, or in our system.
Vậy là hiện có hai bản sao trong bộ nhớ của hệ điều hành, hay của hệ thống chúng ta.
So you have one copy of the page in the OS page cache, another copy up in user space in our database system. That's super wasteful. We don't want that.
Một bản sao của trang nằm trong page cache của hệ điều hành, một bản sao khác ở user space trong hệ quản trị cơ sở dữ liệu của chúng ta. Như vậy cực kỳ lãng phí. Chúng ta không muốn thế.
So instead, you can use what's called direct IO, where you basically tell the file system, "Don't put it in your page cache. Bypass all that. Go directly to the hardware. Get what you want.
Thay vào đó, bạn có thể dùng cái gọi là direct IO, tức là về cơ bản bạn bảo hệ thống tệp: "Đừng đưa nó vào page cache của anh. Bỏ qua tất cả. Đi thẳng đến phần cứng. Lấy thứ cần lấy.
And then hand me back the memory buffer for it." And that avoids that additional copy. Things are much, much faster. There's actually other optimizations you can do, called using DPDK, Data Plane Development Kit.
Rồi trả lại cho tôi bộ đệm bộ nhớ của nó." Cách đó tránh được lần sao chép thừa. Mọi thứ nhanh hơn rất nhiều. Thực ra còn những tối ưu hóa khác bạn có thể làm, đó là dùng DPDK, Data Plane Development Kit.
We'll cover this in the advanced class. You can basically have the database system talk directly to the hardware and not go through the file system at all and get data out.
Chúng ta sẽ học điều này trong lớp nâng cao. Về cơ bản bạn có thể để hệ quản trị cơ sở dữ liệu giao tiếp trực tiếp với phần cứng mà không đi qua hệ thống tệp chút nào để lấy dữ liệu ra.
So most database systems run with direct IO. There's one system that's widely used that doesn't use direct IO. Anyone know which one it is? SQLite?
Vì vậy hầu hết các hệ quản trị cơ sở dữ liệu chạy với direct IO. Có một hệ thống được dùng rộng rãi không dùng direct IO. Có ai biết đó là hệ nào không? SQLite?
No, I think you can run with direct IO with those guys. It might be on by default, too. Postgres, right?
Không, tôi nghĩ với hệ đó bạn có thể chạy với direct IO. Có thể nó còn được bật mặc định nữa. Postgres, đúng không?
Postgres, famously, because it's like some relic of the 1980s, relies on the OS page cache.
Postgres, nổi tiếng là vậy, vì nó giống như một di tích từ những năm 1980, dựa vào page cache của hệ điều hành.
Every other database system out there tells you, As I said before, if you have 100 gigs, use 80 of the memory for the buffer pool in your data system.
Mọi hệ cơ sở dữ liệu khác ngoài kia đều bảo bạn rằng, như tôi đã nói trước đó, nếu bạn có 100 gigabyte, thì hãy dùng 80 phần bộ nhớ cho buffer pool trong hệ cơ sở dữ liệu của bạn.
Postgres says use 25%, because they want the other remaining memory to be used for the OS. But then this has all sorts of problems, all sorts of performance issues.
Postgres thì bảo hãy dùng 25%, vì họ muốn phần bộ nhớ còn lại được dành cho hệ điều hành. Nhưng như vậy lại gây ra đủ loại vấn đề, đủ loại vấn đề về hiệu năng.
Because, again, you're maintaining multiple copies of data. And it's wasteful. So Postgres has been trying to get off OS page cache and switch to direct IO for many, many years.
Vì, một lần nữa, bạn đang giữ nhiều bản sao của dữ liệu. Và điều đó rất lãng phí. Vì vậy Postgres đã cố gắng bỏ page cache của hệ điều hành và chuyển sang direct IO suốt rất nhiều năm.
Because this is a LinkedIn post from last year, talking about how they have patches for this. And then coming out in two weeks is Postgres 18.
Vì đây là một bài đăng trên LinkedIn từ năm ngoái, nói về việc họ có các bản vá cho việc này. Và hai tuần nữa sẽ ra mắt Postgres 18.
This, I don't think, has direct IO on by default. But it's now going to have asynchronous IO.
Tôi không nghĩ bản này bật direct IO theo mặc định. Nhưng giờ nó sẽ có IO bất đồng bộ.
So now I can have separate background threads in Postgres, or processes in Postgres, go retrieve data from disk. It's still going to use the OS page cache.
Vậy giờ tôi có thể có các luồng nền riêng trong Postgres, hoặc các tiến trình trong Postgres, đi lấy dữ liệu từ đĩa. Nó vẫn sẽ dùng page cache của hệ điều hành.
But I don't have to block the rest of the system while I'm doing that. Because you need to have asynchronous IO before you can do direct IO.
Nhưng tôi không phải chặn phần còn lại của hệ thống trong lúc làm việc đó. Vì bạn cần có IO bất đồng bộ trước khi có thể dùng direct IO.
Because direct IO is going to be slower, because you're never going to really hit the OS page cache. Yes? Questions?
Vì direct IO sẽ chậm hơn, do bạn sẽ không bao giờ thực sự trúng page cache của hệ điều hành. Vâng? Có câu hỏi nào không?
Do you have to make changes in the kernel to do direct IO? No, no. Direct IO is a POSIX command. Like, when you call fopen, you just say, you pass an O_DIRECT.
Có phải sửa đổi kernel để dùng direct IO không? Không, không. Direct IO là một lệnh của POSIX. Ví dụ, khi gọi fopen, bạn chỉ cần truyền vào O_DIRECT.
By default, that's not that. Yeah, you don't have to make any changes to the kernel. Bottom line is, this is coming in Postgres. They're going to get off of OS page cache very soon.
Mặc định thì không phải vậy. Đúng, bạn không phải thay đổi gì trong kernel cả. Tóm lại, điều này sắp có trong Postgres. Họ sẽ sớm bỏ page cache của hệ điều hành.
And the OS is always going to cause problems for us. All right, I want to finish up with this last example here.
Và hệ điều hành lúc nào cũng sẽ gây rắc rối cho chúng ta. Được rồi, tôi muốn kết thúc bằng ví dụ cuối cùng này.
Again, I know I sound crazy up here, saying the OS is our enemy. We don't want to talk to it. Let me show why.
Một lần nữa, tôi biết mình nghe có vẻ điên khi đứng đây nói hệ điều hành là kẻ thù. Chúng ta không muốn làm việc với nó. Để tôi cho thấy tại sao.
All right, so say I have a dirty page in my buffer pool. And I got it right out of the disk. I call fwrite. What happens?
Được rồi, giả sử tôi có một trang bẩn trong buffer pool. Và tôi vừa lấy nó ra từ đĩa. Tôi gọi fwrite. Chuyện gì xảy ra?
What's that? I heard it. Say it again. Say it again. What are you saying? Say it again. Sorry. Oh, write, still file. Sorry, OK.
Gì cơ? Tôi nghe thấy rồi. Nói lại đi. Nói lại đi. Bạn nói gì? Nói lại đi. Xin lỗi. À, write, still file. Xin lỗi, được rồi.
I thought you said get arrested by 5. All right, sorry. Write, still file, but where? They say on the disk.
Tôi tưởng bạn nói là get arrested by 5. Được rồi, xin lỗi. Write, still file, nhưng ở đâu? Các bạn nói là trên đĩa.
Depends on when you flush. We're not flushing yet. So it sits in a kernel buffer. So his point, if I really want to get into the hardware, I've got to call fsync.
Còn tùy lúc bạn flush. Chúng ta chưa flush. Nên nó nằm trong một bộ đệm của kernel. Ý bạn ấy là, nếu tôi thực sự muốn ghi xuống phần cứng, tôi phải gọi fsync.
That's another POSIX command. It's a blocking call where you tell the OS, make sure this thing is actually written to the hardware. Now, the hardware can play games and lie to you, too.
Đó là một lệnh POSIX khác. Đây là một lời gọi chặn, trong đó bạn bảo hệ điều hành, hãy đảm bảo thứ này thực sự được ghi xuống phần cứng. Nhưng phần cứng cũng có thể giở trò và nói dối bạn.
Because the hardware can have its own battery down there, where you do fsync. It writes to the battery-backed RAM storage. And then it's not really on the actual storage medium yet.
Vì phần cứng có thể có pin riêng ở dưới đó, nơi bạn gọi fsync. Nó ghi vào bộ nhớ RAM có pin dự phòng. Và lúc đó dữ liệu thực ra vẫn chưa nằm trên phương tiện lưu trữ thật.
But in a rare case, you lose power. Then the battery can then do the final write. But when I call fsync, I block until I get a notification saying my flush has succeeded.
Nhưng trong trường hợp hiếm hoi là bạn mất điện. Thì pin sẽ thực hiện lần ghi cuối cùng. Nhưng khi tôi gọi fsync, tôi bị chặn cho đến khi nhận được thông báo cho biết việc flush đã thành công.
But if fsync fails, what happens?
Nhưng nếu fsync thất bại thì chuyện gì xảy ra?
Well, Linux in the old days would mark the dirty pages as clean. Got a bunch of dirty pages that I modified with fwrite.
Ồ, Linux ngày xưa sẽ đánh dấu các trang dirty là clean. Giả sử có một loạt trang dirty mà tôi đã sửa bằng fwrite.
The OS keeps track of them. I call fsync. It wants to write out the dirty pages. And it wants to mark them as clean.
Hệ điều hành theo dõi chúng. Tôi gọi fsync. Nó muốn ghi các trang dirty ra. Và nó muốn đánh dấu chúng là clean.
And it marks them clean and then notifies you that fsync was completed. But if fsync fails for whatever reason, because the hardware fails or flipped out or something, it comes back.
Nó đánh dấu chúng là clean rồi thông báo cho bạn rằng fsync đã hoàn tất. Nhưng nếu fsync thất bại vì bất kỳ lý do gì, vì phần cứng bị lỗi hay hỏng hóc gì đó, thì nó trả về.
And you get a failure notification. You get a failure error number. But then the OS marks those pages, dirty pages, as now clean.
Và bạn nhận được thông báo lỗi. Bạn nhận được một mã lỗi. Nhưng sau đó hệ điều hành lại đánh dấu những trang dirty đó là clean.
So the problem was a bunch of data systems would do fsync in a while loop. While fsync fails, try again.
Vấn đề là nhiều hệ thống dữ liệu gọi fsync trong một vòng lặp while. Chừng nào fsync còn thất bại thì thử lại.
So the first time you call fsync, it would fail. It would loop back around. Then try it again.
Lần đầu bạn gọi fsync, nó thất bại. Nó quay lại vòng lặp. Rồi thử lại.
But since the OS, Linux, would mark the page table as clean, the last time you called fsync, even though it didn't work, when you call fsync the second time, it says, "Oh, yeah, you're good.
Nhưng vì hệ điều hành, tức Linux, đã đánh dấu bảng trang là clean ở lần gọi fsync trước, dù lần đó không thành công, nên khi bạn gọi fsync lần thứ hai, nó nói: "À, ổn rồi.
Done." And it looked like it would succeed. So why would it do this? Why would Linux do this? Again, they fixed this. But why did they used to do this?
Xong." Và trông như nó đã thành công. Vậy tại sao nó lại làm thế? Tại sao Linux lại làm vậy? Họ đã sửa lỗi này rồi. Nhưng tại sao trước đây họ làm thế?
Because Linux wasn't worried about the database system, even though it's the most important thing in the world. They were worried about some people with a thumb drive pulling out the thumb drive.
Vì Linux không quan tâm đến hệ quản trị cơ sở dữ liệu, dù nó là thứ quan trọng nhất trên đời. Họ lo về những người dùng USB rút USB ra.
And then now you have a bunch of pages in your page table from a thumb drive that's never going to come back.
Và khi đó bạn có một đống trang trong bảng trang thuộc về một chiếc USB sẽ không bao giờ quay lại nữa.
So they would mark it as clean so that they can clean it up later on. Right?
Nên họ đánh dấu là clean để sau này có thể dọn đi. Đúng không?
But it was lying to us in the database system that our page was actually written, even though it actually wasn't. So some guy on the Postgres mailing list posted this, like, 2018 or 2017.
Nhưng như vậy nó đã nói dối hệ quản trị cơ sở dữ liệu của chúng ta rằng trang của ta đã được ghi, trong khi thực tế thì chưa. Rồi có một anh trên mailing list của Postgres đăng bài này, khoảng năm 2018 hay 2017.
He's like, "Hey, look, I think Postgres lost some data for me. And I didn't have a kernel panic. I didn't have a disk crash." It was a silent error.
Anh ấy nói: "Này, tôi nghĩ Postgres đã làm mất dữ liệu của tôi. Mà tôi không bị kernel panic. Tôi cũng không bị hỏng đĩa." Đó là một lỗi âm thầm.
Some guy went and started reading through the code in both Postgres and Linux. And it turns out, Linux was lying to us for 20 years. And it wasn't just Postgres.
Có một người bắt đầu đọc mã nguồn của cả Postgres lẫn Linux. Và hóa ra Linux đã nói dối chúng ta suốt 20 năm. Và không chỉ riêng Postgres.
MySQL had this problem. I think MongoDB or WiredTiger had the same problem. So I'm going to put this up for multiple times this semester. Don't do this. Right?
MySQL cũng gặp vấn đề này. Tôi nghĩ MongoDB hay WiredTiger cũng bị tương tự. Tôi sẽ nhắc lại điều này nhiều lần trong học kỳ này. Đừng làm thế. Được chứ?
Don't call fsync again and assume everything's going to be OK, because the OS is going to lie to you. So this was a big scandal. It was called fsyncgate.
Đừng gọi lại fsync rồi cho rằng mọi thứ sẽ ổn, vì hệ điều hành sẽ nói dối bạn. Đây là một vụ bê bối lớn. Nó được gọi là fsyncgate.
This has since been fixed in Linux and also fixed in Postgres and MySQL and MongoDB. But this is a good example where the OS is going to make, read the documentation.
Lỗi này sau đó đã được sửa trong Linux và cũng được sửa trong Postgres, MySQL và MongoDB. Nhưng đây là ví dụ hay về việc hệ điều hành, bạn đọc tài liệu mà thấy, nó nói một đằng nhưng thực tế lại làm một nẻo.
It's going to say one thing. It's actually going to do something different. So therefore, we have to be super protective and make sure that anything that could fail will fail.
Vì vậy, chúng ta phải cực kỳ cẩn trọng và đảm bảo rằng bất cứ thứ gì có thể thất bại thì sẽ thất bại.
And we have to do a bunch of extra stuff in our data system to make sure that we don't lose data.
Và chúng ta phải làm thêm một loạt việc trong hệ thống dữ liệu của mình hệ thống của mình để đảm bảo rằng chúng ta không bị mất dữ liệu.
OK? All right. We're over time. Apologize. We'll pick up on this next class. And then post everything on Piazza. And we'll post project one later today.
Được chứ? Được rồi. Chúng ta đã quá giờ. Xin lỗi các bạn. Chúng ta sẽ tiếp tục phần này ở buổi học sau. Và nhớ đăng mọi thứ lên Piazza. Chúng tôi cũng sẽ đăng project một vào cuối ngày hôm nay.
Hit it. See you later. Bye.
Nào, đi thôi. Hẹn gặp lại. Tạm biệt.
Bye. Bye.
Tạm biệt. Tạm biệt.
Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye. Bye.
Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt. Tạm biệt.
Bye. Bye.
Tạm biệt. Tạm biệt.
Đă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.