Hệ thống file Flash trên Linux

Có thể bạn đã từng nghe nói đến Journaling Flash File System (JFFS) và Yet Another Flash File System (YAFFS), nhưng bạn có biết việc có một hệ thống file dành cho một thiết bị flash bên dưới có ý nghĩa như thế nào không? Bài viết này giới thiệu về hệ thống file flash cho Linux, đi sâu vào một số đặc điểm khi chúng làm việc với những thiết bị hao mòn (consumable devices – những bộ phận của bộ nhớ flash) như phân cấp hao tổn (wear leveling), giới thiệu một số loại hệ thống file khác nhau cùng với những ý tưởng thiết kế cơ bản của chúng.

Thời gian gần đây, các ổ đĩa thể rắn (solid-state driver) trở thành mốt thịnh hành, nhưng các hệ thống nhúng đã dùng thiết bị thể rắn cho việc lưu trữ từ khá lâu. Bạn có thể tìm thấy các hệ thống file flash trong các thiết bị PDA, cellphone, máy chơi nhạc MP3, máy ảnh kỹ thuật số, ổ đĩa flash USB, và ngay cả các máy tính xách tay (ASUS EEEPC, ClassmatePC, XOXO … – ND). Trong nhiều trường hợp, các hệ thống file cho các thiết bị thương mại có thể được thiết kế riêng biệt và có bản quyền thương mại, nhưng chúng đều phải đối mặt với những vấn đề được đề cập trong phần sau của bài viết.

Các hệ thống file trên nền flash có nhiều dạng khác nhau. Bài viết đi vào một số hệ thống file read-only và giới thiệu tổng quan một số hệ thống file read/write ngày nay cùng với cách hoạt động của chúng. Nhưng đầu tiên, ta hãy xem xét các thiết bị flash và những khó khăn đặc thù của chúng.

---

Các công nghệ bộ nhớ Flash

Bộ nhớ flash, có thể là kết quả của nhiều công nghệ khác nhau, là bộ nhớ “không bay hơi” (non-volatile memory), nghĩa là nội dung của chúng vẫn tồn tại sau khi ngắt nguồn điện. Để tham khảo lịch sử của các thiết bị bộ nhớ flash, xem phần Resources.

Hai loại thiết bị flash phổ biến nhất được phân biệt bởi công nghệ đặc thù của chúng: NOR và NAND. Công nghệ flash NOR-based lâu đời hơn, hỗ trợ hiệu suất đọc cao với chi phí cho dung lượng nhỏ hơn. NAND flash cung cấp dung lượng cao hơn với hiệu suất đọc và ghi nhanh hơn đáng kể. NAND cũng đòi hỏi một giao diện nhập xuất phức tạp hơn nhiều.

Các bộ nhớ flash được chia thành các partitions, cho phép nhiều hoạt động diễn ra đồng thời (xoá một partition trong khi đang đọc một partition khác). Các partition tiếp tục được chia thành các block (kích thước thường là 64KB hay 128KB). Khi firmware sử dụng các partition, chúng có thể tiếp tục phân chia segment trên từng block, ví dụ mỗi segment 512 byte trong một block, không bao gồm metadata.

Các thiết bị flash cho thấy một giới hạn cho các chương trình quản lý thiết bị khi so sánh với các thiết bị lưu trữ khác như RAM disk. Đó là hành động Write duy nhất được cho phép trên một thiết bị bộ nhớ flash là đổi một bit từ 1 sang 0. Nếu cần hành động ngược lại, thì block phải được xoá (để reset tất cả các bit về trang thái 1). Điều này có nghĩa là các dữ liệu hợp lệ khác trong block phải được di chuyển để được giữ lại. Bộ nhớ flash NOR thường có thể được lập trình theo từng byte một lúc, trong khi bộ nhớ NAND phải được lập trình theo từng cụm nhiều byte (thường là 512 byte).

Quá trình xoá một block cũng khác nhau giữa hai loại bộ nhớ. Mỗi loại đòi hỏi một phương pháp Erase đặc biệt có thể làm việc trên cả một block của bộ nhớ flash. Công nghệ NOR yêu cầu một bước “chuẩn bị” để xoá tất cả các giá trị về 0 trước khi hành động Erase có thể bắt đầu. Erase là một thao tác điện tử, xoá hết các electron khỏi mỗi cell trong một block.

