Sự dư thừa trông như thế này

Mã dự phòng* được sử dụng rộng rãi trong hệ thống máy tính để tăng độ tin cậy của việc lưu trữ dữ liệu. Trong Yandex, chúng được sử dụng trong nhiều dự án. Ví dụ: sử dụng mã dự phòng thay vì sao chép trong bộ lưu trữ đối tượng nội bộ của chúng tôi sẽ tiết kiệm hàng triệu đô la mà không làm giảm độ tin cậy. Nhưng bất chấp việc chúng được sử dụng rộng rãi, những mô tả rõ ràng về cách thức hoạt động của mã dự phòng vẫn rất hiếm. Những người muốn hiểu sẽ phải đối mặt với những điều sau đây (từ Wikipedia):

Tên tôi là Vadim, tại Yandex tôi đang phát triển MDS lưu trữ đối tượng nội bộ. Trong bài viết này, tôi sẽ mô tả một cách đơn giản cơ sở lý thuyết của mã dự phòng (mã Reed-Solomon và LRC). Tôi sẽ cho bạn biết nó hoạt động như thế nào mà không cần đến toán học phức tạp và các thuật ngữ hiếm. Cuối cùng tôi sẽ đưa ra ví dụ về cách sử dụng mã dự phòng trong Yandex.

Tôi sẽ không xem xét chi tiết một số chi tiết toán học, nhưng tôi sẽ cung cấp các liên kết cho những ai muốn tìm hiểu sâu hơn. Tôi cũng sẽ lưu ý rằng một số định nghĩa toán học có thể không nghiêm ngặt, vì bài viết không dành cho các nhà toán học mà dành cho các kỹ sư muốn hiểu bản chất của vấn đề.

* Trong văn học tiếng Anh, mã dư thừa thường được gọi là mã xóa.

1. Bản chất của mã dự phòng

Bản chất của tất cả các mã dự phòng cực kỳ đơn giản: lưu trữ (hoặc truyền) dữ liệu để không bị mất khi xảy ra lỗi (lỗi đĩa, lỗi truyền dữ liệu, v.v.).

Trong hầu hết* mã dự phòng, dữ liệu được chia thành n khối dữ liệu, trong đó m khối mã dự phòng được tính, tạo ra tổng cộng n + m khối. Mã dự phòng được xây dựng theo cách mà n khối dữ liệu có thể được phục hồi chỉ bằng một phần của n + m khối. Tiếp theo, chúng ta sẽ chỉ xem xét các mã dự phòng khối, nghĩa là những mã trong đó dữ liệu được chia thành các khối.

Để khôi phục tất cả n khối dữ liệu, bạn cần có ít nhất n trong số n + m khối, vì bạn không thể lấy được n khối nếu chỉ có n-1 khối (trong trường hợp này, bạn sẽ phải lấy ra 1 khối không khí"). Liệu n khối ngẫu nhiên gồm n + m khối có đủ để khôi phục tất cả dữ liệu không? Điều này phụ thuộc vào loại mã dự phòng, ví dụ: mã Reed-Solomon cho phép bạn khôi phục tất cả dữ liệu bằng cách sử dụng n khối tùy ý, nhưng mã dự phòng LRC thì không phải lúc nào cũng vậy.

Lưu trữ dữ liệu

Trong các hệ thống lưu trữ dữ liệu, theo quy định, mỗi khối dữ liệu và khối mã dự phòng được ghi vào một đĩa riêng. Sau đó, nếu một đĩa tùy ý bị lỗi, dữ liệu gốc vẫn có thể được khôi phục và đọc. Dữ liệu có thể được phục hồi ngay cả khi nhiều đĩa bị lỗi cùng một lúc.

Truyền dữ liệu

Mã dự phòng có thể được sử dụng để truyền dữ liệu một cách đáng tin cậy qua mạng không đáng tin cậy. Dữ liệu được truyền được chia thành các khối và mã dự phòng được tính toán cho chúng. Cả khối dữ liệu và khối mã dự phòng đều được truyền qua mạng. Nếu xảy ra lỗi ở các khối tùy ý (tối đa một số khối nhất định), dữ liệu vẫn có thể được truyền qua mạng mà không gặp lỗi. Ví dụ, mã Reed-Solomon được sử dụng để truyền dữ liệu qua đường truyền quang và trong truyền thông vệ tinh.

* Ngoài ra còn có các mã dự phòng trong đó dữ liệu không được chia thành các khối, chẳng hạn như mã Hamming và mã CRC, được sử dụng rộng rãi để truyền dữ liệu trong mạng Ethernet. Đây là các mã dùng để mã hóa sửa lỗi, chúng được thiết kế để phát hiện lỗi chứ không phải để sửa chúng (mã Hamming cũng cho phép sửa một phần lỗi).

2. Mã Reed-Solomon

Mã Reed-Solomon là một trong những mã dự phòng được sử dụng rộng rãi nhất, được phát minh vào những năm 1960 và được sử dụng rộng rãi lần đầu tiên vào những năm 1980 để sản xuất hàng loạt đĩa compact.

Có hai câu hỏi chính để hiểu mã Reed-Solomon: 1) cách tạo khối mã dự phòng; 2) cách khôi phục dữ liệu bằng khối mã dự phòng. Hãy cùng tìm câu trả lời cho họ.
Để đơn giản, chúng ta sẽ giả sử thêm rằng n=6 và m=4. Các chương trình khác được xem xét bằng cách tương tự.

