* Đây là phần số 1 của một loạt nơi mọi người có thể đặt câu hỏi về Geth và tôi sẽ cố gắng trả lời câu hỏi được bình chọn cao nhất mỗi tuần với một bài viết ngắn. Câu hỏi được bình chọn cao nhất của tuần này là: Bạn có thể chia sẻ cấu trúc db phẳng khác với cấu trúc cũ như thế nào không? *
Trạng thái trong Ethereum
Trước khi đi sâu vào cấu trúc tăng tốc, hãy tóm tắt lại một chút Ethereum gọi là gì tiểu bang và cách nó được lưu trữ hiện tại ở các cấp độ trừu tượng khác nhau của nó.
Ethereum duy trì hai loại trạng thái khác nhau: tập hợp các tài khoản; và một tập hợp các vị trí lưu trữ cho mỗi tài khoản hợp đồng. Từ một quan điểm hoàn toàn trừu tượngcả hai đều là ánh xạ khóa / giá trị đơn giản. Tập hợp các tài khoản ánh xạ địa chỉ đến số dư, số dư của chúng, v.v. Một vùng lưu trữ của một hợp đồng duy nhất ánh xạ các khóa tùy ý – được xác định và sử dụng bởi hợp đồng – thành các giá trị tùy ý.
Thật không may, trong khi lưu trữ các cặp khóa-giá trị này dưới dạng dữ liệu phẳng sẽ rất hiệu quả, việc xác minh tính đúng đắn của chúng trở nên khó tính toán. Mỗi khi thực hiện sửa đổi, chúng tôi cần băm tất cả dữ liệu đó lại từ đầu.
Thay vì luôn luôn băm toàn bộ tập dữ liệu, chúng ta có thể chia nó thành các phần nhỏ liền kề và xây dựng một cây trên đầu trang! Dữ liệu hữu ích ban đầu sẽ nằm trong các lá và mỗi nút bên trong sẽ là một hàm băm của mọi thứ bên dưới nó. Điều này sẽ cho phép chúng tôi chỉ tính toán lại một số hàm băm logarit khi một cái gì đó được sửa đổi. Cấu trúc dữ liệu này thực sự có một cái tên, đó là cái tên nổi tiếng Cây Merkle.
Thật không may, chúng tôi vẫn còn thiếu một chút về độ phức tạp tính toán. Bố cục cây Merkle ở trên rất hiệu quả trong việc kết hợp các sửa đổi đối với dữ liệu hiện có, nhưng việc chèn và xóa làm thay đổi ranh giới phân đoạn và làm mất hiệu lực tất cả các các băm được tính toán.
Thay vì phân tích tập dữ liệu một cách mù quáng, chúng ta có thể sử dụng chính các khóa để tổ chức dữ liệu thành định dạng cây dựa trên các tiền tố chung! Bằng cách này, việc chèn hoặc xóa sẽ không thay đổi tất cả các nút, thay vào đó sẽ chỉ thay đổi đường dẫn logarit từ gốc đến lá. Cấu trúc dữ liệu này được gọi là Cây Patricia.
Kết hợp hai ý tưởng – bố cục cây của cây Patricia và thuật toán băm của cây Merkle – và bạn sẽ có một Cây Merkle Patriciacấu trúc dữ liệu thực tế được sử dụng để biểu thị trạng thái trong Ethereum. Đảm bảo độ phức tạp lôgarit cho các sửa đổi, chèn, xóa và xác minh! Một phần bổ sung nhỏ là các phím được băm trước khi chèn để cân bằng các lần thử.
Lưu trữ trạng thái trong Ethereum
Mô tả trên giải thích tại sao Ethereum lưu trữ trạng thái của nó trong một cây Merkle Patricia. Than ôi, nhanh như các thao tác mong muốn, mọi lựa chọn đều là sự đánh đổi. Giá của cập nhật logarit và xác minh logarit Là lần đọc logarit và lưu trữ logarit vì mọi chìa khóa riêng lẻ. Điều này là do mọi nút trie nội bộ cần được lưu vào đĩa riêng lẻ.
Tôi không có con số chính xác cho độ sâu của trie tài khoản vào thời điểm hiện tại, nhưng khoảng một năm trước, chúng tôi đã bão hòa độ sâu là 7. Điều này có nghĩa là mỗi thao tác trie (ví dụ: đọc số dư, ghi số dư) chạm ít nhất 7 -8 nút nội bộ, do đó sẽ thực hiện ít nhất 7-8 truy cập cơ sở dữ liệu liên tục. LevelDB cũng sắp xếp dữ liệu của nó thành tối đa 7 cấp, vì vậy sẽ có thêm một hệ số nhân từ đó. Kết quả ròng là một Độc thân truy cập trạng thái dự kiến sẽ khuếch đại thành 25-50 ngẫu nhiên truy cập đĩa. Nhân điều này với tất cả trạng thái đọc và ghi rằng tất cả các giao dịch trong một khối chạm và bạn có đáng sợ con số.
[Of course all client implementations try their best to minimize this overhead. Geth uses large memory areas for caching trie nodes; and also uses in-memory pruning to avoid writing to disk nodes that get deleted anyway after a few blocks. That’s for a different blog post however.]
Kinh khủng như những con số này, đây là chi phí vận hành một nút Ethereum và có khả năng xác minh bằng mã hóa mọi trạng thái mọi lúc. Nhưng chúng ta có thể làm tốt hơn không?
Không phải tất cả các quyền truy cập đều được tạo ra như nhau
Ethereum dựa trên các bằng chứng mật mã cho trạng thái của nó. Không có cách nào xung quanh việc khuếch đại đĩa nếu chúng ta muốn duy trì khả năng xác minh tất cả dữ liệu của mình. Điều đó nói rằng, chúng tôi có thể – và làm – tin tưởng vào dữ liệu chúng tôi đã xác minh.
Không có ích gì để xác minh và xác minh lại mọi mục trạng thái, mỗi khi chúng tôi kéo nó lên khỏi đĩa. Cây Merkle Patricia rất cần thiết cho việc viết, nhưng nó là một chi phí cho việc đọc. Chúng ta không thể loại bỏ nó, và chúng ta không thể làm thon gọn nó; nhưng điều đó không có nghĩa là chúng ta nhất thiết phải sử dụng nó ở mọi nơi.
Một nút Ethereum truy cập trạng thái ở một số nơi khác nhau:
- Khi nhập một khối mới, việc thực thi mã EVM thực hiện một số trạng thái đọc và ghi cân bằng hơn hoặc ít hơn. Tuy nhiên, khối từ chối dịch vụ có thể đọc nhiều hơn ghi.
- Khi một toán tử nút truy xuất trạng thái (ví dụ: eth_call và gia đình), việc thực thi mã EVM chỉ thực hiện đọc (nó cũng có thể ghi, nhưng những thứ đó sẽ bị loại bỏ ở cuối và không tồn tại).
- Khi một nút đang đồng bộ hóa, nó đang yêu cầu trạng thái từ các nút ở xa cần đào nó lên và phục vụ nó qua mạng.
Dựa trên các mẫu truy cập ở trên, nếu chúng ta có thể đọc ngắn mạch không đạt đến trạng thái trie, một loạt các hoạt động của nút sẽ trở thành đáng kể nhanh hơn. Nó thậm chí có thể cho phép một số mẫu truy cập mới (như lặp lại trạng thái) mà trước đây rất tốn kém.
Tất nhiên, luôn có sự đánh đổi. Nếu không loại bỏ bộ ba, bất kỳ cấu trúc tăng tốc mới nào cũng tăng thêm chi phí. Câu hỏi đặt ra là liệu chi phí bổ sung có cung cấp đủ giá trị để đảm bảo không?
Trở về bản gốc
Chúng tôi đã xây dựng cây Merkle Patricia kỳ diệu này để giải quyết tất cả các vấn đề của chúng tôi và bây giờ chúng tôi muốn tìm hiểu về nó để đọc. Chúng ta nên sử dụng cấu trúc tăng tốc nào để đọc nhanh trở lại? Chà, nếu chúng ta không cần trie, chúng ta không cần bất kỳ sự phức tạp nào được giới thiệu. Chúng ta có thể quay trở lại nguồn gốc.
Như đã đề cập ở phần đầu của bài đăng này, lý tưởng lý thuyết lưu trữ dữ liệu cho trạng thái của Ethereum là một kho lưu trữ giá trị-khóa đơn giản (riêng biệt cho các tài khoản và từng hợp đồng). Tuy nhiên, không có những ràng buộc của cây Merkle Patricia, “không có gì” ngăn cản chúng ta thực sự triển khai giải pháp lý tưởng!
Một thời gian trước, Geth đã giới thiệu ảnh chụp nhanh cấu trúc tăng tốc (không được bật theo mặc định). Ảnh chụp nhanh là một cái nhìn đầy đủ về trạng thái Ethereum tại một khối nhất định. Triển khai trừu tượng một cách khôn ngoan, nó là nơi chứa tất cả các tài khoản và vùng lưu trữ, được thể hiện bằng một kho khóa-giá trị phẳng.
Bất cứ khi nào chúng tôi muốn truy cập vào một tài khoản hoặc nơi lưu trữ, chúng tôi chỉ phải trả 1 lần tra cứu LevelDB thay vì 7-8 như mỗi trie. Cập nhật ảnh chụp nhanh về lý thuyết cũng đơn giản, sau khi xử lý một khối, chúng tôi thực hiện thêm 1 lần ghi LevelDB cho mỗi vị trí cập nhật.
Ảnh chụp nhanh về cơ bản làm giảm lần đọc từ O (log n) đến O (1) (nhân với chi phí LevelDB) với chi phí tăng ghi từ O (log n) sang O (1 + log n) (nhân với chi phí LevelDB) và tăng dung lượng lưu trữ trên đĩa từ O (n log n) đến O (n + n log n).
Chi tiết về quỷ dữ
Việc duy trì một ảnh chụp nhanh có thể sử dụng được về trạng thái Ethereum có sự phức tạp của nó. Miễn là các khối đến từng khối một, luôn xây dựng trên khối cuối cùng, thì cách tiếp cận đơn giản của việc hợp nhất sẽ thay đổi thành các tác phẩm chụp nhanh. Tuy nhiên, nếu có một reorg nhỏ (thậm chí một khối), chúng tôi đang gặp rắc rối, vì không có hoàn tác. Ghi liên tục là hoạt động một chiều đối với biểu diễn dữ liệu phẳng. Để làm cho vấn đề tồi tệ hơn, việc truy cập trạng thái cũ hơn (ví dụ: 3 khối cũ đối với một số DApp hoặc 64+ để đồng bộ hóa nhanh / snap) là không thể.
Để khắc phục hạn chế này, ảnh chụp nhanh của Geth bao gồm hai thực thể: một lớp đĩa liên tục là ảnh chụp nhanh hoàn chỉnh của một khối cũ hơn (ví dụ: HEAD-128); và một cây các lớp khác biệt trong bộ nhớ tập hợp các ghi trên đầu trang.
Bất cứ khi nào một khối mới được xử lý, chúng tôi không hợp nhất việc ghi trực tiếp vào lớp đĩa, thay vào đó chỉ tạo một lớp khác trong bộ nhớ mới với các thay đổi. Nếu có đủ các lớp khác biệt trong bộ nhớ được xếp chồng lên trên, thì các lớp dưới cùng sẽ bắt đầu được hợp nhất với nhau và cuối cùng được đẩy vào đĩa. Bất cứ khi nào một mục trạng thái được đọc, chúng tôi bắt đầu ở lớp khác biệt trên cùng và tiếp tục quay ngược lại cho đến khi chúng tôi tìm thấy nó hoặc chạm đến đĩa.
Biểu diễn dữ liệu này rất mạnh mẽ vì nó giải quyết được rất nhiều vấn đề. Vì các lớp khác biệt trong bộ nhớ được tập hợp thành một cây, các reorgs nông hơn 128 khối có thể chỉ cần chọn lớp khác biệt thuộc về khối mẹ và xây dựng tiếp tục từ đó. DApp và bộ đồng bộ từ xa cần trạng thái cũ hơn có quyền truy cập vào 128 cái gần đây. Chi phí tăng thêm 128 lần tra cứu bản đồ, nhưng 128 lần tra cứu trong bộ nhớ là các đơn hàng có cường độ nhanh hơn 8 lần đọc đĩa được khuếch đại 4x-5x bởi LevelDB.
Tất nhiên, có rất nhiều và rất nhiều gotchas và cảnh báo. Không đi vào quá nhiều chi tiết, một danh sách nhanh các điểm tốt hơn là:
- Tự hủy (và xóa) là những con thú đặc biệt vì chúng cần ngắn mạch đi xuống các lớp khác nhau.
- Nếu có một bản reorg sâu hơn lớp đĩa liên tục, ảnh chụp nhanh cần được loại bỏ hoàn toàn và tạo lại. Cái này rất đắt tiền.
- Khi tắt máy, các lớp khác biệt trong bộ nhớ cần được lưu vào nhật ký và được tải sao lưu, nếu không ảnh chụp nhanh sẽ trở nên vô dụng khi khởi động lại.
- Sử dụng lớp khác biệt dưới cùng nhất làm bộ tích lũy và chỉ chuyển vào đĩa khi nó vượt quá mức sử dụng bộ nhớ. Điều này cho phép ghi trùng lặp cho các vị trí giống nhau trên các khối.
- Phân bổ bộ nhớ đệm đọc cho lớp đĩa để các hợp đồng truy cập lặp đi lặp lại cùng một khe cắm cổ không gây ra số lần truy cập đĩa.
- Sử dụng bộ lọc nở tích lũy trong các lớp khác biệt trong bộ nhớ để nhanh chóng phát hiện xem liệu có khả năng một mục nằm trong phạm vi khác biệt hay chúng ta có thể chuyển đến đĩa ngay lập tức hay không.
- Các khóa không phải là dữ liệu thô (địa chỉ tài khoản, khóa lưu trữ), mà là các hàm băm của chúng, đảm bảo ảnh chụp nhanh có cùng thứ tự lặp lại như cây Merkle Patricia.
- Việc tạo lớp đĩa liên tục mất nhiều thời gian hơn đáng kể so với cửa sổ cắt tỉa cho các lần thử trạng thái, vì vậy ngay cả trình tạo cũng cần tự động tuân theo chuỗi.
cái tốt, cái dở, cái xấu xí
Cấu trúc tăng tốc ảnh chụp nhanh của Geth làm giảm độ phức tạp của việc đọc trạng thái khoảng một bậc của độ lớn. Điều này có nghĩa là DoS dựa trên đọc nhận được một thứ tự cường độ khó hơn để thực hiện; và eth_call các lệnh gọi nhận được thứ tự cường độ nhanh hơn (nếu không bị ràng buộc CPU).
Ảnh chụp nhanh cũng cho phép lặp lại trạng thái cực nhanh của các khối gần đây nhất. Đây thực sự là lý do chính để xây dựng ảnh chụp nhanhvì nó cho phép tạo ra búng tay thuật toán đồng bộ. Mô tả đó là một bài đăng blog hoàn toàn mới, nhưng các tiêu chuẩn mới nhất trên Rinkeby nói về khối lượng:
Tất nhiên, sự đánh đổi luôn hiện hữu. Sau khi đồng bộ ban đầu hoàn tất, mất khoảng 9-10 giờ trên mainnet để tạo ảnh chụp nhanh ban đầu (nó được duy trì trực tiếp sau đó) và cần thêm khoảng 15 GB dung lượng đĩa bổ sung.
Về phần xấu xí? Chà, chúng tôi đã mất hơn 6 tháng để cảm thấy đủ tự tin về bức ảnh chụp nhanh để gửi nó, nhưng ngay cả bây giờ nó vẫn đứng sau –snapshot cờ và vẫn còn điều chỉnh và đánh bóng được thực hiện xung quanh việc sử dụng bộ nhớ và khôi phục sự cố.
Nói chung, chúng tôi rất tự hào về sự cải tiến này. Đó là một khối lượng công việc điên rồ và đó là một cảnh quay khổng lồ trong bóng tối để thực hiện mọi thứ và hy vọng nó sẽ thành công. Như một sự thật thú vị, phiên bản đầu tiên của snap sync (đồng bộ hóa lá) đã được viết cách đây 2,5 năm và bị chặn kể từ đó vì chúng tôi thiếu sự tăng tốc cần thiết để bão hòa nó.
Phần kết
Hy vọng bạn thích bài đăng đầu tiên này của Hỏi về Geth. Tôi mất khoảng gấp đôi để hoàn thành nó so với mục tiêu của tôi, nhưng tôi cảm thấy chủ đề xứng đáng có thêm thời gian. Gặp lại bạn vào tuần tới.
[PS: I deliberately didn’t link the asking/voting website into this post as I’m sure it’s a temporary thing and I don’t want to leave broken links for posterity; nor have someone buy the name and host something malicious in the future. You can find it among my Twitter posts.]