Hành động Erase trên thiết bị flash NOR diễn ra trong nhiều giây, trong khi một thiết bị NAND có thể Erase trong hàng mili giây. Một đặc tính quan trọng của các thiết bị flash là nó có thể thực hiện được bao nhiêu hành động Erase. Trong một thiết bị NOR, mỗi block trong bộ nhớ flash có thể được xoá đến một trăm nghìn lần. Các bộ nhớ NAND có thể được xoá lên đến một triệu lần.

---

Các thử thách của bộ nhớ flash

Bên cạnh, và cũng là kết quả của những giới hạn đã được nêu ra trong phần trước, việc quản lý các thiết bị flash còn có nhiều thử thách khác. Ba vấn đề quan trọng nhất là dọn rác (garbage collection), quản lý các bad block, và phân cấp hao tổn.

Dọn rác

Dọn rác là quá trình thu hồi các block không hợp lệ (các block chứa các dữ liệu không hợp lệ). Công việc thu hồi gồm có chuyển các dữ liệu hợp lệ sang một block mới, sau đó xoá block không hợp lệ để làm cho nó có thể sử dụng trở lại. Quá trình này thường được chạy nền hoặc được gọi khi cần, chẳng hạn khi hệ thống file còn ít không gian trống.

Quản lý các bad block

Khi được sử dụng, theo thời gian, các thiết bị flash có thể tạo ra các bad blocks, hay thậm chí ngay từ khi được chuyển từ nhà chế tạo đã có các bad block và không thể sử dụng. Bạn có thể biết có bad block từ một hành động không thành công của flash (chẳng hạn Erase hay Write), trả về những Error Correction Code, hay ECC.

Sau khi xác định được các bad block, chúng sẽ được đánh dấu ngay trong thiết bị flash, trong một bảng bad block. Cách thực hiện điều này thì tùy vào từng thiết bị, tuy nhiên có thể được hiện thực với một tập các block dành riêng, được quản lý tách biệt với những block dữ liệu bình thường. Quá trình xử lý các bad block – trong trường hợp có từ nhà sản xuất hoặc trong quá trình sử dụng – được gọi là quản lý bad block. Trong một số trường hợp, chức năng này được hiện thực trong phần cứng bằng một con vi điều khiển gắn trong và do đó trong suốt với hệ thống file bên trên.

Phân cấp hao tổn

Các thiết bị flash được tạo thành từ các bộ phận có thể bị hao mòn: Bạn có thể thực hiện một số lần hữu hạn các thao tác Erase trên mỗi block trước khi chúng bị trở thành bad (và do đó phải được chương trình quản lý bad block đánh dấu). Để tối ưu hoá thời gian sử dụng của thiết bị flash, người ta đi tìm những giải thuật phân cấp hao tổn.

Các giải thuật Dynamic wear-leveling nhằm giải quyết vấn đề của một số hữu hạn các chu kỳ Erase cho một block. Thay vì sử dụng các block một cách ngẫu nhiên, dynamic wear-leveling cố gắn phân bố các block sao cho số lần sử dụng mỗi block là như nhau. Trong khi đó các giải thuật Static wear-leveling nhắm đến những vấn đề thú vị hơn. Bên cạnh việc bị giới hạn số chu kỳ Erase, các thiết bị flash còn bị giới hạn một số hữu hạn các chu kỳ Read. Điều này có nghĩa là nếu dữ liệu được lưu giữ quá lâu trong một block và được đọc quá nhiều lần, dữ liệu có thể bị mất. Các giải thuật static wear-leveling giải quyết việc này bằng cách định kỳ di chuyển các dữ liệu cũ sang những block mới.

---

Kiến trúc hệ thống

Như vậy là ta đã khám phá đôi điều về thiết bị flash và những thử thách cơ bản cho loại thiết bị này. Bây giờ, ta hãy xem cách các thành phần kết hợp với nhau như một kiến trúc phân lớp như thế nào (Hình 1).Ở trên cùng là lớp hệ thống file ảo (VFS), biểu diễn một lớp giao diện chung cho các ứng dụng tầng cao hơn. Bên dưới VFS là hệ thống file flash, ta sẽ xem xét kỹ ở phần sau. Tiếp theo là lớp Flash Translation Layer (FTL), cung cấp toàn bộ các chức năng quản lý cho một thiết bị flash, bao gồm cấp phát các block, cũng như phiên dịch địa chỉ, dynamic wear leveling, và dọn rác. Trong một số thiết bị flash, một phần của FTL có thể được hiện thực trong phần cứng.

Hình 1 Cấu trúc cơ bản của một hệ thống file flash