Cách tạo khối mã dự phòng

Mỗi khối mã dự phòng được tính độc lập với các khối khác. Tất cả n khối dữ liệu được sử dụng để đếm từng khối. Trong sơ đồ bên dưới, X1-X6 là các khối dữ liệu, P1-P4 là các khối mã dự phòng.

Tất cả các khối dữ liệu phải có cùng kích thước và các bit 16 có thể được sử dụng để căn chỉnh. Các khối mã dự phòng thu được sẽ có cùng kích thước với các khối dữ liệu. Tất cả các khối dữ liệu được chia thành các từ (ví dụ: XNUMX bit). Giả sử chúng ta chia các khối dữ liệu thành k từ. Khi đó tất cả các khối mã dự phòng cũng sẽ được chia thành k từ.

Để đếm từ thứ i của mỗi khối dự phòng, từ thứ i của tất cả các khối dữ liệu sẽ được sử dụng. Chúng sẽ được tính theo công thức sau:

Ở đây các giá trị x là các từ của khối dữ liệu, p là các từ của các khối mã dự phòng, tất cả alpha, beta, gamma và delta đều là các số được chọn đặc biệt giống nhau cho tất cả i. Phải nói ngay rằng tất cả những giá trị này không phải là số thông thường mà là các phần tử của trường Galois; cánh đồng.

Tại sao cần có trường Galois?

Có vẻ như mọi thứ đều đơn giản: chúng ta chia dữ liệu thành các khối, các khối thành các từ, sử dụng các từ của khối dữ liệu, chúng ta đếm số từ của các khối mã dự phòng - chúng ta nhận được các khối mã dự phòng. Nói chung đây là cách nó hoạt động, nhưng điều khó khăn nằm ở các chi tiết:

Như đã nêu ở trên, kích thước từ là cố định, trong ví dụ của chúng tôi là 16 bit. Các công thức ở trên cho mã Reed-Solomon sao cho khi sử dụng các số nguyên thông thường, kết quả tính p có thể không biểu diễn được bằng cách sử dụng một từ có kích thước hợp lệ.
Khi khôi phục dữ liệu, các công thức trên sẽ được coi là hệ phương trình cần phải giải mới có thể khôi phục được dữ liệu. Trong quá trình giải có thể phải chia các số nguyên cho nhau dẫn đến một số thực không thể biểu diễn chính xác trong bộ nhớ máy tính.

Những vấn đề này ngăn cản việc sử dụng số nguyên cho mã Reed-Solomon. Lời giải của bài toán là nguyên bản, có thể mô tả như sau: hãy nghĩ ra những số đặc biệt có thể biểu diễn bằng các từ có độ dài cần thiết (ví dụ: 16 bit) và kết quả của việc thực hiện tất cả các phép toán trên đó (cộng , trừ, nhân, chia) cũng sẽ được trình bày trong bộ nhớ máy tính bằng cách sử dụng các từ có độ dài cần thiết.

Những con số “đặc biệt” như vậy đã được toán học nghiên cứu từ lâu; chúng được gọi là trường. Trường là một tập hợp các phần tử với các phép tính cộng, trừ, nhân và chia được xác định cho chúng.

Trường Galois* là các trường mà mỗi phép tính (+, -, *, /) có một kết quả duy nhất cho hai phần tử bất kỳ của trường. Trường Galois có thể được xây dựng cho các số có lũy thừa 2: 2, 4, 8, 16, v.v. (thực ra là lũy thừa của bất kỳ số nguyên tố p nào, nhưng trong thực tế chúng ta chỉ quan tâm đến lũy thừa của 2). Ví dụ: đối với các từ 16 bit, đây là trường chứa 65 phần tử, với mỗi cặp phần tử bạn có thể tìm thấy kết quả của bất kỳ thao tác nào (+, -, *, /). Các giá trị x, p, alpha, beta, gamma, delta từ các phương trình trên sẽ được coi là phần tử của trường Galois để tính toán.

