Biến thể B-tree mới cho bộ nhớ Nand flash

Nghiên cứu này giới thiệu một biến thể mới của cây B-tree cho bộ nhớ flash gọi là OMB. Biến thể này giúp làm giảm số lượng các thao tác trên bộ nhớ flash đồng thời tăng hiệu suất sử dụng của bộ nhớ flash do đó tuổi thọ của bộ nhớ flash sẽ được tăng lên.
Nội dung trích xuất từ tài liệu:
Biến thể B-tree mới cho bộ nhớ Nand flash168 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” Biến thể B-tree mới cho bộ nhớ Nand flash Hồ Văn Phi1, Nguyễn Văn Lợi2 1,2 Khoa Công nghệ thông tin, Trường CĐ CNTT hữu nghị Việt - Hàn phihv@viethanit.edu.vn, loinv@viethanit.edu.vn Abstract. Bộ nhớ flash được sử dụng rất phổ biến hiện nay do những ưu điểm nổi bật của loại bộ nhớ này như tốc độ nhanh, gọn nhẹ, tính ổn định cao, tiêu thụ ít điện năng. Tuy nhiên, bên cạnh những ưu điểm nổi bật nói trên bộ nhớ flash vẫn có những nhược điểm đáng chú ý như thuộc tính “Erase-before-write” (xóa dữ liệu trước khi ghi vào một ô nhớ cụ thể), vòng đời hữu hạn (số lần xóa hạn chế -khoảng 10.000~100.000 lần). Những nhược điểm này khiến cho việc triển khai cây chỉ mục B-tree trên bộ nhớ flash giảm hiệu quả đáng kể bởi vì một số lượng lớn các thao tác trên bộ nhớ flash được thực hiện mỗi khi cập nhật dữ liệu trên cây B-tree. Nghiên cứu này giới thiệu một biến thể mới của cây B-tree cho bộ nhớ flash gọi là OMB. Biến thể này giúp làm giảm số lượng các thao tác trên bộ nhớ flash đồng thời tăng hiệu suất sử dụng của bộ nhớ flash do đó tuổi thọ của bộ nhớ flash sẽ được tăng lên. Keywords: Chỉ mục B-tree, bộ nhớ flash, cây B-tree trên flash.1 Giới thiệu Bộ nhớ Flash [1-2] được sử dụng rất phổ biến hiện nay nhờ vào những ưu điểm nổi bật củachúng như tốc độ cao, tiêu thụ ít điện năng, kích thước nhỏ gọn và độ an toàn dữ liệu cao. Tuynhiên, bên cạnh những điểm mạnh đó, bộ nhớ flash vẫn có những điểm yếu cần lưu tâm đó làđặc tính “xóa trước khi ghi” (erase-before-write - không thể ghi đè (overwrite)) và vòng đời hữuhạn (khoảng từ 10.000 đến 100.000 lần xóa trên mỗi block). Bộ nhớ flash có cấu tạo và cơ chếhoạt động hoàn toàn khác với đĩa cứng (HDD) thông thường. Do đó để giúp các hệ điều hànhtruy cập bộ nhớ flash một cách tương tự như HDD, một phần mềm trung gian có tên là FTL[1](Flash Translation Layer) được sử dụng để chuyển đổi địa chỉ logic sang địa chỉ vật lý ánh xạgiữa máy tính và bộ nhớ flash. FTL có 3 chức năng chính đó là: ánh xạ địa chỉ (Address mapping), thu hồi khối nhớ khônghợp lệ (Gabbage collection) và điều phối ghi dữ liệu trên các khối nhớ (Wear leveling). Chứcnăng ánh xạ địa chỉ cung cấp các thuật toán ánh xạ giữa địa chỉ logic và địa chỉ vật lý trên bộnhớ flash. Đã có rất nhiều thuật toán ánh xạ địa chỉ được giới thiệu. Chúng có thể được gomthành 3 nhóm chính: Ánh xạ sector (Sector mapping), ánh xạ khối (Block mapping) và ánh xạlai (Hybrid mapping). Gabbage collection có chức năng thu hồi các khối nhớ không hợp lệ đểtái sử dụng. Khi số lượng khối nhớ hợp lệ trên bộ nhớ flash thấp hơn ngưỡng cho phép, gabbagecollection sẽ được tự động kích hoạt để thu hồi và tái sử dụng các khối không hợp lệ. Wearleveling được sử dụng để điều tiết các khối nhớ để đảm bảo các khối nhớ có tần suất được sửdụng là tương đương nhau. Wear leveling sẽ quyết định khối nhớ nào được sử dụng khi có yêucầu ghi dữ liệu vào bộ nhớ flash. Mặc dù hiệu suất của bộ nhớ flash tăng đáng kể bằng cách sử dụng các thuật toán FTL, tuynhiên, việc triển khai cây chỉ mục B-tree trên bộ nhớ flash vẫn bị giảm đáng kể do một số lượnglớn các thao tác (read/write/erase) trên bộ nhớ flash được thực hiện mỗi khi cập nhật dữ liệu trênHồ Văn Phi, Nguyễn Văn Lợi 169cây B-tree. Để giải quyết vấn đề này, đã có nhiều lược đồ cây chỉ mục B-tree cho bộ nhớ flashđược giới thiệu. Tuy nhiên, những lược đồ đó vẫn tồn tại một số nhược điểm như giảm hiệu suấthoạt động và vòng đời của bộ nhớ flash hoặc nguy cơ mất dữ liệu khi nguồn điện bị cắtđột ngột. Nghiên cứu này giới một biến thể mới của cây chỉ mục B-tree cho bộ nhớ flash gọi lại OMB.Biến thể có cơ chế tách nút khác với cây chỉ mục B-tree nguyên mẫu gọi là cơ chế tràn. Nếumột nút lá được điền đầy bởi các giá trị khóa liên tiếp thì toàn bộ nút đó được ghi vào bộ nhớthay vì tách thành 2 nút khác nhau như cây B-tree nguyên thủy. Ngoài ra, khi một nút có sốlượng giá trị khóa giữa ngưỡng cho phép, nút đó vẫn giữ nguyên mà không phải bị ghép với cácnút anh em lân cận của nó. Cơ chế tràn giúp cho biến thể mới này giảm một số lượng đáng kểcác thao tác của bộ nhớ flash. Bên cạnh đó nó cũng giúp cho việc sử dụng không gian nhớ trongcác khối nhớ cũng đạt hiệu suất cao. Kết quả thử nghiệm cho thấy giải pháp mới này giúp cho việc triển khai cây chỉ mục B-treetrên bộ nhớ flash có hiệu quả cao, tiết kiệm được không gian nhớ và kéo dài tuổi thọ của bộ nhớflash bởi vì OMB làm giảm số lượng thao tác xóa của bộ nhớ flash.2 Kiến thức cơ bản và nghiên cứu liên quan Flash là một loại thiết bị bộ nhớ thứ cấp được sử dụng rất phổ biến hiện nay. Chúng có mặttrong các thiết bị điện tử như máy tính, điện thoại thông minh, các thiết bị nhúng, thẻ nhớ,USB,... Khác với đĩa cứng thông thường, bộ nhớ flash gồm một dãy các thẻ nhớ Nand flash. Bộnhớ flash được tổ chức thành các khối nhớ; mỗi khối nhớ chứa một số lượng cụ thể các trangnhớ (32, 64, 128 trang). Trang nhớ là đơn vị nhỏ nhất của thao tác đọc và ghi trong khi đó khốinhớ là đơn vị nhỏ nhất của thao tác xóa. Bộ nhớ flash hỗ trợ 3 thao tác cơ bản là đọc, ghi vàxóa. Đọc là thao tác có tốc độ nhanh nhất tiếp đến là thao tác ghi. Một thao tác ghi mất khoảng2ms; chậm hơn 10 lần so với thao tác đọc. Và chậm nhất là thao tác xóa, chậm hơn 10 lần so vớithao tác ghi. Hiện nay, bộ nhớ flash có vòng đời khoảng 10.000 - 100.000 lần xóa khối. Nếu sốlần xóa của một khối vượt quá ngưỡng này thì khối đó không còn khả năng sử dụng. Cây chỉ mục B-tree là một cấu trúc dữ liệu được sử dụng rộng rãi trong các hệ quản trị cơ sởdữ liệu và hệ điều hành nhờ vào tốc độ truy cập nhanh của nó. Tuy nhiên, ...