Linux kerenl sử dụng giao diện Memory Technology Device (MTD) làm lớp giao diện chung cho các thiết bị flash. MTD có thể tự động dò ra độ rộng bus của thiết bị flash và số thiết bị cần thiết cho việc hiện thực độ rộng của bus đó.

---

Các hệ thống file flash

Hiện tay Linux đã có sẵn một số hệ thống file flash. Phần tiếp theo này sẽ giải thích về thiết kế cũng như ưu nhược điểm của từng loại.

Journaling Flash File System (Hệ thống file flash cổ trục)

JFFS là một trong những hệ thống file flash đầu tiên cho Linux. JFFS là một hệ thống file log-structured được thiết kế cho các thiết bị flash NOR. Hệ thống file này rất đặc thù và giải quyết nhiều vấn đề với các thiết bị flash, nhưng nó lại vướng phải một vấn đề khác.

JFFS xem các thiết bị flash như là một “khoanh tròn” các block (circular log of blocks). Dữ liệu ghi vào flash thì được ghi vào đuôi, và các block ở phía đầu được thu hồi. Vùng không gian giữa đuôi và đầu là khoảng trống; khi vùng trống này còn lại ít, chương trình dọn rác được gọi lên. Chương trình dọn rác sẽ chuyển những block hợp lệ ra phía sau đuôi của khoanh tròn, bỏ qua các block không hợp lệ hoặc không dùng nữa, sau đó xoá chúng đi (xem Hình 2). Kết quả là một hệ thống file được phân cấp hao tổn tự động theo cả hai giải thuật static và dynamic. Vấn đề cơ bản với kiến trúc này là thiết bị flash bị xoá quá thường xuyên (thay vì dùng một chiết lược tối ưu hoá các thao tác xoá), làm cho thiết bị hao tổn rất nhanh.

Hình 2 Circular log trước và sau khi dọn rác

Khi mount một JFFS, các chi tiết về cấu trúc được đọc vào bộ nhớ, điều này dẫn đến thời gian mount lâu và phải tốn bộ nhớ hơn.

Journaling Flash File System 2

Mặc dù JFFS rất hữu dụng vào thời gian đầu, giải thuật wear-leveling của nó lại có xu hướng làm giảm tuổi thọ của các thiết bị flash NOR. Do đó người ta phải thiết kế lại giải thuật bên dưới để loại bỏ kiến trúc circular log đi. Giải thuật JFFS2 ra đời thiết kế cho thiết bị flash NAND đồng thời tăng hiệu suất nhờ các giải thuật nén.

Trong JFFS2, mỗi block trong flash được đối xử độc lập với nhau. JFFS2 giữ các danh sách block để phân cấp tổn hại cho thiết bị một cách đầy đủ. Danh sách Clean chứa các block có toàn các node hợp lệ. Danh sách Dirty chứa các block có ít nhất một node không dùng được. Cuối cùng, một danh sách Free biểu diễn các block đã được Erase và sẵn sàng để sử dụng.

Giải thuật dọn rác sau đó có thể quyết định một cách thông minh là những block nào nên được thu hồi theo một cách hợp lý. Hiện tại, giải thuật tiến hành chọn lựa theo xác suất trong danh sách Clean hay Dirty. Danh sách Dirty được chọn trong 99% tổng số lần để thu hồi block (di chuyển các nội dung hợp lệ sang một block khác), và danh sách Clean được chọn 1% trong tổng số lần (chỉ đơn giản là di chuyển nội dung sang block mới). Trong cả hai trường hợp, block được chọn sẽ được xoá và đặt vào dành sách Free (xem Hình 3). Điều này cho phép bộ dọn rác sử dụng lại các block không dùng nữa và đồng thời di chuyển dữ liệu để hỗ trợ static wear-leveling.

Hình 3 Quản lý block và dọn rác trong JFFS2

Yet Another Flash File System

YAFFS là một hệ thống file flash được phát triển cho thiết bị NAND. Phiên bản đầu tiên (YAFFS) hỗ trợ các thiết bị flash với các page kích thước 512 byte, nhưng phiên bản gần đây (YAFFS2) hỗ trợ các thiết bị mới hơn với kích thước page lớn hơn và số chu kỳ Write giới hạn cũng lớn hơn.