Vì vậy, chúng ta có một hệ phương trình mà chúng ta có thể xây dựng các khối mã dự phòng bằng cách viết một chương trình máy tính thích hợp. Sử dụng cùng một hệ phương trình, bạn có thể thực hiện khôi phục dữ liệu.

* Đây không phải là một định nghĩa chặt chẽ mà là một mô tả.

Cách khôi phục dữ liệu

Cần khôi phục khi thiếu một số khối n + m. Đây có thể là cả khối dữ liệu và khối mã dự phòng. Việc thiếu các khối dữ liệu và/hoặc khối mã dự phòng sẽ có nghĩa là các biến x và/hoặc p tương ứng không xác định được trong các phương trình trên.

Các phương trình của mã Reed-Solomon có thể được xem như một hệ phương trình trong đó tất cả các giá trị alpha, beta, gamma, delta là hằng số, tất cả x và p tương ứng với các khối có sẵn đều là các biến đã biết, còn lại x và p chưa được biết.

Ví dụ: nếu không có khối dữ liệu 1, 2, 3 và khối mã dự phòng 2 thì nhóm từ thứ i sẽ có hệ phương trình sau (ẩn số được đánh dấu màu đỏ):

Chúng ta có một hệ gồm 4 phương trình với 4 ẩn số, nghĩa là chúng ta có thể giải và khôi phục dữ liệu!

Từ hệ phương trình này, một số kết luận rút ra về việc phục hồi dữ liệu cho mã Reed-Solomon (n khối dữ liệu, m khối mã dự phòng):

Dữ liệu có thể được phục hồi nếu có m khối hoặc ít hơn bị mất. Nếu m+1 hoặc nhiều khối bị mất, dữ liệu không thể được khôi phục: không thể giải hệ m phương trình với m + 1 ẩn số.
Để khôi phục dù chỉ một khối dữ liệu, bạn cần sử dụng bất kỳ n khối còn lại nào và bạn có thể sử dụng bất kỳ mã dự phòng nào.

Bạn cần biết điều gì khác

Trong phần mô tả ở trên, tôi tránh một số vấn đề quan trọng đòi hỏi phải đi sâu hơn vào toán học để xem xét. Đặc biệt, tôi không nói bất cứ điều gì về những điều sau đây:

Hệ phương trình mã Reed-Solomon phải có nghiệm (duy nhất) cho mọi tổ hợp ẩn số (không quá m ẩn số). Dựa trên yêu cầu này, các giá trị alpha, beta, gamma và delta được chọn.
Một hệ phương trình phải có khả năng được xây dựng tự động (tùy thuộc vào khối nào không có sẵn) và có thể giải được.
Chúng ta cần xây dựng trường Galois: với một kích thước từ nhất định, có thể tìm thấy kết quả của bất kỳ phép toán (+, -, *, /) nào cho hai phần tử bất kỳ.

Ở cuối bài viết có phần tham khảo tài liệu về những vấn đề quan trọng này.

Lựa chọn n và m

Làm thế nào để chọn n và m trong thực tế? Trong thực tế, trong các hệ thống lưu trữ dữ liệu, mã dự phòng được sử dụng để tiết kiệm dung lượng nên m luôn được chọn nhỏ hơn n. Giá trị cụ thể của chúng phụ thuộc vào một số yếu tố, bao gồm:

Độ tin cậy của việc lưu trữ dữ liệu. M càng lớn thì số lỗi đĩa có thể sống sót càng nhiều, nghĩa là độ tin cậy càng cao.
Lưu trữ dư thừa. Tỷ lệ m/n càng cao thì khả năng dự phòng lưu trữ càng cao và hệ thống sẽ càng đắt tiền.
Yêu cầu thời gian xử lý. Tổng n + m càng lớn thì thời gian đáp ứng yêu cầu sẽ càng lâu. Vì việc đọc dữ liệu (trong quá trình khôi phục) yêu cầu đọc n khối được lưu trữ trên n đĩa khác nhau nên thời gian đọc sẽ được xác định bởi đĩa chậm nhất.

Ngoài ra, việc lưu trữ dữ liệu trong một số DC đặt ra các hạn chế bổ sung đối với việc lựa chọn n và m: nếu 1 DC bị tắt, dữ liệu vẫn phải có sẵn để đọc. Ví dụ: khi lưu trữ dữ liệu ở 3 DC, phải đáp ứng điều kiện sau: m >= n/2, nếu không có thể xảy ra tình huống không thể đọc dữ liệu khi tắt 1 DC.

