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ả.
Welcome back to 162, everybody. I don't know if you're like me, it's pretty hard to turn away from the continuous state counts in the election, but let's get to some operating systems.
Chào mừng các bạn quay lại với CS 162. Không biết các bạn có giống tôi không, thật khó mà rời mắt khỏi việc cập nhật liên tục số phiếu theo từng bang trong cuộc bầu cử, nhưng chúng ta hãy quay lại với hệ điều hành.
We've been talking about how to actually store information on devices and give us the proper abstraction to files and directories and so on.
Chúng ta đã nói về cách thực sự lưu trữ thông tin trên các thiết bị và cung cấp cho ta một trừu tượng hóa phù hợp cho tệp và thư mục, v.v.
And we're gonna get much more into that today. We started by talking about devices and performance.
Và hôm nay chúng ta sẽ đi sâu hơn nhiều vào phần đó. Chúng ta bắt đầu bằng việc nói về thiết bị và hiệu năng.
So if you remember, one of the things that we talked about is how important it is to keep your overhead down. And so we talked about this particular graph of effective bandwidth.
Nếu còn nhớ, một trong những điều chúng ta đã nói là việc giữ chi phí phụ (overhead) ở mức thấp quan trọng đến mức nào. Và chúng ta đã xem đồ thị này về băng thông hiệu dụng.
And it said that even though we have a gigabit per second link, our effective bandwidth can be a lot lower.
Nó cho thấy rằng dù ta có đường truyền một gigabit mỗi giây, băng thông hiệu dụng của ta có thể thấp hơn rất nhiều.
And the reason is that there's this big overhead, for instance, a millisecond that affects our bandwidth.
Lý do là có một overhead lớn, chẳng hạn một mili giây, ảnh hưởng đến băng thông của ta.
So this graph kind of showed you the size of a packet along the x-axis and how long it takes to send it.
Đồ thị này cho bạn thấy kích thước gói tin trên trục x và thời gian cần để gửi nó.
And this is gonna be a linear graph with respect to the size of the packet, but it has an intercept that's not zero.
Đây sẽ là một đồ thị tuyến tính theo kích thước gói tin, nhưng có tung độ gốc khác không.
And so that means that the effective bandwidth, which is how much you actually get, how many bytes per unit time you actually get, is more like this red curve.
Và điều đó có nghĩa là băng thông hiệu dụng, tức là lượng bạn thực sự nhận được, số byte trên một đơn vị thời gian bạn thực sự nhận được, giống với đường cong màu đỏ này hơn.
And you have to get past a certain point before you can even get half of a gigabit per second.
Và bạn phải vượt qua một điểm nhất định thì mới có thể đạt được dù chỉ nửa gigabit mỗi giây.
Okay, and so when we look at our file systems coming up, we're gonna wanna make sure that we somehow keep the effective bandwidth as low, keep the effective bandwidth as close to the real bandwidth as possible.
Được rồi, vì vậy khi xét các hệ thống tệp sắp tới, chúng ta sẽ muốn đảm bảo rằng bằng cách nào đó giữ băng thông hiệu dụng ở mức thấp, giữ băng thông hiệu dụng càng gần băng thông thực càng tốt.
And that's gonna mean we have to keep our overhead low. The other thing we talked about in some detail last time was performance and queuing theory.
Và điều đó có nghĩa là ta phải giữ overhead ở mức thấp. Điều khác mà chúng ta đã nói khá chi tiết vào lần trước là hiệu năng và lý thuyết hàng đợi.
And I just wanted to remind you of what we came up with. So among other things, We talked about how there can be many examples of queues feeding into servers, okay?
Và tôi muốn nhắc lại những gì chúng ta đã rút ra. Vậy, trong số những điều khác, chúng ta đã nói rằng có thể có nhiều ví dụ về các hàng đợi đưa vào các máy chủ, đúng không?
And oftentimes you can take a much bigger system with lots of queues and lots of intermediate servers and boil it down to this, okay?
Và thường thì bạn có thể lấy một hệ thống lớn hơn nhiều với rất nhiều hàng đợi và rất nhiều máy chủ trung gian và rút gọn nó về dạng này, được chứ?
And boiling it down to this, we basically were talking about a system in equilibrium, among other things. And so this queue is neither growing nor shrinking without bound, probabilistically.
Và khi rút gọn về dạng này, về cơ bản chúng ta đang nói về một hệ thống ở trạng thái cân bằng, cùng với những điều khác. Và vì thế hàng đợi này, về mặt xác suất, không tăng cũng không giảm một cách vô hạn.
We have an arrival rate that's some lambda per unit time. And we have a service rate, which is mu.
Chúng ta có tốc độ đến là lambda trên một đơn vị thời gian. Và có tốc độ phục vụ là mu.
And by the way, mu can also be one over the average service time of the server, all right?
Nhân tiện, mu cũng có thể là một chia cho thời gian phục vụ trung bình của máy chủ, được chứ?
And so the different parameters we talked about are: lambda is the average, or mean, number of arriving customers per second. T-sir is the average time to service a customer.
Các tham số chúng ta đã nói đến là: lambda là số khách hàng đến trung bình, hay kỳ vọng, mỗi giây. T-sir là thời gian trung bình để phục vụ một khách hàng.
Sometimes that's called the mean or the M1 moment. We have C, which is this squared coefficient of variance. And that's the standard deviation squared over M1 squared. This is unitless.
Đôi khi đại lượng đó được gọi là trung bình hay moment bậc một, M1. Ta có C, là bình phương hệ số biến thiên. Và đó là độ lệch chuẩn bình phương chia cho M1 bình phương. Đại lượng này không có đơn vị.
And what's amazing about that is that our result, C, basically tells us all we need to know. We don't need to know how complicated the overall probability distribution was.
Và điều tuyệt vời ở đây là kết quả của chúng ta, C, về cơ bản cho ta biết tất cả những gì cần biết. Ta không cần biết toàn bộ phân phối xác suất phức tạp đến mức nào.
So this server is allowed to have an arbitrarily complicated service distribution. And we can compute the average service rate by taking one over that average time.
Vì vậy máy chủ này được phép có một phân phối thời gian phục vụ phức tạp tùy ý. Và ta tính được tốc độ phục vụ trung bình bằng cách lấy một chia cho thời gian trung bình đó.
Its arrival rate, however, is memoryless in our model. So we're keeping things very simple here.
Tuy nhiên, tốc độ đến trong mô hình của ta là không nhớ. Vậy là ở đây ta giữ mọi thứ rất đơn giản.
Computing from our parameters, so if we know the average time to serve, or the average time to get your hamburger at McDonald's, then one over that is mu, okay?
Tính từ các tham số của ta, nếu ta biết thời gian phục vụ trung bình, hay thời gian trung bình để nhận được chiếc hamburger ở McDonald's, thì một chia cho giá trị đó là mu, được chứ?
The server utilization is lambda over mu, or multiplying this out, lambda times T-sir. And the interesting thing we talked about is the fact that this server utilization can't be bigger than one.
Mức sử dụng máy chủ là lambda chia mu, hay nhân ra thì là lambda nhân T-sir. Và điều thú vị mà ta đã nói tới là việc mức sử dụng máy chủ này không thể lớn hơn một.
Can anybody remember why it can't be bigger than one? What happens if rho is greater than one?
Có ai nhớ vì sao nó không thể lớn hơn một không? Điều gì xảy ra nếu rho lớn hơn một?
What happens if rho is greater than one? Q grows without bound. Yep, that's a problem, okay?
Điều gì xảy ra nếu rho lớn hơn một? Q tăng lên không giới hạn. Đúng, đó là một vấn đề, được chứ?
So the parameters we might wish to compute, so if you notice here, these three red ones are enough to compute the green ones and pretty much everything else.
Vậy các tham số mà ta có thể muốn tính, nếu để ý ở đây, ba tham số màu đỏ này đủ để tính các tham số màu xanh lá và hầu như mọi thứ khác.
So if you have pretty much three out of these five, then you can compute the others.
Vậy nếu bạn có ba trong số năm tham số này, thì bạn có thể tính các tham số còn lại.
And notice, by the way, that C is talking about the standard deviation of the service time of the server, since this is a general, potentially a general probability distribution.
Và nhân tiện, lưu ý rằng C nói về độ lệch chuẩn của thời gian phục vụ của máy chủ, vì đây là một phân phối xác suất tổng quát, có thể là một phân phối xác suất tổng quát.
So parameters we might care about is how long are you in the queue? That's T sub Q. Or what's the length of the queue on average, okay?
Vậy tham số ta có thể quan tâm là bạn ở trong hàng đợi bao lâu? Đó là T chỉ số Q. Hoặc độ dài trung bình của hàng đợi là bao nhiêu, được chứ?
And using Little's law, which we talked about last time, that's lambda times TQ.
Và dùng định luật Little mà ta đã nói lần trước, đó là lambda nhân TQ.
And some results that matter here now are, for instance, if you have a memoryless arrival rate and a memoryless server rate, or an M/M/1 Q, then the time in the queue turns out to be the service time times rho over one minus rho.
Và một số kết quả quan trọng ở đây là, chẳng hạn, nếu bạn có tốc độ đến không nhớ và tốc độ phục vụ không nhớ, hay một hàng đợi M/M/1, thì thời gian trong hàng đợi hóa ra là thời gian phục vụ nhân rho chia một trừ rho.
And if you have a general distribution where it's not memoryless going out, then notice the difference between these two is very, it's very close.
Và nếu bạn có một phân phối tổng quát, không phải không nhớ ở đầu ra, thì để ý sự khác biệt giữa hai công thức này rất nhỏ, rất gần nhau.
It's still the service time times this extra factor of one half one plus C times rho over one minus rho.
Vẫn là thời gian phục vụ nhân thêm một thừa số một phần hai nhân một cộng C, nhân rho chia một trừ rho.
And the interesting question that we sort of confronted last time was, why is it that the service latency blows up?
Và câu hỏi thú vị mà lần trước ta đã gặp là, vì sao độ trễ phục vụ lại tăng vọt?
And the answer is, the simple answer is that all of these models come out with this rho over one minus rho factor.
Và câu trả lời, câu trả lời đơn giản là tất cả các mô hình này đều cho ra thừa số rho chia một trừ rho này.
So that as rho goes to one, this thing blows up to infinity.
Nên khi rho tiến tới một, đại lượng này tăng vọt đến vô cùng.
And so really this behavior that we're seeing here, potentially going to infinity if there's an infinite queue, is solely the fact of this rho over one minus rho.
Và vì thế hành vi mà ta đang thấy ở đây, có khả năng tiến tới vô cùng nếu hàng đợi là vô hạn, hoàn toàn là do thừa số rho trên một trừ rho này.
All right? So you should be able, I gave some examples at the end of the lecture last time. So I would say you might wanna remember them.
Được chứ? Vậy các em nên có thể, cuối bài giảng lần trước tôi đã đưa ra một vài ví dụ. Nên tôi nghĩ các em có thể muốn nhớ chúng.
This could be a useful thing for midterm three.
Điều này có thể hữu ích cho bài kiểm tra giữa kỳ số ba.
The important thing to keep in mind is, I would go through the last lecture to understand where these numbers, what these numbers mean, but the most important sort of back-of-the-envelope queuing theory results we've talked about in this class are these two: the M/M/1 queue and the M/G/1 queue.
Điều quan trọng cần nhớ là, các em nên xem lại bài giảng trước để hiểu những con số này là gì, chúng có ý nghĩa gì, nhưng những kết quả lý thuyết hàng đợi ước lượng nhanh quan trọng nhất mà chúng ta đã nói đến trong lớp này là hai kết quả sau: hàng đợi M/M/1 và hàng đợi M/G/1.
And the one, by the way, at the end just means there's a single queue, or a single server, excuse me.
Nhân tiện, số 1 ở cuối chỉ có nghĩa là chỉ có một hàng đợi, à nhầm, một máy phục vụ.
So we could have multiple servers and then the equations would be a little different, but if we were gonna do that to you, we'd give you the equation.
Vậy chúng ta có thể có nhiều máy phục vụ và khi đó các phương trình sẽ hơi khác, nhưng nếu ra đề cho các em như vậy, chúng tôi sẽ cho sẵn phương trình.
All right, any questions before I move on?
Được rồi, có câu hỏi nào trước khi tôi đi tiếp không?
So once you've got these equations, by the way, it's just a matter of plugging and playing.
Một khi đã có các phương trình này, thì nhân tiện, chỉ việc thay số vào là xong.
So you get some estimates of, if this is disk service rates, you might have estimates of how often requests come in from the user processes to the kernel.
Các em có một số ước lượng, chẳng hạn nếu đây là tốc độ phục vụ của đĩa, các em có thể có ước lượng về tần suất các yêu cầu đi từ các tiến trình người dùng đến kernel.
This queue might be queuing in the kernel.
Hàng đợi này có thể là hàng đợi trong kernel.
And this service rate has to do with the disk drive, which we gave you a way of computing how long it takes to do something with the disk.
Và tốc độ phục vụ này liên quan đến ổ đĩa, mà chúng ta đã đưa ra cách tính thời gian cần để thực hiện một thao tác với đĩa.
And so once you know some of these parameters, and you could make an estimate: is my queue gonna blow up? Or do I need another disk in order to get more service rate here?
Và khi đã biết một số tham số này, các em có thể ước lượng: hàng đợi của mình có bị tăng vọt không? Hay mình cần thêm một đĩa nữa để có tốc độ phục vụ cao hơn?
Okay, good.
Được rồi, tốt.
So we also talked about, a couple of lectures ago, a few ways of hiding I/O latency, which I wanted to just bring up because as we start designing file systems, you'll be able to start seeing where we can put some of these different options in here.
Chúng ta cũng đã nói, cách đây vài bài giảng, về một số cách che giấu độ trễ I/O, mà tôi muốn nhắc lại vì khi bắt đầu thiết kế hệ thống tệp, các em sẽ bắt đầu thấy có thể đặt những lựa chọn khác nhau này ở đâu.
So blocking interface, of course, is the one that you've learned from pretty much lecture number two or whatever, which says that I do a read and I say I wanna read so many bytes.
Giao diện chặn (blocking), dĩ nhiên, là giao diện mà các em đã học từ khoảng bài giảng số hai, tức là tôi gọi read và nói muốn đọc ngần này byte.
And what happens is the system call doesn't return until we have that number of bytes or until there's an end of file.
Và điều xảy ra là lời gọi hệ thống không trả về cho đến khi có đủ số byte đó hoặc cho đến khi gặp cuối tệp.
When we go to write, I'd say write these number of bytes and it won't return until they've all been written.
Khi ghi, tôi nói hãy ghi ngần này byte và nó sẽ không trả về cho đến khi tất cả đã được ghi.
Or if it does return, it'll at least tell us how many bytes have been written. Okay, and so that's a blocking interface.
Hoặc nếu có trả về, ít nhất nó cũng cho biết đã ghi được bao nhiêu byte. Được rồi, đó là giao diện chặn.
The other two I gave you a few lectures ago were the non-blocking and the asynchronous. The non-blocking interface basically says, do what you can immediately and then come back and tell me, don't wait.
Hai loại còn lại mà tôi đã giới thiệu cách đây vài bài giảng là không chặn (non-blocking) và bất đồng bộ (asynchronous). Giao diện không chặn về cơ bản nói rằng, hãy làm những gì có thể ngay lập tức rồi quay lại báo cho tôi, đừng chờ.
So the non-blocking interface may require you to process it in a loop, but you'll never be blocked waiting. The asynchronous interface is what I like to call the tell me later interface.
Vì vậy giao diện non-blocking có thể yêu cầu bạn xử lý nó trong một vòng lặp, nhưng bạn sẽ không bao giờ bị chặn để chờ. Giao diện bất đồng bộ là thứ tôi hay gọi là giao diện "lát nữa báo cho tôi".
This is an example where the user code hands a buffer to the kernel and says, well, do my read of 100 bytes and put it in this buffer.
Đây là ví dụ mà trong đó mã người dùng đưa một buffer cho kernel và nói rằng, hãy thực hiện việc đọc 100 byte của tôi và đặt vào buffer này.
And then it immediately returns from the kernel, but you get a signal later that says it's ready. Okay, and so those are kind of two asynchronous options.
Sau đó nó trả về ngay lập tức từ kernel, nhưng sau đó bạn nhận được một tín hiệu cho biết dữ liệu đã sẵn sàng. Được rồi, đó là hai lựa chọn bất đồng bộ.
And the reason they're interesting to bring up is pretty much in the kernel, the non-blocking and asynchronous interfaces are really what the devices provide. Okay, they don't provide blocking.
Lý do chúng đáng nhắc đến là vì hầu như trong kernel, các giao diện non-blocking và bất đồng bộ chính là những gì các thiết bị cung cấp. Các thiết bị không cung cấp blocking.
That's something that we give to the processes and it's an abstraction. Okay, so the asynchronous interface is exactly like a type of callback, yes.
Đó là thứ chúng ta trao cho các tiến trình, và nó là một sự trừu tượng hóa. Vâng, giao diện bất đồng bộ giống hệt một kiểu callback.
Okay, and if you're interested, you can often turn this on for file systems and other devices by using the IOCTL interface on the file descriptor after you've opened it.
Và nếu bạn quan tâm, bạn thường có thể bật nó cho hệ thống tệp và các thiết bị khác bằng cách dùng giao diện IOCTL trên file descriptor sau khi đã mở nó.
So that's a good question. Okay, so if you remember, we've had this kind of diagram almost from day one.
Đó là một câu hỏi hay. Được rồi, nếu còn nhớ, chúng ta đã có kiểu sơ đồ này gần như từ ngày đầu tiên.
We talked about, in lecture four even, we talked about a bunch of different ways of accessing files like streams and file descriptors, et cetera. So that's the fopen and versus open.
Ngay từ bài giảng bốn, chúng ta đã nói về nhiều cách khác nhau để truy cập tệp như stream và file descriptor, v.v. Đó là fopen so với open.
And then we've talked a bunch about devices over the last couple of lectures. And so today we're gonna talk about what's in the middle.
Rồi chúng ta đã nói khá nhiều về các thiết bị trong vài bài giảng vừa qua. Và hôm nay chúng ta sẽ nói về phần nằm ở giữa.
And what's in the middle is interesting because above we have this abstraction of byte streams. Okay, streams of bytes where we can ask for 12 bytes or 13 bytes or whatever.
Phần ở giữa này thú vị vì ở phía trên chúng ta có sự trừu tượng hóa là các byte stream. Tức là các dòng byte mà ta có thể yêu cầu 12 byte hay 13 byte hay bao nhiêu tùy ý.
Underneath, we know that there are blocks. Okay, we talked about disks having sectors or multiple sectors together giving you a block. And so that's not byte oriented, that's block oriented.
Còn bên dưới, chúng ta biết có các khối. Chúng ta đã nói về việc đĩa có các sector hoặc nhiều sector gộp lại tạo thành một khối. Vậy nó không hướng byte, mà hướng khối.
So somehow in the middle, the file system has to provide a matching between the blocks underneath and the streams above. And that's what the file system is gonna help us do.
Cho nên bằng cách nào đó ở giữa, hệ thống tệp phải cung cấp sự ánh xạ giữa các khối bên dưới và các stream bên trên. Và đó là điều hệ thống tệp sẽ giúp chúng ta làm.
Okay, and of course the things you're all used to with files, like looking them up in directories, opening them, closing them, writing them, all of that stuff needs this thing in red here to work properly.
Và tất nhiên, những thứ bạn quen thuộc với tệp, như tra cứu chúng trong thư mục, mở, đóng, ghi chúng, tất cả những thứ đó cần phần màu đỏ này để hoạt động đúng.
And so that's what our next couple of lectures are about. Okay, so how do we go from storage to file system?
Và đó là nội dung của vài bài giảng tiếp theo. Vậy làm thế nào để đi từ lưu trữ đến hệ thống tệp?
So up at the top level here, we have variable size buffers, and the API and syscalls that we're using are all about: give me this number of bytes, and maybe we set the offset, give me this number of bytes at some offset, or write these bytes at some offset.
Ở tầng trên cùng, chúng ta có các buffer kích thước thay đổi, và API cùng các syscall chúng ta dùng đều xoay quanh việc: cho tôi số byte này, và có thể ta đặt offset, cho tôi số byte này tại một offset nào đó, hoặc ghi các byte này tại một offset.
Underneath is the file system, which is a block based interface. And a typical block that we might talk about is four kilobytes.
Bên dưới là hệ thống tệp, một giao diện dựa trên khối. Và một khối điển hình mà chúng ta có thể nói đến là bốn kilobyte.
That's a pretty common block size, which you should recognize from when we were talking about virtual memory as well. The devices underneath mostly map to these blocks.
Đó là kích thước khối khá phổ biến, mà các bạn hẳn đã nhận ra từ lúc chúng ta nói về bộ nhớ ảo. Các thiết bị bên dưới hầu hết ánh xạ tới những khối này.
Okay, so underneath we have sectors, which are smaller than a block, but typically we put a bunch of sectors together on a track on a disk and we call that a block.
Được rồi, bên dưới chúng ta có các sector, nhỏ hơn một khối, nhưng thông thường ta gộp một loạt sector lại với nhau trên một track của đĩa và gọi đó là một khối.
And so the physical sector, being the minimum chunk of bytes that you could read or write, could be either 512 bytes, that's pretty standard, or, on the really big drives that we have these days, four kilobytes.
Còn sector vật lý, là đoạn byte nhỏ nhất mà bạn có thể đọc hoặc ghi, có thể là 512 byte, đó là kích thước khá chuẩn, hoặc, trên những ổ đĩa rất lớn ngày nay, là bốn kilobyte.
Okay, and so that's the basic chunk of bytes that you can read and write.
Được rồi, vậy đó là đoạn byte cơ bản mà bạn có thể đọc và ghi.
And so somehow, again, we're gonna have to go from this variable size up top through the block interface to the actual physical interface of the disk drive.
Và như vậy, một lần nữa, bằng cách nào đó chúng ta sẽ phải đi từ giao diện kích thước biến đổi ở trên, qua giao diện khối xuống giao diện vật lý thực sự của ổ đĩa.
And one of the things we're not gonna talk about today, but next time, is we wanna try to put some sort of caching in here or something to make this faster.
Và một điều chúng ta sẽ không nói hôm nay, mà để lần sau, là chúng ta muốn đặt một dạng caching nào đó vào đây hoặc thứ gì đó để làm cho nó nhanh hơn.
Okay, because I've sort of joked at various times this term that pretty much everything in operating systems is a cache.
Được rồi, vì trong học kỳ này tôi đã nhiều lần nói đùa rằng hầu như mọi thứ trong hệ điều hành đều là một cache.
Okay, and so obviously there's gonna be a cache somewhere here, but we're gonna deal with structure first and then we'll cache it later. And we also talked about SSDs or flash-based disk drives.
Được rồi, nên rõ ràng sẽ có một cache ở đâu đó quanh đây, nhưng chúng ta sẽ xử lý cấu trúc trước rồi sau đó mới thêm cache. Chúng ta cũng đã nói về SSD hay ổ đĩa dựa trên flash.
So one of the things that's different than just raw flash chips is when you put it into an SSD, this interface between the operating system through the device driver and the device has a lot of similarities between a disk drive and an SSD.
Một điều khác với các chip flash thô là khi đặt nó vào một SSD, giao diện giữa hệ điều hành, thông qua trình điều khiển thiết bị, và thiết bị có nhiều điểm tương đồng giữa ổ đĩa và SSD.
And in fact, there is a layer in there that makes that SSD look like spinning storage, except it doesn't have the seek time and the rotational time to slow you up.
Và thực tế, có một tầng ở trong đó làm cho SSD trông như bộ lưu trữ quay, ngoại trừ việc nó không có thời gian seek và thời gian quay làm bạn chậm lại.
Okay, and if you notice the other thing that's very unique about the SSD, which I mentioned, and if we get to something at the end of the lecture today, I'll show you again, is that this SSD, the blocks are things that can never be overwritten.
Được rồi, và nếu để ý, điều khác rất đặc biệt ở SSD, mà tôi đã đề cập, và nếu cuối bài giảng hôm nay còn thời gian, tôi sẽ cho bạn xem lại, là ở SSD này, các khối không bao giờ có thể bị ghi đè.
Okay, you have to take an erased block and write to it. You can't take a block you've already written to and change the bytes.
Được rồi, bạn phải lấy một khối đã xóa và ghi vào nó. Bạn không thể lấy một khối đã ghi rồi và thay đổi các byte.
What you have to do is, if you're gonna change a physical block, what you really have to do is find a new physical block, copy everything over except for what you wanna change.
Điều bạn phải làm là, nếu muốn thay đổi một khối vật lý, thì thực sự phải tìm một khối vật lý mới, sao chép mọi thứ sang, trừ phần bạn muốn thay đổi.
And then the previous block gets garbage collected. And the way that the operating system doesn't have to deal with that is this translation layer.
Và khối trước đó sẽ được thu gom rác. Và cách để hệ điều hành không phải xử lý chuyện đó là nhờ tầng dịch này.
And so the logical block numbers that the file system and the device driver think you're using are actually translated inside the SSD to the physical blocks on a flash memory.
Và như vậy các số khối logic mà hệ thống tập tin và trình điều khiển thiết bị nghĩ rằng đang dùng thực ra được dịch bên trong SSD sang các khối vật lý trên bộ nhớ flash.
And that translation layer in the firmware is responsible for making sure that things don't wear out, so that you're not overusing some particular physical block by writing it, erasing it, writing it, erasing it over and over again.
Và tầng dịch đó trong firmware chịu trách nhiệm bảo đảm rằng mọi thứ không bị mòn, để bạn không dùng quá mức một khối vật lý nào đó bằng cách ghi, xóa, ghi, xóa lặp đi lặp lại.
Instead, there's actually wear leveling firmware that makes sure that the SSD doesn't get overwritten.
Thay vào đó, thực sự có firmware cân bằng độ mòn bảo đảm SSD không bị ghi đè quá mức.
Okay, and so then the other thing that needs to be kept track of is a bunch of erasures that happens.
Được rồi, và như vậy điều khác cần được theo dõi là một loạt thao tác xóa xảy ra.
You actually have to work to make sure that you erase a bunch of blocks that aren't in use anymore so that you can have them ready to go.
Thực ra bạn phải làm việc để đảm bảo xóa một loạt khối không còn được sử dụng nữa, để chúng sẵn sàng cho lần dùng tiếp theo.
All right, and so that's a fundamentally different aspect from hard disk drives, where you can actually overwrite the sectors. Okay, but the interface is pretty much the same.
Được rồi, vậy đây là một điểm khác biệt căn bản so với ổ đĩa cứng, nơi bạn thực sự có thể ghi đè lên các sector. Nhưng giao diện thì gần như giống nhau.
It's dealing with four kilobyte blocks that are read and written. It's just the underlying physical thing's a little different, but we're popping up. Okay, so now there's a good question here.
Nó xử lý các khối bốn kilobyte được đọc và ghi. Chỉ là phần vật lý bên dưới hơi khác một chút, nhưng chúng ta đang đi lên các tầng trên. Được rồi, ở đây có một câu hỏi hay.
So if you overwrite a block with zeros to erase the file, is there any way to tell the SSD to actually erase it?
Nếu bạn ghi đè một khối bằng các số 0 để xóa tệp, thì có cách nào bảo SSD thực sự xóa nó không?
That's a really good question, and the answer is not always yes.
Đó là một câu hỏi rất hay, và câu trả lời là không phải lúc nào cũng được.
So modern, there are some SSDs that have the ability to encrypt things natively on the drive itself, and then you have a little more control over it.
Ngày nay có một số SSD có khả năng mã hóa dữ liệu ngay trên chính ổ đĩa, và khi đó bạn kiểm soát được nhiều hơn một chút.
But just because you write a bunch of zeros into block number 536 absolutely means nothing in terms of what actually happened to the data underneath, because you're writing to a completely new block.
Nhưng việc bạn ghi một loạt số 0 vào khối số 536 hoàn toàn không có ý nghĩa gì đối với những gì thực sự xảy ra với dữ liệu bên dưới, vì bạn đang ghi vào một khối hoàn toàn mới.
Okay, that's a good question. Now, oops, where am I here? Okay, so how do we build a file system? So what's a file system?
Được rồi, đó là một câu hỏi hay. Giờ thì, ôi, tôi đang ở đâu đây nhỉ? Được rồi, vậy làm thế nào để xây dựng một hệ thống tệp? Hệ thống tệp là gì?
A file system is a layer of the operating system that transforms the block interface of the disks into files or directories or things you're used to.
Hệ thống tệp là một tầng của hệ điều hành biến đổi giao diện khối của đĩa thành các tệp hay thư mục, những thứ mà bạn đã quen thuộc.
And so this is a classic operating system situation that you're very familiar with, hopefully, by now, been doing this all term, where you take a limited hardware interface, which is an array of blocks, and you provide a new virtualized interface that's much more convenient and provides, in this instance, a whole bunch of features like naming, so we can find files by name, not necessarily block numbers.
Đây là một tình huống hệ điều hành kinh điển mà bạn rất quen thuộc, hy vọng là đến giờ bạn đã làm việc này suốt cả học kỳ, trong đó bạn lấy một giao diện phần cứng hạn chế, tức là một mảng các khối, và cung cấp một giao diện ảo hóa mới tiện lợi hơn nhiều và trong trường hợp này có hàng loạt tính năng như đặt tên, để ta tìm tệp theo tên, không nhất thiết theo số khối.
We can organize the file names inside of directories. We can map files into blocks and figure out which blocks belong to which files.
Chúng ta có thể tổ chức các tên tệp bên trong các thư mục. Chúng ta có thể ánh xạ tệp vào các khối và xác định khối nào thuộc về tệp nào.
And then of course, things like protection and reliability are important things as well, which is we wanna enforce the access restrictions to prevent unauthorized parties from reading and writing files that they're not supposed to, and reliability.
Và tất nhiên, những thứ như bảo vệ và độ tin cậy cũng là những điều quan trọng, nghĩa là chúng ta muốn thực thi các hạn chế truy cập để ngăn các bên không được phép đọc và ghi những tệp mà họ không được phép, và độ tin cậy.
We're gonna wanna put some level of redundancy into the system to make sure we don't lose our data even though we have crashes and hardware failures, et cetera.
Chúng ta sẽ muốn đưa một mức dư thừa nào đó vào hệ thống để đảm bảo không mất dữ liệu dù có sự cố treo máy và hỏng phần cứng, v.v.
Okay, so this level of abstracting is really what the file system's about.
Được rồi, tầng trừu tượng hóa này chính là bản chất của hệ thống tệp.
And I'm gonna give you a number of actual case studies to show you how people have done that in several file systems that are currently actively used.
Và tôi sẽ đưa ra một số nghiên cứu điển hình thực tế để cho bạn thấy người ta đã làm điều đó thế nào trong một số hệ thống tệp đang được sử dụng tích cực hiện nay.
So again, what we just said a little bit ago, but I wanted to repeat this, is the user's view of files is that they're durable data structures that you put the data in and it doesn't go away.
Vậy nhắc lại điều chúng ta vừa nói ít phút trước, nhưng tôi muốn lặp lại, là góc nhìn của người dùng về tệp: chúng là các cấu trúc dữ liệu bền vững mà bạn đưa dữ liệu vào và nó không biến mất.
The system's view, of course, is that it's a collection of bytes. That's the Unix view at the system call level. And it doesn't really matter what data structures you put in the disk.
Còn góc nhìn của hệ thống, tất nhiên, là một tập hợp các byte. Đó là góc nhìn của Unix ở mức lời gọi hệ thống. Và thực ra cấu trúc dữ liệu nào bạn đặt trên đĩa cũng không quan trọng.
So the interesting thing is the user only really knows how to interpret the bytes. Unix makes no restrictions on how you structure those bytes. It's entirely up to you.
Điều thú vị là chỉ người dùng mới thật sự biết cách diễn giải các byte. Unix không đặt ra hạn chế nào về cách bạn tổ chức các byte đó. Hoàn toàn do bạn quyết định.
So from the system's point of view, it's a bag of bytes.
Vì vậy, theo góc nhìn của hệ thống, nó chỉ là một túi byte.
And then when you get underneath the system call interface and into the actual file system and so on, and caching system, the system's view then underneath there becomes a collection of blocks, because the block is the logical transfer unit.
Còn khi đi xuống bên dưới giao diện lời gọi hệ thống và vào hệ thống tệp thực sự, cùng hệ thống bộ đệm, thì góc nhìn của hệ thống ở dưới đó trở thành một tập hợp các khối, vì khối là đơn vị truyền logic.
And the block size typically is bigger than the sector size, where the sector is the physical transfer unit. That's the minimum transfer unit on the disk.
Và kích thước khối thường lớn hơn kích thước sector, trong đó sector là đơn vị truyền vật lý. Đó là đơn vị truyền nhỏ nhất trên đĩa.
We bring it into blocks because typically, like, the sector is 512 bytes, it's just too small.
Chúng ta gom thành khối vì thông thường, sector chỉ có 512 byte, như vậy là quá nhỏ.
And so we turn a bunch of sectors into a block, and that's what we read and write off of the disk.
Nên ta gộp nhiều sector thành một khối, và đó là đơn vị ta đọc và ghi trên đĩa.
So you can kind of look at this. Here's the user. They have a file full of bytes. They talk to the file system. The file system talks to the disk.
Bạn có thể hình dung thế này. Đây là người dùng. Họ có một tệp chứa đầy các byte. Họ làm việc với hệ thống tệp. Hệ thống tệp làm việc với đĩa.
And when all is said and done, the user thinks they have files that are a bunch of bytes. So that's our goal.
Và rốt cuộc, người dùng nghĩ rằng họ có các tệp là một dãy byte. Đó là mục tiêu của chúng ta.
So just to hammer this home a little bit, what happens if the user says, "Give me bytes two through 12"?
Để nhấn mạnh thêm một chút, điều gì xảy ra nếu người dùng nói: "Cho tôi các byte từ 2 đến 12"?
Well, what happens is the file system has to fetch the block that has those bytes in it.
Thì hệ thống tệp phải lấy về khối chứa những byte đó.
So that block might be on disk, in which case it's got to pull it in to a cache.
Khối đó có thể nằm trên đĩa, khi đó nó phải được nạp vào bộ đệm.
And then since that's probably 400, excuse me, since that's probably four kilobytes, it has to figure out where bytes two through 12 are, package them up into the user's buffer and return it.
Và vì khối đó có lẽ là 400, xin lỗi, vì có lẽ là bốn kilobyte, nó phải xác định vị trí các byte từ 2 đến 12, đóng gói chúng vào bộ đệm của người dùng rồi trả về.
Now it's quite possible that if this is the second time we asked for, you know, when we go to ask for bytes 13 through 36, maybe that block's already in the cache and we don't actually have to go out to the disk.
Rất có thể nếu đây là lần thứ hai chúng ta yêu cầu, khi ta yêu cầu các byte từ 13 đến 36, thì khối đó có thể đã nằm sẵn trong bộ đệm và ta không thực sự phải truy cập đĩa.
Now, it's an interesting question here. What if you have multiple files with different permissions in the same block? So the answer is that doesn't really happen.
Bây giờ có một câu hỏi thú vị. Nếu có nhiều tệp với quyền truy cập khác nhau nằm trong cùng một khối thì sao? Câu trả lời là điều đó thực ra không xảy ra.
That's a bit of a failure of the file system because right now the file system provides a one-to-one mapping between files and underlying blocks.
Đó phần nào là một hạn chế của hệ thống tệp vì hiện nay hệ thống tệp cung cấp một ánh xạ một-một giữa các tệp và các khối bên dưới.
So the permissions are on the files, not on the individual blocks, because the blocks are assembled into files and the metadata for permissions are actually in the inode, which I'll show you in a little bit, okay?
Vì vậy quyền truy cập được đặt trên các tệp, không phải trên từng khối, vì các khối được ghép lại thành tệp và siêu dữ liệu về quyền truy cập thực ra nằm trong inode, mà lát nữa tôi sẽ cho các bạn xem, được chứ?
Good question though. So what happens if we go to write bytes two through 12? This is a little trickier and I wanted to make sure this is clear.
Câu hỏi hay đấy. Vậy điều gì xảy ra nếu ta ghi các byte từ 2 đến 12? Phần này phức tạp hơn một chút và tôi muốn đảm bảo là nó rõ ràng.
So you have to actually, since you can only deal with blocks at the disk level, you have to pull your block in, overwrite bytes two through 12, and then write it back out before you can modify bytes two through 12.
Thế nên thực ra bạn phải, vì ở cấp độ đĩa, bạn chỉ có thể làm việc với các khối, bạn phải đưa khối đó vào bộ nhớ, ghi đè các byte từ 2 đến 12, rồi ghi nó ngược ra đĩa thì mới sửa được các byte từ 2 đến 12.
You can't actually go in here and only write a few bytes on the disk, okay? It's just not possible.
Bạn không thể thực sự vào đây và chỉ ghi vài byte lên đĩa, được chứ? Điều đó đơn giản là không thể.
So we have to make sure that we, you can start to see why having blocks stored in RAM, at least temporarily, is gonna be really important, because at minimum, we're gonna need to bring a block in, overwrite a couple of bytes, and store it back out.
Vì vậy chúng ta phải đảm bảo rằng chúng ta, bạn có thể bắt đầu thấy tại sao việc lưu các khối trong RAM, ít nhất là tạm thời, lại cực kỳ quan trọng, vì tối thiểu, chúng ta cần đưa một khối vào, ghi đè vài byte, rồi lưu nó ngược ra đĩa.
We're gonna do much better than that when we get to the block cache, but we're not there yet. And of course, everything inside the file system itself is in terms of whole size blocks.
Chúng ta sẽ làm tốt hơn thế nhiều khi nói đến block cache, nhưng bây giờ chúng ta chưa tới đó. Và tất nhiên, mọi thứ bên trong bản thân hệ thống tệp đều tính theo các khối có kích thước đầy đủ.
The actual IO happens in blocks, and any reading and writing of something smaller has to happen across this file system interface, okay?
Thao tác IO thực sự diễn ra theo khối, và mọi việc đọc và ghi những đơn vị nhỏ hơn đều phải diễn ra qua giao diện hệ thống tệp này, được chứ?
Now, so how do we manage a disk?
Vậy, chúng ta quản lý một đĩa như thế nào?
So we're gonna, in the next, I don't know, I'm gonna say half an hour or whatever, we're gonna talk specifically about disk drives, but we're gonna generalize some ideas about how do we manage a disk.
Trong phần tiếp theo, tôi không rõ, cứ cho là khoảng nửa giờ, chúng ta sẽ nói cụ thể về ổ đĩa, nhưng chúng ta sẽ khái quát hóa một số ý tưởng về cách quản lý một đĩa.
So basic entities on a disk that we're gonna wanna have is we're gonna wanna be able to have files and directories.
Các thực thể cơ bản trên đĩa mà chúng ta muốn có là tệp và thư mục.
Okay, so a file is a user visible group of blocks arranged in some logical space, or what I like to say is a bag of bytes.
Được rồi, một tệp là một nhóm các khối hiển thị với người dùng, được sắp xếp trong một không gian logic nào đó, hay tôi thích gọi là một túi các byte.
A directory is a user usable, excuse me, a directory is a user visible index mapping names to files.
Một thư mục là một chỉ mục dùng được cho người dùng, xin lỗi, một thư mục là một chỉ mục hiển thị với người dùng, ánh xạ tên tới các tệp.
So we're gonna have to figure out how to do that so that we can turn a file name into something that's a file, okay?
Vì vậy chúng ta sẽ phải tìm cách làm điều đó để có thể biến một tên tệp thành một tệp thực sự, được chứ?
And so that's gonna be part of what the file system does. So the disk is a linear array of sectors. And so how do you identify those sectors?
Và đó sẽ là một phần việc của hệ thống tệp. Đĩa là một mảng tuyến tính các sector. Vậy làm thế nào để xác định các sector đó?
Well, there's a couple of ways to do that.
Có một vài cách để làm điều đó.
One, which was kind of in the original disks before they got too big, a sector was really just a vector of which cylinder, surface, and sector it's on.
Một cách, vốn có từ những chiếc đĩa ban đầu trước khi chúng trở nên quá lớn, một sector thực chất chỉ là một vectơ gồm cylinder, surface và sector mà nó nằm trên.
So if you remember, a cylinder is all of the tracks that are on top of each other, and it really represents the positioning of the head assembly.
Nếu bạn còn nhớ, một cylinder là tất cả các track nằm chồng lên nhau, và nó thực sự biểu diễn vị trí của cụm đầu đọc.
The surface is which one, top or bottom, and which platter. So that's which surface you're on, and then which sector.
Surface cho biết mặt nào, trên hay dưới, và đĩa từ nào. Đó là bạn đang ở surface nào, rồi đến sector nào.
So the sector itself is a three tuple here defining where that thing is on the disk. It's not really used anymore.
Như vậy bản thân sector ở đây là một bộ ba xác định vị trí của nó trên đĩa. Cách này giờ không còn được dùng nữa.
And one of the reasons was things got so big that the BIOSes weren't able to keep up with it.
Và một trong những lý do là đĩa trở nên quá lớn đến mức BIOS không theo kịp.
And in this instance, the OS slash BIOS, which is lower level in the OS, had to deal with bad sectors, and the disk just got so big that it wasn't working anymore.
Và trong trường hợp này, OS/BIOS, tầng thấp hơn trong OS, phải xử lý các sector hỏng, và đĩa trở nên lớn đến mức cách này không còn hoạt động được nữa.
So at some point, we switched over to the logical block addressing, where every sector has an integer address starting from one and working its way up to the size of the disk.
Vì vậy đến một lúc nào đó, chúng ta chuyển sang logical block addressing, trong đó mỗi sector có một địa chỉ số nguyên bắt đầu từ một và tăng dần lên đến kích thước của đĩa.
And the controller does a mapping from the integer number to a physical position and shields the OS from the structure of the disk.
Và bộ điều khiển thực hiện ánh xạ từ số nguyên đó sang một vị trí vật lý và che chắn hệ điều hành khỏi cấu trúc của đĩa.
So the SSDs don't actually expose the cylinder, surface, sector interface either. So that was a good question in the chat.
Vì vậy SSD thực ra cũng không cung cấp giao diện cylinder, surface, sector. Đó là một câu hỏi hay trong khung chat.
Pretty much this logical block addressing is what had pretty much taken hold before SSDs were really very popular.
Về cơ bản, logical block addressing này đã trở nên phổ biến trước khi SSD thực sự được dùng rộng rãi.
So pretty much the SSDs are giving you this LBA level of an interface, which is a logical ordering of blocks from one to N.
Nên về cơ bản SSD cung cấp cho bạn giao diện mức LBA này, tức là một thứ tự logic của các block từ 1 đến N.
Now, this has some consequences.
Điều này có một số hệ quả.
So if you recall from last lecture, we talked a bit about elevator algorithms to basically take a bunch of requests and rearrange them so that the disk would do a nice clean sweep rather than randomly going all over the place.
Nếu còn nhớ từ bài giảng trước, chúng ta đã nói một chút về các thuật toán thang máy, về cơ bản là nhận một loạt yêu cầu và sắp xếp lại để đĩa quét một lượt gọn gàng thay vì nhảy lung tung khắp nơi.
Once you have logical block addresses, now you're only really guessing that somehow blocks that are next to each other are close to each other and in the same track.
Khi đã có địa chỉ block logic, bạn thực sự chỉ đang đoán rằng bằng cách nào đó các block nằm cạnh nhau thì ở gần nhau và trên cùng một track.
You don't quite have the same level of information that you had before, but operating systems still try to do a job of optimizing for locality.
Bạn không còn có cùng mức thông tin như trước, nhưng hệ điều hành vẫn cố gắng tối ưu cho tính cục bộ.
It's just not quite as precise as it was back in the days with physical positioning that was cylinder surface sector. Now, what does a file system really need to work?
Chỉ là nó không còn chính xác như ngày xưa với định vị vật lý theo cylinder, surface, sector. Vậy hệ thống tệp thực sự cần gì để hoạt động?
Well, it has to track which disk blocks are free. And in the case of the SSD, it's also tracking which blocks, and I say that in quotes, are free.
Nó phải theo dõi những block nào của đĩa còn trống. Và với SSD, nó cũng theo dõi những block nào mà tôi nói trong dấu ngoặc kép, là còn trống.
It's just, it knows the logical block number.
Chỉ là nó biết số block logic.
It doesn't really know what physical part of the flash chips are storing that, but it has a notion that there are these blocks and some of them are free and some aren't.
Nó không thực sự biết phần vật lý nào của chip flash đang lưu dữ liệu đó, nhưng nó có khái niệm rằng có những block này và một số còn trống, một số thì không.
So it's still doing that same idea, which is tracking the disk blocks. And you need to know that so that you can know where to put your newly written data.
Nên nó vẫn làm cùng một việc, đó là theo dõi các block của đĩa. Và bạn cần biết điều đó để biết nơi đặt dữ liệu mới ghi.
You need to track which blocks contain data for which files.
Bạn cần theo dõi block nào chứa dữ liệu của tệp nào.
Okay, so that when you go to open a file and you start reading from bytes two through 12, first thing you gotta figure out is where is the first block of that file?
Được rồi, để khi bạn mở một tệp và bắt đầu đọc từ byte thứ hai đến 12, việc đầu tiên bạn phải tìm ra là block đầu tiên của tệp đó ở đâu?
Well, it's on disk somewhere. How do you know which one it is? Well, that's the file system's problem, Right?
Nó nằm đâu đó trên đĩa. Làm sao biết là block nào? Đó là vấn đề của hệ thống tệp, đúng không?
It also has to track files in a directory so that you can look them up by file name. Okay, again, that's the file system's problem. And where do you put all this?
Nó cũng phải theo dõi các tệp trong một thư mục để bạn có thể tra cứu theo tên tệp. Được rồi, một lần nữa, đó là vấn đề của hệ thống tệp. Và bạn đặt tất cả những thứ này ở đâu?
Well, since we need to be able to shut the whole system down and come back and our data is still there, all of this stuff has to be on disk somewhere.
Vì chúng ta cần có thể tắt toàn bộ hệ thống rồi quay lại mà dữ liệu vẫn còn đó, nên tất cả những thứ này phải nằm đâu đó trên đĩa.
So not only does the disk hold all the data, but it's gotta hold all this metadata in a way that we can start from scratch once we turn the file system, once we turn the operating system on and reboot the machine.
Vậy đĩa không chỉ chứa toàn bộ dữ liệu, mà còn phải chứa toàn bộ siêu dữ liệu này theo cách để chúng ta có thể bắt đầu lại từ đầu khi bật hệ thống tệp, khi bật hệ điều hành và khởi động lại máy.
So we are, you could say there's a little bit of a recursive issue here, but somehow the information that's tracking the files, we need to put that information also on disk, possibly in a file.
Có thể nói ở đây có một vấn đề hơi đệ quy, nhưng bằng cách nào đó, thông tin theo dõi các tệp, thì chúng ta cũng cần lưu thông tin đó trên đĩa, có thể là trong một tệp.
And so if you are tracking that, you can see that perhaps there's something about standard positions for the root file system or something like that, and we'll talk about that in a moment.
Và nếu bạn đang theo dõi điều đó, bạn có thể thấy rằng có lẽ cần có những vị trí chuẩn nào đó cho hệ thống tệp gốc hay đại loại như vậy, và lát nữa chúng ta sẽ nói về điều này.
All right, questions?
Được rồi, có câu hỏi nào không?
Okay, you guys with me so far?
Được, các bạn theo kịp đến đây chứ?
Now, what's the story with putting data structures on disk? It's a bit different than data structures in memory.
Bây giờ, việc đặt cấu trúc dữ liệu lên đĩa thì có gì đặc biệt? Nó hơi khác so với cấu trúc dữ liệu trong bộ nhớ.
So in memory, I could have pointers to things that are arbitrary byte pointers, and I can do linked lists and stuff.
Trong bộ nhớ, tôi có thể có các con trỏ trỏ tới những byte tùy ý, và tôi có thể làm danh sách liên kết và những thứ tương tự.
The ideas there are the same, except that the data structures have to be made out of these minimum quanta of blocks. And that kind of changes what data structures we use a little bit.
Các ý tưởng ở đó vẫn như vậy, ngoại trừ việc các cấu trúc dữ liệu phải được tạo nên từ những khối là đơn vị nhỏ nhất này. Và điều đó làm thay đổi đôi chút các cấu trúc dữ liệu mà chúng ta dùng.
And it turns out once we start worrying about performance, we're also gonna be very careful about which blocks are next to each other on the disk, because we're gonna wanna try to keep them next to each other in the file as well, because that'll give us better performance.
Và hóa ra, một khi bắt đầu lo về hiệu năng, chúng ta cũng sẽ phải rất cẩn thận về việc những khối nào nằm cạnh nhau trên đĩa, vì chúng ta sẽ muốn giữ chúng nằm cạnh nhau cả trong tệp, bởi điều đó sẽ cho hiệu năng tốt hơn.
So the other thing is we can only access one block at a time, So you can't really efficiently read or write a single word; we already said that.
Một điều nữa là chúng ta chỉ có thể truy cập một khối tại một thời điểm, nên thực sự không thể đọc hay ghi một từ đơn lẻ một cách hiệu quả; chúng ta đã nói điều này rồi.
You have to read or write the whole block containing it. And ideally, you want sequential access patterns where you sort of write a bunch of stuff along a track on the disk.
Bạn phải đọc hoặc ghi cả khối chứa nó. Và lý tưởng nhất, bạn muốn các mẫu truy cập tuần tự, trong đó bạn ghi một loạt dữ liệu dọc theo một rãnh trên đĩa.
And you can imagine that with SSDs, as I've told you, every time you go to write something, you actually have to allocate a brand new erased block under the covers and use that to do your overwriting.
Và bạn có thể hình dung rằng với SSD, như tôi đã nói, mỗi lần bạn ghi một thứ gì đó, thực ra bạn phải cấp phát một khối mới tinh đã được xóa ở bên dưới và dùng nó để thực hiện việc ghi đè.
And so part of this has to do with being careful about how much erasing and reallocating you're asking the Flash translation unit to do.
Vì vậy một phần của vấn đề là phải cẩn thận xem bạn yêu cầu Flash translation unit xóa và cấp phát lại bao nhiêu.
And so Flash-aware file systems are a little bit careful about when they even decide to read and write blocks.
Do đó các hệ thống tệp nhận biết Flash khá cẩn thận về việc khi nào mới quyết định đọc và ghi các khối.
And if we get to that at the very end of the lecture, I'll tell you a little bit about F2FS, which is one of the Flash file systems that's in use these days.
Và nếu chúng ta kịp nói đến điều đó ở cuối bài giảng, tôi sẽ nói sơ qua về F2FS, một trong những hệ thống tệp Flash đang được sử dụng ngày nay.
So now the other thing to start thinking about is, when you go to write something on disk, it takes a little while to get there.
Còn một điều nữa bắt đầu cần nghĩ tới là, khi bạn ghi một thứ gì đó lên đĩa, phải mất một lúc nó mới tới nơi.
And furthermore, if we have these data structures that are on disk and they have to look a certain way, there's some consistency in those data structures.
Hơn nữa, nếu chúng ta có những cấu trúc dữ liệu nằm trên đĩa và chúng phải có dạng nhất định, thì các cấu trúc dữ liệu đó cần có tính nhất quán.
Ideally, when we go to shut the whole system down and turn it off, the disk is in a completely meaningful, consistent state.
Lý tưởng nhất, khi chúng ta tắt toàn bộ hệ thống, đĩa ở trong trạng thái hoàn toàn có ý nghĩa và nhất quán.
And I don't know if any of you have ever lost data because your machine crashed at the wrong time. I'm sure there are many of you.
Và tôi không biết có bạn nào từng mất dữ liệu vì máy bị sập vào đúng lúc không may hay không. Tôi chắc là có nhiều bạn rồi.
Then you'll know that the file system doesn't always shut down in a clean state.
Vậy thì bạn sẽ biết rằng hệ thống tệp không phải lúc nào cũng tắt ở trạng thái sạch.
And so although we won't get to this this time, next time we're definitely gonna start talking a bit about journaling and some of the other techniques for making sure that data is never lost, even when we have sudden shutdowns.
Và dù lần này chúng ta sẽ không kịp nói tới, lần sau chúng ta chắc chắn sẽ bắt đầu nói đôi chút về journaling và một số kỹ thuật khác để đảm bảo dữ liệu không bao giờ bị mất, ngay cả khi hệ thống bị tắt đột ngột.
Okay, so that's gonna be important. Okay, now, that's me. I don't have a lot of administrivia. We're almost, almost, almost done grading.
Được rồi, điều đó sẽ rất quan trọng. Được rồi, phần đó là của tôi. Tôi không có nhiều thông báo hành chính. Chúng tôi sắp chấm xong rồi, gần xong rồi.
So I feel almost like I'm talking about counting votes in the current election. We're getting there, it's gonna happen. And so you'll know as soon as we're ready.
Tôi có cảm giác như đang nói về việc kiểm phiếu trong cuộc bầu cử hiện nay vậy. Sắp xong rồi, sẽ có thôi. Và các bạn sẽ biết ngay khi chúng tôi sẵn sàng.
The other thing is, and I think everybody's probably done this, but make sure to fill out the post-midterm survey. Let us know what we're doing, how we can improve.
Một điều nữa, và tôi nghĩ có lẽ ai cũng đã làm rồi, là hãy nhớ điền khảo sát sau giữa kỳ. Hãy cho chúng tôi biết chúng tôi đang làm thế nào và cần cải thiện ra sao.
And the other thing, which I'm not sure we put into the survey, but you're welcome to forward to me individually, is if there are any particular topics you'd like to talk about in the last lecture or two, let me know, and I might throw together an interesting lecture with topics that were requested by people.
Và một điều nữa, mà tôi không chắc chúng tôi đã đưa vào khảo sát hay chưa, nhưng các bạn cứ gửi riêng cho tôi cũng được, là nếu có chủ đề cụ thể nào mà các bạn muốn nói đến trong một hai bài giảng cuối, hãy cho tôi biết, và tôi có thể soạn một bài giảng thú vị với những chủ đề do mọi người đề nghị.
So feel free to take advantage of that.
Vì vậy cứ thoải mái tận dụng nhé.
I've actually had people ask me about things like quantum computing, which is not really 162, but I'm more than happy to talk about things as long as I can say something meaningful about it.
Thực ra đã có người hỏi tôi về những thứ như điện toán lượng tử, cái này không thực sự thuộc 162, nhưng tôi rất sẵn lòng nói về bất cứ điều gì miễn là tôi có thể nói được điều gì đó có ý nghĩa.
Yes, I would say that the results of the midterm grading just is gonna be far less contentious than the results of the election, we shall see.
Vâng, tôi nghĩ kết quả chấm điểm giữa kỳ sẽ ít gây tranh cãi hơn nhiều so với kết quả cuộc bầu cử, chúng ta sẽ xem.
But as you have seen, for those of you that are watching the counting of the election, slow and steady is the name of the game.
Nhưng như các bạn đã thấy, với những bạn đang theo dõi việc kiểm phiếu bầu cử, chậm mà chắc là nguyên tắc của cuộc chơi.
So this is all about taking a breath, which is good. Breathing is good, by the way, too.
Nên tất cả là để hít một hơi thật sâu, thế là tốt. Nhân tiện, hít thở cũng tốt.
The other thing I wanted to point out is if you have any group issues going on, whatever, make sure your TA knows about this. Make sure you reflect those issues in your group evaluations.
Một điều nữa tôi muốn nhắc là nếu nhóm của bạn có vấn đề gì, dù là gì đi nữa, hãy đảm bảo trợ giảng của bạn biết. Hãy phản ánh những vấn đề đó trong bản đánh giá nhóm của các bạn.
Give us some good feedback because we will take all of these things into account at the end of the term. So I don't think there's anything else to say about administrivia.
Hãy cho chúng tôi phản hồi tốt vì chúng tôi sẽ xem xét tất cả những điều này vào cuối học kỳ. Tôi nghĩ không còn gì khác để nói về thông báo hành chính.
I think that's pretty much what I had to say. So I think we're good to go unless anybody had any questions. The term is kind of winding down.
Tôi nghĩ đó là hầu hết những gì tôi muốn nói. Vậy chúng ta có thể bắt đầu, trừ khi ai có câu hỏi. Học kỳ đang dần khép lại.
We're down to like the last maybe six or seven lectures. Sometimes I do my special lecture into RRR week. We might do that, but we're getting down to the last few. So, okay.
Chúng ta chỉ còn khoảng sáu hoặc bảy bài giảng cuối. Đôi khi tôi giảng bài đặc biệt vào tuần RRR. Có thể chúng ta sẽ làm vậy, nhưng chúng ta sắp đến những bài cuối rồi. Được rồi.
No more questions. So let's talk about designing file systems. So what are some critical factors? Well, clearly performance.
Không còn câu hỏi. Vậy hãy nói về thiết kế hệ thống tệp. Vậy đâu là một số yếu tố then chốt? Rõ ràng là hiệu năng.
Okay, and hard disks are a good example of trying to get performance out of a less than ideal device from a performance standpoint.
Được rồi, và đĩa cứng là một ví dụ điển hình của việc cố lấy hiệu năng từ một thiết bị không lý tưởng xét về mặt hiệu năng.
Because if you have to seek and then you have to wait for rotational latency and then you can read, that's gonna take a long time.
Bởi vì nếu bạn phải seek, rồi phải chờ độ trễ quay, rồi mới đọc được, thì sẽ mất rất nhiều thời gian.
And I showed you several examples a couple of lectures ago which showed you the difference between if you have to seek, your total bandwidth goes way down, versus if you don't have to seek, your bandwidth is much higher.
Và tôi đã cho các bạn xem vài ví dụ cách đây vài bài giảng cho thấy sự khác biệt khi bạn phải seek, tổng băng thông của bạn giảm xuống rất nhiều, so với khi không phải seek, băng thông của bạn cao hơn nhiều.
And so we're gonna wanna do a good job of the same thing in our file system. So that's gonna be important, okay? And this, by the way, is hard to get right.
Và vì vậy chúng ta sẽ muốn làm tốt điều tương tự trong hệ thống tệp của mình. Điều đó sẽ rất quan trọng, được chứ? Và nhân tiện, điều này rất khó làm đúng.
What's great about this, by the way, just to put one more point on this, is when you get to SSDs, then randomly writing things in your logical block space or reading from it is no longer a performance issue, because every block pretty much, it takes about the same amount of time to read.
Nhân tiện, điều tuyệt vời ở đây là xin nói thêm một điểm nữa, khi bạn chuyển sang SSD, thì việc ghi ngẫu nhiên vào không gian khối logic của bạn hay đọc từ nó không còn là vấn đề về hiệu năng nữa, vì gần như mọi khối đều mất khoảng thời gian đọc như nhau.
And so some of the optimizations for disk drives are less required in SSDs.
Và vì thế một số tối ưu hóa cho ổ đĩa ít cần thiết hơn trong SSD.
Now, other things that really just feed into the Unix view of the world is that we always have to do open before reading and writing.
Bây giờ, những điều khác phản ánh đúng quan điểm của Unix về thế giới là chúng ta luôn phải gọi open trước khi đọc và ghi.
So, you just think about that: you do an open syscall and then you get the file descriptor back and then you can do reads and writes.
Vậy hãy nghĩ về điều đó: bạn gọi syscall open rồi nhận lại file descriptor, sau đó bạn có thể đọc và ghi.
What's good about that model is you can perform protection checks on open, figure out where the file resources are in advance, and then from that point on, you're really just accessing the blocks directly.
Điểm tốt của mô hình này là bạn có thể kiểm tra quyền bảo vệ khi open, xác định trước các tài nguyên của tệp nằm ở đâu, và từ đó trở đi, bạn thực sự chỉ truy cập trực tiếp các khối.
And this fits in a little bit earlier, there was a question about what if you had different permissions on the block from different people.
Điều này liên quan đến một câu hỏi lúc nãy, có bạn hỏi nếu có các quyền khác nhau trên khối đối với những người khác nhau thì sao.
They just don't do that in these typical file systems. Okay? All of the permissions are attached to the file as a whole.
Các hệ thống tệp thông thường này không làm như vậy. Được chứ? Mọi quyền đều gắn với toàn bộ tệp.
Now, in the last couple of lectures, we're gonna expand quite a bit, where we start talking about file systems that might actually span the globe.
Bây giờ, trong vài bài giảng cuối, chúng ta sẽ mở rộng khá nhiều, khi bắt đầu nói về các hệ thống tệp có thể trải rộng khắp toàn cầu.
In that, excuse me, in that instance, you can't necessarily trust that the permissions that have been checked on open are gonna be kept when you're talking to data that's being stored somewhere in Antarctica or wherever it happens to be.
Trong trường hợp đó, xin lỗi, bạn không nhất thiết có thể tin rằng các quyền đã được kiểm tra khi open sẽ được giữ nguyên khi bạn làm việc với dữ liệu được lưu ở đâu đó tại Nam Cực hoặc bất cứ nơi nào.
And so we might have to adapt slightly different behavior once we get there, okay? Excuse me.
Và vì vậy chúng ta có thể phải áp dụng cách hành xử hơi khác khi đến đó, được chứ? Xin lỗi.
So, the other thing is kind of a side effect of Unix, which is the size of the file is determined as you use it.
Còn một điều nữa là một tác dụng phụ của Unix, đó là kích thước của tệp được xác định trong quá trình bạn sử dụng nó.
And think about this a second: you open a file and then typically you write bytes to it and then you close the file.
Hãy nghĩ về điều này một chút: bạn mở một tệp và thường thì bạn ghi các byte vào đó rồi đóng tệp.
And so the file system really has no idea how big your file is gonna be until you actually close it.
Và vì vậy hệ thống tệp thực sự không biết tệp của bạn sẽ lớn bao nhiêu cho đến khi bạn đóng nó.
Or if you open it, you write some stuff, you close it, and then you go back later and you open it, you append some stuff and close it.
Hoặc nếu bạn mở nó, ghi một ít dữ liệu, đóng nó, rồi sau đó quay lại mở nó, nối thêm một ít dữ liệu và đóng lại.
Now the file is also growing incrementally.
Lúc này tệp cũng đang tăng dần từng bước.
And so to any extent that the file system is gonna optimize the placement of your bytes to try to make everything fast, it runs into this unfortunate problem here that it doesn't really know how big your file is, okay?
Và vì thế, trong chừng mực hệ thống tệp sẽ tối ưu hóa vị trí đặt các byte của bạn để cố làm cho mọi thứ nhanh, nó gặp phải vấn đề đáng tiếc này, đó là nó không thực sự biết tệp của bạn sẽ lớn bao nhiêu, được chứ?
The other thing we're gonna need to do is organize everything into directories. And so we have to figure out what data structure that is. Okay.
Việc khác chúng ta cần làm là tổ chức mọi thứ thành các thư mục. Và vì vậy chúng ta phải xác định đó là cấu trúc dữ liệu gì. Được rồi.
And then finally, we're gonna need to very carefully allocate and free blocks so that our access remains efficient and we can hopefully minimize seeks, as I started out here, maximizing sequential access.
Và cuối cùng, chúng ta sẽ cần cấp phát và giải phóng các khối thật cẩn thận để việc truy cập vẫn hiệu quả và hy vọng có thể giảm thiểu seek, như tôi đã nói ngay từ đầu, đồng thời tối đa hóa truy cập tuần tự.
Those two things are gonna be very important for us in our design. Okay. So what are some important components of a file system? So we have your file path, which is the name.
Hai điều đó sẽ rất quan trọng trong thiết kế của chúng ta. Được rồi. Vậy các thành phần quan trọng của một hệ thống tệp là gì? Đầu tiên ta có đường dẫn tệp, tức là tên.
You go somehow into a directory structure. That's gonna give us something we call an I number, which is really a pointer into an inode array.
Bằng cách nào đó bạn đi vào một cấu trúc thư mục. Nó sẽ cho ta thứ mà ta gọi là I number, thực chất là một con trỏ trỏ vào một mảng inode.
We'll get to that in a little bit. And what is an inode? An inode is basically a file header structure that points out which blocks belong in the file.
Lát nữa ta sẽ nói tới. Vậy inode là gì? Inode về cơ bản là một cấu trúc tiêu đề của tệp chỉ ra những khối nào thuộc về tệp.
So think of this as like an index or like a big array that sort of translates from a position in that array to which data block is in the file.
Hãy hình dung nó như một chỉ mục, hay như một mảng lớn dùng để chuyển đổi từ một vị trí trong mảng đó sang khối dữ liệu nào nằm trong tệp.
And this file header structure is the thing that's gonna get modified as I read and write the file. So I write the file, make it bigger. We're gonna be adding entries here.
Và cấu trúc tiêu đề tệp này chính là thứ sẽ bị sửa đổi khi tôi đọc và ghi tệp. Khi tôi ghi tệp, làm nó lớn hơn, ta sẽ thêm các mục vào đây.
When I allocate a brand new file by opening it with create, what I'm doing is I'm allocating a brand new inode just for that new file.
Khi tôi cấp phát một tệp hoàn toàn mới bằng cách mở nó với create, thì tôi đang cấp phát một inode hoàn toàn mới chỉ cho tệp mới đó.
Now, the interesting question here also that's in the chat here is, does error checking usually depend on the block device or the file system?
Giờ, có một câu hỏi thú vị trong khung chat, đó là việc kiểm tra lỗi thường phụ thuộc vào thiết bị khối hay hệ thống tệp?
So there's a lot of layers of error checking.
Có rất nhiều tầng kiểm tra lỗi.
We'll talk about those next lecture, but just as a simple thing to point out, the data sectors themselves have a whole bunch of Reed-Solomon bits on them that, so you actually write more bits than you think you're writing.
Ta sẽ nói về chúng ở bài giảng sau, nhưng xin nêu một điều đơn giản: bản thân các sector dữ liệu có cả loạt bit Reed-Solomon đi kèm, nên thực ra bạn ghi nhiều bit hơn bạn nghĩ.
And that allows it to handle a lot of read errors just off the disk.
Điều đó cho phép xử lý nhiều lỗi đọc ngay từ đĩa.
And then once we want to really deal with the fact that maybe a whole disk could die, then we start doing stuff like RAID and so on, which we'll talk more.
Và khi ta muốn xử lý trường hợp có thể cả một ổ đĩa bị hỏng, thì ta bắt đầu dùng những thứ như RAID, và ta sẽ nói thêm sau.
So mostly the error checking at one level is on the disk itself. And then at another level, we use redundancy by writing to multiple disk drives in order to deal with a drive failure.
Vậy phần lớn, ở một mức, việc kiểm tra lỗi nằm ngay trên đĩa. Và ở một mức khác, ta dùng dự phòng bằng cách ghi vào nhiều ổ đĩa để đối phó với việc một ổ bị hỏng.
The I here is just for inode. So inode, index, is what the I stands for. And so it's an index node. And this is the index node number, I number, whatever. But, all right.
Chữ I ở đây chỉ là viết tắt của inode. Inode, chữ I là index (chỉ mục). Vậy nó là một nút chỉ mục. Và đây là số hiệu nút chỉ mục, I number, gì cũng được. Thôi được.
Now, if you remember, by the way, way back when we talked about the abstract representation of a process, it's got some thread registers, it's got some address space and so on.
Nhân tiện, nếu bạn còn nhớ, hồi trước khi ta nói về biểu diễn trừu tượng của một tiến trình, nó có một số thanh ghi luồng, có không gian địa chỉ, v.v.
And the file descriptor table is in the process descriptor. And that basically transforms numbers to open file descriptions, if you remember.
Và bảng mô tả tệp nằm trong bộ mô tả tiến trình. Về cơ bản nó chuyển các số thành các mô tả tệp đang mở, nếu bạn còn nhớ.
And the way we talked about it, you can go back and look in, I don't know, lecture six or something, was we said, well, this file description keeps track of what the file name is and what position you're currently at in that file name so that when you're reading and writing, it can kind of pick up where you left off.
Và theo cách ta đã nói, bạn có thể xem lại ở tôi không nhớ, bài giảng sáu hay đâu đó, ta đã nói rằng mô tả tệp này theo dõi tên tệp là gì và vị trí hiện tại của bạn trong tệp đó để khi bạn đọc và ghi, nó có thể tiếp tục từ chỗ bạn đã dừng.
In reality, what's actually being stored in the open file description is the current I number.
Trong thực tế, thứ thực sự được lưu trong mô tả tệp đang mở là I number hiện tại.
Because if you remember, we open the file first, and that's where we trace the name all the way through the directory structure.
Vì nếu bạn còn nhớ, ta mở tệp trước, và đó là lúc ta lần theo tên qua toàn bộ cấu trúc thư mục.
And then eventually we find the I number, which points at the actual file. And that I number now is what we use when we read and write.
Rồi cuối cùng ta tìm ra I number, trỏ tới chính tệp thực sự. Và số I đó bây giờ chính là thứ chúng ta dùng khi đọc và ghi.
So you can actually get into a situation where you open a file and then it gets moved and you can continue to read and write it even though it's moved it somewhere other than what your name pointed at.
Vì vậy bạn thực sự có thể rơi vào tình huống mà bạn mở một tệp và sau đó nó bị di chuyển, và bạn vẫn có thể tiếp tục đọc và ghi nó, dù nó đã được chuyển đến một nơi khác với nơi mà tên của bạn trỏ tới.
And that's because the open has held onto the I number, not the name. All right.
Đó là vì lệnh open đã giữ lại số I, chứ không phải tên. Được rồi.
Now, so we take the file name and we look that up in a directory structure, which gives us the file number. So open performs the name resolution.
Bây giờ, ta lấy tên tệp và tra nó trong cấu trúc thư mục, và nó cho ta số tệp. Vậy open thực hiện việc phân giải tên.
We're gonna have to figure out how to do that, translating path names into a file number.
Chúng ta sẽ phải tìm hiểu cách làm việc đó, tức là dịch đường dẫn thành số tệp.
Read and write operate on the file number and use the file number as an index to locate the block.
Read và write thao tác trên số tệp và dùng số tệp làm chỉ số để xác định vị trí khối.
And so the file number goes into the index structure to the storage block, and that's on disk. And so really you're gonna figure out, well, I'm at offset...
Như vậy số tệp đi vào cấu trúc chỉ mục để tới khối lưu trữ, và khối đó nằm trên đĩa. Và thực ra bạn sẽ xác định xem, à, tôi đang ở độ lệch...
Suppose I was to go to 5K, 5,000 in some file. Well, that's gonna be in the second block, because the first block is zero to 4,095.
Giả sử tôi muốn đến vị trí 5K, tức 5.000 trong một tệp nào đó. Vị trí đó sẽ nằm trong khối thứ hai, vì khối đầu tiên là từ 0 đến 4.095.
And then the second block is gonna handle the next set of bytes.
Và khối thứ hai sẽ xử lý tập byte tiếp theo.
And so I'm gonna look that up in my index structure and find out where the second block is, or block number one. That's gonna point at the disk somewhere.
Vì vậy tôi sẽ tra trong cấu trúc chỉ mục của mình để biết khối thứ hai, hay khối số một, nằm ở đâu. Nó sẽ trỏ tới một chỗ nào đó trên đĩa.
And so I know that when I go to access byte 5,000, I'll know which block it is.
Và như vậy khi truy cập byte 5.000, tôi sẽ biết đó là khối nào.
So we're gonna have to look at both how the directory works and how this inode structure works to help us find which block is of interest to us.
Vì vậy chúng ta sẽ phải xem xét cả cách thư mục hoạt động lẫn cách cấu trúc inode này hoạt động để giúp tìm ra khối nào là khối mà ta quan tâm.
Okay. So there's several components which we're gonna talk about in the next few slides. One is, what's a directory look like? What is it exactly? Another is, what's that actual index structure?
Được rồi. Có một số thành phần mà chúng ta sẽ nói đến trong vài slide tới. Thứ nhất, một thư mục trông như thế nào? Chính xác nó là gì? Thứ hai, cấu trúc chỉ mục thực sự đó là gì?
A third is we're gonna talk about storage blocks and the free space map.
Thứ ba, chúng ta sẽ nói về các khối lưu trữ và bản đồ không gian trống.
A lot of these choices in here, of these four pieces at least, are things that vary depending on what file system you're using.
Rất nhiều lựa chọn ở đây, ít nhất là của bốn phần này, là những thứ thay đổi tùy theo hệ thống tệp bạn đang dùng.
Okay. So let's first ask our question: how do we get the file number? Well, you look it up in the directory.
Được rồi. Trước hết hãy đặt câu hỏi: làm sao để có số tệp? Bạn tra nó trong thư mục.
So a directory is really a file in most file systems containing file name, file number mappings. Okay.
Vậy thư mục thực chất là một tệp trong hầu hết các hệ thống tệp, chứa các ánh xạ từ tên tệp sang số tệp. Được rồi.
And so basically a directory is just a file, and you go in that directory and you find the file name you're looking for, and that gives you the file number.
Về cơ bản, thư mục chỉ là một tệp, bạn vào thư mục đó và tìm tên tệp mà bạn cần, và nó cho bạn số tệp.
And as a result of that, then you can get the index structure and know where to look on disk. The file number could be a file or another directory.
Và nhờ đó, bạn có thể lấy cấu trúc chỉ mục và biết cần tìm ở đâu trên đĩa. Số tệp có thể là một tệp hoặc một thư mục khác.
A directory could point at a file or another directory.
Một thư mục có thể trỏ tới một tệp hoặc một thư mục khác.
So really the way you go through slash A, slash B, slash C, slash D, is you find slash, and in slash you look up A, which points to directory A, and then in directory A you look up B, and so on.
Vậy cách bạn đi qua slash A, slash B, slash C, slash D là bạn tìm slash, và trong slash bạn tra A, nó trỏ tới thư mục A, rồi trong thư mục A bạn tra B, và cứ thế tiếp tục.
And so it's a chain of lookups through multiple different directory structures. And so each file name, file number mapping is actually called a directory entry.
Vậy nên đó là một chuỗi các lần tra cứu qua nhiều cấu trúc thư mục khác nhau. Và mỗi ánh xạ giữa tên tệp và số hiệu tệp thực ra được gọi là một mục thư mục (directory entry).
Okay. Now the processes are never allowed to read the raw bytes of a directory. So if you try to open a directory, it doesn't really work properly.
Được rồi. Các tiến trình không bao giờ được phép đọc các byte thô của một thư mục. Vì vậy nếu bạn thử mở một thư mục, nó không thực sự hoạt động đúng.
And so what I said earlier is that by and large Unix doesn't care about the format of the data in files.
Và điều tôi đã nói trước đó là nhìn chung Unix không quan tâm đến định dạng của dữ liệu trong các tệp.
The one point at which that's not true is the directory format, because the directory format is something that's directly interpreted, interpreted, boy, I'm losing it today, sorry. Directly interpreted by the operating system. Okay.
Điểm duy nhất không đúng như vậy là định dạng thư mục, vì định dạng thư mục là thứ được diễn giải trực tiếp, diễn giải, trời ơi, hôm nay tôi lú quá, xin lỗi. Được hệ điều hành diễn giải trực tiếp. Được rồi.
This is from watching vote counts for too long. I think I'm going slowly crazy. But anyway, so instead there's actually something called a readdir system call.
Đây là do theo dõi kết quả kiểm phiếu quá lâu. Tôi nghĩ mình đang dần phát điên. Nhưng dù sao, thay vào đó có một lời gọi hệ thống tên là readdir.
You can look it up, do a man on it, which iterates over this map without revealing the bytes. Okay. So why shouldn't we let the OS read and write the bytes of the directory?
Các bạn có thể tra cứu, dùng man để xem, nó duyệt qua ánh xạ này mà không để lộ các byte. Được rồi. Vậy tại sao ta không nên cho hệ điều hành đọc và ghi các byte của thư mục?
Well, because they might screw it up. Okay. And so pretty much the read directory, write directory, create, all of that stuff are operations that cause changes to directories indirectly.
Vì chúng có thể làm hỏng nó. Được rồi. Và hầu như các thao tác đọc thư mục, ghi thư mục, tạo, tất cả những thứ đó là các thao tác làm thay đổi thư mục một cách gián tiếp.
Okay. So just keep that in mind. But by and large, except for the format inside a directory, a directory is just a file.
Được rồi. Các bạn cứ ghi nhớ điều đó. Nhưng nhìn chung, ngoại trừ định dạng bên trong một thư mục, thư mục chỉ là một tệp.
And so keep that in mind, because we're going to be building files using our file system. And we're just going to use those files to store data or to store directory mappings.
Hãy ghi nhớ điều đó, vì chúng ta sẽ xây dựng các tệp bằng hệ thống tệp của mình. Và ta sẽ dùng những tệp đó để lưu dữ liệu hoặc lưu các ánh xạ thư mục.
And so the basic bag of bits and bytes that we end up using for our directory is something we're going to get out of our file mapping.
Và như vậy, túi bit và byte cơ bản mà ta dùng cho thư mục là thứ ta sẽ lấy ra từ ánh xạ tệp của mình.
So here's directories just in case. This is what you get on a Mac OS. Just the idea of these folders are something that kind of came up graphically 20 years ago or whatever.
Đây là các thư mục, để minh họa. Đây là những gì bạn thấy trên Mac OS. Ý tưởng về các thư mục dạng này là thứ xuất hiện dưới dạng đồ họa khoảng 20 năm trước hay đại loại thế.
But basically what we're seeing here is this top level directory has a directory in it called static.
Nhưng về cơ bản, ở đây ta thấy thư mục cấp cao nhất này có một thư mục bên trong tên là static.
And that static directory has in it a bunch of other things which have, for instance, homework, and inside of that might have homework0.pdf.
Và thư mục static đó chứa nhiều thứ khác, trong đó có, chẳng hạn, homework, và bên trong đó có thể có homework0.pdf.
This is a set of directories that we search until we eventually get to the actual file.
Đây là một tập các thư mục mà ta tìm kiếm cho đến khi cuối cùng tới được tệp thực sự.
So the directory abstraction, just to say a little bit more. So directories, that's what these blue things are here, are specialized files, contents with lists of pairs of file name and file number.
Vậy về trừu tượng hóa thư mục, tôi nói thêm một chút. Các thư mục, tức là những khối màu xanh này, là các tệp chuyên dụng, có nội dung là danh sách các cặp tên tệp và số hiệu tệp.
So in the /usr directory, what you see here is a pointer to lib4.3, is actually a pointer to this directory.
Vậy trong thư mục /usr, những gì bạn thấy ở đây là một con trỏ tới lib4.3, thực ra là con trỏ tới thư mục này.
A pointer to lib is this one inside the lib4.3 directory, as a pointer to foo, which is this actual file.
Một con trỏ tới lib là cái này bên trong thư mục lib4.3, như một con trỏ tới foo, chính là tệp thực sự này.
So these pointers are really just links, they're inumbers, which point at the inode structure that describes this file, which happens to be a directory in this instance.
Vậy các con trỏ này thực chất chỉ là các liên kết, chúng là các inumber, trỏ tới cấu trúc inode mô tả tệp này, mà trong trường hợp này lại là một thư mục.
So the system calls to create directories: open, create, read directory, traverse the structure. So notice that open and create and things like that actually add things to directories.
Vậy các lời gọi hệ thống để tạo thư mục: open, create, read directory, để duyệt cấu trúc. Lưu ý rằng open, create và những lời gọi tương tự thực ra sẽ thêm các mục vào thư mục.
You can do readdir to read your way through all the entries. There's mkdir and rmdir. You guys know about that.
Bạn có thể dùng readdir để đọc lần lượt qua tất cả các mục. Có mkdir và rmdir. Các bạn biết rồi.
That would be the way that, for instance, the original lib4.3 got put into /usr. And then there's link and unlink, which allow you to mess with these actual links.
Ví dụ, đó là cách lib4.3 ban đầu được đưa vào /usr. Rồi có link và unlink, cho phép bạn can thiệp vào chính các liên kết này.
And there's a bunch of libc support for iterating through the directory. So you should take a look, but there's like opendir.
Và có một loạt hàm hỗ trợ của libc để duyệt qua thư mục. Các bạn nên xem qua, ví dụ có opendir.
And then once you get back to a DIR star, Then you can read the next entry from it and you can process it in various ways.
Sau khi nhận lại một con trỏ DIR, bạn có thể đọc mục kế tiếp từ nó và xử lý theo nhiều cách.
So there's a whole series of system calls that have been made just to traverse this directory tree, which is something that you end up doing almost for sure if you ever write an application that's got to talk to files.
Vậy có cả một loạt lời gọi hệ thống được tạo ra chỉ để duyệt cây thư mục này, việc mà gần như chắc chắn bạn sẽ phải làm nếu từng viết một ứng dụng phải làm việc với tệp.
So what's the directory structure? Well, let's take a look here. I'm just gonna hammer this home. I said this earlier.
Vậy cấu trúc thư mục là gì? Chúng ta cùng xem. Tôi sẽ nhấn mạnh lại điểm này. Tôi đã nói ở trên rồi.
So how many disk accesses does it take to resolve, say, slash my book slash my slash book slash count? Well, you first have to read in the file header for the root directory.
Cần bao nhiêu lần truy cập đĩa để phân giải chẳng hạn /my/book/count? Trước hết bạn phải đọc phần đầu tệp (file header) của thư mục gốc.
So that's the slash directory. And that, it turns out, is at a fixed spot on the disk somewhere.
Tức là thư mục /. Và hóa ra nó nằm ở một vị trí cố định nào đó trên đĩa.
So one of the things that a file system gives you is the place of the root inode for the root directory. And then you read in the first data block for the root.
Vậy một trong những thứ mà hệ thống tệp cung cấp cho bạn là vị trí của inode gốc của thư mục gốc. Rồi bạn đọc khối dữ liệu đầu tiên của thư mục gốc.
So remember, the root is just a file. So I read in the first block of the file and I start traversing the directory.
Hãy nhớ rằng thư mục gốc chỉ là một tệp. Nên tôi đọc khối đầu tiên của tệp và bắt đầu duyệt thư mục.
And eventually, hopefully, I find, it's a table of name-index pairs and I search it linearly to find the word my, or the name my, in it.
Và cuối cùng, hy vọng là tôi tìm thấy, đó là một bảng các cặp tên-chỉ số và tôi tìm tuần tự để tìm từ my, hay tên my, trong đó.
And you can search it linearly in most standard Unixes.
Và bạn có thể tìm tuần tự trong hầu hết các Unix chuẩn.
And so that linear search becomes a really big problem if you have a directory with lots of entries in it, which sometimes automatically generated directories are that way.
Và việc tìm tuần tự đó trở thành một vấn đề rất lớn nếu thư mục có rất nhiều mục, mà đôi khi các thư mục được sinh tự động lại như vậy.
Now, the question here is, if the root is at a fixed place, does that mean it has a maximum size? So the answer is no.
Câu hỏi ở đây là, nếu thư mục gốc ở một vị trí cố định, thì điều đó có nghĩa là nó có kích thước tối đa không? Câu trả lời là không.
The thing that's at a fixed place is the inode index structure, not the file blocks.
Thứ nằm ở vị trí cố định là cấu trúc chỉ mục inode, chứ không phải các khối của tệp.
And there is a maximum file size in a typical file system, but that's much larger than you'd ever fill up with a directory.
Và trong một hệ thống tệp điển hình có kích thước tệp tối đa, nhưng nó lớn hơn nhiều so với mức bạn có thể lấp đầy bằng một thư mục.
Okay, so the fixed thing is the I node, not the data. You'll see that a little bit more as we get there.
Được rồi, vậy thứ cố định là inode, chứ không phải dữ liệu. Các bạn sẽ thấy rõ hơn một chút khi chúng ta đến phần đó.
So then you read in the header for my, so that's another reference.
Sau đó bạn đọc phần đầu của my, đó là một lần truy cập nữa.
And then you look through my defined book, and then you read in the header for book, and header, by the way, is the same as I node.
Rồi bạn tìm trong my để thấy book được định nghĩa, và sau đó bạn đọc phần đầu của book, và nhân tiện, header cũng chính là I node.
And then you read in the data block for book, you search for count, read the file header for count.
Sau đó bạn đọc khối dữ liệu của book, bạn tìm count, rồi đọc file header của count.
And at that point, I now have the I node for the actual file, and that can go in, that's basically cached for all my reads and writes at that point on, in the description.
Và đến lúc đó, tôi đã có I node của chính tập tin đó, và nó có thể được đưa vào, về cơ bản nó được lưu đệm cho mọi thao tác đọc và ghi từ thời điểm đó trở đi, trong phần mô tả (description).
Now, a file descriptor points at the description, which holds on to the header for count, all right.
Bây giờ, một file descriptor trỏ tới description, và description này giữ header của count, được chứ.
Now, the question here is a good one, which is: why not just store the full path in a big hash table?
Câu hỏi ở đây rất hay, đó là: tại sao không lưu toàn bộ đường dẫn trong một bảng băm lớn?
So the answer is there are some file systems that do that, where, so what you're basically saying is you take slash my slash book slash count and you map that to the I node.
Câu trả lời là có một số hệ thống tập tin làm như vậy, trong đó, về cơ bản bạn lấy slash my slash book slash count và ánh xạ nó tới I node.
You could do that, except that then that makes management a little harder, because typically you link a new directory, and if you think about it, you make a directory and then you add things to it.
Bạn có thể làm vậy, nhưng khi đó việc quản lý sẽ khó hơn một chút, vì thông thường bạn liên kết một thư mục mới, và nếu nghĩ kỹ, bạn tạo một thư mục rồi thêm các thứ vào đó.
And so the directory structure itself is typically organized the way we're talking about, but it's not impossible to organize it as a hash table.
Và vì vậy bản thân cấu trúc thư mục thường được tổ chức theo cách chúng ta đang nói, nhưng tổ chức nó thành bảng băm cũng không phải là không thể.
Okay, but let's organize it this way for now, all right. Because this is closer to what most file systems do.
Được rồi, nhưng bây giờ cứ tổ chức theo cách này nhé. Vì cách này gần với cách hầu hết các hệ thống tập tin làm.
It's easier, it's simpler than a huge system wide hash table, because you're not storing, you're not having to worry where to store the hash table.
Nó dễ hơn, đơn giản hơn một bảng băm khổng lồ toàn hệ thống, vì bạn không phải lưu, bạn không phải lo xem lưu bảng băm ở đâu.
I don't know if that answers that question or not. Okay, but it's not out of the question, and there are some file systems that have chosen to do it that way.
Tôi không biết như vậy đã trả lời câu hỏi đó chưa. Được rồi, nhưng không phải là không thể, và có một số hệ thống tập tin đã chọn làm theo cách đó.
So the other thing that we mentioned kind of way back when was current working directory, which is basically a per address space pointer to a directory that's used for resolving file names.
Một điều khác mà chúng ta đã đề cập từ khá lâu là thư mục làm việc hiện tại, về cơ bản là một con trỏ theo từng không gian địa chỉ tới một thư mục dùng để phân giải tên tập tin.
And this is an example in which the current working directory could be slash my slash book.
Và đây là một ví dụ trong đó thư mục làm việc hiện tại có thể là slash my slash book.
And in that case, you could actually cache the inode structure for slash my slash book in the kernel, and thereby when you go to get to count, it's much faster if your current working directory is slash my slash book.
Và trong trường hợp đó, bạn thực sự có thể lưu đệm cấu trúc inode của slash my slash book trong kernel, và nhờ đó khi bạn truy cập count, sẽ nhanh hơn nhiều nếu thư mục làm việc hiện tại của bạn là slash my slash book.
Okay? And in keeping with the notion that everything's a cache, in fact, what we cache under some circumstance, actually what the operating systems do cache, is they cache names.
Đúng không? Và phù hợp với quan niệm rằng mọi thứ đều là cache, thực tế là thứ mà chúng ta lưu đệm trong một số hoàn cảnh, thứ mà hệ điều hành thực sự lưu đệm, chính là các tên.
And so slash my slash book is actually kept, the book pointer is actually kept, in an internal name cache, which gets a little pretty close to the question that was just asked about keeping a path in a big hash table.
Và vì vậy slash my slash book thực ra được giữ lại, con trỏ book thực ra được giữ lại trong một name cache nội bộ, điều này khá gần với câu hỏi vừa được hỏi về việc giữ đường dẫn trong một bảng băm lớn.
So if you think about the hash table as a cache rather than as the ground truth on the directory, then that kind of works the way I think you were thinking there.
Nếu bạn xem bảng băm như một cache chứ không phải là dữ liệu gốc chuẩn của thư mục, thì nó hoạt động gần giống như cách bạn đã nghĩ.
Now, so our in-memory data structures: here's the per process file table, which takes a file descriptor number and that looks up in the file description, and that file description, which is typically system-wide, you load the inode into it and it points at data blocks.
Bây giờ, về các cấu trúc dữ liệu trong bộ nhớ: đây là bảng tệp của từng tiến trình, bảng này nhận một số mô tả tệp (file descriptor) rồi tra cứu trong file description, và file description đó, thường dùng chung cho toàn hệ thống, được nạp inode vào và trỏ tới các khối dữ liệu.
And so once we pull the inode into memory, then we can read the various blocks in the file pretty quickly and we don't care where the actual file name is.
Và một khi đã đưa inode vào bộ nhớ, thì ta có thể đọc các khối khác nhau của tệp khá nhanh và không cần quan tâm tên tệp thực sự là gì.
So the open system call basically finds the inode on the disk from the path name by traversing all the directories, creates an in-memory inode.
Vậy lời gọi hệ thống open về cơ bản tìm inode trên đĩa từ tên đường dẫn bằng cách duyệt qua tất cả các thư mục, rồi tạo một inode trong bộ nhớ.
And from that point on, then access to the file is fast and it's independent of how long the path name is.
Và từ đó trở đi, việc truy cập tệp rất nhanh và không phụ thuộc vào độ dài của tên đường dẫn.
One entry in this table, no matter how many instances of the file are open.
Chỉ có một mục trong bảng này, bất kể có bao nhiêu thực thể của tệp đang mở.
So if this file is open by many people, there's only one description here with many different file descriptors pointing at it.
Nên nếu tệp này được nhiều người mở, thì ở đây chỉ có một description với nhiều số mô tả tệp khác nhau trỏ tới nó.
Okay, now if you rename or move a file, does it create a new inode or modify the existing inode? Neither.
Được rồi, nếu bạn đổi tên hoặc di chuyển một tệp, thì nó tạo inode mới hay sửa inode hiện có? Không cái nào cả.
What it does when you move the file is it just changes the directory structure. It's the same inode, it's unchanged.
Khi bạn di chuyển tệp, nó chỉ thay đổi cấu trúc thư mục. Vẫn là inode đó, không thay đổi.
So the inode is the file in some sense and you can move it around, but all you're doing there is you're changing who's pointing at that inode. Okay, I hope that answered that question.
Vì vậy inode theo một nghĩa nào đó chính là tệp và bạn có thể di chuyển nó, nhưng thứ bạn làm ở đây chỉ là thay đổi cái đang trỏ tới inode đó. Được rồi, hy vọng đã trả lời được câu hỏi đó.
And in fact, if the same file is in several different directories, then you're gonna have several different directories point at the inode and it just all works out.
Và thực tế, nếu cùng một tệp nằm trong nhiều thư mục khác nhau, thì sẽ có nhiều thư mục khác nhau cùng trỏ tới inode và mọi thứ vẫn hoạt động ổn.
Okay, and so this is part of why the inode is the thing that we wanna store our permission bits on as well.
Được rồi, và đây là một phần lý do vì sao inode là nơi mà ta cũng muốn lưu các bit quyền truy cập.
Okay, now of course, the first file system we're gonna talk about is the FAT file system and it violates a whole bunch of these things, but it's probably the most common file system in use today.
Được rồi, tất nhiên, hệ thống tệp đầu tiên ta sẽ nói tới là hệ thống tệp FAT và nó vi phạm khá nhiều điều trong số này, nhưng có lẽ nó là hệ thống tệp phổ biến nhất đang được dùng hiện nay.
So we're gonna start with that one. So read and write system calls look up in memory inode using the file handle. And so once we've opened, then everything is fast.
Vì vậy ta sẽ bắt đầu với nó. Các lời gọi hệ thống read và write tra cứu inode trong bộ nhớ bằng file handle. Và như vậy một khi đã mở tệp thì mọi thứ đều nhanh.
Okay, so the last thing I wanna do before we look at some case studies is let's see if we can understand what our characteristics of our files are in order to help us design our file system.
Được rồi, điều cuối cùng tôi muốn làm trước khi xem các trường hợp nghiên cứu là xem liệu ta có hiểu được các đặc điểm của các tệp để giúp thiết kế hệ thống tệp của mình hay không.
And so there've been many things studied over the years. Here's one that was published in FAST, which is a file system conference, 2007.
Và đã có nhiều nghiên cứu qua các năm. Đây là một nghiên cứu được công bố tại FAST, một hội nghị về hệ thống tệp, năm 2007.
And one of the observations was really that most files are small.
Và một trong những quan sát là hầu hết các tệp đều nhỏ.
So what they did was they tracked the size of files in the file system over the years, and starting in 2005, years' worth of data.
Họ đã theo dõi kích thước của các tệp trong hệ thống tệp qua nhiều năm, bắt đầu từ năm 2005, với dữ liệu của nhiều năm.
And what you see here is that most of the files are in this small range here, even though there are some long tails, okay?
Và những gì bạn thấy ở đây là hầu hết các tệp nằm trong khoảng nhỏ này, dù có một số đuôi dài, được chứ?
And so most files are small, which says that I need to optimize for small, that's like 2K or less, files. But most of the bytes are in the large files, okay?
Vậy hầu hết các tệp đều nhỏ, nghĩa là tôi cần tối ưu cho các tệp nhỏ, cỡ 2K hoặc nhỏ hơn. Nhưng phần lớn số byte nằm trong các tệp lớn, được chứ?
So if you look at how many bytes are in total in the file system versus how much of the space it uses up, what you find is that most of the space on the file system is used by the large files, even though there's a lot of small files.
Vậy nếu bạn xem tổng số byte trong hệ thống tệp so với dung lượng mà chúng chiếm, thì bạn sẽ thấy phần lớn dung lượng trên hệ thống tệp được dùng bởi các tệp lớn, mặc dù có rất nhiều tệp nhỏ.
So there's a lot of small files, but most of the bytes are in the large files.
Vậy là có rất nhiều tệp nhỏ, nhưng phần lớn số byte nằm trong các tệp lớn.
So what these two pieces of data show you, and the trends of course are that files keep getting bigger and so on.
Vậy hai tập dữ liệu này cho chúng ta thấy và tất nhiên xu hướng là các tệp ngày càng lớn hơn, v.v.
But what these two pieces of data show you is that one, we need to be extremely efficient with small files. And two, we need to support large files still, because those are very important.
Nhưng hai tập dữ liệu này cho chúng ta thấy, thứ nhất, chúng ta cần cực kỳ hiệu quả với các tệp nhỏ. Và thứ hai, chúng ta vẫn cần hỗ trợ các tệp lớn, vì chúng rất quan trọng.
So we can't really focus on just small files or large files. We wanna have something that does both well, okay?
Vì vậy chúng ta không thể chỉ tập trung vào tệp nhỏ hoặc tệp lớn. Chúng ta muốn có một thiết kế làm tốt cả hai, được chứ?
And we're gonna keep that in mind, because that's gonna tell us a little bit about why various operating systems designed their file systems the way they did.
Và chúng ta sẽ ghi nhớ điều đó, vì nó sẽ cho chúng ta biết phần nào lý do vì sao các hệ điều hành khác nhau thiết kế hệ thống tệp của chúng theo cách như vậy.
So the first one I wanna show you is the most common file system in the world.
Cái đầu tiên tôi muốn giới thiệu là hệ thống tệp phổ biến nhất trên thế giới.
I would say this is the one that you have on your cameras, that when you take and plug in a USB stick, it's a FAT file system and so on.
Tôi cho rằng đây là hệ thống mà bạn có trên máy ảnh của mình, khi bạn cắm một chiếc USB vào, nó là hệ thống tệp FAT, v.v.
This was the original MS-DOS file system and it has found its way through many iterations and sizes to ridiculously large flash drives, okay?
Đây là hệ thống tệp MS-DOS ban đầu và nó đã trải qua nhiều phiên bản và kích thước, cho đến những ổ flash lớn đến mức phi lý, được chứ?
And so this is a good one to know, because it kind of lets us see the simplest form of how we could build a file system.
Đây là một hệ thống nên biết, vì nó cho chúng ta thấy dạng đơn giản nhất của cách xây dựng một hệ thống tệp.
And so the simple idea, FAT stands for file allocation table. And what a file allocation table is, is it's just a big table of integers, Okay?
Ý tưởng đơn giản là, FAT là viết tắt của file allocation table (bảng cấp phát tệp). Và bảng cấp phát tệp chỉ là một bảng lớn các số nguyên, được chứ?
And you can think of it as sitting next to the disk blocks. Okay, and that big table of integers is one-to-one correspondence with all the data blocks.
Bạn có thể hình dung nó nằm cạnh các khối đĩa. Được rồi, và bảng số nguyên lớn đó tương ứng một-một với tất cả các khối dữ liệu.
So there is an entry zero in the FAT, which corresponds to disk block zero; entry one corresponds to disk block one, and so on.
Vậy có mục số không trong FAT, tương ứng với khối đĩa số không; mục số một tương ứng với khối đĩa số một, và cứ thế.
So you could almost think of the FAT file system as being one integer worth of metadata per block, okay?
Bạn gần như có thể xem hệ thống tệp FAT là mỗi khối có một số nguyên siêu dữ liệu, được chứ?
And this FAT directory, or this FAT index, is basically gonna be stored on the disk in a few disk blocks, and it's actually replicated for reliability reasons.
Và thư mục FAT này, hay chỉ mục FAT này, về cơ bản sẽ được lưu trên đĩa trong một vài khối đĩa, và thực ra nó được nhân bản vì lý do độ tin cậy.
And let's see how we can build a file system out of it. Okay, so assume for now that we have a way to translate a path.
Hãy xem chúng ta có thể xây dựng một hệ thống tệp từ nó như thế nào.
So that means a full name into a file number, okay? So let's assume we have a directory, and I'll show you how that works in a moment.
Được rồi, bây giờ giả sử chúng ta có cách để dịch một đường dẫn, nghĩa là một tên đầy đủ, thành một số hiệu tệp, được chứ? Vậy giả sử chúng ta có một thư mục, và lát nữa tôi sẽ chỉ cách nó hoạt động.
Well, then disk storage is just a bunch of disk blocks. So what's a file? Well, a file is a bunch of disk blocks. How do you figure out which disk blocks they are?
Khi đó, bộ nhớ đĩa chỉ là một loạt các khối đĩa. Vậy tệp là gì? Tệp là một tập hợp các khối đĩa. Làm sao để biết đó là những khối đĩa nào?
Well, we're gonna somehow link them together in a linear order so that we've got a file out of them. And you could think that each block holds file data, okay?
Chúng ta sẽ liên kết chúng với nhau theo một thứ tự tuyến tính để từ đó có được một tệp. Và bạn có thể xem mỗi khối chứa dữ liệu của tệp, được chứ?
You can think of it as block number X of the file, or block B of the file; offset X gives you, if we have say 4K byte blocks, gives you which of the 4K bytes we're interested in, okay?
Bạn có thể xem đó là khối số X của tệp, hoặc khối B của tệp; độ lệch X cho bạn, nếu chúng ta có, chẳng hạn, các khối 4K byte, thì nó cho biết ta quan tâm đến byte nào trong 4K byte đó, được chứ?
And there'll be N blocks. And so if we put a bunch of blocks together, block zero will be some disk block, then there'll be block one, block two.
Và sẽ có N khối. Vậy nếu ta ghép một loạt khối lại với nhau, khối số không sẽ là một khối đĩa nào đó, rồi đến khối một, khối hai.
And then we can figure out which block we need, and then inside it, which index we need to get the byte we want, okay?
Sau đó ta có thể xác định mình cần khối nào, rồi bên trong khối đó, cần chỉ số nào để lấy được byte mong muốn, được chứ?
So for instance, suppose that we're talking about a file, and I'm gonna call it file 31, block zero, file 31, block one, File 31, block two.
Ví dụ, giả sử ta đang nói về một tệp, và tôi sẽ gọi nó là tệp 31, khối không của tệp 31, khối một của tệp 31, khối hai của tệp 31.
So what I've just assumed here is that somehow our files are numbered and each file has a set of blocks, zero, one, two, and notice that they're spread potentially all over the disk, okay?
Như vậy ở đây tôi đã giả sử rằng các tệp được đánh số và mỗi tệp có một tập các khối: không, một, hai, và hãy chú ý rằng chúng có thể nằm rải rác khắp đĩa, được chứ?
So this is a potentially big problem with the FAT file system. And so suppose now, so what are B? So B is the block number and X is the offset, okay?
Đây có thể là một vấn đề lớn của hệ thống tệp FAT. Và giả sử bây giờ, vậy B là gì? B là số khối còn X là độ dời (offset), được chứ?
And so in this block here, if I were interested, suppose I were interested in getting byte five of the file, I would know that that's block zero, because the blocks are, say, 4K in size.
Và trong khối này đây, nếu tôi muốn lấy byte số năm của tệp, tôi sẽ biết đó là khối không, vì các khối có kích thước, chẳng hạn, 4K.
So it'd be block zero, byte five.
Vậy đó sẽ là khối không, byte số năm.
And so that would mean I'd go to this and I'd go to block zero and I'd find the fifth block in that, and that would give me the byte that I wanted.
Điều đó nghĩa là tôi sẽ đi đến khối không này và tìm byte thứ năm trong đó, và nó sẽ cho tôi byte mà tôi muốn.
Okay, does that help? So B is a block number here, okay? Now, let's suppose we wanna read from file 31, block two, some offset X.
Được rồi, như vậy đã rõ chưa? Ở đây B là số khối, được chứ? Bây giờ, giả sử ta muốn đọc từ tệp 31, khối hai, tại một độ dời X nào đó.
What do we do? Well, we have to index and find block two, which is down here. So how do we know what block two is of file 31?
Ta làm gì? Ta phải đánh chỉ mục và tìm khối hai, nằm ở dưới này. Vậy làm sao biết khối hai của tệp 31 là khối nào?
Well, FAT does this extremely simply, okay? All it does is we start with entry 31, which is the file number.
FAT làm việc này cực kỳ đơn giản, được chứ? Ta bắt đầu từ mục 31, chính là số tệp.
And so that means that the file number corresponds directly to whatever block, this is block 31, represents block zero of the disk, okay?
Điều đó có nghĩa là số tệp tương ứng trực tiếp với khối nào đó, đây là khối 31, đại diện cho khối không của tệp trên đĩa, được chứ?
So the 31st disk block is block zero of file 31, okay? And then what does the FAT do?
Tức là khối đĩa thứ 31 là khối không của tệp 31, được chứ? Vậy FAT làm gì tiếp theo?
The FAT is a set of pointers that say, well, from block 31 or from this potentially spot in the FAT file system, the next block is what this link points to.
FAT là một tập các con trỏ cho biết rằng, từ khối 31, hay từ vị trí này trong hệ thống tệp FAT, khối tiếp theo là khối mà liên kết này trỏ tới.
So this 31 is gonna have a 32 in it, because block 32 in the disk is the next block of the file.
Vậy mục 31 sẽ chứa số 32, vì khối 32 trên đĩa là khối kế tiếp của tệp.
And then down here, I don't know what block number this is, doesn't really matter, is block three of the file.
Rồi ở dưới này, tôi không biết đây là khối số mấy, cũng không quan trọng, là khối ba của tệp.
And so basically I can walk through the blocks of the file by starting at the head block, which is the file number, and then just following the pointers, and that gives me block zero, block one, block two, okay?
Về cơ bản, tôi có thể duyệt qua các khối của tệp bằng cách bắt đầu từ khối đầu, chính là số tệp, rồi cứ lần theo các con trỏ, và như vậy tôi có khối không, khối một, khối hai, được chứ?
And so the way I read the block from the disk is, I wanted block two, do two hops, and then I pull the whole block in.
Vậy cách tôi đọc khối từ đĩa là: tôi muốn khối hai, thì nhảy hai bước, rồi nạp toàn bộ khối đó vào.
And at that point, now I can read byte X out of that block and hand it back to the user, okay? Questions?
Và đến lúc đó, tôi có thể đọc byte X trong khối ấy rồi trả về cho người dùng, được chứ? Có câu hỏi nào không?
Now, if you read in the literature, what you'll find is there's many versions of the FAT file system.
Bây giờ, nếu các em đọc tài liệu, các em sẽ thấy có nhiều phiên bản của hệ thống tệp FAT.
There was one that was 12 bits, one that was 16 bits, one that's 32 bits, okay?
Có bản 12 bit, bản 16 bit, bản 32 bit, được chứ?
That talks about the size of the integer in each one of these slots, which has to do with disk block, the number of disk blocks on the disk.
Con số đó nói về kích thước của số nguyên trong mỗi ô này, và nó liên quan đến khối đĩa, tức là số khối đĩa trên đĩa.
So you could imagine that FAT32 has many more, much larger disks it can handle than the original FAT12.
Vậy các em có thể hình dung FAT32 xử lý được những ổ đĩa lớn hơn nhiều so với FAT12 ban đầu.
Now, a very interesting question here that's in the chat is, what if you want file 32?
Bây giờ, có một câu hỏi rất thú vị trong phần chat, nếu em muốn tệp 32 thì sao?
The answer is there is no file 32, because file 32 would put you in the middle of file 31. Okay? So not every file number corresponds to the beginning of a file, okay?
Câu trả lời là không có tệp 32, vì tệp 32 sẽ đưa em vào giữa tệp 31. Được chứ? Vậy không phải số tệp nào cũng tương ứng với phần đầu của một tệp, được chứ?
So let me say that again. So file 32 isn't a file, okay? File 31 is a file. Block 32, it turns out, is the second block of that file. How do I know that?
Tôi nói lại nhé. Tệp 32 không phải là một tệp. Tệp 31 mới là một tệp. Hóa ra khối 32 là khối thứ hai của tệp đó. Làm sao tôi biết?
Well, I have to keep track of where my files start. That's where the directory is gonna come into play.
Chà, tôi phải theo dõi xem các tệp bắt đầu ở đâu. Đó là chỗ thư mục phát huy tác dụng.
If I thought 32 was a file and I popped in there, what I'm gonna find is that file is gonna look funny because it's gonna be missing the first block.
Nếu tôi tưởng 32 là một tệp và nhảy vào đó, tôi sẽ thấy tệp đó trông rất lạ vì nó thiếu khối đầu tiên.
And if this is, say, a video and there's a certain encoding in it, I'm gonna not be able to properly encode it because I'm jumping into the middle of that file.
Và nếu đây là, chẳng hạn, một video có một kiểu mã hóa nào đó, tôi sẽ không thể giải mã đúng được vì tôi đang nhảy vào giữa tệp đó.
Okay? So you can start to see the ways in which a FAT file system can get really screwed up.
Được chứ? Như vậy các em bắt đầu thấy những cách mà một hệ thống tệp FAT có thể bị hỏng nặng.
Like, if I lose track of where all the file numbers are, then it's gonna be very hard to figure out where the starts of all the files are.
Ví dụ, nếu tôi mất dấu tất cả các số tệp, thì sẽ rất khó xác định điểm bắt đầu của tất cả các tệp.
Now, there are recovery programs that will go through and try to figure out that, oh, look, here's this block, this block, and this block, and they look like they're block zero, one, and two of a video file.
Có những chương trình khôi phục sẽ duyệt qua và cố tìm ra rằng, à, nhìn này, có khối này, khối này và khối này, và trông chúng như khối 0, 1 và 2 của một tệp video.
Therefore, I'm gonna call this a file and I'm gonna generate a new FAT for you that will let you read it as a file. But it's a very error-prone process, okay?
Vì thế, tôi sẽ coi đây là một tệp và tạo cho bạn một FAT mới để bạn đọc nó như một tệp. Nhưng đó là một quá trình rất dễ sai sót, được chứ?
Now, how do we, let's look at this. So the files are a collection of disk blocks. The FAT is a linked list, one-to-one with the blocks, okay?
Bây giờ, làm thế nào, hãy xem cái này. Các tệp là một tập hợp các khối đĩa. FAT là một danh sách liên kết, tương ứng một-một với các khối, được chứ?
The file number is the index of the root of the block list for the file. The question that's an interesting one is, do they always go down? No.
Số tệp là chỉ số của gốc danh sách khối của tệp đó. Một câu hỏi thú vị là, chúng có luôn đi xuống không? Không.
In fact, that's gonna depend a lot on if you read some files and you write some files, and you delete some files, and you read some files, and you write some files, and you delete some files, and you iterate days, months, years.
Thực tế, điều đó phụ thuộc nhiều vào việc em đọc một số tệp và ghi một số tệp, và xóa một số tệp, rồi lại đọc một số tệp, ghi một số tệp, xóa một số tệp, và lặp lại qua nhiều ngày, nhiều tháng, nhiều năm.
It's gonna matter what blocks are free, and so you could link all over the place.
Khối nào còn trống sẽ quan trọng, nên liên kết có thể nhảy khắp nơi.
So there is no locality in the FAT file system, especially after you've used it for a while, so that in fact, the disk head is gonna be going all over the place as you try to read linearly through a file.
Vì vậy hệ thống tệp FAT không có tính cục bộ, đặc biệt sau khi em đã dùng nó một thời gian, đến mức thực tế là đầu đọc đĩa sẽ phải chạy lung tung khắp nơi khi bạn cố đọc tuần tự một tệp.
So you can already see this has got a problem here, okay? Why is this used in cameras, USBs? Well, it was the lowest common denominator.
Vậy là bạn đã thấy ngay đây có một vấn đề, đúng không? Tại sao nó vẫn được dùng trong máy ảnh, USB? Vì nó là mẫu số chung thấp nhất.
They wanted something that could work in the original MS-DOS slash Windows boxes and so on, and so pretty much it just, historical reasons, FAT is the thing used, okay?
Họ muốn có thứ gì đó chạy được trên các máy MS-DOS hay Windows ban đầu, v.v., nên về cơ bản chỉ là vì lý do lịch sử mà FAT được dùng, được chứ?
So that may be an unsatisfying answer, but that's the reason. So the offset on the file is a block number and an offset within the block.
Có thể đó là câu trả lời không thỏa đáng, nhưng đó là lý do. Vậy offset trong tệp gồm một số hiệu khối và một offset bên trong khối.
You follow the list to get the block number. Unused blocks are marked free. So what does that mean?
Bạn đi theo danh sách liên kết để lấy số hiệu khối. Các khối không dùng được đánh dấu là trống. Vậy điều đó nghĩa là gì?
That means the FAT has a special entry that isn't a link to another FAT entry that just says, "I'm free," okay?
Nghĩa là FAT có một mục đặc biệt không phải là liên kết tới mục FAT khác mà chỉ nói rằng: "Tôi trống", được chứ?
And so when you need a new block, you can scan through the FAT to find ones that are marked as free, and those are ones that you can use, okay?
Và khi bạn cần một khối mới, bạn có thể quét qua FAT để tìm các mục được đánh dấu là trống, và đó là những khối bạn có thể dùng, được chứ?
And so let me give you an example here. So suppose that I wanna, let's see, I guess I had a duplicate here, okay. Suppose that I wanted to do a write, okay?
Để tôi cho bạn một ví dụ. Giả sử tôi muốn, để xem nào, hình như tôi có một slide bị lặp ở đây, được rồi. Giả sử tôi muốn thực hiện một thao tác ghi, được chứ?
So actually, before I do that, I wanna show you something else here. So let's take a look at two files, okay?
Thực ra, trước khi làm vậy, tôi muốn cho bạn xem một thứ khác. Hãy xem hai tệp nhé.
So here's an example with two files, file 31 and file, whatever file number two is. I have no idea what that number is, doesn't really matter, but it's got two blocks in it.
Đây là ví dụ với hai tệp: tệp 31 và tệp kia, số hiệu thứ hai là gì cũng được. Tôi không biết số đó là bao nhiêu, cũng không quan trọng, nhưng nó có hai khối.
File 31's got three blocks. And notice that I've essentially written here another block into file 31, and so you can kind of see how these pointers can get all scrambled.
Tệp 31 có ba khối. Và lưu ý là về cơ bản tôi đã ghi thêm một khối nữa vào tệp 31, nên bạn có thể thấy các con trỏ này có thể bị xáo trộn như thế nào.
Now, the question might be, where is this FAT stored? Well, it's stored on disk, okay, at the beginning. And there's a special entry here that marks things as free.
Bây giờ, câu hỏi có thể là: FAT này được lưu ở đâu? Nó được lưu trên đĩa, ở phần đầu. Và có một mục đặc biệt ở đây để đánh dấu là trống.
And the question might be, what's the quickest way to format? Well, you could mark all the FAT entries as free. That's a quick format, so-called.
Và câu hỏi có thể là: cách định dạng nhanh nhất là gì? Bạn có thể đánh dấu tất cả các mục FAT là trống. Đó chính là cái gọi là định dạng nhanh.
And in that case, it doesn't really delete the data. What it does is it removes all the indexes.
Và trong trường hợp đó, nó không thực sự xóa dữ liệu. Nó chỉ loại bỏ tất cả các chỉ mục.
And so if you do a quick format, and you do a directory, you do a list in the directory, it's really a dir, D-I-R, in Windows or whatever, you'll think that things are gone, but in fact, All the data's underlying because all you've done is erased all the indexes, and somebody with a file recovery program might be able to still look at it, okay?
Vậy nếu bạn định dạng nhanh, rồi bạn xem thư mục, liệt kê nội dung thư mục, thực ra là lệnh dir, D-I-R, trong Windows hay gì đó, bạn sẽ nghĩ mọi thứ đã biến mất, nhưng thực tế toàn bộ dữ liệu vẫn nằm bên dưới vì tất cả những gì bạn làm là xóa các chỉ mục, và ai đó có chương trình khôi phục tệp vẫn có thể xem được chúng, được chứ?
So one of the good things about FAT is that it's simple. You can basically implement it in device firmware.
Một trong những ưu điểm của FAT là nó đơn giản. Về cơ bản bạn có thể cài đặt nó trong firmware của thiết bị.
And so that's one of the reasons that it's also used in cameras and so on, because it's really simple to implement and doesn't require a lot of work.
Và đó cũng là một lý do nó được dùng trong máy ảnh, v.v., vì nó rất dễ cài đặt và không đòi hỏi nhiều công sức.
Okay, is the free list kept as a linked list? Technically, the free list in the FAT spec is really just zero entries here.
Được rồi, danh sách trống có được giữ dưới dạng danh sách liên kết không? Về mặt kỹ thuật, danh sách trống trong đặc tả FAT thực chất chỉ là các mục có giá trị 0 ở đây.
If you wanted to have a linked list, you could do that in memory as a way of avoiding having to scan all the way through.
Nếu bạn muốn có một danh sách liên kết, thì bạn có thể làm điều đó trong bộ nhớ như một cách để tránh phải quét qua toàn bộ.
And sometimes if you have enough memory, what most devices will do is they'll just load the whole FAT in the memory, so it's much quicker to go through, okay?
Và đôi khi nếu có đủ bộ nhớ, thì hầu hết các thiết bị sẽ nạp toàn bộ FAT vào bộ nhớ, nên việc duyệt qua nhanh hơn nhiều, được chứ?
But technically speaking, if you took something and removed the USB key and you'd look at the FAT, things are indicated as free by being zero, okay?
Nhưng về mặt kỹ thuật, nếu bạn lấy một thiết bị, rút USB ra rồi xem FAT, thì các mục trống được đánh dấu bằng giá trị 0, được chứ?
So let's look at directories for a moment here. So a directory in FAT is a file containing a file name, file number mappings, okay?
Bây giờ ta hãy xem qua thư mục một chút. Một thư mục trong FAT là một tệp chứa các ánh xạ từ tên tệp sang số hiệu tệp, được chứ?
And so here's an example where we might have the name music, and it has a pointer in it to the file number for that music directory.
Và đây là một ví dụ, ta có thể có tên music, và trong đó có một con trỏ tới số hiệu tệp của thư mục music đó.
Notice that there's typically the dot, which is pointing to this guy, and then the dot dot, which is pointing to the parent. We link these directory entries together. Why are they linked together?
Lưu ý là thường có dấu chấm, trỏ tới chính thư mục này, và hai dấu chấm, trỏ tới thư mục cha. Ta liên kết các mục thư mục này với nhau. Tại sao chúng được liên kết với nhau?
Well, just because in the FAT things are all linked, right? So this is the first very clear instance, hopefully for you guys, of a directory is just a file that's got special formatting, okay?
Đơn giản là vì trong FAT mọi thứ đều được liên kết, đúng không? Vậy đây là ví dụ rất rõ ràng đầu tiên, hy vọng là với các bạn, cho thấy thư mục chỉ là một tệp có định dạng đặc biệt, được chứ?
Now, the interesting question that was on this is, what if the sector, the root directory fails, Then you potentially lose your data. Now, the FAT, there's actually two copies of it.
Bây giờ, câu hỏi thú vị được đặt ra ở đây là, nếu sector chứa thư mục gốc bị hỏng thì sao, thì có thể bạn sẽ mất dữ liệu. Còn FAT thì thực ra có hai bản sao.
So you have a couple of chances to not lose it.
Vậy bạn có vài cơ hội để không bị mất nó.
But if you really lose the FAT, then you've just lost all of the indexes and potentially have no idea what files are linked together. So free space for new or deleted entries is kept.
Nhưng nếu bạn thực sự mất FAT, thì bạn mất toàn bộ các chỉ mục và có thể không biết những tệp nào được liên kết với nhau. Không gian trống cho các mục mới hoặc đã xóa vẫn được giữ lại.
So when you delete something in a directory, you just link over it and there's free space in that directory.
Khi bạn xóa một thứ trong thư mục, bạn chỉ cần liên kết bỏ qua nó và thư mục đó có không gian trống.
In the FAT, the file attributes are kept in the directory, which means, unlike what I was saying earlier, that we're not able to put permissions on the file itself, but rather on the directory.
Trong FAT, các thuộc tính tệp được lưu trong thư mục, nghĩa là, khác với những gì tôi nói trước đó, ta không thể đặt quyền truy cập lên chính tệp, mà chỉ đặt lên thư mục.
So that's not quite the way we wanted it. So what distinguishes directory files from normal files? You can get to them by starting at the root directory, okay?
Vậy đó không hẳn là cách mà ta mong muốn. Vậy điều gì phân biệt tệp thư mục với tệp thông thường? Bạn có thể tới chúng bằng cách bắt đầu từ thư mục gốc, được chứ?
So all of this depends a lot on the actual format of the metadata not getting screwed up.
Vì vậy tất cả những điều này phụ thuộc rất nhiều vào việc định dạng thực tế của siêu dữ liệu không bị hỏng.
And so any of you who have ever lost, I once lost a whole bunch of pictures in a camera because a couple of blocks failed in the wrong way and it's very hard to get them back.
Và bất kỳ ai trong các bạn từng bị mất dữ liệu, tôi từng mất cả loạt ảnh trong một chiếc máy ảnh vì vài khối bị hỏng đúng vào chỗ không nên và rất khó để lấy lại chúng.
So the FAT file system is very fragile, as you can see, but again, it's used a lot in very large USB keys.
Như bạn thấy, hệ thống tệp FAT rất mong manh, nhưng một lần nữa, nó được dùng rất nhiều trong các USB dung lượng lớn.
Okay, and it's a linked list of entries. You have to linearly search through and so on. So where do you find the root directory?
Được rồi, và nó là một danh sách liên kết các mục. Bạn phải tìm kiếm tuyến tính qua nó, v.v. Vậy tìm thư mục gốc ở đâu?
Just to circle back on that, it's at a well-defined place on disk. The case of FAT, this is block 32, excuse me, block two.
Quay lại điểm đó, nó nằm ở một vị trí được xác định rõ trên đĩa. Trong trường hợp FAT, đó là khối 32, xin lỗi, khối hai.
There are no block zero or one. Don't ask me why, that's just what they did.
Không có block số không hay số một. Đừng hỏi tại sao, họ làm như vậy thôi.
So pretty much the very first block on the disk is the primary FAT and that's where you start your lookup. Okay, good.
Vậy nên block đầu tiên trên đĩa gần như chính là FAT chính và đó là nơi bạn bắt đầu tra cứu. Được rồi, tốt.
So discussion, suppose you start with a file number. How long does it take to find a block? Well, it's linear, right? You have to linearly search your way through.
Giờ ta thảo luận: giả sử bạn bắt đầu từ một số hiệu tệp. Mất bao lâu để tìm một block? Thì nó tuyến tính, đúng không? Bạn phải tìm tuần tự từng bước một.
What's the block layout for a file? Well, the layout for a file is accidentally whatever happens to be used as you're writing and wherever the free blocks are.
Cách bố trí block của một tệp thì sao? Cách bố trí của một tệp là ngẫu nhiên, tùy vào những block nào được dùng khi bạn ghi và tùy vào chỗ có các block trống.
What about sequential access? Well, sequential access is slow because you have to work your way through pointer, pointer, pointer, pointer.
Còn truy cập tuần tự thì sao? Truy cập tuần tự chậm vì bạn phải đi qua lần lượt con trỏ, con trỏ, con trỏ, con trỏ.
So I guess if going from pointer to pointer is not too bad, then your sequential access is not too bad. Random access is pretty bad, right?
Nên tôi đoán nếu việc đi từ con trỏ này sang con trỏ khác không quá tệ, thì truy cập tuần tự cũng không quá tệ. Truy cập ngẫu nhiên thì khá tệ, đúng không?
So if I wanted to get to block three from file 31, my only thing I can do is work my way through all of these links until I get to block three.
Nếu tôi muốn đến block số ba của tệp 31, thì việc duy nhất tôi có thể làm là đi dọc qua tất cả các liên kết này cho đến khi tới block số ba.
Okay, and so the FAT file system's very bad for random access unless you have a driver slash file system that pulls the whole FAT in and re-indexes it in a way that's fast.
Được rồi, và vì thế hệ thống tệp FAT rất kém về truy cập ngẫu nhiên, trừ khi bạn có một trình điều khiển hoặc hệ thống tệp nạp toàn bộ FAT vào và lập lại chỉ mục theo cách nhanh hơn.
And you can do that.
Và bạn có thể làm vậy.
There's nothing, no reason not to other than it takes a lot of memory and is not simple, which is one of the reasons that people like to use FATs in camera because it's such a simple thing.
Không có gì, không có lý do gì để không làm, ngoài việc nó tốn nhiều bộ nhớ và không đơn giản, và đó là một trong những lý do người ta thích dùng FAT trong máy ảnh vì nó rất đơn giản.
What about fragmentation? That's where the file is split across many parts of the disk. Well, as you see, just plain happens.
Còn hiện tượng phân mảnh thì sao? Đó là khi tệp bị chia ra nhiều phần ở nhiều nơi trên đĩa. Như bạn thấy, nó cứ thế xảy ra.
This is why there are all these defrag routines that you can run on old Windows boxes and so on to rearrange the blocks so that you really are linking sequentially and you can get some sequential performance out of this.
Đây là lý do có tất cả các tiện ích chống phân mảnh mà bạn có thể chạy trên các máy Windows cũ để sắp xếp lại các block sao cho các liên kết thật sự nằm tuần tự và bạn có thể đạt được hiệu năng tuần tự nào đó từ hệ thống này.
But if you don't do that, then the blocks are potentially all over the place. Small files, yeah, it handles them well enough, right? Big files, well, there's a lot of links.
Nhưng nếu không làm vậy, các block có thể nằm rải rác khắp nơi. Tệp nhỏ thì xử lý khá ổn, đúng không? Tệp lớn thì có rất nhiều liên kết.
I mean, the biggest problem with a big file is you can't get randomly to the end of it without following a bunch of links.
Ý tôi là vấn đề lớn nhất với tệp lớn là bạn không thể nhảy ngẫu nhiên đến cuối tệp mà không đi qua hàng loạt liên kết.
So that's a bit of an issue. Okay, so let's look at a different case study. I wanna talk about the Berkeley FAST file system.
Đó là một vấn đề. Được rồi, ta hãy xem một trường hợp nghiên cứu khác. Tôi muốn nói về hệ thống tệp Berkeley FAST.
Okay, so inodes in Unix, including the Berkeley FAST file system. The file number is no longer just a pointer into something like the FAT. It's actually an index into a set of inode arrays.
Được rồi, vậy là các inode trong Unix, bao gồm cả hệ thống tệp Berkeley FAST. Số hiệu tệp không còn chỉ là một con trỏ trỏ vào thứ gì đó như FAT nữa. Thực ra nó là một chỉ số trong một tập các mảng inode.
And so those inode arrays, each file or directory is an inode, okay? And so the file number is an index into this array.
Và trong các mảng inode đó, mỗi tệp hoặc thư mục là một inode, được chứ? Và số hiệu tệp là chỉ số trong mảng này.
Each inode corresponds to a single file and contains all its metadata.
Mỗi inode tương ứng với một tệp và chứa toàn bộ siêu dữ liệu của nó.
So things like the read or write permissions are stored with the file, not in the directory like they were in the FAT system. It allows multiple names or directory entries for a file.
Như các quyền đọc hoặc ghi được lưu cùng với tệp, chứ không nằm trong thư mục như trong hệ thống FAT. Nó cho phép một tệp có nhiều tên hay nhiều mục thư mục.
So again, the idea there is the inode is the file. The directory entries can point at it. You can name that file 12 different ways.
Vậy ý tưởng ở đây một lần nữa là: inode chính là tệp. Các mục thư mục có thể trỏ tới nó. Bạn có thể đặt tên cho tệp đó theo 12 cách khác nhau.
As long as you get to that through the directory structure, you can now use the same file because its identity is defined by the inode.
Miễn là bạn đi tới nó thông qua cấu trúc thư mục, thì bạn dùng được cùng một tệp, vì danh tính của nó được xác định bởi inode.
Okay, so this is a much cleaner approach to dealing with files. Okay, so the inode in Unix typically maintains a multi-level tree structure.
Được rồi, đây là cách tiếp cận gọn gàng hơn nhiều để xử lý tệp. Được rồi, inode trong Unix thường duy trì một cấu trúc cây nhiều cấp.
I'll show you this in a second. It's used to find storage blocks for files.
Lát nữa tôi sẽ cho các bạn xem. Nó được dùng để tìm các khối lưu trữ của tệp.
And it's been designed in this asymmetric way, which you'll see in a moment, to make it great for little and large files.
Và nó được thiết kế theo kiểu bất đối xứng này, như các bạn sẽ thấy ngay, để hoạt động tốt với cả tệp nhỏ lẫn tệp lớn.
Okay, if you remember, I showed you that there's a huge number of little files, but some really big files, and we need to handle both of those well.
Các bạn còn nhớ, tôi đã cho xem là có một số lượng khổng lồ các tệp nhỏ, nhưng cũng có một số tệp rất lớn, và ta cần xử lý tốt cả hai loại.
Okay, so the original inode format, which I'm gonna show you, appeared in Berkeley Standard Distribution Unix 4.1. And I've said this a couple of times. I said this about sockets.
Được rồi, định dạng inode ban đầu mà tôi sắp trình bày xuất hiện trong Berkeley Standard Distribution Unix 4.1. Tôi đã nói điều này vài lần rồi, tôi cũng nói về socket như vậy.
You know, BSD, Berkeley Standard Distribution, was famous for all sorts of innovations in operating systems. So this is a, you know, go Bears kind of scenario. This is part of your heritage here.
BSD, Berkeley Standard Distribution, nổi tiếng với đủ loại đổi mới trong hệ điều hành. Nên đây là kiểu tình huống "go Bears" đấy. Đây là một phần di sản của các bạn ở đây.
And just as a more recent thing, this is a very similar structure to what Linux EXT 2 or 3 ended up with.
Và nói về một ví dụ gần đây hơn, cấu trúc này rất giống với cái mà Linux EXT 2 hoặc 3 có được.
EXT 3 is pretty much what you would get if you formatted, you know, a new version of Linux, and you weren't trying to make a huge system, and for the EXT 4, okay?
EXT 3 gần như là thứ bạn sẽ có nếu bạn định dạng một phiên bản Linux mới, và không cố xây dựng một hệ thống khổng lồ, còn với hệ thống lớn thì là EXT 4, được chứ?
So, go bears. So here's the inode structure typically.
Vậy, go Bears. Đây là cấu trúc inode thường gặp.
It looks like this, where an inode has a bunch of metadata, and then it has a bunch of what are called direct pointers, which are pointers directly to block numbers, okay?
Nó trông như thế này: một inode có một loạt siêu dữ liệu, rồi có một loạt cái gọi là con trỏ trực tiếp, tức là các con trỏ trỏ thẳng tới số khối, được chứ?
And so the block numbers, remember I talked about the logical block numbers earlier, point in a big space from one to N. And so the direct pointers point directly at a set of blocks.
Và các số khối này, nhớ là tôi đã nói về số khối logic trước đó, trỏ vào một không gian lớn từ một đến N. Vậy các con trỏ trực tiếp trỏ thẳng tới một tập các khối.
And then there are double indirect pointers, which is, this is showing you an indirect pointer here, for instance, points at a block. And inside that block is a bunch of pointers to blocks.
Và sau đó có các con trỏ gián tiếp kép, còn đây, ví dụ, là một con trỏ gián tiếp, trỏ tới một khối. Và bên trong khối đó là một loạt con trỏ tới các khối.
And then doubly indirect pointers point at a block, which points at blocks, which point at a bunch of data blocks.
Rồi con trỏ gián tiếp kép trỏ tới một khối, khối này trỏ tới các khối, và các khối đó trỏ tới một loạt khối dữ liệu.
And then finally a triply indirect goes to a block, which points to a block, which points to a block, which points to a bunch of data blocks.
Và cuối cùng, con trỏ gián tiếp ba đi tới một khối, khối này trỏ tới một khối, khối đó lại trỏ tới một khối, rồi khối cuối trỏ tới một loạt khối dữ liệu.
So all of the data blocks are over here on the far right. And this index structure, notice how it's asymmetric.
Tất cả các khối dữ liệu nằm ở phía ngoài cùng bên phải. Và với cấu trúc chỉ mục này, hãy để ý nó bất đối xứng như thế nào.
So the first N direct pointers, you go, you have the inode, you can directly figure out which data blocks are there.
N con trỏ trực tiếp đầu tiên: bạn có inode, bạn có thể xác định trực tiếp những khối dữ liệu nào nằm ở đó.
And then if you go past, let's say, block 10, then you start having to pull in a block, which then lets you get N blocks out of it, okay?
Còn nếu đi quá, giả sử, khối 10, thì bạn bắt đầu phải nạp thêm một khối, và khối đó cho phép bạn lấy ra N khối, được chứ?
Can anybody figure out why we did a bunch of direct pointers and then we had some indirect, doubly indirect and triply indirect pointers? Why this crazy structure?
Có ai đoán được vì sao ta dùng một loạt con trỏ trực tiếp rồi sau đó mới có các con trỏ gián tiếp, gián tiếp cấp hai và gián tiếp cấp ba không? Tại sao lại có cấu trúc kỳ lạ này?
Any idea? Something about small versus large files. Yeah. What does this do exactly? Good.
Có ý kiến nào không? Liên quan đến tệp nhỏ so với tệp lớn. Vâng. Chính xác thì nó làm gì? Tốt.
So somebody else said here, the head of the file is fast, but you can still accommodate large files. That's correct. In fact, for files that are small enough, it's only one hop.
Có bạn khác nói là phần đầu của tệp thì nhanh, nhưng vẫn có thể chứa được các tệp lớn. Đúng vậy. Thật ra, với những tệp đủ nhỏ thì chỉ cần một bước nhảy.
Once we've got the inode in memory, which we get on open, we can look directly in the inode to find out the first N blocks just directly.
Khi đã có inode trong bộ nhớ, việc này diễn ra lúc open, ta có thể xem thẳng trong inode để biết N khối đầu tiên một cách trực tiếp.
So this is extremely efficient for small files, right? But we can accommodate large files, and for really large files, the triply indirect pointers give us a huge number of data blocks, okay?
Như vậy là cực kỳ hiệu quả với các tệp nhỏ, đúng không? Nhưng ta vẫn chứa được tệp lớn, và với những tệp thật sự lớn, các con trỏ gián tiếp cấp ba cho ta một lượng khối dữ liệu khổng lồ, được chứ?
And so this structure was set up precisely to handle small files really well and still be able to handle big files mostly well, fairly well.
Cấu trúc này được thiết kế chính là để xử lý thật tốt các tệp nhỏ mà vẫn xử lý được các tệp lớn ở mức khá tốt.
And if you imagine caching, we haven't talked about that yet, all of these intermediate blocks, then in fact, once you've gone to the trouble of doing the triply indirect blocks and you pull in the first triple indirect block and then the doubles and the indirect blocks, then these can be put in the cache and you can get the rest of these very fast, okay?
Và nếu bạn hình dung việc caching, chúng ta chưa nói đến phần đó, tất cả các khối trung gian này, thì thực ra, một khi bạn đã mất công đi qua các khối gián tiếp cấp ba và nạp khối gián tiếp cấp ba đầu tiên rồi các khối cấp hai và các khối gián tiếp, thì chúng có thể được đưa vào cache và bạn lấy phần còn lại rất nhanh, được chứ?
Now, the question is to clarify, does the file number point to a single inode or to an array of multiple inodes? The answer is the file number points to a single inode, okay?
Bây giờ, câu hỏi để làm rõ là, số hiệu tệp trỏ đến một inode duy nhất hay đến một mảng nhiều inode? Câu trả lời là số hiệu tệp trỏ đến một inode duy nhất, nhé?
So the file is defined by its inode. Each file has only one inode.
Vậy một tệp được xác định bởi inode của nó. Mỗi tệp chỉ có một inode.
And when you talk about an inode, it is an index into this inode array that points at where the inode is. Does that make sense? All right, are we good?
Và khi nói đến một inode, nó là một chỉ số trong mảng inode này trỏ đến nơi inode nằm. Như vậy có hợp lý không? Được rồi, ổn chứ?
One more clarification. So the inode number points at the inode array. Every file has one inode, okay? Is the number of direct pointers part of the spec? Yes.
Thêm một điểm làm rõ nữa. Số hiệu inode trỏ vào mảng inode. Mỗi tệp có một inode, nhé? Số con trỏ trực tiếp có nằm trong đặc tả không? Có.
So file systems typically have a specific inode format. So that's part of the file system. Okay, and you don't often have the option to vary it.
Các hệ thống tệp thường có một định dạng inode cụ thể. Nên đó là một phần của hệ thống tệp. Và thường bạn không có lựa chọn để thay đổi nó.
In fact, I'm not sure of a commonly used file system offhand that lets you change the number of direct pointers. Inodes are one-to-one for every file, yes. So each file has an inode.
Thật ra, tôi không nhớ ra ngay hệ thống tệp phổ biến nào cho phép thay đổi số con trỏ trực tiếp. Inode tương ứng một-một với mỗi tệp, đúng vậy. Vậy mỗi tệp có một inode.
Each inode that is in use belongs to a file. Typically, there's a whole bunch of these that are free, because if there weren't any free ones, you couldn't create any new files.
Mỗi inode đang được sử dụng thì thuộc về một tệp. Thường thì có cả một loạt inode còn trống, vì nếu không còn cái nào trống thì bạn không thể tạo tệp mới.
So there's a bunch of free ones. But for the ones that are in use, they're only being used by one file, and each file has one inode.
Vậy có một loạt inode trống. Nhưng với những inode đang dùng, mỗi cái chỉ được một tệp sử dụng, và mỗi tệp có một inode.
And the file number is unique to the file. Yes. I don't know if I can say this in any other way. Does this make sense? What we're looking at here is exactly one file.
Và số hiệu tệp là duy nhất đối với tệp đó. Vâng. Tôi không biết còn cách nào khác để diễn đạt không. Như vậy có hợp lý không? Những gì chúng ta đang xem ở đây chính xác là một tệp.
Okay, and it has exactly one inode number, which represents this spot. Should I pause on this, or are we good?
Được rồi, và nó có đúng một số inode, đại diện cho vị trí này. Tôi có nên tạm dừng ở đây không, hay là mọi người đã nắm rồi?
Okay, I'm assuming that we're good. The inode array does not include a pointer to an inode. The inode array has inodes in it. The I number is a pointer in the inode array.
Được rồi, tôi cho rằng mọi người đã hiểu. Mảng inode không chứa con trỏ tới một inode. Mảng inode chứa các inode. I number là một con trỏ trong mảng inode.
Okay, so you can think of this as an array of structs if you want, but it's on disk. So the inodes are actually in the inode array, which is stored on disk.
Được rồi, nếu muốn thì bạn có thể coi đây là một mảng các struct, nhưng nó nằm trên đĩa. Vậy các inode thực sự nằm trong mảng inode, và mảng này được lưu trên đĩa.
Now, the top of the inode is the file attributes, which are things like what user is it created in, what group is it in, the typical read-write-execute permissions of the user, group and world, things like the setUID and setGID bits, which say that whenever you try to execute this file, if it's an executable,
Bây giờ, phần đầu của inode là các thuộc tính của tệp, chẳng hạn như tệp được tạo bởi người dùng nào, thuộc nhóm nào, các quyền đọc-ghi-thực thi thông thường của người dùng, nhóm và những người khác, những thứ như các bit setUID và setGID, cho biết rằng mỗi khi bạn cố thực thi tệp này, nếu nó là tệp thực thi,
does it get an effective user ID that is the same as the owner, or an effective group ID that's the same as the group?
thì nó có nhận effective user ID giống với chủ sở hữu hay không, hoặc effective group ID giống với nhóm hay không?
Those bits are all stored in the metadata, okay, whether this can be read or written, et cetera, okay? The other thing is, for instance, here's an example of 12 pointers, okay?
Tất cả các bit đó đều được lưu trong siêu dữ liệu, tức là tệp có thể đọc hay ghi được hay không, v.v., được chứ? Thứ khác là, ví dụ, đây là ví dụ với 12 con trỏ, được chứ?
This wasn't the original BSD necessarily, but certainly Linux has 12 of these direct pointers. The original BSD had 10. That's part of the spec.
Đây không hẳn là của BSD gốc, nhưng chắc chắn Linux có 12 con trỏ trực tiếp như vậy. BSD gốc có 10. Đó là một phần của đặc tả.
But what this is saying is that in this inode, we have, for instance, 12 pointers that point to data blocks, and if it's 4K blocks, that means that the direct pointers are sufficient for files up to 48 kilobytes.
Nhưng điều này nói lên rằng trong inode này, chúng ta có, ví dụ, 12 con trỏ trỏ tới các khối dữ liệu, và nếu các khối là 4K, thì các con trỏ trực tiếp đủ cho các tệp có kích thước tới 48 kilobyte.
Everybody with me? Why? Because we have 12 pointers, 12 times four kilobytes. Four kilobytes, okay?
Mọi người theo kịp chứ? Tại sao? Vì ta có 12 con trỏ, 12 nhân bốn kilobyte. Bốn kilobyte, được chứ?
So we can do pretty well with lots of small files having only one lookup hop, one indirection to get to the data blocks.
Nên ta có thể xử lý khá tốt rất nhiều tệp nhỏ chỉ với một bước tra cứu, một lần gián tiếp để tới các khối dữ liệu.
Once we've loaded the inode into RAM, then we can get these data blocks, okay?
Khi đã nạp inode vào RAM, ta có thể lấy các khối dữ liệu này, được chứ?
And again, that's getting us this thing that we talked about earlier, which is that most of the files are small.
Và điều đó lại cho ta thứ mà ta đã nói trước đó, đó là hầu hết các tệp đều nhỏ.
So most of the inodes don't have any indirect, doubly indirect or triply indirect pointers. Those are zeros. They basically have everything in this small number of direct pointers, okay?
Vì vậy hầu hết các inode không có con trỏ gián tiếp, gián tiếp hai cấp hay gián tiếp ba cấp nào. Chúng bằng không. Về cơ bản mọi thứ đều nằm trong số ít con trỏ trực tiếp này, được chứ?
If you, so does the file system not support 512 byte blocks? Okay, so that's an interesting question.
Nếu bạn, vậy hệ thống tệp không hỗ trợ khối 512 byte sao? Được rồi, đó là một câu hỏi thú vị.
And the answer is that originally these blocks were small and they were 512 bytes in the original BSD, okay? Because the sector sizes were 512 bytes.
Và câu trả lời là ban đầu các khối này nhỏ và là 512 byte trong BSD gốc, được chứ? Vì kích thước sector là 512 byte.
When we got to the fast file system, which I wanna finish up here before we end today, these blocks were bigger.
Khi ta tới fast file system, mà tôi muốn kết thúc ở đây trước khi hết giờ hôm nay, các khối này lớn hơn.
And so then there was a special way to deal with fragmentation where you'd have data blocks that were partially used, but let's leave that for another conversation.
Và khi đó có một cách đặc biệt để xử lý phân mảnh khi bạn có những khối dữ liệu chỉ được dùng một phần, nhưng hãy để chuyện đó cho một cuộc trao đổi khác.
So, and by the way, just to finish one thing though, is if the sectors are 512 bytes on disk, when we read data blocks and when they're four kilobytes, we don't, nothing that the file system, the file system has no idea that the disk is operating in 512 bytes because the disk device driver only pulls in and out 4k bytes.
Và nhân tiện, chỉ để kết thúc một điều thôi, là nếu các sector trên đĩa là 512 byte, thì khi ta đọc các khối dữ liệu và khi chúng là bốn kilobyte, ta không, không có gì mà hệ thống tệp, hệ thống tệp không hề biết rằng đĩa đang hoạt động với các khối 512 byte vì trình điều khiển thiết bị đĩa chỉ đọc vào và ghi ra 4k byte.
So there's never that level of granularity, it's never exposed to this file system, okay?
Vì vậy không bao giờ có mức độ chi tiết đó, nó không bao giờ được để lộ ra cho hệ thống tệp này, được chứ?
Now, so once we get to the indirect pointers, We can actually get up to terabytes of data, okay?
Bây giờ, một khi chúng ta đến các con trỏ gián tiếp, chúng ta thực sự có thể đạt tới hàng terabyte dữ liệu, được chứ?
So once we get to these, this level up here, we're in pretty good shape, and that basically handles the really large files in our original study there.
Vậy một khi đến được các con trỏ này, tầng ở phía trên này, thì chúng ta khá ổn rồi, và về cơ bản nó xử lý được các tệp thực sự lớn trong phần khảo sát ban đầu của chúng ta.
So we're good to go with one, two and three level indirect pointers, okay?
Vậy chúng ta ổn với các con trỏ gián tiếp một, hai và ba cấp, được chứ?
Putting it all together, we basically have an on-disk index where we have these inode arrays with a bunch of inodes in them that index files for us.
Gộp tất cả lại, về cơ bản chúng ta có một chỉ mục trên đĩa, trong đó có các mảng inode chứa một loạt inode dùng để đánh chỉ mục các tệp cho chúng ta.
And in the case of the original Unix, it was 10 direct pointers. And we can sort of ask our question: how many accesses for block 23?
Và trong trường hợp Unix gốc, có 10 con trỏ trực tiếp. Và chúng ta có thể đặt câu hỏi: cần bao nhiêu lần truy cập để đọc khối 23?
Well, what you do is you get through the direct ones, and then you start talking about the two of them, because you have to get one for the indirect blocks.
Chà, bạn đi qua các con trỏ trực tiếp, rồi bạn bắt đầu tính đến hai lần truy cập, vì bạn phải đọc thêm một khối cho các khối gián tiếp.
If we have 10 direct pointers in this example, to get to block 23, we have to basically get past the first 10.
Nếu trong ví dụ này có 10 con trỏ trực tiếp, để đến khối 23, về cơ bản ta phải vượt qua 10 khối đầu tiên.
And then we know that the block 23 is gonna be in the set of data blocks that are singly indirect.
Rồi ta biết rằng khối 23 sẽ nằm trong tập các khối dữ liệu gián tiếp một cấp.
So we're gonna have to read this indirect block, and then we'll be able to go down to block 13 in this grouping to get block 23, okay?
Vì vậy ta sẽ phải đọc khối gián tiếp này, rồi sau đó đi xuống khối 13 trong nhóm này để lấy khối 23, được chứ?
And so, and actually if it's zero indexed, we'll go to block 12 here to get to the one we want. But notice that we can easily figure it out.
Và thực ra nếu đánh chỉ số từ 0, thì ta sẽ đi đến khối 12 ở đây để lấy khối mình muốn. Nhưng hãy chú ý là ta có thể dễ dàng tính ra.
If we know what block we're interested in, we can figure out where in this structure we have to go to get our block.
Nếu ta biết mình quan tâm đến khối nào, ta có thể tính ra cần đi đến đâu trong cấu trúc này để lấy khối đó.
So this inode being well-defined based on the file system means that we can easily go from block number to where the data block is, all right?
Vậy inode này được định nghĩa rõ ràng dựa trên hệ thống tệp, nghĩa là ta có thể dễ dàng đi từ số khối đến vị trí của khối dữ liệu, được chứ?
So how about block five? Well, that's just a direct block. So we just do one read. How about block 340?
Còn khối 5 thì sao? Đó chỉ là một khối trực tiếp. Vậy ta chỉ cần một lần đọc. Còn khối 340 thì sao?
Well, it turns out we have to go down to the doubly indirect blocks at that point here, read this guy, this guy, and so on. So you guys can figure that out, all right?
Chà, hóa ra lúc đó ta phải đi xuống các khối gián tiếp hai cấp ở đây, đọc khối này, khối này, và cứ thế. Các bạn có thể tự tính ra điều đó, được chứ?
Now, if you guys will give me another few moments here, I wanna actually talk about the Fast File System.
Bây giờ, nếu các bạn cho tôi thêm vài phút nữa, tôi muốn nói về Fast File System.
So, so far we're really talking about Berkeley BSD 4.1, but as you can imagine, if you look at this data structure, there's nothing in this data structure that says these data blocks are laid out in any intelligent way on disk.
Cho đến giờ chúng ta thực sự đang nói về Berkeley BSD 4.1, nhưng như các bạn có thể hình dung, nếu nhìn vào cấu trúc dữ liệu này, không có gì trong cấu trúc dữ liệu này cho biết các khối dữ liệu được bố trí trên đĩa theo cách thông minh nào.
In fact, the original Berkeley Unix 4.1 BSD file system had this unfortunate property that it would start out really fast. Why is that?
Thực tế, hệ thống tệp Berkeley Unix 4.1 BSD gốc có một đặc điểm đáng tiếc là lúc đầu nó chạy rất nhanh. Tại sao vậy?
Well, because as I allocated new files, I'd lay out all my blocks on disk in a sequential order and reading them back would be fast.
Chà, vì khi tôi cấp phát các tệp mới, tôi bố trí tất cả các khối trên đĩa theo thứ tự tuần tự và đọc lại chúng sẽ nhanh.
But over time, as you read and wrote and read and wrote and deleted, what would happen is the file system would get more and more slow over time, progressively slower until it was half or worse of the original performance.
Nhưng theo thời gian, khi bạn đọc, ghi, đọc, ghi rồi xóa, thì điều xảy ra là hệ thống tệp sẽ ngày càng chậm đi theo thời gian, chậm dần cho đến khi chỉ còn một nửa hoặc thậm chí tệ hơn so với hiệu năng ban đầu.
And the reason is that these blocks would start becoming randomly scattered on the disk, because the free list in the original BSD was literally a linked list and it had no idea of locality on disk.
Và lý do là những khối này bắt đầu bị phân tán ngẫu nhiên trên đĩa, bởi vì danh sách trống (free list) trong BSD gốc thực sự chỉ là một danh sách liên kết và nó hoàn toàn không có khái niệm về tính cục bộ trên đĩa.
So you can imagine that's a problem. So what did they do? Well, this is basically, we gotta deal with performance.
Vậy các bạn có thể hình dung đó là một vấn đề. Vậy họ đã làm gì? Về cơ bản, chúng ta phải xử lý vấn đề hiệu năng.
And so what happened is, among other things, we gotta go back to this from last time, two times ago.
Và điều đã xảy ra là, trong số những việc khác, chúng ta cần quay lại nội dung từ lần trước, tức là hai buổi trước.
If we wanna optimize reading on a disk, we remember that the seek time plus the rotational latency plus the transfer time all add up to give me my total time.
Nếu muốn tối ưu việc đọc trên đĩa, hãy nhớ rằng thời gian tìm (seek time) cộng với độ trễ quay cộng với thời gian truyền, tất cả cộng lại cho ra tổng thời gian của tôi.
And this seek and rotational latency can be long, especially the seek time. And so the seek time, we would like to avoid as much as possible.
Và thời gian tìm cùng độ trễ quay có thể rất dài, nhất là thời gian tìm. Do đó, ta muốn tránh thời gian tìm càng nhiều càng tốt.
So if you are reading sequentially, say here, and you're reading through this because this was a video or whatever, what I'd like is, as I read successive blocks, it'd be great if they all were on the same track, because then I could get them really rapidly.
Vậy nếu bạn đang đọc tuần tự, chẳng hạn ở đây, và bạn đang đọc xuyên suốt vì đây là một video hay thứ gì đó, thì điều tôi muốn là, khi đọc các khối liên tiếp, sẽ thật tuyệt nếu tất cả chúng nằm trên cùng một track, vì khi đó tôi có thể lấy chúng rất nhanh.
Well, that can only happen if my file system is conscious of that and tries to figure out how to lay them out in a way that mostly means that sequential access either stays on the same track, or if it has to change tracks or cylinders, will go to an adjoining cylinder with a little tiny head movement rather than going all over the place.
Điều đó chỉ xảy ra được nếu hệ thống tệp ý thức được điều này và tìm cách bố trí các khối theo cách để truy cập tuần tự phần lớn vẫn nằm trên cùng một track, hoặc nếu phải đổi track hay cylinder, thì sẽ sang một cylinder liền kề chỉ với một chuyển động đầu đọc rất nhỏ thay vì chạy lung tung khắp nơi.
And so we're gonna try to optimize so that we first read from the same track, then from the same cylinder, neither of those require us to move the head, and then only from tracks that are adjacent.
Vì vậy chúng ta sẽ cố tối ưu để trước tiên đọc từ cùng một track, rồi từ cùng một cylinder, cả hai trường hợp đều không đòi hỏi phải di chuyển đầu đọc, và sau đó mới chỉ đọc từ các track liền kề.
And so the fast file system, which is BSD 4.2, 1984, had the same inode structure.
Và hệ thống tệp nhanh (fast file system), tức BSD 4.2, năm 1984, có cùng cấu trúc inode.
So from the standpoint of what kind of files are supported, they basically kept that same idea that we just showed you of really efficient small files, but the ability to support the large ones.
Vì vậy xét về loại tệp được hỗ trợ, về cơ bản họ giữ nguyên ý tưởng mà chúng tôi vừa trình bày, là xử lý các tệp nhỏ thật hiệu quả, nhưng vẫn có khả năng hỗ trợ các tệp lớn.
One of the things they did do is they went from a block size of 512 to 1024.
Một trong những điều họ đã làm là chuyển kích thước khối từ 512 lên 1024.
So they doubled the block size, and that immediately gave them a lot more sequential movement, because we could read successive blocks very quickly.
Tức là họ tăng gấp đôi kích thước khối, và điều đó ngay lập tức mang lại nhiều chuyển động tuần tự hơn hẳn, vì chúng ta có thể đọc các khối liên tiếp rất nhanh.
We can read basically twice as many bytes at a time. So that was good.
Về cơ bản, mỗi lần ta đọc được nhiều byte gấp đôi. Vậy là tốt.
So the paper on the fast file system is up there on the resources page for you guys to take a look. And again, this is a Berkeley project, was well known at the time.
Bài báo về hệ thống tệp nhanh được đăng ở đó trên trang tài nguyên để các bạn xem. Và nhắc lại, đây là một dự án của Berkeley, rất nổi tiếng vào thời đó.
And it did a bunch of optimizations for performance and reliability.
Nó thực hiện hàng loạt tối ưu về hiệu năng và độ tin cậy.
Among other things, distributing inodes rather than having a single inode array that was on the outer tracks of the disk, or the outer cylinders of the disk, it actually distributed them throughout.
Trong số đó, nó phân tán các inode thay vì có một mảng inode duy nhất nằm ở các track ngoài cùng của đĩa, hay các cylinder ngoài cùng của đĩa, nó thực sự phân bố chúng khắp đĩa.
It used bitmap allocation in the place of a free list.
Nó dùng cấp phát bằng bitmap thay cho free list.
So the nice thing about a bitmap is now you have sort of one spot for every sector, and now you can make a decision.
Điểm hay của bitmap là bây giờ bạn có một vị trí cho mỗi sector. và bây giờ bạn có thể đưa ra quyết định.
You can say, oh, look, there's a big range, an empty space on the disk with a big range of free blocks that I could allocate sequentially.
Bạn có thể nói: ồ, nhìn này, có một vùng rất lớn, một khoảng trống trên đĩa với một dải lớn các khối còn trống mà tôi có thể cấp phát tuần tự.
And so the free list gave them a much better idea of what was sequentially free and not.
Và như vậy danh sách trống cho họ ý niệm tốt hơn nhiều về phần nào còn trống liên tục và phần nào không.
Another trick that they did was they kept 10 of the disk space free, and that probabilistically gave them a lot of runs of empty space, which gave them a much better ability to read sequentially off the disk.
Một mẹo khác họ dùng là giữ trống 10 dung lượng đĩa, và theo xác suất, điều đó tạo ra nhiều đoạn không gian trống liền nhau, giúp họ đọc tuần tự từ đĩa tốt hơn nhiều.
Okay, so in the early days, which we were talking about here, early Unix and DOS Windows, the FAT file system, et cetera, basically put all the headers on the outermost cylinders, and two problems with that are, one, since the inodes are all in one place, if a head crash destroyed the disk, you've just destroyed all your inodes,
Được rồi, vậy trong những ngày đầu mà chúng ta đang nói ở đây, Unix thời đầu và DOS Windows, hệ thống tệp FAT, v.v., về cơ bản đặt tất cả các header ở các cylinder ngoài cùng, và có hai vấn đề với cách này: thứ nhất, vì tất cả inode nằm ở một chỗ, nếu đầu đọc va chạm làm hỏng đĩa, bạn đã phá hủy toàn bộ inode của mình,
and now you lost track of all of the places of your files. So that's a problem, right? Problem number two was, when you create a file, you don't really know how big it'll become.
và bây giờ bạn mất dấu vị trí của tất cả các tệp. Đó là một vấn đề, đúng không? Vấn đề thứ hai là, khi bạn tạo một tệp, bạn không thực sự biết nó sẽ lớn đến mức nào.
And so the question is, how do you allocate sequentially enough space to get good performance?
Và câu hỏi là, làm sao cấp phát đủ không gian tuần tự để có hiệu năng tốt?
And we'll talk about that next time since we've just run out of time here, but just to give you a little bit of things to think about on our way out is that they basically divided the disk itself into a bunch of block groups and distributed the inodes around in the groups and came up with a way of basically allocating files
Chúng ta sẽ nói về điều đó vào lần sau vì đã hết giờ, nhưng để các bạn có chút điều suy nghĩ trước khi ra về, là họ về cơ bản đã chia chính chiếc đĩa thành nhiều nhóm khối (block group) và phân bố các inode vào trong các nhóm và nghĩ ra một cách để cấp phát các tệp
sequentially within a group. And given the heuristics for doing that, they actually improved the performance of this quite a bit. We'll talk about that next time.
một cách tuần tự trong một nhóm. Và nhờ các phương pháp heuristic để làm việc đó, họ đã cải thiện hiệu năng khá nhiều. Chúng ta sẽ nói về điều đó vào lần sau.
For now, just in conclusion, we've been talking about file systems, about transforming blocks into files and directories, optimizing for access and usage patterns, maximizing sequential access and allowing very efficient random access.
Còn bây giờ, để kết luận, chúng ta đã nói về hệ thống tệp, về việc biến các khối thành tệp và thư mục, tối ưu hóa theo các mẫu truy cập và sử dụng, tối đa hóa truy cập tuần tự và cho phép truy cập ngẫu nhiên rất hiệu quả.
We talked about file and directories being defined by a header called inode. We talked about naming, which is translating from user visible names to actual system resources.
Chúng ta đã nói về tệp và thư mục được định nghĩa bởi một header gọi là inode. Chúng ta đã nói về việc đặt tên, tức là chuyển đổi từ tên người dùng nhìn thấy sang tài nguyên thực của hệ thống.
The directories are used for naming And a linked or tree structure stored in the files. And that's how we basically define which blocks belong in a file.
Thư mục được dùng để đặt tên và một cấu trúc liên kết hoặc cây được lưu trong các tệp. Và đó là cách chúng ta xác định những khối nào thuộc về một tệp.
We talked about the FAT scheme, which is very widely used. It's a linked list approach. Cameras, USB drives, SD cards, et cetera, they're all FAT.
Chúng ta đã nói về sơ đồ FAT, được sử dụng rất rộng rãi. Đó là cách tiếp cận danh sách liên kết. Máy ảnh, ổ USB, thẻ SD, v.v., tất cả đều dùng FAT.
It's very simple to implement in firmware, but very poor performance. And it basically has no security, as you can see.
Nó rất đơn giản để cài đặt trong firmware, nhưng hiệu năng rất kém. Và về cơ bản nó không có bảo mật, như các bạn thấy.
We wanna look at the actual file access patterns: lots of small files, but a few really big ones taking up all the space.
Chúng ta muốn xem xét các mẫu truy cập tệp thực tế: rất nhiều tệp nhỏ, nhưng một vài tệp thật lớn chiếm hết dung lượng.
And so next time we'll talk about laying out file systems to take advantage of that, including the fast file system. All right, and then we'll talk about a couple of others.
Và vì vậy lần sau chúng ta sẽ nói về cách bố trí hệ thống tệp để tận dụng điều đó, bao gồm fast file system. Được rồi, và sau đó chúng ta sẽ nói về một vài hệ thống khác.
I have two other file systems that we'll talk about very briefly at the beginning of the next lecture, including NTFS, which is the Windows file system, and F2FS, which is one that's optimized for Flash.
Tôi có hai hệ thống tệp khác mà chúng ta sẽ nói rất ngắn gọn ở đầu bài giảng tiếp theo, gồm NTFS, hệ thống tệp của Windows, và F2FS, là hệ thống tệp được tối ưu cho bộ nhớ Flash.
All right. So I think that's when we're gonna call it a night.
Được rồi. Vậy em nghĩ hôm nay chúng ta dừng ở đây.
I hope everybody has a great weekend, and we're going to not try to get too crazy watching the vote counts coming in.
Hy vọng mọi người có một cuối tuần thật tuyệt, và đừng quá căng thẳng khi theo dõi kết quả kiểm phiếu đang được cập nhật.
But otherwise, I hope you all have a wonderful weekend, and we'll see you on Monday. Is the BSD file system still in use? That's a question on the chat.
Dù sao thì, chúc các em một cuối tuần thật tuyệt vời, và hẹn gặp lại các em vào thứ Hai. Hệ thống tệp BSD có còn được dùng không? Đó là câu hỏi trong khung chat.
The answer is yes. It's definitely still in use in BSD, Unix, and Linux EXT 2 slash 3 is also essentially the BSD file system.
Câu trả lời là có. Nó chắc chắn vẫn được dùng trong BSD, Unix, và EXT 2/3 của Linux về cơ bản cũng chính là hệ thống tệp BSD.
So, all right. You guys have a great evening. Bye now.
Được rồi. Chúc các em một buổi tối tốt lành. Tạm biệt.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.