Trong hầu hết các hệ thống file flash, những block không dùng được sẽ được đánh dấu obsolete, nhưng YAFFS2 còn đánh dấu các block theo các số thứ tự tăng dần. Từ đó, khi hệ thống file được scan lúc mount, các node hợp lệ có thể được xác định nhanh chóng. YAFFS giữ các cấu trúc cây trong RAM để biểu diễn cho cấu trúc block của thiết bị flash, ngoài ra còn có checkpointing – quá trình lưu giữ cấu trúc cây trên RAM sang thiết bị flash khi unmount hệ thống để nó có thể đọc và phục hồi lại vào RAM một cách nhanh chóng khi được mount (xem Hình 4). Do đó, hiệu suất khi mount là một ưu điểm lớn của YAFFS2 so với các hệ thống file flash khác.

Hình 4 Quản lý block và dọn rác trong YAFFS2

---

Các hệ thống file nén chỉ đọc (read-only compressed file system)

Trong một số hệ thống nhúng, việc sử dụng một hệ thống file thay đổi được là không cần thiết, một hệ thống file bất biến cũng đáp ứng đủ nhu cầu. Linux hỗ trợ nhiều loại hệ thống file chỉ đọc, trong đó hai loại phổ biến nhất là cramfs và SquashFS.

Cramfs

Hệ thống file cramfs là một hệ thống file nén chỉ đọc trên Linux, có thể được cài đặt trong các thiết bị flash. Đặc tính của cramfs là đơn giản và hiệu quả về không gian lưu trữ. Hệ thống file này được dùng trong các thiết kế nhúng kích thước nhỏ.

Thông tin quản lý (metadata) của cramfs không được nén, nhưng cramfs dùng zlib để nén theo từng trang dữ liệu để cho phép truy cập trang ngẫu nhiên (Các trang được giải nén khi truy cập).

Bạn có thể thử nghiệm cramfs bằng công cụ mkcramfs và thiết bị loopback.

SquashFS

SquashFS là một hệ thống file nén chỉ đọc khác trên Linux cũng rất hữu dụng trong các thiết bị flash. Ta có thể thấy sự hiện diện của hệ thống file này trong rất nhiều bản phân phối Live CD Linux. Ngoài việc hỗ trợ zlib cho việc nén, SquashFS còn dùng giải thuật “Lembel-Ziv-Markov chain Alogrithm” (LZMA) để tối ưu hóa nén dữ liệu cùng với tốc độ.

Cũng giống như cramfs, bạn có thể dùng SquashFS trên một hệ thống Linux với mksquashfs và thiết bị loopback.

---

Hướng phát triển

Theo quy luật của nguồn mở, các phần mềm liên tục tiến hoá, và các hệ thống file flash khác cũng đang được phát triển. Trong đó một hệ thống thú vị là LogFS, có một số ý tưởng rất hay. Chẳng hạn, LogFS giữ một cấu trúc cây trên thiết bị flash để thời gian mount tương đồng với các hệ thống file truyền thống, chẳng hạn ext2. Nó cũng dùng một wandering tree cho việc dọn rác (một dạng của cây B+). Tuy nhiên điều làm cho LogFS trở nên hấp dẫn là nó rất co dãn (scalable) và có thể hỗ trợ các thiết bị flash kích thước lưu trữ lớn.

Ngoài ra còn có những lựa chọn khác đang được phát triển, như UbiFS. Hệ thống file flash là một kiến trúc rất hấp dẫn và sẽ tiếp tục tạo cảm hứng nghiên cứu trong tương lai.

Resources

• See Wikipedia’s overview of flash memory technologies and list of file systems, including disk-based file systems, distributed file systems, and special-purpose file systems (including solid-state media file systems).
• Read more about NAND vs. NOR flash technology.
• Tim’s “Anatomy of the Linux file system” (developerWorks, Oct 2007) introduces the VFS, its major structures, and its architecture. It also provides an introduction to file systems and illustrates how Linux can support so many file systems concurrently.
• Read how JFFS and its successor, JFFS2 (PDF file) take different approaches to flash device management.
• Compare YAFFS to other popular flash file systems.
• LogFS and UbiFS are two new flash file systems that solve many problems associated with current flash file systems.
• The MTD is a generic subsystem for memory devices, such as flash parts. It provides a generic interface between lower-level hardware drivers and the upper layers of the file system.
• Cramfs and SquashFS are read-only compressed file systems for Linux. Both were designed for memory-constrained embedded systems, but you’ll also find SquashFS used in Live CD distributions. Sometimes, you’ll find these used with UnionFS, which implements a union mount for a file system (overlaying one file system on another). SquashFS has the advantage of better compression and performance using LZMA and a set of patches.

Đông Thao dịch từ Anatomy of Linux flash file systems – M. Tim Jones