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ả.
Let's get started. A lot to cover. Round of applause for DJ Cash. Thank you for keeping everything fresh. So we've got a lot to cover today.
Chúng ta bắt đầu thôi. Hôm nay có rất nhiều nội dung. Hãy vỗ tay chào DJ Cash. Cảm ơn bạn đã giữ cho mọi thứ luôn mới mẻ. Hôm nay chúng ta có rất nhiều nội dung cần học.
Plus, we have the guest speaker, so I'm going to jump right into it and try to cover as much as we can today.
Thêm nữa, chúng ta còn có diễn giả khách mời, nên tôi sẽ vào thẳng vấn đề và cố gắng đi qua càng nhiều càng tốt trong hôm nay.
So last class was the last lecture we did. Or the previous lecture, we sort of wrapped up our discussion on what the storage layer of the database system looks like.
Buổi trước là bài giảng gần nhất của chúng ta. Hay nói đúng hơn, ở bài giảng trước, chúng ta đã kết thúc phần thảo luận về tầng lưu trữ của một hệ quản trị cơ sở dữ liệu trông như thế nào.
Right, down on disk. We already talked about buffer pools and how to bring those into memory. So now we're going to start going up the stack.
Đúng rồi, ở dưới đĩa. Chúng ta đã nói về buffer pool và cách đưa dữ liệu vào bộ nhớ. Giờ chúng ta sẽ bắt đầu đi lên các tầng phía trên.
Remember this diagram from the beginning of the semester, where we're now going to start talking about how we're going to build the support infrastructure in a database system to start executing queries.
Hãy nhớ sơ đồ này từ đầu học kỳ, giờ chúng ta sẽ bắt đầu nói về cách xây dựng hạ tầng hỗ trợ trong hệ quản trị cơ sở dữ liệu để bắt đầu thực thi truy vấn.
So we're going to be sort of this middle layer here, what I'll sort of call access methods.
Chúng ta sẽ ở tầng giữa này, mà tôi tạm gọi là các access method.
Basically, the API we're going to expose to the operator execution, the execution engine up above, to get access to the data that we want.
Về cơ bản, đó là API mà chúng ta cung cấp cho phần thực thi toán tử, tức execution engine ở phía trên, để truy cập dữ liệu mà nó cần.
So today, and for the next week as well, we're actually talking about data structures.
Vì vậy hôm nay, và cả tuần tới nữa, chúng ta sẽ nói về cấu trúc dữ liệu.
We're going to build on top of our buffer pool manager pages now that we can use to store data for a variety of reasons.
Giờ chúng ta sẽ xây dựng trên nền các trang của buffer pool manager, những trang mà ta có thể dùng để lưu dữ liệu cho nhiều mục đích khác nhau.
So today's class will be about hash tables, so unordered data structures. And then all next week will be about trees, or ordered data structures.
Bài hôm nay sẽ nói về bảng băm, tức các cấu trúc dữ liệu không có thứ tự. Còn cả tuần sau sẽ nói về cây, tức các cấu trúc dữ liệu có thứ tự.
So again, we're going to talk about the background about why we want to do this, why we need our own data structures, why you don't want to use STL vector for the stuff that we want to do.
Một lần nữa, chúng ta sẽ nói về bối cảnh: vì sao ta muốn làm việc này, vì sao ta cần cấu trúc dữ liệu của riêng mình, vì sao bạn không nên dùng STL vector cho những việc chúng ta muốn làm.
And then we'll quickly talk about what hash functions look like. Then we'll talk about two approaches to do hash tables.
Sau đó chúng ta sẽ nói nhanh về hàm băm trông như thế nào. Rồi chúng ta sẽ nói về hai cách tiếp cận để xây dựng bảng băm.
The first will be static hashing schemes, where you assume the size of the hash table is fixed.
Cách đầu tiên là các lược đồ băm tĩnh, trong đó ta giả định kích thước bảng băm là cố định.
And then there'll be dynamic hashing schemes, which will be a data structure that can grow and shrink depending on the number of keys that you're going to put in it.
Sau đó sẽ là các lược đồ băm động, là cấu trúc dữ liệu có thể mở rộng và thu nhỏ tùy theo số lượng khóa mà bạn đưa vào.
And in a database system, you're typically going to need both of these, right? Because as we'll see in a second, we're going to use these data structures for a bunch of things.
Và trong một hệ quản trị cơ sở dữ liệu, thường bạn sẽ cần cả hai loại này, đúng không? Bởi vì như ta sẽ thấy ngay sau đây, chúng ta dùng các cấu trúc dữ liệu này cho rất nhiều việc.
And then we'll finish off with a guest lecture from the Yugabyte co-founder.
Và chúng ta sẽ kết thúc bằng bài giảng của khách mời, người đồng sáng lập Yugabyte.
OK, so these data structures we're going to build here are going to be used, again, all throughout the database system for a variety of things. Obviously, we could use them for table indexes.
Được rồi, những cấu trúc dữ liệu mà chúng ta sẽ xây dựng ở đây sẽ được dùng trong suốt hệ quản trị cơ sở dữ liệu cho nhiều mục đích khác nhau. Hiển nhiên, ta có thể dùng chúng cho chỉ mục của bảng.
That's probably what you're most familiar with at this point.
Đó có lẽ là thứ bạn quen thuộc nhất vào lúc này.
Like, how do I take a primary key or a secondary key, do a lookup to then find the record ID that's going to be on some table page?
Ví dụ, làm sao lấy một khóa chính hoặc khóa phụ, rồi tra cứu để tìm record ID nằm trên một trang nào đó của bảng?
But we're also going to use them for internal things, like the metadata, like the catalog of the database. We talked about the page directory.
Nhưng chúng ta cũng sẽ dùng chúng cho các việc nội bộ, như siêu dữ liệu, chẳng hạn danh mục (catalog) của cơ sở dữ liệu. Chúng ta đã nói về page directory.
It's this hash table structure we use to look up to find the location of pages within files. We can also use this for the core data storage itself.
Đó là cấu trúc bảng băm mà ta dùng để tra cứu và tìm vị trí của các trang bên trong các tệp. Chúng ta cũng có thể dùng nó cho chính việc lưu trữ dữ liệu cốt lõi.
We saw this before when we talked about index organized storage, where we said that instead of having these unordered heap pages for our tuples, we're actually going to store the tuples in the leaf nodes of a tree data structure, typically a B+tree.
Chúng ta đã thấy điều này trước đây khi nói về index organized storage, trong đó thay vì có các heap page không có thứ tự để chứa các tuple, chúng ta thực sự sẽ lưu các tuple trong các nút lá của một cấu trúc dữ liệu dạng cây, thường là B+tree.
And then another one that we're going to see as well, but we'll see mostly when we talk about query execution: we can use these data structures for temporary data storage.
Và còn một cách dùng nữa mà chúng ta cũng sẽ thấy, nhưng chủ yếu sẽ gặp khi nói về thực thi truy vấn: chúng ta có thể dùng các cấu trúc dữ liệu này để lưu trữ dữ liệu tạm thời.
So when we do a hash join, when we join two tables, if we're doing a hash join, we're going to build a hash table, one of the hash tables we'll talk about today, populate it, do the join, and then immediately throw it away.
Vì vậy khi thực hiện hash join, tức là khi nối hai bảng, nếu dùng hash join, chúng ta sẽ xây dựng một bảng băm, một trong những bảng băm mà hôm nay chúng ta sẽ bàn, điền dữ liệu vào nó, thực hiện phép nối, rồi vứt nó đi ngay lập tức.
But because we may end up building a hash table that's larger than the amount of memory that's available to us, because we're trying to join some large tables, then we're going to back that hash table by the BufferPoolManager so it can spill the disk if we run out of space.
Nhưng vì có thể ta sẽ xây dựng một bảng băm lớn hơn dung lượng bộ nhớ mà chúng ta có, do đang cố nối một số bảng lớn, nên chúng ta sẽ dùng BufferPoolManager làm nền cho bảng băm đó để nó có thể tràn ra đĩa nếu hết dung lượng.
So again, the data structure we'll cover in the next two weeks will be all throughout our system.
Vậy một lần nữa, các cấu trúc dữ liệu mà ta sẽ học trong hai tuần tới sẽ xuất hiện khắp nơi trong hệ thống của chúng ta.
And we're not going to want to use, in many cases, the things you can get off the shelf, like a third-party library or the SDL or pick your favorite Rust crate, because those are going to be typically not backed by the BufferPoolManager.
Và trong nhiều trường hợp, chúng ta sẽ không muốn dùng những thứ có sẵn, như thư viện bên thứ ba, SDL, hay crate Rust yêu thích nào đó của bạn, vì những thứ đó thường không được BufferPoolManager làm nền.
They're going to be backed by malloc. We can override malloc, but it's still going to be OS memory that's ephemeral. System crashes, you lose whatever's in there.
Chúng được làm nền bởi malloc. Chúng ta có thể ghi đè malloc, nhưng đó vẫn là bộ nhớ của hệ điều hành và mang tính tạm thời. Hệ thống sập thì mọi thứ trong đó đều mất.
And if you're not in memory, it's going to start thrashing on its own. The OS is going to do that for you, and we don't want that to happen.
Và nếu dữ liệu không nằm trong bộ nhớ, nó sẽ tự bắt đầu thrashing. Hệ điều hành sẽ làm việc đó cho bạn, và chúng ta không muốn điều đó xảy ra.
We want to control everything.
Chúng ta muốn kiểm soát mọi thứ.
So there'll be two main decisions that we have in how we're going to design these data structures, because it's going to be slightly different than maybe seen in your previous algorithms class, because we're going to make trade-offs again about how we're going to choose the internals of the data structure based on the properties we said we cared about earlier in the semester, where we want to maximize the amount of sequential I.O.
Vì vậy sẽ có hai quyết định chính trong cách chúng ta thiết kế các cấu trúc dữ liệu này, vì nó sẽ hơi khác so với những gì các bạn có thể đã thấy trong môn thuật toán trước đây, bởi chúng ta lại sẽ đánh đổi trong việc chọn cách tổ chức bên trong của cấu trúc dữ liệu dựa trên những thuộc tính mà ta đã nói là quan tâm hồi đầu học kỳ, tức là muốn tối đa hóa lượng I/O tuần tự
rather than a random I.O.
thay vì I/O ngẫu nhiên.
So that means there'll be some things that may seem more inefficient to do versus if something was entirely in memory, but we're going to do that because we can convert random writes and random reads to sequential writes and sequential reads, and that's going to be faster for us.
Điều đó nghĩa là sẽ có vài thứ có vẻ kém hiệu quả hơn so với khi mọi thứ nằm hoàn toàn trong bộ nhớ, nhưng chúng ta làm vậy vì có thể chuyển các lần ghi ngẫu nhiên và đọc ngẫu nhiên thành ghi tuần tự và đọc tuần tự, và như thế sẽ nhanh hơn cho chúng ta.
So today's class is we're going to mostly focus on the data organization side, like basically how we're going to represent the data structure internally, like the actual physical thing we're to store in memory on disk pages.
Vậy bài hôm nay chúng ta chủ yếu tập trung vào phần tổ chức dữ liệu, tức là cơ bản cách biểu diễn cấu trúc dữ liệu ở bên trong, như thứ vật lý thực sự mà ta lưu trong bộ nhớ trên các trang đĩa.
There's another challenging thing we have to worry about, but we'll cover this in two weeks, of how do we make sure that our data structures are thread safe?
Còn một vấn đề khó khác mà chúng ta phải lo, nhưng chúng ta sẽ bàn nó sau hai tuần nữa, là làm sao để đảm bảo cấu trúc dữ liệu của chúng ta an toàn luồng (thread safe)?
How do we allow for concurrent access, multiple threads reading and writing to our data structure at the same time, and doing this in such a way that it's safe to do these operations and not worry about you changing some pointer address, and then now, all of a sudden, some other thread reads that, and goes off in the middle of nowhere, and you segfault?
Làm sao để cho phép truy cập đồng thời, tức là nhiều luồng cùng đọc và ghi vào cấu trúc dữ liệu cùng một lúc, và làm điều này theo cách mà các thao tác đó an toàn và không phải lo chuyện bạn vừa đổi một địa chỉ con trỏ, rồi đột nhiên một luồng khác đọc giá trị đó, và nhảy đến một nơi vô định nào đó, và bạn bị segfault?
So for today's discussion and then Monday's next class, we're going to assume that our data structures are single-threaded, and there's only one thread going to access from the time, so we're understanding the basics, and then we'll see how to add latches and protect things later on.
Vì vậy, trong buổi hôm nay và buổi học tiếp theo vào thứ Hai, chúng ta sẽ giả định rằng các cấu trúc dữ liệu là đơn luồng, và tại mỗi thời điểm chỉ có một luồng truy cập, để chúng ta nắm được những kiến thức cơ bản, rồi sau đó chúng ta sẽ xem cách thêm latch và bảo vệ dữ liệu.
But there'll be other weird things that come up, too.
Nhưng cũng sẽ có những điều kỳ lạ khác xuất hiện.
Why we don't want to talk about concurrency stuff at this point, because there's a higher level notion of correctness that we're not going to worry about just yet.
Lý do chúng ta chưa muốn nói về đồng thời ở thời điểm này là vì có một khái niệm đúng đắn ở mức cao hơn mà chúng ta chưa cần bận tâm lúc này.
But say if my one thread deletes something, sorry, I insert a key, somebody else, some other thread deletes that key, now I go back and try to read that same key, and I don't see it.
Nhưng giả sử một luồng của tôi xóa thứ gì đó, xin lỗi, tôi chèn một khóa, rồi một luồng khác xóa khóa đó, sau đó tôi quay lại đọc chính khóa đó và không thấy nó.
Is that correct? At the lowest level, the physical level, yes. At a logical level, maybe not. If that doesn't make sense, don't worry. We'll cover that later. That's not this class.
Như vậy có đúng không? Ở mức thấp nhất, mức vật lý, thì đúng. Ở mức logic, có thể không. Nếu chưa hiểu thì đừng lo. Chúng ta sẽ học sau. Đó không phải nội dung của buổi này.
All right, so like I said, the data structure we're going to focus on today is hash tables.
Được rồi, như tôi đã nói, cấu trúc dữ liệu chúng ta tập trung hôm nay là bảng băm (hash table).
And again, everyone should have taken basic CS classes that I've described this before, so nothing I'm saying here should be wildly new to anyone.
Và một lần nữa, ai cũng đã học các môn khoa học máy tính cơ bản có mô tả điều này rồi, nên không có gì tôi nói ở đây là quá mới với các bạn.
But it's basically an unordered associative array that allows us to map arbitrary keys to arbitrary values.
Về cơ bản nó là một mảng kết hợp không có thứ tự cho phép ánh xạ các khóa tùy ý tới các giá trị tùy ý.
And at its core, the way this is going to work is there's going to be some kind of hash function, which I'll talk about in a second, that we're going to use to take our key, which could be of any arbitrary length, run through a hash function.
Và về cốt lõi, cách hoạt động là sẽ có một hàm băm nào đó, lát nữa tôi sẽ nói, mà chúng ta dùng để lấy khóa của mình, có thể có độ dài bất kỳ, rồi cho qua hàm băm.
It then can compute some integer representation of that data.
Sau đó nó tính ra một biểu diễn số nguyên của dữ liệu đó.
And then we're going to use that to figure out where we want to jump to in our hash table to find the data that we're looking for.
Rồi chúng ta dùng nó để xác định cần nhảy tới đâu trong bảng băm để tìm dữ liệu mình cần.
So the space complexity of a hash table is going to be O(N), where N is defined as the number of keys that I expect to store in my data structure.
Vậy độ phức tạp không gian của bảng băm là O(N), trong đó N được định nghĩa là số lượng khóa mà tôi dự kiến lưu trong cấu trúc dữ liệu.
Now, in many cases, I may actually not store exactly N. I actually want to be less than that.
Trong nhiều trường hợp, thực tế tôi có thể không lưu đúng N. Tôi thực sự muốn nó ít hơn thế.
Sometimes you just double the size you expect to store, and that's what you want to allocate it as. So N can be like the 2N of reality.
Đôi khi bạn chỉ cần nhân đôi kích thước dự kiến cần lưu, và đó là kích thước bạn muốn cấp phát. Vậy N có thể là 2N trong thực tế.
For the time complexity, on average, it's going to be O(1), because we're going to assume that we have a way to take our key that we want to find, hash it, and then we jump some offset in our data structure.
Về độ phức tạp thời gian, trung bình là O(1), vì chúng ta giả định rằng có cách lấy khóa mà mình muốn tìm, băm nó, rồi nhảy tới một độ dời nào đó trong cấu trúc dữ liệu.
And lo and behold, there's the data that we're looking for. So average case is O(1).
Và thật bất ngờ, dữ liệu chúng ta cần tìm nằm ngay đó. Vậy trường hợp trung bình là O(1).
Worst case is O(N), meaning I have to scan all the keys individually, one by one, to find the thing that I'm looking for.
Trường hợp xấu nhất là O(N), nghĩa là tôi phải quét từng khóa một, lần lượt từng khóa, để tìm thứ mình cần.
So now, if you've taken algorithms class, all the theoreticians see that O(1), and they start salivating. Like, oh, man, that's great. Oh, I don't care about anything else.
Bây giờ, nếu các bạn đã học môn thuật toán, thì các nhà lý thuyết thấy O(1) là họ bắt đầu thèm thuồng. Kiểu như, ôi, tuyệt quá. Tôi không cần quan tâm đến thứ gì khác nữa.
And I think we sort of mentioned this early in the semester. In the database world, we do care about these constants.
Và tôi nghĩ chúng ta đã nhắc đến điều này từ đầu học kỳ. Trong thế giới cơ sở dữ liệu, chúng ta có quan tâm đến các hằng số này.
And even though it is O(1), there's going to be a big difference in performance based on how you actually implement these things. So if it takes me, my hash function is something really stupid.
Và dù nó là O(1), vẫn sẽ có sự khác biệt lớn về hiệu năng tùy theo cách các bạn thực sự triển khai những thứ này. Giả sử hàm băm của tôi là thứ gì đó rất tệ.
And it takes me 100 milliseconds to compute the hash to find out where to jump to find the data that I want.
Và tôi mất 100 mili giây để tính giá trị băm nhằm biết phải nhảy đến đâu để tìm dữ liệu mình muốn.
Yeah, it's O(1), but I could have a faster hash function that do this in one millisecond. That's two orders of magnitude difference. For one lookup, maybe not a big deal.
Đúng, nó vẫn là O(1), nhưng tôi có thể có một hàm băm nhanh hơn, làm việc này trong một mili giây. Đó là chênh lệch hai bậc độ lớn. Với một lần tra cứu thì có thể không đáng kể.
But again, think always in larger scales. If I'm doing a billion lookups, then that extra 99 milliseconds is going to add up.
Nhưng một lần nữa, hãy luôn nghĩ ở quy mô lớn hơn. Nếu tôi thực hiện một tỉ lần tra cứu, thì 99 mili giây dư ra đó sẽ cộng dồn lại.
So in the database world, we care about constants, because at the end of the day, that's going to equal money.
Vì vậy trong thế giới cơ sở dữ liệu, chúng ta quan tâm đến các hằng số, bởi vì cuối cùng thì điều đó quy ra tiền.
Because if I can have a more efficient data structure, where even though it's still O(1), theoretical, but the constant time it takes to do these operations is smaller and smaller, then I can store more data, or I can run my workload on a smaller machine.
Bởi vì nếu tôi có một cấu trúc dữ liệu hiệu quả hơn, mà dù về mặt lý thuyết vẫn là O(1), nhưng thời gian hằng số để thực hiện các thao tác này ngày càng nhỏ hơn, thì tôi có thể lưu trữ nhiều dữ liệu hơn, hoặc chạy khối lượng công việc trên một máy nhỏ hơn.
And at large scale, again, you save real money.
Và ở quy mô lớn, một lần nữa, các bạn tiết kiệm được tiền thật.
All right, so let's look at a sort of straw man proposal, the simplest hash table you can imagine, of what I'll call a static hash table.
Được rồi, hãy xem một đề xuất đơn giản mang tính minh họa, bảng băm đơn giản nhất mà các bạn có thể tưởng tượng, mà tôi sẽ gọi là bảng băm tĩnh.
All right, think of this, again, as a giant array of memory. And instead of calling them frames like we did in the buffer pool, we'll call them slots.
Được rồi, một lần nữa hãy coi nó như một mảng bộ nhớ khổng lồ. Và thay vì gọi chúng là frame như ở buffer pool, chúng ta sẽ gọi chúng là slot.
And they'll be locations in our array where we can store data.
Chúng là các vị trí trong mảng nơi chúng ta có thể lưu dữ liệu.
And so to make this work, we're going to assume that we know the number of keys ahead of time, so say big N.
Và để cách này hoạt động, chúng ta sẽ giả định rằng biết trước số lượng khóa, gọi là N lớn.
And to now find any key that we want, assuming we're going to be storing integers, we're just going to take whatever that key is, mod it by the N, the number of slots that we have.
Và bây giờ, để tìm bất kỳ khóa nào mình muốn, giả sử chúng ta lưu các số nguyên, chúng ta chỉ cần lấy khóa đó, rồi lấy phần dư khi chia cho N, số slot mà chúng ta có.
Actually, that could be, yeah, it's little N at the top, big N at the bottom. They're the same, just ignore the difference there.
Thực ra, ừ, ở trên là n nhỏ, ở dưới là N lớn. Chúng giống nhau, cứ bỏ qua sự khác biệt đó.
So I can take any key that I want, hash it, and then it'll tell me where that location is in my slot array.
Vậy tôi có thể lấy bất kỳ khóa nào, băm nó, và nó sẽ cho tôi biết vị trí đó nằm ở đâu trong mảng slot.
And then now I can maintain a, in the slot array itself, I'll have basically just pointers to some other location in memory or in other pages with the actual data that I want.
Và rồi trong chính mảng slot, về cơ bản tôi chỉ có các con trỏ trỏ đến một vị trí khác trong bộ nhớ hoặc trong các trang khác, nơi chứa dữ liệu thực sự mà tôi muốn.
And I have to store the original key and the value, because if I start jumping into the array and I land at some location in my data payload area, I've got to know whether I'm actually looking at the same key or not.
Và tôi phải lưu cả khóa gốc lẫn giá trị, bởi vì nếu tôi nhảy vào mảng và đáp xuống một vị trí nào đó trong vùng dữ liệu, tôi phải biết mình có thực sự đang nhìn đúng khóa đó hay không.
So this is unrealistic for a couple of reasons. One is, I assume that I know exactly the number of elements or the number of keys ahead of time.
Điều này không thực tế vì một vài lý do. Thứ nhất, tôi giả định rằng mình biết chính xác số phần tử hay số khóa ngay từ trước.
And in real world systems, that's almost never the case.
Mà trong các hệ thống thực tế thì hầu như không bao giờ như vậy.
The way to get around that, you could do one pass of the data, count the number of records, then do another pass, and then populate your hash table.
Cách để giải quyết là bạn có thể duyệt dữ liệu một lượt, đếm số bản ghi, rồi duyệt thêm một lượt nữa, và sau đó mới điền dữ liệu vào bảng băm.
Some systems do that, but in general, we can't assume that's the case. And we can also maybe assume in some cases that the number of keys isn't going to shrink or grow over time.
Một số hệ thống có làm vậy, nhưng nhìn chung ta không thể giả định như thế. Và trong một số trường hợp, ta cũng có thể giả định rằng số lượng khóa sẽ không co lại hay tăng lên theo thời gian.
The other big assumption here is that we're assuming that each key is unique.
Giả định lớn còn lại ở đây là ta cho rằng mỗi khóa là duy nhất.
And therefore, when I do my hash and I land in my slot array and it tells me where to go find the data that I want, I know that there isn't going to be something else in my slot array for another record that we need to find.
Do đó, khi tôi băm rồi rơi vào mảng slot của mình và nó cho tôi biết nơi cần đến để tìm dữ liệu tôi muốn, tôi biết rằng sẽ không có thứ nào khác trong mảng slot dành cho một bản ghi khác mà ta cần tìm.
Right?
Đúng không?
And to make that work, I've got to actually basically allocate all of the possible key space that I could ever have, so N, even though I may not actually have it all, or the estimate may be wrong, but that's going to avoid having any collisions.
Và để điều đó hoạt động, về cơ bản tôi phải cấp phát toàn bộ không gian khóa có thể có mà tôi từng cần, tức là N, dù thực tế có thể tôi không có hết, hoặc ước lượng có thể sai, nhưng nó sẽ tránh được mọi va chạm.
And the last one is a slightly theoretical discussion, but when we run these hash functions, oftentimes, we're not going to end up with...
Và điểm cuối cùng là một thảo luận hơi mang tính lý thuyết, đó là khi ta chạy các hàm băm này, thường thì ta sẽ không kết thúc với...
two distinct keys could end up hashing to the same value.
hai khóa khác nhau có thể được băm ra cùng một giá trị.
And so there is a class of algorithms or class of methods called perfect hashing, where you have a hash function that guarantees that there will never be any conflicts.
Và có một lớp thuật toán hay phương pháp gọi là perfect hashing, trong đó bạn có một hàm băm đảm bảo rằng sẽ không bao giờ có xung đột.
And think of it this way: if I have a number from 1 to 1,000, a hash function could just return that number, because I won't have any conflicts.
Hãy nghĩ thế này: nếu tôi có một số từ 1 đến 1.000, hàm băm có thể chỉ trả về chính số đó, vì tôi sẽ không có xung đột nào.
But if I'm trying to map a larger key space into a smaller one, then I can't assume that would be a perfect hash.
Nhưng nếu tôi đang ánh xạ một không gian khóa lớn hơn vào một không gian nhỏ hơn, thì tôi không thể giả định đó là một perfect hash.
So the way you do a perfect hash is you basically have to pass through the data once, make sure that there's no conflicts, and then maintain another hash table that maps the original key to its location in the slot.
Vậy cách để làm perfect hash là về cơ bản bạn phải duyệt qua dữ liệu một lần, đảm bảo không có xung đột nào, rồi duy trì thêm một bảng băm khác ánh xạ khóa gốc tới vị trí của nó trong slot.
So I'm building a hash table for my hash table, and that's not entirely practical. You can cheat in some cases.
Tức là tôi đang xây một bảng băm cho bảng băm của mình, và điều đó không hoàn toàn thực tế. Trong một số trường hợp bạn có thể "lách".
You can say, if I know the top 10 keys, then I'll have if-then-elses that bypass the hash function. But as far as I know, no system does that.
Bạn có thể nói, nếu tôi biết 10 khóa hàng đầu, thì tôi sẽ dùng các câu lệnh if-then-else để bỏ qua hàm băm. Nhưng theo tôi biết thì không có hệ thống nào làm vậy.
So at its core, what is a hash table? Most people think it's the actual data structure itself, but it's actually a combination of things.
Vậy về cốt lõi, bảng băm là gì? Hầu hết mọi người nghĩ đó là chính cấu trúc dữ liệu, nhưng thực ra nó là sự kết hợp của nhiều thứ.
The first is going to be what hash function we're going to use, again, to take the arbitrary key space and map it to a smaller domain.
Thứ đầu tiên là hàm băm mà ta sẽ dùng, một lần nữa, để lấy không gian khóa tùy ý và ánh xạ nó vào một miền nhỏ hơn.
And we'll see in a second, there'll be this trade-off between how fast you want our hash function to be versus how many collisions I could potentially have.
Và ta sẽ thấy ngay sau đây, sẽ có sự đánh đổi giữa việc bạn muốn hàm băm nhanh đến mức nào so với việc có bao nhiêu va chạm mà tôi có thể gặp.
And then the second piece will be the hashing scheme. So within my data structure now, if I have keys hashed to the same location in my hash table, what do I do?
Và phần thứ hai sẽ là lược đồ băm (hashing scheme). Vậy trong cấu trúc dữ liệu của tôi lúc này, nếu có các khóa được băm vào cùng một vị trí trong bảng băm, thì tôi làm gì?
What's the protocol to decide how to resolve that conflict?
Giao thức nào quyết định cách giải quyết xung đột đó?
And we'll see two examples of how to do this, but there's a bunch of ones people have developed over the years.
Và chúng ta sẽ xem hai ví dụ về cách làm việc này, nhưng có rất nhiều cách mà người ta đã phát triển qua nhiều năm.
So once you have the hash function, the hashing scheme, and you have the storage space you want to put the things, then you have your hash table.
Vậy khi bạn đã có hàm băm, lược đồ băm, và có không gian lưu trữ để đặt dữ liệu vào, thì bạn đã có một bảng băm.
So let's quickly talk about hash functions. I'll just give you the basics of what you need to know when you build a data system.
Giờ hãy nói nhanh về các hàm băm. Tôi sẽ chỉ nói những điều cơ bản bạn cần biết khi xây dựng một hệ thống dữ liệu.
But the truth be told, we actually don't care what the algorithm is going to be. And I don't think it's worth our time to even discuss how to build a good hash function.
Nhưng thực ra, chúng ta không quan tâm thuật toán đó là gì. Và tôi nghĩ cũng không đáng để mất thời gian thảo luận về cách xây dựng một hàm băm tốt.
There's other classes that do that. So for us, we're actually just using something that's off the shelf. And those systems are, most of the newer systems are going to do this.
Có những lớp học khác dạy việc đó. Với chúng ta, chỉ cần dùng thứ có sẵn là được. Và các hệ thống, hầu hết các hệ thống mới hơn, đều làm như vậy.
Very few newer systems build their own hash functions. So again, a hash function is pretty basic. The idea is that it's a one-way hash.
Rất ít hệ thống mới tự xây dựng hàm băm của riêng mình. Vậy hàm băm khá là cơ bản. Ý tưởng là đây là một phép băm một chiều.
So given some key of arbitrary length, we want to do some computation on it to then generate a random 32 or 64-bit integer.
Cho một khóa có độ dài bất kỳ, chúng ta thực hiện một phép tính trên nó để sinh ra một số nguyên 32 hoặc 64 bit ngẫu nhiên.
And again, the thing that we care about is we want something to be fast as possible and have a low collision rate. What's the fastest hash function you could build? Identity? Faster.
Và điều chúng ta quan tâm là muốn nó nhanh nhất có thể và có tỉ lệ va chạm thấp. Hàm băm nhanh nhất bạn có thể xây dựng là gì? Hàm đồng nhất? Nhanh hơn nữa.
1 or 0. And return a constant, because that's going to sit in a register. So if I pass you a string, I got to send you back a string.
1 hoặc 0. Và trả về một hằng số, vì nó nằm sẵn trong một thanh ghi. Nếu tôi đưa bạn một chuỗi, tôi phải trả lại bạn một chuỗi.
Sending back 0 or 1 would be way faster than that. But the collision rate is terrible.
Trả về 0 hoặc 1 sẽ nhanh hơn thế rất nhiều. Nhưng tỉ lệ va chạm thì tệ hại.
No matter what key I give you, no matter what email address I give you, the value is going to return 0 or 1. So that's not a good one.
Dù tôi đưa khóa nào, dù tôi đưa địa chỉ email nào, giá trị trả về cũng sẽ là 0 hoặc 1. Vậy đó không phải là một hàm tốt.
The opposite end of the spectrum would be that perfect hash function, where I have a bunch of elaborate infrastructure to guarantee that no matter what key you give me, I'm going to give you a unique hash.
Ở đầu đối lập của phổ là hàm băm hoàn hảo, nơi tôi có cả một hạ tầng phức tạp để đảm bảo rằng dù bạn đưa khóa nào, tôi cũng trả về một giá trị băm duy nhất.
So again, the idea is that we're trying to convert these arbitrary length strings or whatever these keys we're putting in. We want to always then generate a fixed length value.
Vậy ý tưởng là chúng ta đang cố chuyển các chuỗi có độ dài bất kỳ hoặc bất cứ khóa nào mà chúng ta đưa vào. Chúng ta luôn muốn sinh ra một giá trị có độ dài cố định.
So we don't care about any cryptographic properties of this hash function. And we don't care about the hash being reversible.
Chúng ta không quan tâm đến các tính chất mật mã của hàm băm này. Và chúng ta cũng không cần phép băm có thể đảo ngược.
So I don't care about taking whatever you hash me, the hash you give me, and giving back the original value. This is all for the internals of the database system.
Tôi không cần lấy giá trị băm mà bạn đưa cho tôi rồi trả lại giá trị ban đầu. Tất cả chỉ dành cho nội bộ của hệ quản trị cơ sở dữ liệu.
We're not leaking any information on the outside.
Chúng ta không làm rò rỉ thông tin nào ra bên ngoài.
We're not worried about people trying to do an attack on us to overload something or give me keys that always hash at the same location, so I slow things down.
Chúng ta không lo người ta tấn công để làm quá tải hoặc đưa cho tôi những khóa luôn băm vào cùng một vị trí, khiến hệ thống chậm đi.
That's not our problem. We're not worried about those things. This is all on the inside. We're not going to expose these hash values to the outside world. Yes?
Đó không phải vấn đề của chúng ta. Chúng ta không lo những chuyện đó. Tất cả những thứ này đều nằm bên trong hệ thống. Chúng ta sẽ không để lộ các giá trị băm này ra thế giới bên ngoài. Bạn hỏi đi?
AUDIENCE MEMBER 2: Yes, I mean, you can actually remove the page and the stuff, right? Yes. AUDIENCE MEMBER 2: So if you have the page and the stuff, it's OK?
KHÁN GIẢ 2: Vâng, ý em là thực ra thầy có thể bỏ trang và những thứ đó đi, đúng không ạ? Vâng. KHÁN GIẢ 2: Vậy nếu đã có trang và những thứ đó thì vẫn ổn ạ?
A statement is, earlier before, we talked about if we had the record ID, and from that, we can get the page number and the offset. Why do we?
Có một phát biểu thế này: trước đó chúng ta đã nói về việc nếu có record ID, thì từ đó ta có thể lấy được số trang và offset. Tại sao chúng ta lại làm vậy?
AUDIENCE MEMBER 2: The record ID, the page number, is that what changes everything? Is that from 10 to the page number and offset?
KHÁN GIẢ 2: Record ID, số trang, có phải thứ đó làm thay đổi mọi thứ không ạ? Có phải từ 10 thành số trang và offset không ạ?
The record ID, in some systems, are typically going to be the page number and the offset.
Record ID, trong một số hệ thống, thường sẽ là số trang và offset.
You don't need a hash table? AUDIENCE MEMBER 2: I'm asking. I'm asking if we already know the page number and offset, right? AUDIENCE MEMBER 2: You don't, so hold on.
Bạn không cần bảng băm sao? KHÁN GIẢ 2: Em đang hỏi thôi ạ. Em hỏi là nếu ta đã biết số trang và offset rồi thì sao ạ? KHÁN GIẢ 2: Thì không, nên đợi một chút ạ.
So going back here, we're going to use this hash table for a bunch of things. This, right? So table indexes, that's the simplest one to think about.
Quay lại đây, chúng ta sẽ dùng bảng băm này cho rất nhiều việc. Đúng không? Chỉ mục của bảng là trường hợp đơn giản nhất để hình dung.
If, think of something like a higher level key, like a secondary key, or like a primary key. And the primary key is your email address.
Hãy nghĩ đến một khóa ở mức cao hơn, như khóa phụ hoặc khóa chính. Và khóa chính là địa chỉ email của bạn.
So I do a query, select star from table where email address equals yours. How do I then get the record ID then? The table index will give me that. Yes.
Vậy tôi chạy truy vấn: select star from table where email address bằng email của bạn. Vậy làm sao tôi lấy được record ID? Chỉ mục của bảng sẽ cho tôi điều đó. Vâng.
But I also want to emphasize that the thing that we're talking about today, the status order, isn't just for that. We're going to use it to do joins.
Nhưng tôi cũng muốn nhấn mạnh rằng thứ chúng ta nói hôm nay, cấu trúc này, không chỉ dành cho việc đó. Chúng ta sẽ dùng nó để thực hiện phép nối.
We're going to use it to maintain other internal metadata. You're a buffer pool manager. In project one, you guys are using what? STL unordered_map or something, right? Well, again, you crashed. What happens?
Chúng ta sẽ dùng nó để duy trì các siêu dữ liệu nội bộ khác. Bạn là một trình quản lý buffer pool. Trong project một, các bạn đang dùng gì? STL unordered_map hay gì đó, đúng không? Vậy nếu hệ thống bị sập thì sao?
That map is gone.
Map đó mất hết.
But say you wanted to make sure that the, well, you could replace that STL map with one of these hash tables that we're talking about here today and not use the STL one.
Nhưng giả sử bạn muốn đảm bảo rằng, bạn có thể thay STL map đó bằng một trong những bảng băm mà hôm nay chúng ta nói đến, và không dùng bản STL nữa.
Because do you think you can do a better job than that? You usually can. Although the Google data structure library Abseil is actually pretty good. The Facebook one is pretty good too.
Vì bạn nghĩ mình có thể làm tốt hơn thế không? Thường là có. Dù thư viện cấu trúc dữ liệu Abseil của Google thực ra khá tốt. Thư viện của Facebook cũng khá tốt.
But again, that's not going to be backed by a buffer pool manager. So again, we don't care about cryptography. We don't care about denial of service attacks. This is all internal.
Nhưng một lần nữa, chúng không được hỗ trợ bởi trình quản lý buffer pool. Vậy nên, chúng ta không quan tâm đến mật mã học. Chúng ta không quan tâm đến tấn công từ chối dịch vụ. Tất cả đều là nội bộ.
We're not exposed to the outside world. So I just want to quickly talk about what options are available to you. And I'm going to tell them it's 20 years now.
Chúng ta không tiếp xúc với thế giới bên ngoài. Giờ tôi muốn nói nhanh về những lựa chọn có sẵn cho các bạn. Và tôi sẽ nói với các bạn là chuyện đó đã 20 năm rồi.
But there was this resurgence of interest in hash functions for database systems in 2008, started by MurmurHash.
Nhưng đã có một làn sóng quan tâm trở lại đến các hàm băm cho hệ quản trị cơ sở dữ liệu vào năm 2008, bắt đầu từ MurmurHash.
And it was some random guy on GitHub or something who just posted, here's my really good hash function. And a bunch of databases picked it up and started using it.
Và đó chỉ là một anh chàng ngẫu nhiên nào đó trên GitHub đã đăng lên: đây là hàm băm rất tốt của tôi. Và hàng loạt cơ sở dữ liệu đã lấy nó về và bắt đầu sử dụng.
And over the years, there's been improvements to it. The main takeaway is going to be the state-of-the-art one that's considered the fastest right now is RapidHash.
Và qua nhiều năm, nó đã được cải tiến. Điều cần nhớ chính là hàm tiên tiến nhất, được coi là nhanh nhất hiện nay, là RapidHash.
But as far as I know, no database system uses RapidHash yet, because it's too new. Most of the newer systems are going to use XXHash or XXHash3.
Nhưng theo tôi biết thì chưa hệ quản trị cơ sở dữ liệu nào dùng RapidHash, vì nó còn quá mới. Hầu hết các hệ thống mới hơn sẽ dùng XXHash hoặc XXHash3.
So in general, this is what you're going to want to use. And that's it. That's all you need about hash functions. String in, or byte array in, 64-bit integer out, XXHash would be fast.
Nên nhìn chung, đây là thứ các em sẽ muốn dùng. Và chỉ vậy thôi. Đó là tất cả những gì các em cần biết về hàm băm. Đầu vào là chuỗi, hoặc mảng byte, đầu ra là số nguyên 64 bit, XXHash sẽ nhanh.
Let's use that. OK? You could use RapidHash. You could use RapidHash. Sorry. Sorry. Their statement is, why can't you use RapidHash? You can. So maybe state-of-the-art is both of them.
Cứ dùng cái đó. OK? Các em cũng có thể dùng RapidHash. Dùng RapidHash cũng được. Xin lỗi. Xin lỗi. Ý bạn ấy là, sao không dùng RapidHash được? Dùng được. Vậy có lẽ cả hai đều là state-of-the-art.
But nobody uses this one yet, as far as I know. I haven't grepped all of GitHub to see where it shows up in any database system, because we have all the GitHub accounts.
Nhưng theo tôi biết thì chưa ai dùng cái này. Tôi chưa grep toàn bộ GitHub để xem nó xuất hiện ở hệ cơ sở dữ liệu nào, vì chúng tôi có tất cả các tài khoản GitHub.
We have all the GitHub URLs for every database system that's open source. So we could check. But I think we checked last year, and nobody was using it.
Chúng tôi có mọi URL GitHub của từng hệ cơ sở dữ liệu mã nguồn mở. Nên có thể kiểm tra. Nhưng tôi nghĩ năm ngoái đã kiểm tra rồi và không ai dùng nó.
So again, assume we have some hash function. RapidHash is going forward in the rest of this lecture. We don't care how it's actually being implemented.
Vậy nên, một lần nữa, hãy giả sử ta có một hàm băm nào đó. Trong phần còn lại của bài giảng này, ta sẽ dùng RapidHash. Ta không quan tâm nó được cài đặt thực tế ra sao.
We just know, if we give it some byte array, we'll get some integer out. OK? All right. So first, we're going to talk about static hashing schemes.
Ta chỉ biết rằng nếu đưa vào một mảng byte, ta sẽ nhận ra một số nguyên. OK? Được rồi. Trước tiên, ta sẽ nói về các lược đồ băm tĩnh.
Again, the idea here is that you specify, when you allocate the data structure, the number of potential locations where you could want to store records, store information, the number of slots that you want in your implementation.
Một lần nữa, ý tưởng ở đây là các em chỉ định, khi cấp phát cấu trúc dữ liệu, số vị trí có thể mà các em muốn lưu các bản ghi, lưu thông tin, tức là số ô (slot) mà các em muốn trong cài đặt của mình.
We'll see dynamic hashing in a second. And again, that'll be a hash table that can grow and shrink with more or less keys over time.
Lát nữa ta sẽ xem băm động. Và đó sẽ là một bảng băm có thể lớn lên và co lại theo số khóa nhiều hơn hay ít hơn theo thời gian.
With static hashing, you allocate things at the very beginning, and that's it. So we're going to talk about, basically, the two most common approaches, linear probe hashing and cuckoo hashing.
Với băm tĩnh, các em cấp phát mọi thứ ngay từ đầu, và thế là hết. Vậy ta sẽ nói về, về cơ bản, hai cách tiếp cận phổ biến nhất: băm dò tuyến tính và băm cuckoo.
Linear probe hashing is used everywhere. It's the most common one. It's actually the most simple one. And this would be a good example where simple is actually better.
Băm dò tuyến tính được dùng ở khắp nơi. Đây là loại phổ biến nhất. Thực ra nó cũng là loại đơn giản nhất. Và đây là một ví dụ tốt cho thấy đơn giản lại thực sự tốt hơn.
It's actually more performant than all these other fancy ones. So if you take the Advanced Database class, we'll cover all the various things people have developed over the years.
Nó thực sự hiệu năng cao hơn tất cả những loại cầu kỳ khác. Nếu các em học lớp Advanced Database, chúng tôi sẽ đề cập mọi thứ người ta đã phát triển qua các năm.
Robin Hood hashing, hopscotch hashing, twist tables. There's another category of hash tables we're going to talk about in this class called precise hash tables or memory-efficient hash tables.
Robin Hood hashing, hopscotch hashing, twist tables. Có một loại bảng băm khác mà ta sẽ nói tới trong lớp này, gọi là bảng băm chính xác hay bảng băm tiết kiệm bộ nhớ.
This is where, again, you know you're going to be doing a hash join, And I'm going to build my data structure, then immediately throw it away.
Đây là trường hợp mà, một lần nữa, các em biết mình sắp thực hiện hash join, và tôi sẽ xây dựng cấu trúc dữ liệu rồi vứt đi ngay.
So I want something that is compact and as small as possible, because I'm not worried about building a hash table, and then an hour later, someone will come along and try to insert something into it or delete things.
Nên tôi muốn thứ gì đó gọn và nhỏ nhất có thể, vì tôi không lo việc xây một bảng băm, rồi một giờ sau có ai đó đến và cố chèn thứ gì vào đó hoặc xóa đi.
So the one thing I understand is that the terminology starts to overlap and gets kind of confusing with these things.
Điều tôi hiểu là thuật ngữ bắt đầu chồng chéo và khá dễ gây nhầm lẫn với những thứ này.
So I'm going to be talking about linear probe hashing, and there'll be another hash table called linear hashing that I'll cover at the end of the class.
Tôi sẽ nói về băm dò tuyến tính (linear probe hashing), và sẽ có một bảng băm khác gọi là băm tuyến tính (linear hashing) mà tôi sẽ trình bày ở cuối lớp.
That's a dynamic hashing scheme. Linear probe hashing is a static hashing scheme. And these are also used in a category called open addressing, or open addressing algorithms, for hash tables.
Đó là một lược đồ băm động. Băm dò tuyến tính là lược đồ băm tĩnh. Và chúng cũng được dùng trong một nhóm gọi là địa chỉ mở (open addressing), hay các thuật toán open addressing, dành cho bảng băm.
And this just basically means that the location of a key in my hash table is open, meaning it could be anywhere.
Và điều này về cơ bản có nghĩa là vị trí của một khóa trong bảng băm là mở, tức là nó có thể nằm ở bất kỳ đâu.
There's no guarantee that if I insert the same key in my data structure at different times, it's always going to be in the exact same location.
Không có gì đảm bảo rằng nếu tôi chèn cùng một khóa vào cấu trúc dữ liệu vào những thời điểm khác nhau, thì nó luôn nằm đúng ở cùng một vị trí.
It's allowed to move. It's allowed to be in different locations.
Nó được phép di chuyển. Nó được phép nằm ở các vị trí khác nhau.
And so the hash function is basically going to give us a way to jump into the hash table, at least as a starting point.
Và vì vậy hàm băm về cơ bản sẽ cho chúng ta một cách để nhảy vào bảng băm, ít nhất là làm điểm bắt đầu.
And then we may have to look around, scan some data to find the key that we're actually looking for. There's no guarantee it's going to be exactly in that location.
Sau đó chúng ta có thể phải nhìn xung quanh, quét một ít dữ liệu để tìm khóa mà chúng ta thực sự đang cần. Không có gì đảm bảo nó sẽ nằm đúng ở vị trí đó.
It'll make more sense when I show examples. Again, linear probe hashing is the most basic one, but it's used in a lot of systems.
Khi tôi cho xem ví dụ thì sẽ dễ hiểu hơn. Một lần nữa, linear probe hashing là loại cơ bản nhất, nhưng nó được dùng trong rất nhiều hệ thống.
All right, so the way to think about the hash table is just, again, a giant table of fixed-length slots. And it can be backed by pages in our buffer pool manager.
Được rồi, vậy cách nghĩ về bảng băm chỉ là, một lần nữa, một bảng khổng lồ gồm các ô có độ dài cố định. Và nó có thể được lưu trên các trang trong buffer pool manager.
And so how it's going to work is that when we hash into our hash table, if there's another key in the location where our key wants to go into, Then we know that space is being occupied, and we have to scan down linearly, like looking at one slot after another, till we find a free slot.
Và cách nó hoạt động là khi chúng ta băm vào bảng băm, nếu đã có một khóa khác ở vị trí mà khóa của chúng ta muốn vào, thì chúng ta biết chỗ đó đã bị chiếm, và phải quét xuống một cách tuyến tính, nhìn hết ô này đến ô khác, cho đến khi tìm được một ô trống.
And once we find the free slot, then we can put our key in, and then we're done. All right, insertions and deletions and searches all sort of work the same way.
Và khi tìm được ô trống, chúng ta đặt khóa vào, và thế là xong. Được rồi, các thao tác chèn, xóa và tìm kiếm đều hoạt động theo cùng một cách.
We do have to keep track, when we start scanning through, where we started when we entered the hash table, because we'll loop back around.
Chúng ta phải ghi nhớ, khi bắt đầu quét, mình đã bắt đầu từ đâu khi vào bảng băm, vì chúng ta sẽ quay vòng lại.
If we come back to the original location, we don't want to get stuck in an infinite loop, because we know the hash table is full.
Nếu chúng ta quay về vị trí ban đầu, chúng ta không muốn bị kẹt trong một vòng lặp vô hạn, vì khi đó chúng ta biết bảng băm đã đầy.
And then depending on what our operation is, we may have to stop what we're doing and resize things.
Và tùy vào thao tác của chúng ta là gì, chúng ta có thể phải dừng việc đang làm và thay đổi kích thước.
So in most implementations, there'll be this notion of the load factor, which is basically the number of actively used slots over the number of total slots.
Trong hầu hết các cách triển khai, sẽ có khái niệm load factor, về cơ bản là số ô đang được sử dụng chia cho tổng số ô.
And when that gets above some threshold, then the systems say, well, I think I'm getting too big, and I'm going to run out of space. Let me halt any operations.
Và khi nó vượt quá một ngưỡng nào đó, thì hệ thống sẽ nói, ừm, tôi thấy mình đang quá lớn, và sắp hết chỗ. Hãy tạm dừng mọi thao tác.
Again, assume you take a global latch on the whole data structure.
Một lần nữa, giả sử bạn lấy một global latch trên toàn bộ cấu trúc dữ liệu.
Allocate a new hash table that's twice the size of the original one, take all the keys out, and put it into the new one. That sucks. That's really slow.
Cấp phát một bảng băm mới có kích thước gấp đôi bảng ban đầu, lấy hết các khóa ra, và đưa vào bảng mới. Thật tệ. Cái đó rất chậm.
This is, again, why you typically allocate the hash table to be a little bit larger than what you expect to actually put in it, so you don't have to do that.
Đây, một lần nữa, là lý do bạn thường cấp phát bảng băm lớn hơn một chút so với lượng bạn dự kiến thực sự đưa vào, để không phải làm việc đó.
But some systems allow you to play around with this load factor to say, I'll allow myself to be 99% full before I have to resize.
Nhưng một số hệ thống cho phép bạn tùy chỉnh load factor này để nói rằng, tôi cho phép bảng đầy tới 99% trước khi phải thay đổi kích thước.
All right, so let's look at a real simple example. So I'm showing this on PowerPoint. Again, it's a diagram.
Được rồi, hãy xem một ví dụ thật đơn giản. Tôi đang trình bày cái này trên PowerPoint. Một lần nữa, đây là một sơ đồ.
But assume that this data is being stored in buffer pool pages that are being backed by disk.
Nhưng giả sử dữ liệu này đang được lưu trong các trang của buffer pool và được lưu trữ phía sau bằng đĩa.
So I have my hash function, and then I have the N defined as the number of slots that I have.
Vậy tôi có hàm băm của mình, và N được định nghĩa là số lượng slot mà tôi có.
So if I want to insert key A, I'm going to hash it, modulo the number N, and it's going to land in that slot there.
Nếu tôi muốn chèn khóa A, tôi sẽ băm nó, rồi lấy modulo N, và nó sẽ rơi vào slot ở đó.
And again, in this case here, my hash table is empty. The slot is empty, so my key A can go right in there.
Và một lần nữa, trong trường hợp này bảng băm của tôi đang trống. Slot đang trống, nên khóa A của tôi có thể vào ngay đó.
And again, I have to store the key and the value together. The value actually may be a pointer to something else. We'll cover that in a second.
Và một lần nữa, tôi phải lưu khóa và giá trị cùng với nhau. Giá trị thực ra có thể là một con trỏ tới thứ khác. Chúng ta sẽ nói về điều đó ngay sau đây.
But I need the original key, because if now I start having collisions, and I start changing the location of where the key I'm actually inserting is, not the original one where I started it, then I need to know whether the slot I'm looking at contains the thing that I want.
Nhưng tôi cần khóa gốc, vì nếu bây giờ bắt đầu có va chạm, và tôi bắt đầu thay đổi vị trí đặt khóa mà tôi đang chèn, không phải vị trí ban đầu mà tôi bắt đầu, thì tôi cần biết slot mình đang xem có chứa thứ tôi muốn hay không.
I insert B, hash to the top. That's fine. Now I insert C. Now I have a collision. C wants to go where A is, but it can't, because A is sitting there.
Tôi chèn B, băm lên phía trên. Ổn. Giờ tôi chèn C. Bây giờ có va chạm. C muốn vào chỗ của A, nhưng không được, vì A đang nằm đó.
So we basically recognize that the slot is occupied, do a linear scan to the next free slot. We see that it's empty.
Vậy về cơ bản ta nhận ra slot đã bị chiếm, và quét tuyến tính tới slot trống kế tiếp. Ta thấy nó trống.
Or the next slot, we see that it's empty, and then we can go ahead and start our key there. Same thing for D. D wants to be where C is. It's occupied.
Hoặc slot tiếp theo, ta thấy nó trống, và khi đó ta có thể đặt khóa của mình vào đó. D cũng vậy. D muốn vào chỗ của C. Chỗ đó đã bị chiếm.
So it has to scan down, and I put D there. E wants to go where A is. Can't go where C is. Can't go where D is. We finally find a free slot there.
Nên nó phải quét xuống, và tôi đặt D ở đó. E muốn vào chỗ của A. Không vào chỗ C được. Không vào chỗ D được. Cuối cùng ta tìm được một slot trống ở đó.
And just to finish off, we'll put F. Wants to go where E is, and it goes to the bottom.
Và để kết thúc, ta sẽ đặt F. Nó muốn vào chỗ của E, và nó đi xuống dưới cùng.
Pretty easy, right?
Khá dễ, đúng không?
And because we're doing a bunch of sequential operations, if I have to read multiple pages from disk, I can read these pages in sequential order till I find a free slot that I want.
Và vì ta đang thực hiện hàng loạt thao tác tuần tự, nếu tôi phải đọc nhiều trang từ đĩa, tôi có thể đọc các trang này theo thứ tự tuần tự cho tới khi tìm được slot trống mà tôi muốn.
All right, so how do I make sure that my entries, or the data I'm storing, is going to be fixed length?
Được rồi, vậy làm sao để đảm bảo các mục của tôi, hay dữ liệu tôi lưu, có độ dài cố định?
So if the data I want to store is fixed length, then I can just inline it with the data structure itself. So I can also store the hash.
Nếu dữ liệu tôi muốn lưu có độ dài cố định, thì tôi có thể lưu nội tuyến ngay trong cấu trúc dữ liệu. Tôi cũng có thể lưu giá trị băm.
It makes things go faster, because I want to compare the hash. Whatever I have in there plus the hash of the thing I'm trying to put in there, I can store the hash there.
Điều này giúp mọi thứ nhanh hơn, vì tôi muốn so sánh giá trị băm. Bất cứ thứ gì có trong đó cộng với giá trị băm của thứ tôi đang định đặt vào, tôi có thể lưu giá trị băm ở đó.
But space versus compute trade-off. It takes more space, but makes the lookup go faster. But if my value fits in just fine, I can store this inline.
Nhưng đây là sự đánh đổi giữa không gian và tính toán. Nó tốn thêm không gian, nhưng tra cứu nhanh hơn. Nhưng nếu giá trị của tôi vừa khít, tôi có thể lưu nội tuyến.
Obviously, I don't want it too wide now, because now the size that I'm jumping from slot to slot gets really big, and it can become wasteful. Yes?
Dĩ nhiên, tôi không muốn nó quá rộng, vì khi đó khoảng cách tôi nhảy từ slot này sang slot khác trở nên rất lớn, và có thể gây lãng phí. Vâng?
Yeah, this question is, this is doing inserts. How do you find things? It's the same thing, right? So say I have F. I want to look for F. I hash it.
Vâng, câu hỏi là, đây là chèn. Làm sao tìm dữ liệu? Cũng như vậy thôi. Giả sử tôi có F. Tôi muốn tìm F. Tôi băm nó.
I land where E is. E's not what I want.
Tôi rơi vào chỗ của E. E không phải thứ tôi muốn.
I keep scanning till I find the value that I want, or a free slot, an empty slot, meaning that I know my key can't be in there, because if it existed, I would have seen it when I was scanning through.
Tôi tiếp tục quét cho tới khi tìm thấy giá trị mình muốn, hoặc một slot trống, một slot trống, nghĩa là tôi biết khóa của mình không thể nằm trong đó, vì nếu nó tồn tại thì tôi đã thấy nó khi quét qua rồi.
That's what we said in the beginning, O(N). Worst case scenario, I read everything. Keep track of where I started, so I don't keep going.
Đó là điều chúng ta đã nói lúc đầu, O(N). Trường hợp xấu nhất, tôi phải đọc toàn bộ. Hãy ghi nhớ vị trí tôi bắt đầu, để không đi tiếp mãi.
All right, so if our data is small and it's fixed length, we just store it in the hash table itself.
Được rồi, vậy nếu dữ liệu nhỏ và có độ dài cố định, chúng ta chỉ cần lưu nó ngay trong bảng băm.
If our data is variable length or too big, then we end up basically storing some kind of record ID or a pointer or something to a temp page and just have the data we want chucked in there.
Nếu dữ liệu có độ dài thay đổi hoặc quá lớn, thì về cơ bản chúng ta lưu một loại record ID nào đó hoặc một con trỏ hay thứ gì đó trỏ tới một trang tạm và cứ để dữ liệu mình cần ở trong đó.
If we're storing this as an index, like a table index, then the record ID would just be to the original tuple.
Nếu chúng ta lưu nó như một chỉ mục, chẳng hạn chỉ mục của bảng, thì record ID sẽ chỉ tới tuple gốc.
But if I'm building a hash table for a join, I don't want to maybe reference the original data, because I might have made it manipulated or just another join prior to that, so I need to sort of temp pages to put data that I want.
Nhưng nếu tôi xây dựng bảng băm cho một phép join, có thể tôi không muốn tham chiếu tới dữ liệu gốc, vì có thể nó đã bị biến đổi hoặc đã qua một phép join khác trước đó, nên tôi cần các trang tạm để đặt dữ liệu mình muốn.
But it's the same mechanism to have a pointer to say, okay, you want the value, I have to find a match, here's where to go find it. Yes?
Nhưng cơ chế vẫn như nhau: có một con trỏ để nói rằng, được rồi, bạn muốn giá trị thì tôi phải tìm một kết quả khớp, và đây là chỗ để đi tìm nó. Bạn hỏi?
This question is, if you have a JSON field in a tuple, wouldn't you?
Câu hỏi này là, nếu bạn có một trường JSON trong một tuple, thì chẳng phải bạn sẽ...
Yes? Yes?
Vâng? Vâng?
But like, if it's variable length, I don't want it in the, I don't want it, I can't put it in my slot array, because it breaks the whole mechanism of taking the hash of the key and then modifying the number of slots.
Nhưng nếu nó có độ dài thay đổi, tôi không muốn đặt nó vào, tôi không muốn, tôi không thể đặt nó vào mảng slot của mình, vì nó phá vỡ toàn bộ cơ chế lấy giá trị băm của khóa rồi điều chỉnh theo số lượng slot.
So it's variable length, I'm gonna jump to random locations, I can't do that. So I can't put it in there, I gotta put it somewhere else.
Nó có độ dài thay đổi, tôi sẽ nhảy tới các vị trí ngẫu nhiên, và tôi không thể làm vậy. Vì thế tôi không thể đặt nó vào đó, mà phải đặt ở chỗ khác.
So I'm just saying here is like, you just have this sort of temp thing, where the key that you're trying to do lookups on is now in this other temp space that could be variable length, could be slotted pages or whatever you want, doesn't matter.
Nên ý tôi ở đây là, bạn có một vùng tạm như thế này, nơi khóa mà bạn đang muốn tra cứu giờ nằm trong không gian tạm khác này, có thể có độ dài thay đổi, có thể là các slotted page hay gì tùy bạn, không quan trọng.
And then now in my hash table, I'm storing fixed length record IDs.
Còn trong bảng băm của tôi, giờ tôi lưu các record ID có độ dài cố định.
So, it's the same as, and it's correct, like when you want to store the keys in the hash table to make it fast as possible, yes, but if they're variable length, you can't do that, because now all your slots are, yes.
Vậy nó giống như, và bạn nói đúng, khi bạn muốn lưu các khóa trong bảng băm để nó nhanh nhất có thể, vâng, nhưng nếu chúng có độ dài thay đổi thì bạn không thể làm vậy, vì khi đó tất cả các slot của bạn, vâng.
So the trick you could do would be, say you're storing variable length strings, I could take the first like eight characters, store that in my hash table, right?
Vậy mẹo bạn có thể dùng là, giả sử bạn lưu các chuỗi có độ dài thay đổi, tôi có thể lấy khoảng tám ký tự đầu tiên, lưu chúng trong bảng băm, đúng không?
Still need the record ID to get the original one, but at least now I can just look for the prefix and see whether that matches. What's that? This is German strings, yes.
Vẫn cần record ID để lấy bản gốc, nhưng ít nhất giờ tôi chỉ cần tìm tiền tố và xem nó có khớp không. Gì vậy? Đây là German strings, vâng.
German strings basically says like, when we had that, the overflow page, we had the, You know, we didn't want to inline the variable length data, we had a pointer to it.
German strings về cơ bản nói rằng, khi chúng ta có trang tràn đó, chúng ta có, Bạn biết đấy, chúng ta không muốn nhúng trực tiếp dữ liệu có độ dài thay đổi, mà có một con trỏ tới nó.
But in order to see if I have a match on that variable length data, I got to follow that pointer. So I can again just store a prefix to do that early matching, right?
Nhưng để biết liệu mình có khớp với dữ liệu có độ dài thay đổi đó hay không, tôi phải lần theo con trỏ đó. Vậy là tôi lại có thể chỉ lưu một tiền tố để so khớp sớm, đúng không?
And it was invented by the Germans, I called it German strings, and apparently that's the term I'm using now. But yeah, German strings.
Và nó do người Đức phát minh, tôi gọi là German strings, và có vẻ đó là thuật ngữ tôi đang dùng bây giờ. Nhưng vâng, German strings.
All right, so not all the hash tables in our systems will care about deletes, but again, if they're table indexes, you do. So how are we going to handle that?
Được rồi, không phải bảng băm nào trong hệ thống của chúng ta cũng quan tâm đến thao tác xóa, nhưng nếu chúng là chỉ mục của bảng thì có đấy. Vậy chúng ta sẽ xử lý việc đó như thế nào?
So the idea again, so say I want to delete key C. So I do my hash, I mod it, I land where A is.
Ý tưởng là thế này, giả sử tôi muốn xóa khóa C. Tôi băm, lấy mod, và rơi vào chỗ của A.
A is not the key that I'm looking for, I jump down to C, here's C. I want to go ahead and delete it, and I can just remove it.
A không phải khóa tôi cần tìm, tôi nhảy xuống C, đây là C. Tôi muốn xóa nó, và tôi có thể chỉ cần gỡ nó đi.
The question, the statement is, when the load factor gets too large, without deleting, just to me in general, or this example here.
Câu hỏi, hay đúng hơn nhận định, là khi hệ số tải trở nên quá lớn, không tính việc xóa, hỏi chung thôi, hay là trong ví dụ này.
Yeah, the question is, when the load factor gets too large, do I have to resize the table?
Vâng, câu hỏi là, khi hệ số tải quá lớn thì tôi có phải thay đổi kích thước bảng không?
Yes, you allocate a whole second table, scan through, and hash everything, put it back in the new one, yes. Dynamic hashing won't do that, we'll see that in a second.
Có, bạn cấp phát cả một bảng thứ hai, quét qua, băm lại mọi thứ, rồi đưa vào bảng mới, đúng vậy. Dynamic hashing sẽ không làm như vậy, chút nữa chúng ta sẽ thấy.
All right, is this a good idea or a bad idea? What did I do here? I deleted key C, I just removed it from my slot.
Được rồi, đây là ý hay hay dở? Tôi đã làm gì ở đây? Tôi xóa khóa C, tôi chỉ gỡ nó khỏi ô của nó.
Yes, he's pathetic here.
Đúng, cậu ấy thật thảm hại ở chỗ này.
So the statement is, if now something wants to do a lookup on D, well, D's gonna hash where C was, because it was occupied when we tried to insert D, it had to go to the slot below it.
Vậy nhận định là, nếu bây giờ có thứ gì muốn tra cứu D, thì D sẽ băm đến chỗ C đã ở, vì khi chúng ta chèn D thì chỗ đó đã bị chiếm, nên nó phải xuống ô bên dưới.
So it's gonna hash here now, land to where C used to be, see that it's empty.
Giờ nó sẽ băm đến đây, rơi vào chỗ C từng ở, thấy là trống.
And again, the protocol for deciding whether a key exists or not is, I keep scanning until I find it, or I see an empty slot, Then I'm done.
Và giao thức để quyết định một khóa có tồn tại hay không là, tôi cứ quét tiếp cho đến khi tìm thấy nó, hoặc thấy một ô trống, thì dừng.
So it's gonna see an empty slot right away, and think that nothing's there, and we're screwed, right? So there's two approaches to handle this.
Nên nó sẽ thấy ngay một ô trống, và nghĩ rằng chẳng có gì ở đó, và chúng ta gặp rắc rối rồi, đúng không? Vậy có hai cách tiếp cận để xử lý việc này.
One is basically what we talked about before, resizing the table, you basically just move everything around.
Một cách về cơ bản là điều chúng ta đã nói trước đó, thay đổi kích thước bảng, tức là bạn di chuyển mọi thứ.
So you figure out what the key you deleted, scan everything afterwards until you find the first free slot, and rehash everything you see to figure out where it actually should go.
Nên bạn xác định khóa mà bạn đã xóa, quét mọi thứ phía sau cho đến khi gặp ô trống đầu tiên, và băm lại mọi thứ bạn thấy để xác định thực sự nó nên nằm ở đâu.
So you're kind of like dumping out a portion of the table and inserting it back in, right?
Tức là bạn như đang đổ một phần của bảng ra rồi chèn nó trở lại, đúng không?
You could be stupid and start moving things around, you could just move things, but that's not gonna work, because things may not, you have to rehash to decide whether it actually should go where we want to point things.
Bạn có thể làm dại là bắt đầu dịch chuyển mọi thứ, bạn có thể chỉ việc di chuyển, nhưng cách đó sẽ không chạy, vì có thể các phần tử không, bạn phải băm lại để quyết định liệu nó có thực sự nên nằm ở chỗ mà chúng ta muốn trỏ tới hay không.
So in this case here, looking up D would be fine, it would still work, E would work as well as F, right?
Vậy trong trường hợp này, tra cứu D sẽ ổn, vẫn chạy được, E cũng chạy được, F cũng vậy, đúng không?
But then the tricky one, of course, what do you do with B? Do you wrap B around or not, right? Doesn't matter, okay.
Nhưng trường hợp hóc búa, tất nhiên, là làm gì với B? Bạn có cuộn B vòng lại hay không, đúng không? Không quan trọng, được rồi.
So nobody does this, don't do this, this is just way too expensive, because again, you don't know how many things you're gonna have to rehash at the moment you do this, right?
Nên không ai làm vậy cả, đừng làm thế, cách này quá tốn kém, vì một lần nữa, bạn không biết sẽ phải băm lại bao nhiêu phần tử vào thời điểm bạn thực hiện việc này, đúng không?
So what you really wanna do is just use tombstones. And you basically maintain a little marker to denote that the key that used to be here has been deleted.
Vì vậy, điều bạn thực sự muốn làm là dùng tombstone. Về cơ bản, bạn duy trì một dấu hiệu nhỏ để cho biết khóa từng nằm ở đây đã bị xóa.
It's not physically removed, right? I mean, you could zero out the bits if you want, doesn't matter.
Nó không bị xóa vật lý, đúng không? Ý tôi là, bạn có thể đặt các bit về 0 nếu muốn, không quan trọng.
But when you do a scan, the thread's gonna see that the space used to contain something, but it's not there anymore, and it knows to treat that as if it was occupied and not a truly empty space, so keep scanning to find the things you want, right?
Nhưng khi bạn thực hiện một lần quét, luồng sẽ thấy rằng chỗ này từng chứa thứ gì đó, nhưng giờ không còn nữa, và nó biết phải coi đó như một ô đã bị chiếm chứ không phải ô thực sự trống, nên cứ tiếp tục quét để tìm thứ bạn muốn, đúng không?
So I delete C, hash to A, go down here, mark a little tombstone.
Vậy tôi xóa C, băm ra A, đi xuống đây, đánh dấu một tombstone nhỏ.
Now when I do a lookup on D, D lands where C used to be, sees that there's a tombstone, and says, "All right, well, something used to be here and it's not anymore.
Bây giờ khi tôi tra cứu D, D rơi vào chỗ C từng nằm, thấy có một tombstone, và nói: "Được rồi, từng có thứ gì đó ở đây và giờ không còn nữa.
Let me just go ahead and keep scanning till I find the thing that I want," and then I'm done.
Cứ tiếp tục quét cho đến khi tìm được thứ mình muốn", và thế là xong.
And occasionally, there'll be some background thread, if you wanted to go ahead and prune these up, and in which case, you would have to do rehashing if you wanted that.
Thỉnh thoảng sẽ có một luồng nền nào đó, nếu bạn muốn dọn dẹp các tombstone này, và khi đó, bạn sẽ phải băm lại nếu muốn làm vậy.
Or if now someone wants to insert something into the space that is occupied by a tombstone, you can just use it. And that's still considered valid and correct. What's that, if I do what?
Hoặc nếu bây giờ ai đó muốn chèn một thứ vào chỗ đang bị tombstone chiếm, bạn có thể dùng luôn chỗ đó. Và như vậy vẫn được coi là hợp lệ và đúng. Bạn hỏi gì, nếu tôi làm gì cơ?
The question is, what would happen if I queried to get C?
Câu hỏi là điều gì sẽ xảy ra nếu tôi truy vấn để lấy C?
Well, it would, in this case here, you would see what hashes to A, so you land at A, say this is, not delete, this is a get.
Trong trường hợp này, bạn sẽ thấy khóa nào băm ra A, nên bạn đến A, giả sử đây là một lệnh get, không phải xóa.
I would see A is not what I want, I'd keep scanning, I'd see the tombstone spot on C is, I know that's not what I want either, because it's considered deleted.
Tôi thấy A không phải thứ mình muốn, tôi tiếp tục quét, tôi thấy chỗ tombstone ở C, tôi biết đó cũng không phải thứ tôi muốn, vì nó được coi là đã bị xóa.
Then I have to keep scanning down D, E, F, wrap around to B, then I get to that first free slot up there, it's empty.
Rồi tôi phải quét tiếp xuống D, E, F, vòng lại B, sau đó tôi đến ô trống đầu tiên ở phía trên kia, nó đang trống.
At this point, I didn't see C, and I would have seen it if it was, as I did my scan, so I would say it's not found. Yes.
Đến lúc này, tôi không thấy C, và lẽ ra tôi đã thấy nếu nó có, trong lúc quét, nên tôi sẽ kết luận là không tìm thấy. Vâng.
The question is, if I do an update to D, or insert a new D?
Câu hỏi là nếu tôi cập nhật D, hoặc chèn một D mới thì sao?
So what would I do if I updated the value of D?
Vậy tôi sẽ làm gì nếu cập nhật giá trị của D?
For this, we wouldn't, for updates, you scan the key that you're looking for, if it doesn't exist, you don't update it.
Với trường hợp này, với các lệnh cập nhật, bạn quét khóa cần tìm, nếu nó không tồn tại thì không cập nhật.
If you do see it, then you just could overwrite it, and you wouldn't need to move where D is.
Nếu bạn thấy nó, thì chỉ cần ghi đè lên, và bạn không cần di chuyển vị trí của D.
We're not worried about it, updates we're not worried about here. It's insert, update, deletes, or sorry, insert, deletes, and selects, gets.
Chúng ta không lo về điều đó, ở đây chúng ta không lo về cập nhật. Chỉ là chèn, xóa và chọn, à nhầm, chèn, xóa và lấy dữ liệu (get).
All right. So now, let's say I want to insert a new key, G. G hashes to where C used to be. Again, the tombstone's there, it knows that logically the space is unoccupied.
Được rồi. Bây giờ, giả sử tôi muốn chèn một khóa mới, G. G băm ra chỗ C từng nằm. Một lần nữa, tombstone ở đó, nó biết rằng về mặt logic ô này đang trống.
So let's go ahead and put the thing we want in there. So you wouldn't typically store the tombstone in line, on every slot.
Vậy hãy đặt thứ chúng ta muốn vào đó. Thông thường bạn sẽ không lưu tombstone trực tiếp trong từng ô.
Typically, it'd be like in the page header, you would say, here's all the slots, and whether they're considered occupied or not, in a simple bitmap.
Thường thì nó sẽ nằm trong phần đầu trang (page header), bạn sẽ ghi rằng đây là tất cả các ô, và chúng có được coi là bị chiếm hay không, bằng một bitmap đơn giản.
And that ensures that all your data is aligned. Yes?
Và điều đó đảm bảo mọi dữ liệu của bạn được căn chỉnh. Vâng, bạn hỏi gì?
The question is, am I going to maintain a map about tombstones, or what?
Câu hỏi là: liệu em có phải duy trì một bản đồ về các tombstone hay không?
The question is, do I need to maintain a separate data structure that says for a given key, it's been deleted? This is the data structure, right?
Câu hỏi là: liệu em có cần duy trì một cấu trúc dữ liệu riêng để cho biết với một khóa nhất định, nó đã bị xóa hay chưa? Đây là cấu trúc dữ liệu đó, đúng không?
So the question is like, do I need to record that this tombstone corresponds to a previous value? But like the, I suppose you could do that, that would help prevent the problem.
Vậy câu hỏi là, liệu em có cần ghi lại rằng tombstone này tương ứng với một giá trị trước đó không? Thì, tôi nghĩ là em có thể làm vậy, và nó sẽ giúp ngăn chặn vấn đề này.
Like I said before, like if I look for C, I then have to wrap around. I could just see the tombstone, ah, C used to be here, and that's what I'm looking for.
Như tôi đã nói trước đó, nếu tôi tìm C, tôi sẽ phải quay vòng lại. Tôi có thể chỉ cần thấy tombstone, à, C từng ở đây, và đó là thứ tôi đang tìm.
I guess it's not here anymore, right?
Vậy chắc là nó không còn ở đây nữa, đúng không?
The problem with that one is though, you don't know whether someone else inserted C after, later on, and I would miss that if I saw the tombstone and immediately jumped out.
Nhưng vấn đề của cách đó là, em không biết liệu có ai khác đã chèn C vào sau đó, muộn hơn hay không, và tôi sẽ bỏ sót nó nếu thấy tombstone rồi thoát ra ngay.
I think you're saying like, are we relying on information that we store in the tombstone to help optimize certain things? That's what you're saying.
Tôi nghĩ ý em là, liệu chúng ta có dựa vào thông tin lưu trong tombstone để giúp tối ưu một số việc hay không? Đó là ý em, đúng không.
I suppose you could, nobody does that, because it's extra complexity, and this is so simple, it just makes it so fast.
Tôi nghĩ là có thể, nhưng không ai làm vậy, vì nó thêm phức tạp, trong khi cách này rất đơn giản, và làm nó chạy rất nhanh.
Like the extra checks you're talking about are just not, probably not worth it, right?
Những kiểm tra thêm mà em nói đến thì không, có lẽ không đáng, đúng không?
I might be wrong with that, but if you're, yeah, most people don't do that, because most people are also gonna not support deletes anyway, Because they're gonna use these for hash tables, right?
Tôi có thể sai, nhưng, vâng, hầu hết mọi người không làm vậy, vì hầu hết mọi người dù sao cũng sẽ không hỗ trợ xóa, bởi họ sẽ dùng chúng cho các bảng băm, đúng không?
I'm just inserting and then reading and then throwing it away.
Tôi chỉ chèn vào, rồi đọc, rồi vứt đi.
But if you want to support deletes, that's an additional optimization I'm thinking you could do, but I don't think anybody does it, because it's just more machinery.
Nhưng nếu em muốn hỗ trợ xóa, thì đó là một tối ưu hóa bổ sung mà tôi nghĩ em có thể làm, nhưng tôi không nghĩ có ai làm, vì nó chỉ thêm cơ chế phức tạp.
All right, let me jump through, because we're short on time, because we haven't got to the dynamic stuff, but, if you want to handle non-unique keys, you basically have to, you can store them either in separate linked lists, or you just store the key multiple times.
Được rồi, để tôi lướt qua nhanh, vì chúng ta sắp hết thời gian, và chưa đến phần động, nhưng nếu em muốn xử lý các khóa không duy nhất, về cơ bản em có thể lưu chúng trong các danh sách liên kết riêng, hoặc em chỉ cần lưu khóa đó nhiều lần.
That's what most systems do with the second one.
Hầu hết các hệ thống dùng cách thứ hai.
The tricky thing, of course, is gonna be that, depending on the operation I'm doing, I may see, you know, say, go give me key XYZ, I may hash into it, land it, see key XYZ.
Điều khó, dĩ nhiên, là tùy thao tác tôi đang làm, tôi có thể thấy, ví dụ, hãy đưa tôi khóa XYZ, tôi băm vào, đáp xuống, và thấy khóa XYZ.
I have to keep going until I see the first free slot, and I look up, because at that point, then I know that I'm not gonna see any more XYZs.
Tôi phải tiếp tục cho đến khi gặp ô trống đầu tiên, và tôi dừng tìm, vì lúc đó tôi biết mình sẽ không còn thấy XYZ nào nữa.
And the same for deletes. If I want to remove all the XYZs, I have to do that.
Xóa cũng vậy. Nếu muốn xóa tất cả các XYZ, tôi phải làm như thế.
And most systems do that, because you don't need to maintain the separate data structure up above to store my keys in a giant hash table. All right. Let me skip optimizations.
Và hầu hết các hệ thống làm vậy, vì em không cần duy trì một cấu trúc dữ liệu riêng ở phía trên để lưu các khóa của tôi trong một bảng băm khổng lồ. Được rồi. Tôi sẽ bỏ qua phần tối ưu hóa.
Just to say, like, you could have specialized hash tables based on the keys. So in ClickHouse, for example, they have hash tables for strings, have separate hash tables for integers.
Chỉ nói rằng, em có thể có các bảng băm chuyên biệt dựa trên khóa. Ví dụ trong ClickHouse, họ có các bảng băm cho chuỗi, có các bảng băm riêng cho số nguyên.
They have separate hash tables for large strings, right? You have 20 different hash tables in their implementation, which is crazy.
Họ có các bảng băm riêng cho chuỗi lớn, đúng không? Trong cách triển khai của họ có tới 20 bảng băm khác nhau, thật điên rồ.
So they have an amazing blog article that talks about a lot of these things. All right, I'm gonna talk about an alternative to linear probing hashing called cuckoo hashing.
Họ có một bài blog tuyệt vời nói về rất nhiều điều này. Được rồi, tôi sẽ nói về một phương án thay thế cho linear probing hashing gọi là cuckoo hashing.
And this idea should be pretty simple, but it's, again, breaking this conceived notion that, like, we're gonna have one hash function to tell me one location where I can find my, Find the key that I'm looking for.
Ý tưởng này khá đơn giản, nhưng một lần nữa, nó phá vỡ quan niệm quen thuộc rằng ta chỉ có một hàm băm cho tôi biết một vị trí duy nhất để tìm khóa mà mình đang tìm.
I'm actually gonna have multiple hash functions, and my key could be in multiple locations.
Thực ra tôi sẽ có nhiều hàm băm, và khóa của tôi có thể nằm ở nhiều vị trí.
And it may change over time, because, again, the open addressing allows me to do that, to, over time, as the keys that I'm inserting change.
Và nó có thể thay đổi theo thời gian, vì một lần nữa, open addressing cho phép tôi làm vậy, theo thời gian, khi các khóa mà tôi chèn vào thay đổi.
So the lookups and deletions are always gonna be O(1), guaranteed, guaranteed, because I'm going to, if I hash it, I'm either gonna find exactly the key I'm looking for, may have to hash it multiple times, still constant factor, but, again, that's not free, or I'm not gonna see it at all.
Vì vậy tra cứu và xóa luôn là O(1), được đảm bảo, đảm bảo, bởi vì nếu tôi băm nó, tôi sẽ hoặc tìm thấy đúng khóa mình đang tìm, có thể phải băm nhiều lần, vẫn là hệ số hằng, nhưng một lần nữa, điều đó không miễn phí, hoặc tôi sẽ không thấy nó ở đâu cả.
The inserts are gonna be more expensive, because I may have to take a slot for somebody else, remove the key, and then insert it back in.
Việc chèn sẽ tốn kém hơn, vì tôi có thể phải chiếm một slot của khóa khác, lấy khóa đó ra, rồi chèn nó lại vào.
Let's look at an example and see what I mean. So I wanna put A. I have a single hash table, like I did before, and a bunch of slots.
Hãy xem một ví dụ để hiểu ý tôi. Tôi muốn đặt A vào. Tôi có một bảng băm duy nhất như trước, với một loạt slot.
In this case here, I'm gonna have two hash functions.
Trong trường hợp này, tôi sẽ có hai hàm băm.
It's gonna be the same implementation, like same rapid hash, or XXHash3, just you give it a different seed, so that they guarantee to produce, or not guarantee, they're going to produce different hash values.
Cùng một cách cài đặt, ví dụ cùng rapid hash hoặc XXHash3, chỉ là bạn đưa cho nó một seed khác nhau, để chúng đảm bảo sẽ tạo ra hoặc không đảm bảo, nhưng chúng sẽ tạo ra các giá trị băm khác nhau.
So I'm gonna hash both of them, the key twice, remove the hash function, and I'm gonna end up with two different slots, and I'm gonna look to see which one's empty.
Vậy tôi sẽ băm khóa hai lần, lấy phần dư theo kích thước bảng, và tôi sẽ có hai slot khác nhau, rồi xem slot nào còn trống.
In this case here, I'm completely empty. I'm gonna flip a coin and choose the first one, and that's where my key is gonna go.
Trong trường hợp này, cả hai đều trống hoàn toàn. Tôi sẽ tung đồng xu và chọn slot đầu tiên, và khóa của tôi sẽ vào đó.
Now I'm gonna do the same thing, I'm gonna hash B, two different locations. The first one, the first hash function, is occupied by A, so I'm gonna ignore that.
Giờ tôi làm tương tự, băm B, ra hai vị trí khác nhau. Vị trí đầu, từ hàm băm thứ nhất, đã bị A chiếm, nên tôi bỏ qua.
Instead, I'm gonna choose the free slot that the second hash function has, or points to, and I'll get B. Now let's see an example where I have collisions at both locations.
Thay vào đó, tôi chọn slot trống mà hàm băm thứ hai trỏ tới, và đặt B vào đó. Giờ hãy xem một ví dụ mà cả hai vị trí đều bị va chạm.
So, hashing C: the first hash function is where A is, second hash function goes where B is, both are occupied. So the way this is gonna work is, I'm gonna choose a victim.
Băm C: hàm băm thứ nhất trỏ tới chỗ của A, hàm băm thứ hai trỏ tới chỗ của B, cả hai đều đã bị chiếm. Cách nó hoạt động là tôi sẽ chọn một nạn nhân.
I'm gonna choose one of the slots that I'm hashing to, I'm gonna steal their location, kick them out of the house, put my shit in there, and then they gotta go find a new place to live.
Tôi chọn một trong các slot mà mình băm tới, tôi sẽ chiếm vị trí của họ, đuổi họ ra khỏi nhà, đặt đồ của tôi vào đó, và rồi họ phải đi tìm chỗ ở mới.
It's called cuckoo hashing, because there's a cuckoo bird. That's what they do: they go find other birds' nests, kick them out, and then plant their own eggs.
Nó gọi là cuckoo hashing vì có loài chim cu. Chúng làm vậy đấy: tìm tổ của những con chim khác, đuổi chúng đi, rồi đặt trứng của mình vào.
What's that? The question is, where did the victim entry go? Let's keep going.
Gì cơ? Câu hỏi là mục nạn nhân đi đâu? Hãy tiếp tục.
All right, so, we're gonna take the first one, so C's gonna kick out B, put his stuff in there, and then now we gotta put B back in.
Được rồi, ta lấy slot đầu tiên, nên C sẽ đuổi B ra, đặt đồ của mình vào, và giờ ta phải đặt B lại vào.
So with B, I'm showing, for simplicity, I'm showing only hashing. The first hash function is back here, we decided to choose the second hash function.
Với B, để đơn giản, tôi chỉ minh họa phần băm. Hàm băm đầu tiên nằm ở đằng này, và ta đã quyết định chọn hàm băm thứ hai.
In actuality, you're not gonna record what hash function you used to insert it, because there's extra space that's unneeded.
Thực tế, bạn sẽ không ghi lại hàm băm nào đã dùng để chèn nó, vì như thế tốn thêm không gian không cần thiết.
You would end up hashing it again, and then see which one is occupied, or which one points you to the place you just got kicked out of.
Bạn sẽ băm lại lần nữa, rồi xem ô nào đang bị chiếm, hoặc ô nào trỏ bạn về chỗ vừa bị đá ra.
So, now we hash B again, the first hash function, it goes where A is, so same thing, it's gonna take its slot, kick A out, now we get A back in.
Giờ ta băm B lại, với hàm băm đầu tiên, nó rơi vào chỗ của A, nên cũng như vậy, nó chiếm ô đó, đá A ra, và giờ ta phải đưa A vào lại.
We're gonna hash A, and it's gonna land here, and that was the free slot, one of the free slots we had in the very beginning. How did what? Gotta prevent cycles?
Ta băm A, và nó sẽ rơi vào đây, và đó là ô trống, một trong những ô trống ta có ngay từ đầu. Làm sao ư? Phải ngăn chu trình à?
You just keep track of like, hey, this is the key I just inserted, I'm trying to, that I started off with. Statement is, the list was quite long, yes.
Bạn chỉ cần theo dõi khóa mà bạn vừa chèn, khóa mà bạn bắt đầu chèn ngay từ đầu. Ý bạn là danh sách đó khá dài, đúng vậy.
In fact, no, no, it's not a list, you don't need the list, I don't care about how I got there, I just care what he has started with.
Thực ra không, đó không phải là danh sách, bạn không cần danh sách, tôi không quan tâm mình đến đó bằng cách nào, chỉ quan tâm nó bắt đầu từ đâu.
Uh, to his point, yeah, I see, right, so, I don't know exactly. I don't think you need, you don't need the full list though.
À, theo ý bạn đó, vâng, tôi hiểu, nhưng tôi cũng không biết chính xác. Tôi nghĩ bạn không cần toàn bộ danh sách.
I think you just need where you started, and the most recent one.
Tôi nghĩ bạn chỉ cần điểm bắt đầu và điểm gần nhất.
Yeah, no, you can have, I don't know the answer, but it's gonna be, if you have to maintain the list, it's unavoidable. Yes.
Vâng, không, bạn có thể làm vậy, tôi không biết câu trả lời, nhưng nếu phải duy trì danh sách thì không tránh được. Vâng.
Statement is, if you collect all hash functions, the hash table's full, double the size, and rebuild it. Yep, no free lunch. You always have to do something. So now, we're gonna do a lookup.
Ý bạn là, nếu dùng hết các hàm băm mà bảng băm đầy, thì tăng gấp đôi kích thước và xây dựng lại. Đúng, không có bữa trưa miễn phí. Lúc nào bạn cũng phải làm gì đó. Giờ ta sẽ thực hiện một lần tra cứu.
I'm gonna get B, I'm gonna hash it twice.
Tôi lấy B, và băm nó hai lần.
Again, I'm showing this being parallel because it's PowerPoint, and actually how do you just hash the first one, see whether it has the thing you want, if it's there, you're done, then hash, if not, then hash the second one to see it, right?
Một lần nữa, tôi minh họa song song vì đây là PowerPoint, còn thực tế bạn chỉ băm cái đầu tiên, xem nó có thứ bạn cần không, nếu có thì xong, nếu không thì băm cái thứ hai để xem, đúng không?
But in this case here, I would hash the first one, look for B, and I would find it in my slot there, but I could also look at the other one.
Nhưng ở trường hợp này, tôi sẽ băm cái đầu tiên, tìm B, và tôi sẽ thấy nó ở ô đó, nhưng tôi cũng có thể xem ô còn lại.
And that's why it's O(1). Because I'm guaranteed to either see it immediately, my first sort of step into the data structure, or it doesn't exist.
Và đó là lý do nó là O(1). Vì chắc chắn tôi hoặc thấy nó ngay lập tức, ở bước đầu tiên vào cấu trúc dữ liệu, hoặc nó không tồn tại.
Yes. Go back here.
Vâng. Quay lại đây.
So we were here, C collided, so, yeah, sorry. We want to start at C, C collided with A and B, we gotta pick a victim.
Ta đang ở đây, C va chạm, nên, vâng, xin lỗi. Ta muốn bắt đầu từ C, C va chạm với A và B, ta phải chọn một nạn nhân.
We pick B, yes. C goes in there, B pops out, we gotta put it back in.
Ta chọn B, đúng. C vào đó, B bị đẩy ra, ta phải đưa nó vào lại.
If either of them are the same? Yeah.
Nếu cả hai giống nhau ư? Vâng.
Well, so, the second hash function is where I came from, yes. So, you would do both of them when you come back out, try to go back in.
À, hàm băm thứ hai là chỗ tôi vừa bị đá ra, đúng. Vậy bạn sẽ thử cả hai khi bị đẩy ra và cố vào lại.
Is this, the protocols are the same if you're inserting a key for the first step versus like, I got evicted, I gotta go back in. It's the same.
Giao thức có giống nhau không, khi bạn chèn một khóa ở bước đầu so với khi bị đuổi ra và phải vào lại? Nó giống nhau.
And for PowerPoint reasons, I'm just not showing, yeah, but you would do both. Yes.
Và vì lý do PowerPoint nên tôi không minh họa, nhưng bạn sẽ làm cả hai. Vâng.
Question is, how do you know how many hash functions to use? Yeah, so, there's, I think there's been theoretical work done on this.
Câu hỏi là, làm sao biết nên dùng bao nhiêu hàm băm? Vâng, tôi nghĩ đã có những công trình lý thuyết về vấn đề này.
You can prove that, like, for a hash table of this size, this many expected keys, you want this number of hash functions.
Có thể chứng minh rằng, với một bảng băm có kích thước này và số khóa kỳ vọng này, thì bạn cần số lượng hàm băm này.
And then there's a trade-off also, too, of, like, if I have a lot of hash functions, then I may, it's more work, but I can maybe not hit a cycle as quickly, right?
Ngoài ra còn có một sự đánh đổi nữa, đó là nếu tôi có nhiều hàm băm, thì sẽ tốn nhiều công việc hơn, nhưng có thể sẽ không gặp chu trình nhanh như vậy, đúng không?
I forget the default one. So, the most, the best open source implementation of a cuckoo hash table was actually from CMU, from Dave Andersen.
Tôi quên mất giá trị mặc định là bao nhiêu. Vậy, bản cài đặt mã nguồn mở tốt nhất của bảng băm cuckoo thực ra đến từ CMU, của Dave Andersen.
They still maintain it. And I think the default is, like, six hash functions.
Họ vẫn đang duy trì nó. Và tôi nghĩ mặc định là khoảng sáu hàm băm.
Other questions? So, this is a neat little trick. It's a cool idea.
Còn câu hỏi nào khác không? Đây là một mẹo nhỏ khá hay. Đó là một ý tưởng thú vị.
It's slower than a linear probe hash table, because linear probing is so simple that you can rip through it quickly. So, very few systems do this.
Nó chậm hơn bảng băm linear probe, vì linear probing đơn giản đến mức bạn có thể duyệt qua rất nhanh. Cho nên rất ít hệ thống làm như vậy.
All right, so, in the two schemes that I showed, you got to know the number of keys ahead of time.
Được rồi, trong hai cơ chế tôi vừa trình bày, bạn phải biết trước số lượng khóa.
And then if we, our load factor gets too much, or it gets stuck in an infinite loop in the cuckoo hashing, or we run out of free slots in our linear probe hash table, we got to stop what we're doing, reallocate space, and resize it, right?
Và nếu hệ số tải (load factor) quá cao, hoặc cuckoo hashing bị kẹt trong vòng lặp vô hạn, hoặc bảng băm linear probe hết ô trống, thì ta phải dừng việc đang làm, cấp phát lại không gian và thay đổi kích thước, đúng không?
So, dynamic hash tables are going to have a mechanism built in that allows them to grow and shrink incrementally as needed as you're inserting things.
Vì vậy, các bảng băm động sẽ có một cơ chế tích hợp sẵn cho phép chúng tăng và giảm kích thước dần dần khi cần trong lúc bạn chèn dữ liệu.
So, the hash table you're probably most familiar with is chained hash table. I think this is what Python gives you, or Java HashMap gives you, right?
Bảng băm mà bạn có lẽ quen thuộc nhất là bảng băm chuỗi (chained hash table). Tôi nghĩ đây là thứ Python cung cấp, hoặc Java HashMap cung cấp, đúng không?
But in the database world, there's two more sophisticated ones, extendible hashing and linear hashing.
Nhưng trong thế giới cơ sở dữ liệu, còn có hai loại tinh vi hơn, là extendible hashing và linear hashing.
And again, I was saying, the confusing part is, I just have the linear probe hash table, and there'll be now a linear hashing hash table. And they're separate things. One's static, one's dynamic.
Và như tôi đã nói, điều gây nhầm lẫn là, tôi vừa có bảng băm linear probe, và bây giờ sẽ có thêm bảng băm linear hashing. Chúng là hai thứ khác nhau. Một cái tĩnh, một cái động.
I don't make up these names, right? I don't have any control. All right, so chain hashing, right? This is what you get in Java HashMap.
Tôi không đặt ra những cái tên này, tôi không có quyền quyết định. Được rồi, chain hashing, đúng không? Đây là thứ bạn có trong Java HashMap.
Actually, I don't know if Python gives you this by default, but this is what Java gives you.
Thực ra tôi không biết Python có cung cấp cái này mặc định không, nhưng đây là thứ Java cung cấp.
So, you're basically going to maintain a linked list of buckets for a given slot where you can insert keys.
Về cơ bản, bạn sẽ duy trì một danh sách liên kết các bucket cho mỗi ô nơi bạn có thể chèn các khóa.
So, it's kind of like a partitioned version of the linear probe hash table where you still have to do a sequential scan, potentially, to find the thing you're looking for.
Nó giống như một phiên bản phân vùng của bảng băm linear probe trong đó bạn vẫn phải quét tuần tự, có thể là vậy, để tìm thứ bạn cần.
At least now you don't have to scan the entire table. It's just scoped into some portion of the table. And you resolve collisions by just placing elements that collide with each other.
Ít nhất bây giờ bạn không phải quét toàn bộ bảng. Nó chỉ giới hạn trong một phần của bảng. Và bạn giải quyết xung đột bằng cách đặt các phần tử xung đột với nhau vào cùng chỗ.
You're going to append them to the end of this bucket linked list, right? You're going to find the key you're looking for.
Bạn sẽ nối chúng vào cuối danh sách liên kết của bucket này, đúng không? Bạn sẽ tìm khóa mà bạn cần.
You just hash into some linked list, and then you scan through and find to see whether the key exists or not. So, now we have this separate data structure of bucket pointers.
Bạn chỉ cần băm vào một danh sách liên kết nào đó, rồi quét qua để xem khóa đó có tồn tại hay không. Vậy là bây giờ chúng ta có một cấu trúc dữ liệu riêng chứa các con trỏ bucket.
And here's where we have all our buckets, right? So, I want to do a put on A. I hash it, mod N, by the number of bucket pointers I have.
Và đây là nơi chứa tất cả các bucket của chúng ta, đúng không? Giả sử tôi muốn thực hiện put trên A. Tôi băm nó, rồi lấy mod N, với N là số con trỏ bucket mà tôi có.
And that's going to then give me a pointer now to the starting location of the bucket chain. And now I just do my linear scan, linear probe, to find the first free slot.
Và kết quả sẽ cho tôi một con trỏ tới vị trí bắt đầu của chuỗi bucket. Sau đó tôi chỉ cần quét tuyến tính, dò tuyến tính, để tìm ô trống đầu tiên.
As soon as I find one, I can put the key that I want. So, I'll put A there.
Hễ tìm thấy một ô, tôi có thể đặt khóa mình muốn vào. Vậy tôi đặt A vào đó.
Same thing, I want to insert B, hash into the bucket pointer array, find the location, and we put it there.
Tương tự, tôi muốn chèn B, băm vào mảng con trỏ bucket, tìm vị trí, rồi đặt nó vào đó.
Now, we want to do a put C. C ends up in the same bucket chain as A.
Bây giờ, ta muốn put C. C rơi vào cùng chuỗi bucket với A.
But it scans through and sees A is occupying the first slot, jumps down to the next one until it gets it, right?
Nhưng nó quét qua và thấy A đang chiếm ô đầu tiên, nên nhảy xuống ô kế tiếp cho tới khi có chỗ, đúng không?
And then same thing with D. D goes where A and C are. By this point, our bucket, for simplicity, only has two slots.
Và tương tự với D. D đi vào chỗ có A và C. Đến lúc này, để đơn giản, bucket của ta chỉ có hai ô.
So, we have to make a new bucket and just have a pointer from that bucket to the next one. All right? So, obviously, this bucket chain can grow infinitely.
Vì vậy, ta phải tạo một bucket mới và chỉ cần có một con trỏ từ bucket đó tới bucket kế tiếp. Được chứ? Rõ ràng là chuỗi bucket này có thể dài vô hạn.
And so, if I'm unlucky and my hash function is terrible, they're all mapping to the same location, then it's going to be, again, O(n) and look up for everything.
Nên nếu tôi xui xẻo và hàm băm của tôi quá tệ, tất cả đều ánh xạ về cùng một vị trí, thì lại là O(n) cho mọi lần tra cứu.
And that's going to be bad. But the hash function, if it has low collision rate, then I'll have some more randomness and things will be more evenly spread out.
Và như vậy sẽ rất tệ. Nhưng nếu hàm băm có tỉ lệ va chạm thấp, thì sẽ có tính ngẫu nhiên hơn và dữ liệu sẽ phân tán đều hơn.
Same thing, put E, so forth. Goes in here, put F, goes down here, right?
Tương tự, put E, và cứ thế. Vào đây, put F thì xuống đây, đúng không?
So, one little optimization you can do that some systems do is you put a little filter in the bucket pointer array, similar to that prefix in the German strings that I just mentioned, where I can check this filter to say, hey, is the key I want, could it even exist in my bucket chain that I'm going to point to?
Có một tối ưu hóa nhỏ mà một số hệ thống áp dụng là đặt một bộ lọc nhỏ trong mảng con trỏ bucket, tương tự phần tiền tố trong chuỗi kiểu Đức mà tôi vừa đề cập, nơi tôi có thể kiểm tra bộ lọc này để biết: này, khóa tôi muốn liệu có thể tồn tại trong chuỗi bucket mà tôi sắp trỏ tới không?
If yes, then I do the scan. If no, then I don't even bother doing the scan. So, typically, you're going to use something like a Bloom filter.
Nếu có, tôi quét. Nếu không, tôi thậm chí không cần quét. Thông thường, bạn sẽ dùng thứ như Bloom filter.
It's okay if you don't know what a Bloom filter is. We'll cover that next week. But it basically, it gives you set membership. It just tells you, does this thing even exist or not?
Nếu bạn chưa biết Bloom filter là gì cũng không sao. Chúng ta sẽ học vào tuần sau. Nhưng về cơ bản, nó cho bạn biết quan hệ thuộc về tập hợp. Nó chỉ cho biết thứ này có tồn tại hay không?
And it may give you actually a false positive. It may tell you it exists when it doesn't actually exist, but it'll never give you a false negative.
Và thực ra nó có thể cho dương tính giả. Nó có thể báo là tồn tại trong khi thực tế không tồn tại, nhưng nó sẽ không bao giờ cho âm tính giả.
And it'll never say this thing doesn't exist when it actually truly does. All right.
Nó sẽ không bao giờ nói thứ này không tồn tại khi thực sự nó có tồn tại. Được rồi.
Let me try to plow through in 13 minutes, one of the two hardest data structures, but we can revisit this again on Monday next week, yeah.
Tôi sẽ cố gắng lướt qua trong 13 phút một trong hai cấu trúc dữ liệu khó nhất, nhưng chúng ta có thể xem lại vào thứ Hai tuần sau, nhé.
All right, so, extendable hashing is a more sophisticated dynamic hashing scheme that extends or builds upon the chain hashing approach that I just talked about before, where when I want to start resizing the data structure, I'm going to split buckets.
Được rồi, extendable hashing là một lược đồ băm động tinh vi hơn mở rộng hay xây dựng dựa trên cách băm theo chuỗi mà tôi vừa nói ban nãy, trong đó khi tôi muốn bắt đầu thay đổi kích thước cấu trúc dữ liệu, tôi sẽ tách các bucket.
Instead of just letting this linked list grow forever, which could end up being O(n), when my bucket gets full, I'm going to split it and redistribute the keys inside that bucket.
Thay vì cứ để danh sách liên kết này lớn mãi, có thể dẫn tới O(n), khi bucket của tôi đầy, thì tôi sẽ tách nó ra và phân phối lại các khóa bên trong bucket đó.
So, at most, the bucket chain can't grow forever. Every chain's going to have one bucket in it, right?
Như vậy, tối đa thì chuỗi bucket không thể cứ dài ra mãi. Mỗi chuỗi sẽ chỉ có một bucket, đúng không?
But the game they're going to play, to make this all work, is they're going to allow, in our bucket array, multiple locations in that bucket array to point to the same bucket.
Nhưng mẹo mà họ dùng để làm cho tất cả hoạt động được là họ cho phép, trong mảng bucket của chúng ta, nhiều vị trí trong mảng bucket đó cùng trỏ đến một bucket.
And that's going to be okay, right? So, this is not widely used. It's an older technique. It was in, it was a GNU database management system.
Và điều đó hoàn toàn ổn, đúng không? Kỹ thuật này không được dùng rộng rãi. Nó là một kỹ thuật cũ. Nó từng có trong một hệ quản trị cơ sở dữ liệu của GNU.
It's an embedded key-value store that the GNU environment provides you.
Đó là một kho khóa-giá trị nhúng mà môi trường GNU cung cấp cho bạn.
It's also used in AsterixDB, which is a big data system at UC Irvine from 10 years ago, but I think got merged into Couchbase, and Couchbase uses a lot of these techniques now.
Nó cũng được dùng trong AsterixDB, một hệ thống dữ liệu lớn ở UC Irvine từ 10 năm trước, nhưng tôi nghĩ đã được sáp nhập vào Couchbase, và hiện nay Couchbase dùng rất nhiều kỹ thuật này.
All right, so, let's see what this looks like.
Được rồi, hãy xem nó trông như thế nào.
Okay, so, for every bucket, there's going to be this sort of local indicator saying, how many bits do you have to use to get to that bucket?
Được rồi, với mỗi bucket, sẽ có một chỉ báo cục bộ cho biết cần dùng bao nhiêu bit để đến được bucket đó?
And there's going to be this global bit counter thing that's going to tell me, globally, how many bits do I need to consider at this point in time, based on the size of my hash table, to find a particular bucket for a given key?
Và sẽ có một bộ đếm bit toàn cục cho tôi biết, xét trên toàn cục, tại thời điểm này tôi cần xét bao nhiêu bit, dựa trên kích thước bảng băm, để tìm bucket cho một khóa cho trước?
So, it's basically going to determine that this is the maximum number of bits we have to consider in our hash.
Về cơ bản nó sẽ xác định đây là số lượng bit tối đa mà ta phải xét trong giá trị băm.
So, again, the hash function's going to return like a 32-bit integer or a 64-bit integer, but the way this scheme works is, at least as you start building it up, it's growing and resizing things, you only need to look at a small portion of those bits at the very beginning, right?
Vậy nên, một lần nữa, hàm băm sẽ trả về một số nguyên 32 bit hoặc 64 bit, nhưng cách sơ đồ này hoạt động là, ít nhất khi bạn mới bắt đầu xây dựng nó, nó đang lớn dần và thay đổi kích thước, bạn chỉ cần nhìn vào một phần nhỏ trong số các bit đó ở ngay phần đầu, đúng không?
So, in this case here, the global bit counter is two, so that means that I only need to look at two bits in my hash value, right?
Vậy trong trường hợp này, bộ đếm bit toàn cục là hai, nghĩa là tôi chỉ cần nhìn hai bit trong giá trị băm, đúng không?
And so, this global thing is going to increase anytime I'm going to start doing splits, I need to resize things, but then the local bit counter, it's just sort of keeping track of, like, for this bucket, how many bits did I actually use to get there?
Và giá trị toàn cục này sẽ tăng lên mỗi khi tôi bắt đầu thực hiện việc tách, tôi cần thay đổi kích thước, còn bộ đếm bit cục bộ thì chỉ theo dõi, kiểu như, với bucket này, tôi thực sự đã dùng bao nhiêu bit để đến đó?
But the way we're going to get into it, we need to use the global one and the hash bits and the bucket array on the side here, right?
Nhưng cách ta truy cập là cần dùng giá trị toàn cục cùng các bit băm và mảng bucket ở bên cạnh đây, đúng không?
All right, so let's sort of think of it like this, right?
Được rồi, hãy nghĩ về nó như thế này, đúng không?
So, for these first two elements, so first two locations in the bucket array, I only need the first bit, but for the other two, I need to look at all two bits, okay?
Với hai phần tử đầu tiên này, tức hai vị trí đầu tiên trong mảng bucket, tôi chỉ cần bit đầu tiên, nhưng với hai vị trí còn lại, tôi cần xét cả hai bit, được chứ?
So, let's first do a lookup on A, right?
Vậy trước hết hãy tra cứu A, đúng không?
The first thing I do is I hash A, I get back now a, you know, 64-bit integer, maybe 64 bits, but I look at my global counter, my bit counter, and it's set to two.
Việc đầu tiên tôi làm là băm A, và giờ tôi nhận lại một số nguyên 64 bit, có thể là 64 bit, nhưng tôi nhìn vào bộ đếm toàn cục, bộ đếm bit của tôi, và nó được đặt là hai.
So, I know I only need to look at two bits to find in my hash table the bucket I want for the headless potential key, right?
Vậy tôi biết mình chỉ cần nhìn hai bit để tìm trong bảng băm bucket mà tôi muốn cho khóa tiềm năng đó, đúng không?
So, the first two bits are zero, one, so I look in my bucket array, or zero, one, follow whatever that pointer is, and I land in that bucket that I want, right?
Hai bit đầu tiên là không, một, nên tôi nhìn vào mảng bucket, hoặc không, một, đi theo con trỏ đó, và tôi đến đúng bucket mà tôi muốn, đúng không?
That's pretty easy.
Khá dễ.
If I want to do a put, now I'll put a B, same thing, hash it, look at the first two bits, right? It's one, zero.
Nếu tôi muốn thực hiện put, giờ tôi sẽ put một B, cũng như vậy, băm nó, xem hai bit đầu, đúng không? Là một, không.
That takes me to this bucket here, and because I had a free slot, I can go ahead and insert it without spilling, and that's fine, right?
Nó đưa tôi đến bucket này, và vì còn một slot trống, tôi có thể chèn vào luôn mà không bị tràn, vậy là ổn, đúng không?
Now, let me do a put on C, and now when I hash it, the first two bits are one, zero again, and that's gonna take us to this bucket, but there's no more free slots for it inside the bucket, so now I have to overflow it.
Bây giờ, tôi thực hiện put C, và giờ khi băm nó, hai bit đầu lại là một, không, và nó sẽ đưa chúng ta đến bucket này, nhưng trong bucket không còn slot trống nào nữa, nên giờ tôi phải xử lý tràn.
So, the way this is gonna work is that I'm gonna increase my global bit counter to now three, and now I'm gonna create a new slot array here that's gonna be double the size that I had before, because I'm now gonna include an extra bit in the addressing scheme for it, right?
Cách nó hoạt động là tôi sẽ tăng bộ đếm bit toàn cục lên thành ba, và giờ tôi sẽ tạo một mảng slot mới ở đây có kích thước gấp đôi mảng trước đó, vì giờ tôi sẽ đưa thêm một bit vào cách đánh địa chỉ của nó, đúng không?
So, this thing's not that big. This is not like resizing the giant hash table of all my keys. This is a small operation. This is no big deal, right?
Cái này không lớn lắm. Đây không phải là thay đổi kích thước cả bảng băm khổng lồ chứa tất cả các khóa. Đây là một thao tác nhỏ. Không có gì to tát, đúng không?
So, now I'm gonna resize it, and now the global bit counter is three, but I have a bunch of other, and I have still that middle guy, that middle bucket I need to split, but for the one at the top and one at the bottom, I'm gonna leave them alone, because they're not being modified by this insert, right?
Vậy giờ tôi thay đổi kích thước nó, và bộ đếm bit toàn cục là ba, nhưng tôi còn một loạt cái khác, và vẫn còn bucket ở giữa đó mà tôi cần tách, còn cái ở trên cùng và cái ở dưới cùng thì tôi để yên, vì chúng không bị thay đổi bởi lần chèn này, đúng không?
It's only that one in the middle.
Chỉ có cái ở giữa thôi.
So, I'm gonna go ahead and split the middle guy, right, and then go through and rehash the keys that are in it to decide where they need to go next, right?
Vậy tôi sẽ tách cái ở giữa ra, đúng không, rồi duyệt qua và băm lại các khóa trong nó để quyết định chúng cần đi đâu tiếp theo, đúng không?
So, now, in my bucket array, I know that I have a bunch of locations here where I only need to look at the first bit, and that's gonna take me to that first location here.
Vậy bây giờ, trong mảng bucket của tôi, tôi có một loạt vị trí ở đây mà tôi chỉ cần xem bit đầu tiên, và nó sẽ đưa tôi đến vị trí đầu tiên ở đây.
So, bit is there, is go there.
Vậy bit là thế này, cứ đi đến đó.
Then I have these other ones here, you need to look at two bits, and that's gonna take me to the one down here, and then for three bits, those will be separated into those separate ones here, right?
Rồi có những cái khác ở đây, bạn cần xem hai bit, và nó sẽ đưa tôi đến cái ở dưới này, rồi với ba bit, chúng sẽ được tách ra thành những cái riêng biệt ở đây, đúng không?
Yes, question?
Vâng, bạn có câu hỏi?
Yes, question, is the number next to the bucket keeping track of how many times it's in the split? More or less, yes, yes, yes.
Vâng, câu hỏi, con số bên cạnh bucket có phải để theo dõi nó đã được tách bao nhiêu lần không? Gần như vậy, vâng, vâng, vâng.
So, the question is, could you come up with a pathological case where this thing just grows exponentially because everything's hashed in the same location? Yes.
Vậy câu hỏi là, liệu có thể nghĩ ra một trường hợp bệnh lý mà cái này cứ tăng theo cấp số nhân vì mọi thứ đều được băm vào cùng một vị trí không? Có.
So, like, if you have a table that has a billion records and you're trying to build a hash table on one column, And that one column only stores the value one.
Chẳng hạn, nếu bạn có một bảng với một tỉ bản ghi và bạn đang cố xây dựng một bảng băm trên một cột, Và cột đó chỉ lưu giá trị một.
It's a billion records that all have value one. Yeah, this is gonna be terrible for us, right? Don't do that, right?
Tức là một tỉ bản ghi đều có giá trị một. Vâng, thế này sẽ rất tệ cho chúng ta, đúng không? Đừng làm vậy nhé.
The question is, am I keeping track of which one is a two-bucket one or a three-bucket one? No, so you implicitly get that.
Câu hỏi là, liệu em có theo dõi cái nào là bucket hai ngăn hay ba ngăn không? Không, cái đó em có được một cách ngầm định.
So, I'm showing these numbers here, the one, three, three, two, but this is for demonstration purposes. The pointers themselves, because I'm allowing multiple slots to point to the same thing, right?
Ở đây tôi đang hiển thị các số này, một, ba, ba, hai, nhưng đó chỉ là để minh họa. Bản thân các con trỏ, vì tôi cho phép nhiều slot trỏ tới cùng một thứ, đúng không?
So, because I haven't split the first bucket yet, then if anything hashes to any of those slots here, implicitly, I know I only need to look at the first bit, and that takes me to that one, and they're all pointing to the same thing.
Vì tôi chưa tách bucket đầu tiên, nên nếu bất cứ thứ gì băm vào một trong các slot này, thì ngầm hiểu là tôi chỉ cần nhìn bit đầu tiên, và nó đưa tôi tới bucket đó, và tất cả đều trỏ tới cùng một thứ.
Yes? So, I have two questions. First, you said when you overflow, we don't want to cut one into two, but must we split two buckets and just redirect the hash?
Vâng? Em có hai câu hỏi. Thứ nhất, thầy nói khi bị tràn thì ta không muốn cắt một thành hai, nhưng chẳng phải ta phải tách hai bucket và chỉ chuyển hướng hàm băm sao?
One half of two to one and the other half of two to two?
Một nửa của hai về một và nửa còn lại của hai về hai?
So, his statement is, in this case here, when I want to overflow and split two, instead of splitting it, you're proposing to do what? To? Redirect one. What do you mean redirect?
Ý bạn là, trong trường hợp này, khi tôi muốn xử lý tràn và tách bucket hai, thay vì tách nó, bạn đề xuất làm gì? Để? Chuyển hướng một. Chuyển hướng nghĩa là sao?
Like, the second array. Like this thing, this thing here. Yeah, like, it's, well, okay, the first one, you just cut, it's like, the first array number two.
Kiểu như mảng thứ hai. Như cái này, cái này đây. Vâng, kiểu như, ừm, được rồi, cái đầu tiên thì cứ cắt, giống như mảng đầu tiên số hai.
Yes. And you just merge it with number one from number one, and that's the idea.
Vâng. Rồi gộp nó với số một từ số một, ý là vậy.
I see, but can't you just merge, I think it is, could you just take the, I see, take the second from the top, merge it back into one.
Tôi hiểu, nhưng không thể chỉ gộp sao, tôi nghĩ là, có thể lấy cái, Tôi hiểu, lấy cái thứ hai từ trên xuống, gộp ngược lại thành một.
No, because the hash value to get into that second one. You would still change the left-hand part, but you would still have more data on the right-hand side.
Không, vì giá trị băm để vào cái thứ hai đó. Bạn vẫn sẽ thay đổi phần bên trái, nhưng vẫn còn nhiều dữ liệu hơn ở phía bên phải.
So, it's just one OO goes in. Yeah, I understand what you're saying.
Vậy là chỉ có một OO đi vào. Vâng, tôi hiểu ý bạn.
I'd have to think about whether that's correct. You could do it, but like, you. Like, go to the one, go to the one. So, this goes back to what I was saying before.
Tôi phải suy nghĩ xem cách đó có đúng không. Làm được thì cũng làm được, nhưng mà. Kiểu như, đi tới cái một, đi tới cái một. Điều này quay lại với những gì tôi đã nói trước đó.
It isn't like an algorithms class where you assume everything's in memory. That top page, right, like the one with the one on it, that may be out on disk.
Đây không phải lớp thuật toán nơi bạn giả định mọi thứ đều nằm trong bộ nhớ. Trang trên cùng đó, cái có số một, có thể đang nằm trên đĩa.
So, you're proposing I gotta go create, still create the new page, right? So there's one allocate there.
Vậy bạn đề xuất là tôi vẫn phải tạo trang mới, đúng không? Tức là có một lần cấp phát ở đó.
Then I gotta go read that other page, bring it back in, and do a write to it again. It's just that extra machinery is just not worth it.
Rồi tôi phải đọc trang kia, đưa nó vào lại, và ghi lên nó một lần nữa. Cơ chế thêm đó đơn giản là không đáng.
What if you look at the least significant bits? Like, is it not like, same as, you wanna look at least significant bits, when that'd be more random.
Nếu nhìn vào các bit ít quan trọng nhất thì sao? Chẳng phải nó giống như, bạn muốn nhìn các bit ít quan trọng nhất, khi đó sẽ ngẫu nhiên hơn.
Depends on the hash function. It definitely means hashed, right? So, the hash is, hash is supposed to generate a, right, so you still get the result of the hash function.
Tùy hàm băm. Chắc chắn là đã được băm, đúng không? Hàm băm được cho là tạo ra một, đúng, nên bạn vẫn nhận được kết quả của hàm băm.
Yes, yeah, it's random.
Vâng, đúng, nó ngẫu nhiên.
So, his statement is, and he's correct, like, when we talk about bit packing, he said, like, oh, like, you sort of think it's a 32-bit integer, but most of the front of the bits are gonna be zero, and therefore that's sort of wasteful.
Ý bạn ấy là, và bạn ấy đúng, khi nói về bit packing, bạn ấy bảo, kiểu như, ồ, bạn hình dung nó là một số nguyên 32 bit, nhưng phần lớn các bit ở phía đầu sẽ bằng không, và do đó như vậy là lãng phí.
You're basically, with a hash function, you're taking, you're generating random integers for arbitrary keys.
Về cơ bản, với một hàm băm, bạn lấy, bạn tạo ra các số nguyên ngẫu nhiên cho các khóa bất kỳ.
So, like, the string A and the string B, those are pretty close to each other if you just look at the bit sequence, but if I take a good hash function, they may be completely different hash values.
Ví dụ, chuỗi A và chuỗi B, nếu chỉ nhìn vào dãy bit thì chúng khá gần nhau, nhưng nếu tôi dùng một hàm băm tốt, chúng có thể cho ra các giá trị băm hoàn toàn khác nhau.
Therefore, the bit sequences are completely random. So, I'm just showing you whatever, the most significant ones here.
Do đó, các dãy bit hoàn toàn ngẫu nhiên. Nên ở đây tôi chỉ cho các bạn xem những bit có trọng số cao nhất thôi.
All right, so, all right, let me get through this last one, linear hashing, and then we'll switch over to the guest speaker.
Được rồi, giờ hãy để tôi nói nốt phần cuối cùng, linear hashing, rồi chúng ta sẽ chuyển sang diễn giả khách mời.
So, that is the same, that we wanna be able to resize our hash table without having to rehash everything.
Vậy, vẫn giống như trước, chúng ta muốn thay đổi kích thước bảng băm mà không phải băm lại mọi thứ.
This is gonna be slightly different now, where we're gonna allow, we're gonna trigger a resizing when a, how's this, when a bucket overflows.
Lần này sẽ hơi khác một chút, ở chỗ chúng ta sẽ cho phép, chúng ta sẽ kích hoạt việc thay đổi kích thước khi một, nói thế nào nhỉ, khi một bucket bị tràn.
But the bucket we're not gonna split could potentially not be the one that overflowed. In extendable hashing, the one that overflowed, that's the one I split.
Nhưng bucket mà chúng ta sẽ tách có thể không phải là bucket đã bị tràn. Trong extendable hashing, bucket nào tràn thì tôi tách chính bucket đó.
In linear hashing, it may not be the one. We'll see why in a second.
Trong linear hashing, có thể không phải bucket đó. Lát nữa chúng ta sẽ thấy tại sao.
So, this is actually what Postgres uses. I think they called it the dynahash table, or dynamic hash table, something like that.
Đây thực ra là thứ Postgres sử dụng. Tôi nghĩ họ gọi nó là dynahash table, hay bảng băm động, đại loại thế.
The code that was written to this was written by one of Mike Stonebraker, the inventor of Postgres's students, back in Berkeley in early 90s, late 1980s.
Đoạn mã này được viết bởi một sinh viên của Mike Stonebraker, người phát minh ra Postgres, tại Berkeley vào đầu những năm 90, cuối những năm 1980.
She then went off and re-implemented a linear hash table in this thing called Berkeley DB that Oracle bought in 2006.
Sau đó cô ấy đi cài đặt lại một bảng băm tuyến tính trong thứ gọi là Berkeley DB mà Oracle đã mua vào năm 2006.
And then this is actually an internal data structure that DynamoDB uses as well. All right, so just like before, we have bucket pointers, and they're gonna point to buckets.
Và đây cũng là một cấu trúc dữ liệu nội bộ mà DynamoDB sử dụng. Được rồi, giống như trước, chúng ta có các con trỏ bucket, và chúng sẽ trỏ tới các bucket.
But now I have this extra thing called the split pointer. And that's basically just me pointing to some bucket.
Nhưng bây giờ tôi có thêm một thứ gọi là con trỏ tách (split pointer). Về cơ bản nó chỉ là một con trỏ trỏ tới một bucket nào đó.
That's gonna be the next bucket I'm gonna split whenever any bucket in my hash table overflows.
Đó sẽ là bucket tiếp theo mà tôi tách mỗi khi có bất kỳ bucket nào trong bảng băm bị tràn.
So, at the very beginning, I'm always gonna have powers of two number of buckets. In this case here, it'll be four.
Vậy ngay từ đầu, tôi luôn có số bucket là lũy thừa của hai. Trong trường hợp này là bốn.
And I'll have a hash function that, I could have multiple hash functions that I'm gonna use to decide where in my bucket pointer I wanna jump into based on the location of the split pointer.
Và tôi sẽ có một hàm băm, tôi có thể có nhiều hàm băm để dùng quyết định tôi sẽ nhảy tới đâu trong con trỏ bucket dựa trên vị trí của con trỏ tách.
Does it make more sense in a second? So, say I wanna get six. I take six, I hash it, say we're just doing the identity hash so it's the same value.
Lát nữa sẽ dễ hiểu hơn. Giả sử tôi muốn tìm khóa sáu. Tôi lấy số sáu, băm nó, giả sử chúng ta dùng hàm băm đồng nhất nên giá trị vẫn như cũ.
And I'm gonna modify the number of buckets that I have, in this case four, and I end up getting two.
Và tôi lấy nó modulo số bucket hiện có, ở đây là bốn, và kết quả là hai.
And so, when I do my look at my bucket array, I would see that that bucket is below Where the split pointer is pointing at.
Và như vậy, khi tôi nhìn vào mảng bucket, tôi sẽ thấy bucket đó nằm phía trên vị trí mà con trỏ split đang trỏ tới.
So, I know I only need one hash function to find the thing that I'm looking for.
Vậy nên tôi biết mình chỉ cần một hàm băm để tìm thứ mình cần.
So, then I just jump along, end in a bucket, do linear scan to find the thing that I want. Now, let's say I wanna do a put on 17.
Sau đó tôi chỉ việc nhảy tới, kết thúc ở một bucket, rồi quét tuyến tính để tìm thứ tôi muốn. Bây giờ, giả sử tôi muốn thực hiện put với 17.
I mod it by four, I get one. Now, when I land in this location here, using the single hash function, I see that the bucket is full.
Tôi lấy nó mod 4, được 1. Bây giờ, khi tôi đến vị trí này, dùng hàm băm duy nhất, tôi thấy bucket đã đầy.
So, now I gotta do a, I have to add an extra bucket to my chain and keep track that I overflowed. So, that means I'm gonna split something.
Vậy bây giờ tôi phải thêm một bucket phụ vào chuỗi và ghi nhớ rằng mình đã bị tràn. Nghĩa là tôi sẽ phải split một thứ gì đó.
But the thing I'm gonna split isn't the thing that just overflowed, I'm gonna split whatever the split pointer's pointing at. In this case here, it's pointing to the top bucket, bucket zero.
Nhưng thứ tôi split không phải là bucket vừa bị tràn, mà là bucket mà con trỏ split đang trỏ tới. Trong trường hợp này, nó đang trỏ tới bucket trên cùng, bucket 0.
So, I'm gonna go ahead and split this guy. Even though it has a free slot, and it could absorb another insert, I'm still gonna split it.
Vậy tôi sẽ tiến hành split bucket này. Dù nó vẫn còn một chỗ trống, và có thể nhận thêm một lần chèn nữa, tôi vẫn split nó.
So, now to do this, I'm gonna add an extra entry into my bucket pointer array. So, now there'll be slot four.
Để làm vậy, tôi sẽ thêm một mục vào mảng con trỏ bucket. Vậy bây giờ sẽ có ô số 4.
But now I can't address that if I do mod n, what it was before, which is when I had four. Now, I'm gonna mod it by 2n, whatever I had before.
Nhưng giờ tôi không thể định vị nó nếu dùng mod n, giá trị trước đó, tức là khi tôi có 4. Bây giờ tôi sẽ mod cho 2n, với n là giá trị trước đó.
So, even though I haven't added any entries into my bucket pointer beyond just this fourth one here, I know I'm gonna keep growing.
Vậy nên, dù tôi chưa thêm mục nào vào mảng con trỏ bucket ngoài ô thứ tư này, tôi biết mình sẽ còn tiếp tục mở rộng.
So, I may have to add new entries as my split pointer moves down. So, in this case here, I have my new hash function.
Nên tôi có thể phải thêm các mục mới khi con trỏ split dịch xuống. Vậy ở đây, tôi có hàm băm mới.
Now I gotta go figure out where to go put all of the keys that exist in the first bucket that I split.
Bây giờ tôi phải tìm xem đặt tất cả các khóa đang có trong bucket đầu tiên mà tôi vừa split vào đâu.
So, I take key eight, mod it by now 2n. So, this can get by eight. So, eight mod eight is zero. So, that's gonna stay where it started.
Tôi lấy khóa 8, mod cho 2n, giờ là 8. 8 mod 8 bằng 0. Vậy nó sẽ ở nguyên chỗ ban đầu.
But then 20 mod eight is four. So, that's gonna now point to this one down here. So, I'm gonna move 20 down here. And I move the split pointer down by one.
Nhưng 20 mod 8 bằng 4. Vậy bây giờ nó sẽ trỏ tới bucket ở dưới này. Nên tôi chuyển 20 xuống đây. Và dịch con trỏ split xuống một bước.
Now I do a lookup on 20. First thing I'm gonna do is take the first hash function. So, take whatever the value is, mod by n, and that's gonna land me in location zero.
Bây giờ tôi tra cứu 20. Việc đầu tiên là dùng hàm băm thứ nhất. Lấy giá trị đó, mod cho n, và nó sẽ đưa tôi tới vị trí 0.
Because again, that's where it was before, with the first hash function. But here, now I check to see, is the location with the first hash function above the split pointer?
Vì như trước đó, đó là vị trí của nó với hàm băm thứ nhất. Nhưng bây giờ tôi kiểm tra xem vị trí theo hàm băm thứ nhất có nằm phía trên con trỏ split không?
If yes, then I know that the bucket had been split. So, therefore, I have to hash it again using the second hash function to find where its current real location actually is.
Nếu có, thì tôi biết bucket đó đã bị split. Do đó, tôi phải băm lại bằng hàm băm thứ hai để tìm vị trí thật hiện tại của nó thực sự nằm ở đâu.
Because I don't know, after I do the first hash function, whether it remained at the top or it got moved down to the one at the bottom.
Vì sau khi dùng hàm băm thứ nhất, tôi không biết nó vẫn ở trên hay đã bị chuyển xuống bucket ở dưới.
In this case here, 20 got moved to the bottom. You're shaking your head no, as if this is terrible.
Trong trường hợp này, 20 đã bị chuyển xuống dưới. Bạn đang lắc đầu, như thể điều này tệ lắm.
Like saying no.
Kiểu như nói là không.
Yes, so this sounds crazy, like why would you do this?
Vâng, thế nên nghe có vẻ điên rồ, kiểu như tại sao lại làm vậy?
The idea is that, eventually, if I overflow again, then I'll split the one that I built the chain on.
Ý tưởng là, cuối cùng, nếu tôi lại bị tràn, thì tôi sẽ tách bucket mà tôi đã xây chuỗi tràn lên đó.
So, eventually, it all evens out, and you can end up with a balanced data structure. Yes, by 2n, yes.
Vậy nên cuối cùng mọi thứ sẽ cân bằng lại, và bạn có được một cấu trúc dữ liệu cân bằng. Vâng, theo 2n, đúng vậy.
So, yeah, whenever you split something else. All right, last question. Sorry. How do you do the split here? How do you split 2n, you have like seven neurons?
Vâng, mỗi khi bạn tách một bucket khác. Được rồi, câu hỏi cuối cùng. Xin lỗi nhé. Bạn thực hiện việc tách ở đây như thế nào? Làm sao tách 2n, khi bạn có chẳng hạn bảy neuron?
The question is, would you ever get out of bounds? The array actually exists, you just haven't allocated buckets for the things below it yet.
Câu hỏi là liệu có bao giờ bị vượt ngoài giới hạn không? Mảng đó thực ra vẫn tồn tại, chỉ là bạn chưa cấp phát bucket cho các phần bên dưới nó.
Yeah, all right, sorry. We can come back to this on class next week. We'll pick up on it again. Let's switch over to Karthik. All right, this is Karthik. He's the co-founder of GigaByte.
Vâng, được rồi, xin lỗi nhé. Chúng ta có thể quay lại vấn đề này vào buổi học tuần sau. Chúng ta sẽ tiếp tục sau. Giờ chuyển sang Karthik. Được rồi, đây là Karthik. Anh ấy là đồng sáng lập của GigaByte.
It's been 10 years, right? It's getting there, almost 10 years, nine and a half, yes. It takes 10 years to build a database, so yeah, you're fighting it, it is right.
Đã 10 năm rồi nhỉ? Sắp rồi, gần 10 năm, chín năm rưỡi. Xây một cơ sở dữ liệu mất 10 năm, nên anh đang vật lộn với nó, đúng vậy.
Which is insane. All right, floor is yours. Thank you for being here. So, folks that are not familiar with GigaByteDB, we convert Postgres SQL. It's a new database.
Thật điên rồ. Được rồi, xin mời anh. Cảm ơn anh đã có mặt. Với những bạn chưa quen với GigaByteDB, chúng tôi chuyển đổi Postgres SQL. Đây là một cơ sở dữ liệu mới.
We've taken Postgres as the source code, and we made it a distributed database.
Chúng tôi lấy mã nguồn của Postgres và biến nó thành một cơ sở dữ liệu phân tán.
And we're fully open source in our Apache 2.0, and we've had quite a few, like, you know, members in the community contributing a lot of deployments, et cetera, et cetera.
Chúng tôi hoàn toàn mã nguồn mở theo giấy phép Apache 2.0, và đã có khá nhiều thành viên trong cộng đồng đóng góp rất nhiều, triển khai nhiều hệ thống, vân vân.
And we are a distributed cloud-native version of Postgres, right? These are some of the things we focus on: distributed transactions, multi-API, cloud-native, and getting, you know, supporting AI workloads.
Chúng tôi là phiên bản Postgres phân tán, cloud-native, đúng không? Đây là một số điều chúng tôi tập trung vào: giao dịch phân tán, đa API, cloud-native, và hỗ trợ các tác vụ AI.
We look at a few of these things, right? So, what are we really, as I said, distributed, fully Postgres-compatible database? We're built for business-critical applications, right?
Chúng ta cùng xem một vài điều này nhé. Vậy thực chất chúng tôi là gì, như tôi đã nói, một cơ sở dữ liệu phân tán, tương thích hoàn toàn với Postgres? Chúng tôi được xây dựng cho các ứng dụng trọng yếu của doanh nghiệp.
And we focus on bringing resilience, scalability, and geodistribution of multi-region deployments to Postgres. And this helps people build modern applications.
Và chúng tôi tập trung mang đến khả năng phục hồi, khả năng mở rộng, và phân bố địa lý của các triển khai đa vùng cho Postgres. Điều này giúp mọi người xây dựng các ứng dụng hiện đại.
They can think of multi-region, GNI, Edge, these type of applications, or to modernize their existing applications that are high value, but want to come into the cloud-native world.
Họ có thể nghĩ đến đa vùng, GenAI, Edge, những loại ứng dụng như vậy, hoặc hiện đại hóa các ứng dụng hiện có có giá trị cao, nhưng muốn bước vào thế giới cloud-native.
Our thesis, why, like, it's always important to ask yourselves, if you know why a database exists, we ask ourselves that, and what is the differentiation?
Luận điểm của chúng tôi, tại sao, luôn quan trọng là tự hỏi bản thân, tại sao một cơ sở dữ liệu tồn tại, chúng tôi tự hỏi như vậy, và điểm khác biệt là gì?
So, if you think of Y-axis as how Postgres-compatible a database is, and the X-axis as truly how cloud-native a database is, we were born to be at the intersection of those two.
Nếu bạn coi trục Y là mức độ tương thích với Postgres của một cơ sở dữ liệu, và trục X là mức độ thực sự cloud-native của nó, thì chúng tôi sinh ra để nằm ở giao điểm của hai trục đó.
There's a line on the Y-axis, after which you're reusing Postgres code, and those databases continue to benefit from Postgres and inherit most of the Postgres innovations.
Có một ranh giới trên trục Y, vượt qua đó bạn tái sử dụng mã Postgres, và những cơ sở dữ liệu đó tiếp tục hưởng lợi từ Postgres và thừa hưởng hầu hết các cải tiến của Postgres.
There is a line on the X-axis, the cloud-native database innovation threshold, to the right of which you can truly go and build cloud-native systems, right?
Có một ranh giới trên trục X, ngưỡng đổi mới của cơ sở dữ liệu cloud-native, ở bên phải đường đó, bạn mới thực sự có thể xây dựng các hệ thống cloud-native, đúng không?
To put names to faces, if this is our thesis of the market, you can test it out yourself. You obviously shouldn't trust me.
Để gắn tên với từng đối tượng cụ thể, nếu đây là luận điểm của chúng tôi về thị trường, thì bạn có thể tự kiểm chứng. Dĩ nhiên các bạn không nên tin tôi.
I'm a founder, so you should trust only so far as it goes and extend your own ideas to this.
Tôi là một nhà sáng lập, nên các bạn chỉ nên tin ở mức vừa phải và tự mở rộng những ý tưởng của riêng mình từ đó.
But anyways, The ones above the PG innovation threshold reuse Postgres code, therefore can build along with the Postgres innovation. Otherwise, you're building to it.
Dù sao thì, những hệ thống nằm phía trên ngưỡng đổi mới PG đều tái sử dụng mã Postgres, nên có thể phát triển song hành cùng các đổi mới của Postgres. Nếu không, bạn chỉ đang chạy theo nó.
And those to the right of the cloud-native innovation threshold are architected from the ground up to be shared-nothing, cloud-native, highly resilient and available, right?
Còn những hệ thống nằm bên phải ngưỡng đổi mới cloud-native được thiết kế kiến trúc từ đầu theo mô hình shared-nothing, cloud-native, có khả năng phục hồi và tính sẵn sàng cao, đúng không?
And so we were born after most of these databases, so hopefully we got something right, which was to hybridize the best of those two into a single product.
Chúng tôi ra đời sau hầu hết các cơ sở dữ liệu này, nên hy vọng là chúng tôi đã làm đúng một điều, đó là kết hợp những điểm tốt nhất của hai hướng đó thành một sản phẩm duy nhất.
Okay, these are, again, our areas of innovation: Postgres, distributed, enterprise-grade, AI, right? We have a lot of customers, won't bore you with this.
Được rồi, đây lại là các lĩnh vực đổi mới của chúng tôi: Postgres, phân tán, chuẩn doanh nghiệp, AI, đúng không? Chúng tôi có rất nhiều khách hàng, tôi sẽ không làm các bạn chán với chuyện này.
I'd like to talk about just one customer here, NPCI, which is the National Payment Corporation of India.
Tôi chỉ muốn nói về một khách hàng ở đây, NPCI, tức Tổng công ty Thanh toán Quốc gia Ấn Độ.
So all mobile payments in India are going through a YugoByte database, very proud of the achievement as a product, as a company.
Vậy là mọi khoản thanh toán di động ở Ấn Độ đều đi qua một cơ sở dữ liệu YugaByte, chúng tôi rất tự hào về thành tựu này, với tư cách là một sản phẩm và một công ty.
But anyway, it's just something to show the level to which it waxes and wanes, the level to which you need resilience.
Nhưng dù sao, đó chỉ là ví dụ cho thấy mức độ lên xuống của tải, và mức độ bạn cần khả năng phục hồi.
It is truly the case there that resilience, availability, uptime, and scalability equals money, right, in this example. Okay, so with that, let's jump right into some of the design principles.
Ở đó đúng là khả năng phục hồi, tính sẵn sàng, thời gian hoạt động và khả năng mở rộng đồng nghĩa với tiền, đúng không, trong ví dụ này. Được rồi, vậy chúng ta hãy đi thẳng vào một số nguyên tắc thiết kế.
We wanted to build everything in Postgres, no questions asked.
Chúng tôi muốn xây dựng mọi thứ của Postgres, không có ngoại lệ.
So all the Postgres isolation levels, the Postgres transactional semantics, all of the advanced features and extensions, and the ability to do rolling upgrades and downgrades across major Postgres versions.
Tức là tất cả các mức cô lập của Postgres, ngữ nghĩa giao dịch của Postgres, mọi tính năng nâng cao và phần mở rộng, cùng khả năng nâng cấp cuốn chiếu và hạ cấp giữa các phiên bản chính của Postgres.
That last one was really hard. It's not something that, like, as far as I know, anyone else really does. And it's something that, you know, we're pretty proud of having implemented.
Điều cuối cùng đó thực sự rất khó. Theo tôi biết thì chưa ai khác thực sự làm được điều này. Và chúng tôi khá tự hào vì đã triển khai được nó.
It took a lot of work to really, like, you know, to bring it to fruition.
Chúng tôi đã phải bỏ ra rất nhiều công sức để hiện thực hóa nó.
Anyway, so these are some of the Postgres features that we support, like on the right, like all the way to stored procedures and triggers and everything, right?
Dù sao thì đây là một số tính năng Postgres mà chúng tôi hỗ trợ, như ở bên phải, đi đến tận stored procedure và trigger và mọi thứ, đúng không?
So we pretty much, our goal is to support everything. We also go beyond Postgres. We address some of its architectural limitations.
Mục tiêu của chúng tôi là hỗ trợ tất cả mọi thứ. Chúng tôi cũng đi xa hơn Postgres. Chúng tôi giải quyết một số hạn chế về kiến trúc của nó.
There are architectural limitations when it comes to the core database features, when it comes to scalability, your resilience, availability, DR, disaster recovery, and multi-region deployments and security.
Có những hạn chế về kiến trúc liên quan đến các tính năng cốt lõi của cơ sở dữ liệu, về khả năng mở rộng, khả năng phục hồi, tính sẵn sàng, DR, tức khôi phục sau thảm họa, triển khai đa vùng và bảo mật.
So these are some of the areas that we go ahead and look at in more detail as it relates to modern applications, right?
Đây là một số lĩnh vực mà chúng tôi xem xét chi tiết hơn trong mối liên hệ với các ứng dụng hiện đại, đúng không?
And the same thing, when you look at it, when you flip the coin and look at it, like things like connection pooling and observability and perf tuning, when folks come from other systems or build services today, like Lambda systems, they expect a lot of these things, right?
Và tương tự, khi bạn lật đồng xu lại và nhìn mặt kia, như connection pooling, khả năng quan sát và tinh chỉnh hiệu năng, khi mọi người chuyển từ các hệ thống khác sang hoặc xây dựng các dịch vụ ngày nay, như các hệ thống Lambda, họ kỳ vọng rất nhiều những thứ này, đúng không?
So these are the things we are putting into Postgres at an architectural level.
Vậy đây là những thứ chúng tôi đưa vào Postgres ở cấp độ kiến trúc.
So, and I'll be, I'm breezing through the section because we can get to the really, like, you need to know the layout of what we're building in order to talk about some of the details, right?
Và tôi sẽ lướt nhanh phần này, vì chúng ta có thể đi vào những phần thực sự quan trọng, bởi vì bạn cần biết bố cục của thứ chúng tôi đang xây dựng để có thể nói về một số chi tiết, đúng không?
The other piece that we did, and this was a foundational thesis, like as a way of a quick background, I used to work at Meta before.
Một phần nữa mà chúng tôi đã làm, và đây là luận điểm nền tảng, nói nhanh về bối cảnh, trước đây tôi từng làm việc ở Meta.
And at Meta, what we learned and what we felt was building cloud native applications is not about SQL and NoSQL.
Và ở Meta, điều chúng tôi học được và cảm nhận là việc xây dựng các ứng dụng cloud native không phải là chuyện SQL hay NoSQL.
It's about relaxing constraints and driving value by going faster in certain types of scenarios.
Nó là việc nới lỏng các ràng buộc và tạo ra giá trị bằng cách đi nhanh hơn trong một số loại kịch bản nhất định.
So it's not SQL or NoSQL, it is about how can you operationalize and get those workloads that are being built to really run well in the cloud or in cloud native infrastructure, right?
Vậy nên không phải là SQL hay NoSQL, mà là làm thế nào để vận hành hóa và khiến những khối lượng công việc đang được xây dựng đó chạy thật tốt trên đám mây hoặc trên hạ tầng cloud native, đúng không?
So to that effect, we started with two APIs on top because everybody we spoke to said, don't build another goddamn database.
Với mục đích đó, chúng tôi bắt đầu với hai API ở bên trên vì tất cả những người chúng tôi trao đổi đều nói: đừng xây thêm một cái cơ sở dữ liệu chết tiệt nào nữa.
So when you really looked into it, we figured out they meant, what they meant to say was don't build a new API. No one understands what a new API will do.
Khi tìm hiểu kỹ, chúng tôi nhận ra ý họ là, điều họ muốn nói là đừng xây một API mới. Không ai hiểu một API mới sẽ làm được gì.
However, existing databases like Postgres, like, you know, like say Oracle, Mongo, all of these things, you have an intuition as to when to pick them. And so that's how the industry operates.
Tuy nhiên, với các cơ sở dữ liệu hiện có như Postgres, hay chẳng hạn Oracle, Mongo, tất cả những thứ này, bạn có trực giác về lúc nào nên chọn chúng. Và đó là cách ngành công nghiệp vận hành.
So, You know, we started out with two. One was Apache Cassandra based and the other is obviously Postgres.
Vì vậy, chúng tôi bắt đầu với hai API. Một dựa trên Apache Cassandra và cái còn lại hiển nhiên là Postgres.
And now the DocumentDB folks at Azure are building a Mongo API, like, on top of Postgres.
Và giờ đội DocumentDB ở Azure đang xây dựng một API Mongo trên nền Postgres.
So this is something we inherited, and we can, obviously, being a scalable and resilient version of Postgres, that's pretty exciting.
Đây là thứ chúng tôi thừa hưởng, và rõ ràng chúng tôi có thể, với tư cách là một phiên bản Postgres có khả năng mở rộng và chịu lỗi tốt, điều đó khá thú vị.
There's Oracle as well that we're working with some folks on, and the industry in general is building more and more of these emulation layers, presumably because JNI is making it faster to go in that direction, right?
Cũng có Oracle mà chúng tôi đang làm việc với một số người, và nhìn chung ngành công nghiệp đang xây dựng ngày càng nhiều các lớp giả lập như vậy, có lẽ vì JNI đang giúp đi theo hướng đó nhanh hơn, đúng không?
So this is something that we're just seeing as a trend. Okay, so let's take a look at the architecture at a glance. At the highest level, we wanted to achieve Postgres functionality, right?
Đây là điều mà chúng tôi thấy như một xu hướng. Được rồi, hãy xem qua kiến trúc một cách tổng quan. Ở mức cao nhất, chúng tôi muốn đạt được chức năng của Postgres, đúng không?
So the way we did this was we took the left and moved it to the right. Left is a very, very high level view of what Postgres is.
Cách chúng tôi làm là lấy phần bên trái và chuyển sang bên phải. Bên trái là một cái nhìn rất rất tổng quát về Postgres.
Think of the query processing engine of Postgres as the green box and the storage components as the blue box below. So we retained the green box, right?
Hãy coi bộ máy xử lý truy vấn của Postgres là khối màu xanh lá và các thành phần lưu trữ là khối màu xanh dương bên dưới. Chúng tôi giữ lại khối xanh lá, đúng không?
And made it stateless and to be able to run on any node, and replace the blue box with our own storage layer, which is a distributed transactional storage layer, right?
Và biến nó thành phi trạng thái để có thể chạy trên bất kỳ nút nào, và thay khối xanh dương bằng lớp lưu trữ của riêng chúng tôi, là một lớp lưu trữ giao dịch phân tán, đúng không?
So that means the blue box now is distributed and replicated, and it gives the information to the green boxes above in the way that Postgres expects it, as a tuple.
Nghĩa là khối xanh dương giờ đây được phân tán và nhân bản, và nó cung cấp thông tin cho các khối xanh lá phía trên theo cách Postgres mong đợi, dưới dạng một tuple.
So green box just does its thing and fires off queries.
Vậy khối xanh lá cứ làm việc của nó và gửi đi các truy vấn.
The storage layer does all of the filtering, fetching, all of that stuff, and presents the data in the way the green boxes would have had them in the left, right?
Lớp lưu trữ thực hiện toàn bộ việc lọc, tìm nạp, tất cả những việc đó, và trình bày dữ liệu theo cách mà khối xanh lá boxes lẽ ra đã có chúng ở bên trái, đúng không?
Like the Postgres query processing engine.
Giống như bộ máy xử lý truy vấn của Postgres.
Obviously, if you do this, you get into, it works, but the problem is it doesn't work very well from a performance standpoint, because you're now reading all the data up to a single node and then doing a bunch of processing there.
Rõ ràng là nếu bạn làm vậy thì nó chạy được, nhưng vấn đề là xét về hiệu năng thì nó chạy không tốt lắm, vì bạn đang đọc toàn bộ dữ liệu lên một nút duy nhất rồi xử lý hàng loạt thứ ở đó.
So that doesn't work really well. So the next step immediately that comes up is to start doing these push nodes. How can you push more and more operations to where the data is?
Nên cách đó không hiệu quả lắm. Vì vậy bước tiếp theo xuất hiện ngay là bắt đầu đẩy xuống các nút này (push down). Làm sao đẩy ngày càng nhiều thao tác đến nơi chứa dữ liệu?
How can you be smarter about how little data you can transfer between these nodes, right? That becomes the name of the game. And so that's something that we focused on quite a bit.
Làm sao khéo léo hơn để truyền đi càng ít dữ liệu giữa các nút này càng tốt, đúng không? Đó trở thành mục tiêu chính. Và đó là điều chúng tôi tập trung khá nhiều.
And I'd say all of these things are still going on because Postgres is improving and we're still bringing more of the Postgres features into YugoBytes. So these are all like a continuum, right?
Tôi cho rằng tất cả những việc này vẫn đang tiếp diễn vì Postgres đang được cải tiến và chúng tôi vẫn đang đưa thêm nhiều tính năng của Postgres vào YugoBytes. Vậy tất cả những thứ này giống như một chuỗi liên tục, đúng không?
This is the way it continues to work. And another aspect that we look at is how can we match the performance of Postgres?
Đây là cách nó tiếp tục vận hành. Và một khía cạnh khác chúng tôi xem xét là làm sao để sánh được với hiệu năng của Postgres?
And, you know, this is where it gets into really interesting stuff. YugoByteDB is a log-structured storage engine and Postgres uses a B-tree format to write into disk.
Và đây là chỗ nó trở nên thực sự thú vị. YugoByteDB là một storage engine dạng log-structured còn Postgres dùng định dạng B-tree để ghi xuống đĩa.
I hope folks are familiar. If not, like, you know, maybe ask Andy. He'll tell you in a different class, but log-structured is really good for SSDs and it has a lot of good properties.
Tôi hy vọng mọi người đã quen. Nếu chưa thì cứ hỏi Andy. Thầy ấy sẽ giải thích trong một lớp khác, nhưng log-structured rất tốt cho SSD và có nhiều đặc tính hay.
However, the Postgres cost-based optimizer and its performance is tied at the hip to the way it stores data on disk, right?
Tuy nhiên, bộ tối ưu hóa dựa trên chi phí của Postgres và hiệu năng của nó gắn chặt với cách nó lưu dữ liệu trên đĩa, đúng không?
So this is something that we've been looking at and this is almost a two-year journey for us where think of this as the different access patterns that Postgres exposes.
Đây là điều chúng tôi đã và đang nghiên cứu và đó gần như là hành trình hai năm của chúng tôi, hãy coi đây là các kiểu truy cập khác nhau mà Postgres cung cấp.
And we started out at a pretty low number and, you know, we're working our way to a pretty, pretty high number, right?
Chúng tôi bắt đầu từ một con số khá thấp và đang tiến dần đến một con số khá cao, đúng không?
In terms of what we're able to support, the number of comparable operations we're able to support with respect to Postgres as well as the cost-based optimizer.
Xét về những gì chúng tôi có thể hỗ trợ, số lượng thao tác tương đương mà chúng tôi hỗ trợ so với Postgres cũng như bộ tối ưu hóa dựa trên chi phí.
In this case, Postgres works on a single node.
Ở đây, Postgres chạy trên một nút duy nhất.
So the way it sets up a query plan and the way it executes any query that a user does is often optimized for a single node.
Nên cách nó lập kế hoạch truy vấn và cách nó thực thi mọi truy vấn của người dùng thường được tối ưu cho một nút duy nhất.
And we are a distributed database, which goes after a distributed plan. However, a lot of our users complain that, "Look, this was a simple query that was just a couple of gigabytes on Postgres.
Còn chúng tôi là cơ sở dữ liệu phân tán, nên hướng tới một kế hoạch phân tán. Tuy nhiên, nhiều người dùng của chúng tôi phàn nàn rằng: "Này, đây là một truy vấn đơn giản chỉ vài gigabyte trên Postgres.
It would run on my laptop. It doesn't really work. It's like a hundred times worse on gigabyte." Well, the problem is we sharded it and moved it all over the different nodes.
Nó chạy được trên laptop của tôi. Ở đây thì không ổn. Nó chậm hơn khoảng một trăm lần." Vấn đề là chúng tôi đã phân mảnh nó và rải ra các nút khác nhau.
And if you're fetching 1,000 rows and you're returning one, fetching 1,000 rows from local disk, you know, your order of access is in the microseconds.
Và nếu bạn lấy 1.000 hàng và chỉ trả về một, lấy 1.000 hàng từ đĩa cục bộ, thì bậc độ lớn thời gian truy cập là micro giây.
So 1,000 rows would be in the order of milliseconds, and you filter it down to one row and you return it. Great. Fetching 1,000 rows over the network is in the order of milliseconds.
Vậy 1.000 hàng sẽ cỡ mili giây, rồi bạn lọc xuống còn một hàng và trả về. Tốt. Lấy 1.000 hàng qua mạng thì cỡ mili giây mỗi hàng.
So that would be in the order of hundreds of milliseconds to a second. So your performance sucks, but no use telling the user that because they're thinking, "It's just 1,000 rows.
Vậy tổng cộng sẽ cỡ hàng trăm mili giây đến một giây. Vậy là hiệu năng của bạn rất tệ, nhưng nói với người dùng thì vô ích vì họ sẽ nghĩ: "Chỉ có 1.000 hàng thôi mà.
How bad can it be?" Right?
Có thể tệ đến mức nào chứ?" Đúng không?
So we had to do an adaptive thing where we're able to match Postgres at the lower ends of scale when scale isn't big while providing resilience, but be able to adapt to how to automatically shard and scale.
Vì vậy chúng tôi phải làm một giải pháp thích ứng, có thể sánh ngang Postgres ở các mức quy mô nhỏ, khi quy mô chưa lớn, mà vẫn đảm bảo khả năng phục hồi, nhưng vẫn có thể thích ứng để tự động phân mảnh và mở rộng.
Right? And we had to build a whole framework for it to estimate what percentage of the time we picked the best plan versus Postgres. And we use the TACO framework like this.
Đúng không? Và chúng tôi phải xây dựng cả một framework để ước lượng tỉ lệ phần trăm thời gian chúng tôi chọn được kế hoạch tốt nhất so với Postgres. Và chúng tôi dùng framework TACO như thế này.
There's an academic paper on it. We use that paper to build a framework to then go test it. And so this is one of the parts of our testing suite. Okay.
Có một bài báo học thuật về nó. Chúng tôi dùng bài báo đó để xây dựng một framework rồi đem ra kiểm thử. Và đây là một phần trong bộ kiểm thử của chúng tôi. Được rồi.
Postgres is a single node. And if you put two nodes of Postgres, people will tell you, why don't you deploy PgBouncer? Simple, right? Perfect. We're kind of short on time.
Postgres là một nút đơn. Và nếu bạn dùng hai nút Postgres, mọi người sẽ bảo: sao không triển khai PgBouncer? Đơn giản, đúng không? Hoàn hảo. Chúng ta hơi thiếu thời gian.
You have, like, a last slide or something you want to show? Yeah, so I wanted to say connection manager, building it in, Sharding vector indexes and attaching it to the data.
Anh có slide cuối cùng nào muốn cho xem không? Vâng, tôi muốn nói về connection manager, tích hợp sẵn nó vào, phân mảnh các chỉ mục vectơ và gắn chúng với dữ liệu.
These are some of the topics that we work on.
Đây là một số chủ đề mà chúng tôi đang làm.
Looking forward, we're looking at a whole bunch of future things, like putting in BM25, other types of indexes, so on and so forth, a whole bunch of stuff.
Trong tương lai, chúng tôi đang xem xét rất nhiều thứ, như đưa BM25 vào, các loại chỉ mục khác, v.v., còn rất nhiều thứ nữa.
I had something interesting that maybe, if you had five minutes, Andy, I'll share. If not, it's okay. It was about a few interesting architectural war stories.
Tôi có một chuyện khá thú vị, nếu anh có năm phút, Andy, tôi sẽ chia sẻ. Nếu không thì cũng không sao. Đó là vài câu chuyện thực tế thú vị về kiến trúc.
I just had three, four of them. But if it's interesting, I'll show it. Otherwise, I'll skip. I mean, it's interesting to me. We're out of time.
Tôi chỉ có ba, bốn câu chuyện. Nhưng nếu hay thì tôi sẽ cho xem. Không thì tôi bỏ qua. Ý tôi là, tôi thấy nó thú vị. Hết giờ rồi.
We're getting the students out of their classes. They're gonna run through. Sorry. Got it, got it, got it. Okay, no worries. We'll do that another time, yeah. Any questions for Karthik?
Sinh viên còn phải đi học lớp khác. Các em sẽ chạy đi. Xin lỗi. Hiểu rồi, hiểu rồi. Được, không sao. Để lần khác nhé. Có câu hỏi nào cho Karthik không?
And again, we posted on Piazza for their interest and things like that. They're two of my best students, master's student, undergrad, are currently at Ulibyte.
Và một lần nữa, chúng tôi đã đăng trên Piazza để các bạn quan tâm xem. Hai trong số những sinh viên giỏi nhất của tôi, một thạc sĩ, một đại học, hiện đang làm ở Ulibyte.
I had some of my best students do internships there and they've all been very happy. Okay? All right, let's give Karthik a round of applause. Thank you, man.
Một số sinh viên giỏi nhất của tôi đã thực tập ở đó và tất cả đều rất hài lòng. Được chứ? Nào, chúng ta hãy dành một tràng pháo tay cho Karthik. Cảm ơn anh.
Thank you so much for being here. All right. Have a good weekend. Remember, homework two is due on Sunday.
Cảm ơn anh rất nhiều vì đã đến đây. Được rồi. Chúc cuối tuần vui vẻ. Nhớ rằng bài tập về nhà 2 hạn nộp vào Chủ nhật.
Get the fortune, get the fortune, motherfuck the fame. Maintain, remember, stay flow with the grain. Get the fortune, motherfuck the fame, maintain, remember, stay flow with the grain.
Get the fortune, get the fortune, motherfuck the fame. Maintain, remember, stay flow with the grain. Get the fortune, motherfuck the fame, maintain, remember, stay flow with the grain.
Đă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.