3. LRC - Mã tái thiết địa phương

Để khôi phục dữ liệu bằng mã Reed-Solomon, bạn phải sử dụng n khối dữ liệu tùy ý. Đây là một bất lợi rất đáng kể đối với các hệ thống lưu trữ dữ liệu phân tán, vì để khôi phục dữ liệu trên một đĩa bị hỏng, bạn sẽ phải đọc dữ liệu từ hầu hết các đĩa khác, tạo ra một tải bổ sung lớn cho các đĩa và mạng.

Các lỗi phổ biến nhất là không thể truy cập được một khối dữ liệu do một đĩa bị lỗi hoặc quá tải. Có thể bằng cách nào đó giảm tải quá mức cho việc phục hồi dữ liệu trong trường hợp (phổ biến nhất) này không? Hóa ra là bạn có thể: có các mã dự phòng LRC dành riêng cho mục đích này.

LRC (Local Reconstruction Codes) là các mã dự phòng được Microsoft phát triển để sử dụng trong Windows Azure Storage. Ý tưởng đằng sau LRC rất đơn giản: chia tất cả các khối dữ liệu thành hai (hoặc nhiều) nhóm và tính toán một phần các khối mã dự phòng cho mỗi nhóm một cách riêng biệt. Sau đó, một số khối mã dự phòng sẽ được tính toán bằng cách sử dụng tất cả các khối dữ liệu (trong LRC, chúng được gọi là mã dự phòng toàn cục), và một số sẽ được tính toán bằng cách sử dụng một trong hai nhóm khối dữ liệu (chúng được gọi là mã dự phòng cục bộ).

LRC được ký hiệu bằng ba số: nrl, trong đó n là số khối dữ liệu, r là số khối mã dự phòng toàn cục, l là số khối mã dự phòng cục bộ. Để đọc dữ liệu khi không có một khối dữ liệu, bạn chỉ cần đọc n/l khối - con số này ít hơn l lần so với mã Reed-Solomon.

Ví dụ, hãy xem xét sơ đồ LRC 6-2-2. X1–X6 — 6 khối dữ liệu, P1, P2 — 2 khối dự phòng toàn cục, P3, P4 — 2 khối dự phòng cục bộ.

Các khối mã dự phòng P1, P2 được tính bằng tất cả các khối dữ liệu. Khối mã dự phòng P3 – sử dụng khối dữ liệu X1-X3, khối mã dự phòng P4 – sử dụng khối dữ liệu X4-X6.

Phần còn lại được thực hiện trong LRC bằng cách tương tự với mã Reed-Solomon. Phương trình đếm số từ của khối mã dự phòng sẽ là:

Để chọn được các số alpha, beta, gamma, delta phải đáp ứng một số điều kiện đảm bảo khả năng phục hồi được dữ liệu (tức là giải hệ phương trình). Bạn có thể đọc thêm về họ trong Bài viết.
Ngoài ra trong thực tế, phép toán XOR còn được sử dụng để tính mã dự phòng cục bộ P3, P4.

Một số kết luận rút ra từ hệ phương trình của LRC:

Để khôi phục 1 khối dữ liệu bất kỳ, chỉ cần đọc n/l khối (trong ví dụ của chúng tôi là n/2).
Nếu các khối r + l không có sẵn và tất cả các khối được bao gồm trong một nhóm thì dữ liệu không thể được khôi phục. Điều này rất dễ giải thích bằng một ví dụ. Giả sử các khối X1–X3 và P3 không khả dụng: đây là các khối r + l từ cùng một nhóm, trong trường hợp của chúng ta là 4. Khi đó ta có hệ 3 phương trình với 4 ẩn chưa giải được.
Trong tất cả các trường hợp khác không có khối r + l (khi có ít nhất một khối từ mỗi nhóm), dữ liệu trong LRC có thể được khôi phục.

Như vậy, LRC vượt trội hơn mã Reed-Solomon trong việc khôi phục dữ liệu sau các lỗi đơn lẻ. Trong mã Reed-Solomon, để khôi phục ngay cả một khối dữ liệu, bạn cần sử dụng n khối và trong LRC, để khôi phục một khối dữ liệu, chỉ cần sử dụng n/l khối (n/2 trong ví dụ của chúng tôi). Mặt khác, LRC kém hơn mã Reed-Solomon về số lỗi tối đa cho phép. Trong các ví dụ trên, mã Reed-Solomon có thể khôi phục dữ liệu cho 4 lỗi bất kỳ và đối với LRC có 2 tổ hợp 4 lỗi khi không thể khôi phục dữ liệu.

