Thuật toán phục hồi là tập hợp các nguyên lý và thủ tục thuật toán được thiết kế trong hệ quản trị cơ sở dữ liệu nhằm tái thiết trạng thái nhất quán và bảo đảm tính bền vững của dữ liệu sau khi xảy ra sự cố phần cứng, lỗi phần mềm hoặc sập nguồn hệ thống. Cơ chế này đóng vai trò sống còn trong việc hiện thực hóa các thuộc tính nguyên tử tính và độ bền vững của mô hình giao dịch, duy trì tính toàn vẹn của thông tin mà không đòi hỏi can thiệp thủ công. Bài viết này trình bày các phân loại sự cố, ma trận chính sách quản lý bộ đệm, giao thức ghi nhật ký trước, kiến trúc kinh điển của thuật toán ARIES cùng những cải tiến hiện đại trong môi trường lưu trữ đám mây và bộ nhớ bất biến.
Phân loại sự cố và mục tiêu phục hồi
Trong quá trình vận hành của các hệ thống quản trị dữ liệu quy mô lớn, sự cố có thể phát sinh từ nhiều tầng kiến trúc khác nhau. Nhằm thiết lập các quy trình xử lý tối ưu, các nhà nghiên cứu phân chia sự cố thành các nhóm cơ bản:
- Lỗi giao dịch: Xảy ra khi một tiến trình giao dịch nội bộ gặp lỗi logic nghiệp vụ, vi phạm ràng buộc toàn vẹn, gặp tình trạng bế tắc (deadlock) hoặc nhận tín hiệu hủy bỏ chủ động từ ứng dụng. Mục tiêu phục hồi trong tình huống này là hoàn tác cục bộ toàn bộ các hiệu ứng sửa đổi mà giao dịch đó đã thực hiện trên bộ nhớ đệm hoặc đĩa mà không làm gián đoạn các giao dịch đồng thời khác.
- Lỗi sập hệ thống: Xảy ra do sự cố mất nguồn điện đột ngột, lỗi hạt nhân hệ điều hành hoặc hư hỏng bộ nhớ truy cập ngẫu nhiên (RAM). Khi hệ thống sập, toàn bộ nội dung của bộ nhớ tạm thời bị mất hoàn toàn, trong khi dữ liệu trên các thiết bị lưu trữ thứ cấp không bay hơi vẫn được bảo toàn nguyên vẹn. Thuật toán phục hồi phải nhận diện các giao dịch đã hoàn tất để tái lập kết quả, đồng thời dọn dẹp các giao dịch đang dở dang tại thời điểm sập nguồn.
- Lỗi phương tiện lưu trữ: Xảy ra khi thiết bị lưu trữ bền vững gặp hư hỏng vật lý, lỗi cung từ tính (bad sectors) hoặc sự cố hỏng đĩa cứng. Phương thức phục hồi đòi hỏi phải tái tạo dữ liệu từ các bản sao lưu lưu trữ kết hợp với các chuỗi nhật ký lịch sử được lưu trữ tại các vị trí độc lập.
Mục tiêu tối thượng của mọi thuật toán phục hồi là bảo đảm trọn vẹn 4 thuộc tính ACID của giao dịch do Haerder và Reuter (1983) tổng kết, đặc biệt là tính nguyên tử (mọi thao tác của giao dịch hoặc được phản ánh đầy đủ, hoặc không để lại bất kỳ dấu vết nào) và tính bền vững (khi giao dịch đã được xác nhận hoàn tất thành công, các thay đổi của nó sẽ không bao giờ bị mất đi ngay cả khi sập nguồn xảy ra ngay sau đó).
Ma trận chính sách quản lý bộ đệm
Để tối ưu hóa hiệu năng nhập xuất, hệ quản trị cơ sở dữ liệu duy trì một vùng đệm bộ nhớ (buffer pool) chứa các trang dữ liệu được đọc từ đĩa. Mối quan hệ giữa bộ nhớ đệm và thiết bị lưu trữ bền vững được định hình bởi hai quyết định kiến trúc độc lập:
Chính sách STEAL và NO-STEAL
Chính sách liên quan đến việc bộ đệm có được phép ghi đè các trang dữ liệu đã bị sửa đổi (dirty pages) xuống đĩa trước khi giao dịch thực hiện sửa đổi đó cam kết (commit) hay không:
- STEAL: Hệ thống cho phép bộ quản lý bộ đệm ghi một trang bị sửa đổi bởi một giao dịch đang hoạt động xuống đĩa để giải phóng khung bộ nhớ cho các tác vụ khác. Chính sách này cải thiện hiệu suất sử dụng RAM nhưng đòi hỏi thuật toán phục hồi phải có năng lực hoàn tác (UNDO) nhằm xóa bỏ các sửa đổi chưa cam kết nếu giao dịch sau đó bị hủy bỏ hoặc hệ thống sập nguồn.
- NO-STEAL: Trang bị sửa đổi tuyệt đối không được phép ghi xuống đĩa chừng nào giao dịch sở hữu chưa cam kết thành công. Chính sách này loại bỏ nhu cầu hoàn tác nhưng làm suy giảm nghiêm trọng khả năng linh hoạt của bộ quản lý bộ đệm khi xử lý các giao dịch lớn có khối lượng dữ liệu vượt quá kích thước RAM.
Chính sách FORCE và NO-FORCE
Chính sách liên quan đến thời điểm các trang bị sửa đổi của một giao dịch bắt buộc phải được ghi bền vững xuống đĩa:
- FORCE: Khi một giao dịch yêu cầu cam kết, hệ thống bắt buộc phải đẩy toàn bộ các trang dữ liệu mà giao dịch đó đã thay đổi xuống đĩa trước khi trả về thông báo thành công cho người dùng. Cách tiếp cận này loại bỏ nhu cầu tái lập (REDO) khi sập nguồn nhưng sinh ra khối lượng thao tác nhập xuất ngẫu nhiên khổng lồ, gây nghẽn nghiêm trọng thông lượng xử lý.
- NO-FORCE: Giao dịch được phép hoàn tất cam kết ngay khi bản ghi nhật ký của nó được ghi bền vững, trong khi các trang dữ liệu thực tế vẫn có thể nằm lại trong bộ đệm và chỉ được ghi xuống đĩa dần dần trong nền. Chính sách này tối ưu hóa tối đa hiệu năng ghi nhưng đòi hỏi thuật toán phục hồi phải có năng lực tái lập (REDO) để áp dụng lại các thay đổi đã cam kết nhưng chưa kịp đẩy xuống đĩa vật lý trước khi sập nguồn xảy ra.
| Chính sách phối hợp | Yêu cầu hoàn tác (UNDO) | Yêu cầu tái lập (REDO) | Đặc điểm hiệu năng thực tế |
|---|---|---|---|
| NO-STEAL / FORCE | Không cần | Không cần | Hiệu năng rất thấp do nghẽn nhập xuất ngẫu nhiên và giới hạn dung lượng bộ đệm |
| STEAL / FORCE | Bắt buộc có | Không cần | Ghi đĩa cưỡng bức khi cam kết, độ trễ giao dịch cao |
| NO-STEAL / NO-FORCE | Không cần | Bắt buộc có | Không thể xử lý giao dịch cập nhật vượt quá kích thước RAM khả dụng |
| STEAL / NO-FORCE | Bắt buộc có | Bắt buộc có | Hiệu năng cao nhất, là tiêu chuẩn công nghiệp trong các hệ quản trị hiện đại |
Theo phân loại kinh điển của Haerder và Reuter (1983), sự kết hợp giữa chính sách STEAL và NO-FORCE là lựa chọn mang lại thông lượng xử lý cao nhất và khả năng mở rộng tối ưu. Tuy nhiên, kiến trúc này đặt gánh nặng lớn nhất lên thuật toán phục hồi vì hệ thống bắt buộc phải hỗ trợ đầy đủ cả hai năng lực UNDO và REDO.
Giao thức ghi nhật ký trước và cấu trúc LSN
Để hiện thực hóa chính sách STEAL và NO-FORCE một cách an toàn, mọi hệ quản trị cơ sở dữ liệu hiện đại đều dựa trên giao thức ghi nhật ký trước (Write-Ahead Logging, viết tắt là WAL). Giao thức WAL thiết lập hai quy tắc nghiêm ngặt:
- Mọi sửa đổi trên trang dữ liệu phải được mô tả bằng một bản ghi nhật ký tương ứng, và bản ghi nhật ký này bắt buộc phải được xả xuống thiết bị lưu trữ bền vững trước khi trang dữ liệu thực tế được ghi xuống đĩa vật lý (đáp ứng điều kiện cho thao tác hoàn tác UNDO).
- Tất cả các bản ghi nhật ký của một giao dịch phải được ghi bền vững xuống đĩa trước khi giao dịch đó được xem là đã cam kết thành công (đáp ứng điều kiện cho thao tác tái lập REDO).
Để quản lý chặt chẽ trật tự các thao tác, hệ thống sử dụng khái niệm số thứ tự nhật ký (Log Sequence Number, viết tắt là LSN). Mỗi bản ghi nhật ký được gán một chỉ số tăng đơn điệu. Đồng thời, trên phần tiêu đề của mỗi trang dữ liệu luôn chứa một trường đặc tả chỉ số cập nhật:
với là số thứ tự nhật ký gắn với thao tác sửa đổi gần nhất được thực thi trên trang dữ liệu đó, và là số thứ tự nhật ký lớn nhất đã được xả an toàn xuống thiết bị lưu trữ bền vững. Bất đẳng thức trên là điều kiện tiên quyết mà bộ quản lý bộ đệm bắt buộc phải kiểm tra trước khi ghi một trang xuống đĩa: nếu giá trị trên trang lớn hơn giá trị nhật ký đã xả, hệ thống phải thực hiện xả bộ đệm nhật ký xuống đĩa trước khi tiến hành ghi trang.
Thuật toán ARIES: Ba pha phục hồi kinh điển
Được công bố bởi C. Mohan và các cộng sự tại trung tâm nghiên cứu IBM vào năm 1992 (Mohan và cs., 1992), thuật toán ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) đã trở thành chuẩn mực mẫu mực cho mọi công nghệ phục hồi cơ sở dữ liệu thương mại và mã nguồn mở. ARIES vận hành dựa trên triết lý lặp lại lịch sử (repeating history) để tái thiết chính xác trạng thái của hệ thống tại thời điểm trước khi sập nguồn.
Quy trình phục hồi của thuật toán ARIES sau sự cố sập nguồn bao gồm 3 pha tuần tự:
1. Pha phân tích
Pha phân tích quét tệp nhật ký xuôi chiều bắt đầu từ điểm kiểm tra gần nhất cho đến cuối tệp nhật ký để khôi phục lại bức tranh hoạt động của hệ thống tại thời điểm xảy ra sự cố. Hai cấu trúc dữ liệu quan trọng được tái thiết lập trong pha này:
- Bảng giao dịch (Transaction Table): Ghi nhận danh sách tất cả các giao dịch đang hoạt động tại thời điểm sập nguồn cùng trạng thái và chỉ số nhật ký thao tác gần nhất của từng giao dịch. Các giao dịch chưa cam kết được đánh dấu là những giao dịch thất bại cần phải hoàn tác trong pha cuối cùng.
- Bảng trang bẩn (Dirty Page Table): Lưu trữ danh sách các trang dữ liệu đang nằm trong bộ nhớ đệm có chứa sửa đổi nhưng chưa được đẩy xuống đĩa, kèm theo chỉ số nhật ký của thao tác đầu tiên làm bẩn trang đó (RecLSN). Điểm bắt đầu của pha tái lập được xác định bởi giá trị nhỏ nhất trong số các RecLSN của bảng trang bẩn.
2. Pha tái lập
Khác biệt căn bản của ARIES so với các mô hình trước đó là nguyên lý lặp lại lịch sử: hệ thống tái lập lại toàn bộ các hành động đã diễn ra, bao gồm cả các thao tác của những giao dịch đã cam kết lẫn các thao tác của những giao dịch chưa cam kết hoặc bị hủy bỏ. Pha tái lập quét nhật ký xuôi chiều từ điểm bắt đầu tái lập đến cuối nhật ký.
Đối với mỗi bản ghi nhật ký cập nhật, hệ thống so sánh chỉ số của bản ghi với giá trị trên trang dữ liệu thực tế đọc từ đĩa. Thao tác tái lập chỉ được thực thi lại nếu trang dữ liệu trên đĩa chưa phản ánh sửa đổi đó, tức là khi chỉ số trên trang nhỏ hơn chỉ số của bản ghi nhật ký. Việc tái lập cả các giao dịch thất bại giúp hệ thống khôi phục hoàn hảo trạng thái cấu trúc của cơ sở dữ liệu trước khi bắt đầu thu hồi các thay đổi không hợp lệ.
3. Pha hoàn tác
Pha hoàn tác tiến hành quét nhật ký ngược chiều từ cuối nhật ký trở về trước để hủy bỏ tuần tự mọi tác động của các giao dịch thất bại. Điểm đặc sắc nhất trong thiết kế của ARIES là việc sử dụng bản ghi bù (Compensation Log Record, viết tắt là CLR) cho mỗi hành động hoàn tác.
Mỗi khi một thay đổi bị đảo ngược, một bản ghi bù được ghi vào nhật ký trước khi thực hiện sửa đổi trên bộ đệm. Bản ghi bù chứa một con trỏ tham chiếu trực tiếp đến bản ghi trước đó của giao dịch cần được hoàn tác tiếp theo. Cơ chế này bảo đảm tính lũy đẳng (idempotence) tuyệt đối: nếu hệ thống tiếp tục bị sập nguồn lần nữa ngay trong khi đang thực thi pha hoàn tác, chu kỳ phục hồi kế tiếp sẽ đọc các bản ghi bù và tiếp tục công việc dở dang mà không bao giờ lặp lại việc hoàn tác những thao tác đã được đảo ngược trước đó.
Kỹ thuật điểm kiểm tra mờ
Nếu không có cơ chế thu hẹp phạm vi quét nhật ký, thời gian phục hồi sau sập nguồn sẽ tăng dần theo độ dài của toàn bộ lịch sử vận hành hệ thống. Kỹ thuật điểm kiểm tra mờ (fuzzy checkpointing) được thiết kế nhằm hạn chế tối đa độ dài đoạn nhật ký cần xử lý mà không làm đình trệ các luồng giao dịch trực tuyến.
Thay vì dừng toàn bộ hệ thống để đẩy tất cả các trang bẩn xuống đĩa như phương pháp điểm kiểm tra đồng bộ truyền thống, điểm kiểm tra mờ định kỳ ghi nhận một bản ghi điểm kiểm tra vào nhật ký bao gồm bản sao trạng thái của Bảng giao dịch và Bảng trang bẩn tại thời điểm đó. Các trang dữ liệu bẩn tiếp tục được đẩy xuống đĩa một cách bất đồng bộ trong nền, cho phép thu hồi không gian lưu trữ nhật ký cũ mà vẫn đảm bảo tính sẵn sàng cao cho các ứng dụng thực tế.
Sự tiến hóa của kiến trúc phục hồi hiện đại
Sự chuyển dịch mạnh mẽ của phần cứng lưu trữ và điện toán đám mây trong thập kỷ qua đã thúc đẩy các nghiên cứu tái cấu trúc toàn diện thuật toán phục hồi:
- Phục hồi trên bộ nhớ bất biến: Với sự xuất hiện của các công nghệ bộ nhớ bất biến (Non-Volatile Memory, NVM) có khả năng ghi nhớ không bay hơi với độ trễ thấp và khả năng truy cập theo từng byte, Arulraj, Pavlo và Dulloor (2015) đã chứng minh rằng các kiến trúc phục hồi có thể loại bỏ hoàn toàn cơ chế ghi đĩa truyền thống, rút ngắn thời gian khôi phục trạng thái từ vài phút xuống dưới 1 giây.
- Kiến trúc đám mây tách rời lưu trữ: Trong các cơ sở dữ liệu đám mây quy mô lớn, kiến trúc Amazon Aurora do Verbitski và 9 đồng tác giả công bố vào năm 2017 (Verbitski và cs., 2017) đã hiện thực hóa triết lý biến nhật ký thành cơ sở dữ liệu. Toàn bộ quy trình tạo bản ghi nhật ký và tái lập dữ liệu được phân tán trực tiếp xuống tầng lưu trữ phân tán, giải phóng máy chủ tính toán khỏi gánh nặng phục hồi cục bộ khi xảy ra sự cố.
- Tối ưu hóa cho ổ đĩa trạng thái rắn tốc độ cao: Nghiên cứu của Haubenschild và các cộng sự (Haubenschild và cs., 2020) chỉ ra rằng với băng thông cực lớn của các thiết bị NVMe hiện đại, việc sử dụng các cấu trúc khóa tập trung và đồng bộ hóa nhật ký theo nhóm của thuật toán ARIES truyền thống trở thành nút thắt cổ chai chính, mở ra các mô hình ghi nhật ký phi tập trung và tái lập song song không khóa.
Thách thức và vấn đề còn mở
Dù đã đạt được mức độ trưởng thành cao sau nhiều thập kỷ phát triển, công nghệ thuật toán phục hồi vẫn đối mặt với các bài toán mở phức tạp:
- Phục hồi trong cơ sở dữ liệu phân tán xuyên khu vực: Đảm bảo tính nhất quán và độ bền vững trên các cụm máy phân tán đa vùng địa lý đòi hỏi sự kết hợp phức tạp giữa thuật toán phục hồi nội bộ và các giao thức đồng thuận phân tán, tạo ra thách thức lớn về độ trễ mạng.
- Cân bằng giữa hiệu năng thời gian chạy và thời gian khôi phục: Việc tăng tần suất ghi nhật ký và tạo điểm kiểm tra giúp rút ngắn thời gian đưa hệ thống trở lại hoạt động sau sự cố, nhưng lại tiêu tốn tài nguyên nhập xuất quý giá trong quá trình xử lý bình thường. Việc tự động hóa điều chỉnh các tham số phục hồi dựa trên tải công việc động vẫn là một hướng nghiên cứu học thuật then chốt.