Điều quan trọng hơn phụ thuộc vào tình huống cụ thể, nhưng thường thì mức tiết kiệm do tải vượt mức mà LRC mang lại lớn hơn việc lưu trữ kém tin cậy hơn một chút.

4. Mã dự phòng khác

Ngoài mã Reed-Solomon và LRC còn có rất nhiều mã dự phòng khác. Các mã dự phòng khác nhau sử dụng toán học khác nhau. Dưới đây là một số mã dự phòng khác:

Mã dự phòng sử dụng toán tử XOR. Thao tác XOR được thực hiện trên n khối dữ liệu và thu được 1 khối mã dự phòng, tức là sơ đồ n+1 (n khối dữ liệu, 1 mã dự phòng). Được dùng trong RAID 5, trong đó các khối dữ liệu và mã dự phòng được ghi theo chu kỳ vào tất cả các đĩa của mảng.
Thuật toán chẵn-lẻ dựa trên phép toán XOR. Cho phép bạn xây dựng 2 khối mã dự phòng, tức là sơ đồ n+2.
Thuật toán STAR dựa trên hoạt động XOR. Cho phép bạn xây dựng 3 khối mã dự phòng, tức là sơ đồ n+3.
Mã Pyramide là một mã dự phòng khác của Microsoft.

5. Sử dụng trong Yandex

Một số dự án cơ sở hạ tầng Yandex sử dụng mã dự phòng để lưu trữ dữ liệu đáng tin cậy. Dưới đây là một số ví dụ:

Bộ lưu trữ đối tượng nội bộ MDS, mà tôi đã viết ở đầu bài viết.
YT — Hệ thống MapReduce của Yandex.
YDB (Yandex DataBase) - cơ sở dữ liệu phân tán newSQL.

MDS sử dụng mã dự phòng LRC, sơ đồ 8-2-2. Dữ liệu có mã dự phòng được ghi vào 12 đĩa khác nhau ở các máy chủ khác nhau ở 3 DC khác nhau: 4 máy chủ ở mỗi DC. Đọc thêm về điều này trong Bài viết.

YT sử dụng cả mã Reed-Solomon (Sơ đồ 6-3), là mã đầu tiên được triển khai và mã dự phòng LRC (Sơ đồ 12-2-2), trong đó LRC là phương thức lưu trữ ưu tiên.

YDB sử dụng mã dự phòng chẵn-lẻ (Hình 4-2). Về mã dự phòng trong YDB rồi kể trên Highload.

Việc sử dụng các sơ đồ mã dự phòng khác nhau là do các yêu cầu khác nhau đối với hệ thống. Ví dụ: trong MDS, dữ liệu được lưu trữ bằng LRC được đặt trong 3 DC cùng một lúc. Điều quan trọng đối với chúng tôi là dữ liệu vẫn có sẵn để đọc nếu 1 trong số bất kỳ DC nào bị lỗi, do đó các khối phải được phân phối giữa các DC để nếu không có DC nào thì số lượng khối không thể truy cập sẽ không nhiều hơn mức cho phép. Trong sơ đồ 8-2-2, bạn có thể đặt 4 khối vào mỗi DC, sau đó khi tắt bất kỳ DC nào, 4 khối sẽ không khả dụng và dữ liệu có thể được đọc. Dù chúng ta chọn sơ đồ nào khi đặt nó trong 3 DC, trong mọi trường hợp đều phải có (r + l) / n >= 0,5, tức là độ dư thừa bộ nhớ sẽ ít nhất là 50%.

Trong YT, tình huống lại khác: mỗi cụm YT hoàn toàn nằm ở 1 DC (các cụm khác nhau ở các DC khác nhau), do đó không có hạn chế nào như vậy. Sơ đồ 12-2-2 cung cấp khả năng dự phòng 33%, nghĩa là lưu trữ dữ liệu rẻ hơn và nó cũng có thể tồn tại tới 4 lần mất ổ đĩa đồng thời, giống như sơ đồ MDS.

Có nhiều tính năng khác về việc sử dụng mã dự phòng trong hệ thống lưu trữ và xử lý dữ liệu: các sắc thái của việc khôi phục dữ liệu, tác động của việc khôi phục đến thời gian thực hiện truy vấn, tính năng ghi dữ liệu, v.v. Tôi sẽ nói riêng về những tính năng này và các tính năng khác về việc sử dụng mã dự phòng trong thực tế, nếu chủ đề thú vị.