Cách chúng tôi hợp tác với Meta (Facebook) để tạo Shadow Cache

Với sự hợp tác giữa Meta (Facebook), Đại học Princeton và Alluxio, chúng tôi đã phát triển “Shadow Cache” - một thành phần Alluxio nhẹ để theo dõi kích thước tập hợp làm việc và tỷ lệ truy cập bộ nhớ cache vô hạn. Bộ nhớ đệm bóng có thể theo dõi động kích thước tập hợp làm việc trong cửa sổ vừa qua và được thực hiện bởi một loạt các bộ lọc nở. Bộ đệm ẩn bóng tối được triển khai trong Meta (Facebook) Presto và đang được tận dụng để hiểu nút cổ chai của hệ thống và giúp đưa ra các quyết định thiết kế định tuyến.

Động lực và nền tảng

Tại Meta (Facebook), Presto là một công cụ truy vấn thời gian thực phân tán sử dụng ngôn ngữ SQL làm giao diện để thực hiện các truy vấn nhanh, tương tác trên hàng petabyte dữ liệu. Nó hỗ trợ ANSI SQL tiêu chuẩn, bao gồm các truy vấn, tổng hợp, JOIN và các hàm cửa sổ.

Alluxio là nền tảng điều phối dữ liệu như một công nghệ quan trọng hỗ trợ Presto và nhiều ứng dụng và trường hợp sử dụng phân tích dữ liệu khác. Alluxio tạo một lớp dữ liệu ảo liên kết dữ liệu từ bất kỳ hệ thống tệp hoặc kho lưu trữ đối tượng nào, cung cấp không gian tên thống nhất trên các hệ thống lưu trữ và cung cấp dữ liệu cho các ứng dụng sử dụng giao diện tiêu chuẩn công nghiệp với khả năng truy cập dữ liệu nhanh chóng.

Để cải thiện hiệu suất của Presto, việc hiểu tác động của kích thước bộ nhớ cache và tỷ lệ truy cập bộ nhớ cache là điều cần thiết. Presto cần biết thông tin bộ nhớ đệm nhất định từ Alluxio để xác định xem việc mở rộng kích thước bộ nhớ đệm có thể giúp cải thiện hiệu suất và tỷ lệ truy cập bộ nhớ cache khi bộ nhớ đệm bị giới hạn. Thông tin này cũng hữu ích để tối ưu hóa các thuật toán bộ nhớ đệm. Chúng tôi cũng muốn tối ưu hóa thuật toán định tuyến để cân bằng và hiệu quả hơn. Do đó, cách theo dõi và quản lý dữ liệu bộ nhớ cache của Alluxio tốt hơn là chìa khóa cho các quyết định trước khi tối ưu hóa.

Hai câu hỏi chính cần được giải quyết từ phía Presto:

1. Làm thế nào để kích thước bộ nhớ cache cho từng đối tượng thuê?

2. Cải thiện tỷ lệ truy cập bộ nhớ cache tiềm năng là gì?

Chúng tôi đề xuất “Shadow Cache”, một thành phần Alluxio nhẹ để theo dõi kích thước tập hợp hoạt động và tỷ lệ truy cập bộ nhớ cache.

Để trả lời câu hỏi đầu tiên, Shadow Cache sẽ cho quản trị viên biết số byte không trùng lặp mà bộ nhớ đệm đã nhận được trong 24 giờ qua để ước tính nhu cầu bộ nhớ đệm trong tương lai. Đối với câu hỏi thứ hai, Shadow Cache sẽ cho quản trị viên biết có bao nhiêu yêu cầu truy cập vào bộ nhớ cache nếu bộ nhớ cache có thể giữ tất cả các yêu cầu trong 24 giờ qua, tức là những yêu cầu không bao giờ xuất hiện, vì vậy tỷ lệ truy cập tối đa là bộ nhớ cache có thể được tính toán.

Thành phần Alluxio nhẹ này, Shadow Cache, có thể cung cấp thông tin chi tiết về bộ hoạt động của bộ đệm và tốc độ truy cập bộ nhớ cache sẽ như thế nào nếu có không gian bộ nhớ cache vô hạn. Để theo dõi trạng thái bộ nhớ cache của cụm, chúng tôi xác định các số liệu chính sau đây.

• C1: Sử dụng bộ nhớ đệm thực tại một thời điểm nhất định
• C2: Bộ đệm ẩn hoạt động được đặt trong một khoảng thời gian (1 ngày / 1 tuần)
• H1: Tỷ lệ truy cập bộ nhớ cache thực
• H2: Tỷ lệ truy cập Shadow Cache

Các thách thức

Mặc dù chúng tôi đã cố gắng cung cấp các số liệu trên cho bộ nhớ cache của Alluxio, nhưng chúng tôi đã gặp phải một số thách thức.

Bộ nhớ thấp và Chi phí CPU

Shadow Cache là một thành phần nhẹ giúp theo dõi kích thước của các nhóm làm việc được lưu trong bộ nhớ cache. Rất khó để theo dõi một tập hợp làm việc “vô hạn” với bộ nhớ hạn chế. Shadow Cache cũng phải có chi phí CPU thấp vì nó lưu trữ dữ liệu khi xử lý mỗi truy vấn. Nếu không, các yêu cầu của người dùng sẽ bị chặn trong một thời gian dài.

Sự chính xác

Shadow Cache cũng phải đảm bảo độ chính xác. Trong Presto, Shadow Cache đo trạng thái bộ nhớ cache của một cụm và nếu tỷ lệ truy cập bộ nhớ cache giới hạn ước tính quá thấp, Presto có thể xác định sai rằng công việc này không thân thiện với bộ nhớ cache. Ngược lại, nếu tỷ lệ truy cập bộ nhớ cache giới hạn ước tính quá cao, Presto có thể tin rằng việc mở rộng bộ nhớ cache của cụm tại thời điểm này sẽ cải thiện đáng kể hiệu suất tổng thể.

Cập nhật động

Presto và các ứng dụng dữ liệu hiện đại khác chủ yếu được sử dụng để khám phá các xu hướng hiện tại hoặc tương lai. Do đó, Shadow Cache cũng nên loại bỏ các mục lỗi thời trong thời gian thực. Nếu không, nó có khả năng mang lại nhiễu nhiễu cho quyết định. Cửa sổ trượt là một trong những phương pháp phổ biến nhất để lưu trữ các mục mới nhất, nhưng việc tạo cấu trúc dữ liệu cho mô hình cửa sổ trượt không hề đơn giản. Khi cửa sổ trượt, chúng ta cần xóa các mục vừa được chuyển ra trong thời gian thực. Điều quan trọng là phải tìm mục cần xóa càng nhanh càng tốt và xóa nó.

Giải pháp

Do hai yêu cầu về độ chính xác cao và chi phí thấp, chúng tôi nghĩ ngay đến bộ lọc Bloom, bộ lọc đã trở nên phổ biến trong các cơ sở dữ liệu phân tán khác nhau. Shadow Cache ước tính kích thước tập hợp làm việc và tỷ lệ truy cập giới hạn dựa trên bộ lọc Bloom. Đây là cách bộ lọc Bloom giải quyết ba thách thức.

Bộ lọc Bloom: Giải pháp cho những thách thức về chi phí và độ chính xác

Bộ lọc Bloom là một thử nghiệm thành viên cấu trúc dữ liệu xác suất hiệu quả về không gian. Bộ lọc Bloom là một mảng được khởi tạo với tất cả các số không theo bit và mỗi đối tượng chỉ được biểu diễn bằng một số bit, tiết kiệm đáng kể chi phí không gian và cung cấp các truy vấn với hiệu quả tuyệt vời. Bộ lọc Bloom có thể xác định xem một mục có tồn tại hay không. Mục không được tồn tại nếu bộ lọc Bloom trả về rằng nó không tồn tại. Lưu ý rằng dương tính giả là có thể, nhưng âm tính giả thì không.

Bộ lọc Bloom có k hàm băm. Để thêm một phần tử, hãy áp dụng từng hàm băm và đặt bit thành 1. Để truy vấn một phần tử, hãy áp dụng từng hàm băm và AND các bit. Khi tất cả các bit trên k vị trí là 1, mục được coi là tồn tại. Nếu không, mặt hàng đó không được coi là tồn tại.

Chuỗi bộ lọc Bloom: Giải pháp cho Cập nhật động

Bộ lọc Bloom có thể cung cấp cả chi phí thấp và độ chính xác cao, vậy chúng ta có thể áp dụng trực tiếp chúng vào Shadow Cache không?

Vấn đề đầu tiên chúng tôi gặp phải là bộ lọc Bloom không hỗ trợ tính năng xóa. Điều này là do chúng tôi chỉ quan tâm đến kích thước của tập hợp hoạt động của ứng dụng của người dùng theo thời gian và Shadow Cache là bắt buộc để thực hiện điều này. Shadow Cache thực hiện điều này bằng cách liên kết nhiều bộ lọc với nhau để tạo chuỗi bộ lọc Bloom.

Đây là cách chuỗi bộ lọc Bloom có thể được sử dụng để cập nhật kích thước tải của bộ làm việc trong thời gian thực.

Truy vấn: Như đã trình bày ở trên, Shadow Cache là một chuỗi bao gồm nhiều bộ lọc Bloom. Khi theo dõi quy mô nhóm làm việc của người dùng trong 24 giờ qua, chúng tôi có thể chia 24 giờ thành bốn khoảng thời gian. Bộ lọc Bloom theo dõi từng khoảng thời gian trong Shadow Cache và mỗi bộ lọc Bloom theo dõi một khoảng thời gian. Shadow Cache sử dụng tất cả các bộ lọc Bloom hiện có hoặc tạo một bộ lọc Bloom mới cho truy vấn, như thể hiện trong hình sau.

Cập nhật trực tiếp: Để giữ dữ liệu theo thời gian thực, chúng tôi cần Shadow Cache để loại bỏ dữ liệu đã trở nên lỗi thời khi cửa sổ thời gian trượt. Các giá trị bộ lọc Bloom phải được cập nhật liên tục theo thời gian t và các mục bộ lọc Bloom đã nằm ngoài cửa sổ thời gian phải bị xóa. Vì chúng tôi đang kết hợp nhiều bộ lọc Bloom, nên có thể dễ dàng xác định vị trí của các mục đã lỗi thời ở phần cuối của bộ lọc Bloom, như thể hiện trong hình bên dưới. Mỗi khi một khoảng thời gian mới bắt đầu, chúng tôi sẽ xóa bộ lọc cũ nhất khỏi chuỗi và thêm một bộ lọc hoàn toàn trống mới để ghi lại dữ liệu mới nhất.

Kích thước tập hợp làm việc : Khi bộ lọc bloom ánh xạ một mục thành nhiều bit, việc đánh giá kích thước tập hợp làm việc chỉ dựa trên số bit là 1 sẽ gây ra lỗi không thể chấp nhận được vì một bit có thể đại diện cho nhiều mục và một mục có thể nằm rải rác giữa nhiều bit. Do đó, chúng tôi sử dụng công thức do Swamidass & Baldi (2007) suy ra. Chúng tôi tận dụng tính gần đúng với phương trình sau để đo kích thước bộ làm việc.

Trong đó n * là ước tính số lượng mục trong bộ lọc, m là chiều dài (kích thước) của bộ lọc, k là số hàm băm và X là số bit được đặt thành một.

Tỷ lệ truy cập kích thước vô hạn: Sau khi cung cấp chỉ số kích thước thiết lập hoạt động, Shadow Cache cũng cần cung cấp tỷ lệ truy cập kích thước vô hạn. Chúng ta có thể sử dụng bộ lọc Bloom như một bộ nhớ đệm với không gian vô hạn vì chúng có thể theo dõi lượng dữ liệu khổng lồ mà ít sử dụng bộ nhớ. Số lượng yêu cầu của người dùng đến bộ lọc Bloom bằng số lần truy cập trong bộ nhớ đệm vô hạn, được biểu thị là một lần truy cập. Tổng số "yêu cầu của người dùng" được biểu thị là queryNum. QueryNum là tổng số "yêu cầu của người dùng", do đó, tỷ lệ lần truy cập bằng với lần truy cập / queryNum.

Sử dụng Shadow Cache để xác định trạng thái bộ đệm ẩn cụm trước

Sau khi hoàn thành chuỗi bộ lọc Bloom, chúng ta có thể nhanh chóng tìm hiểu các chỉ số H1, H2, C1, C2 đã được xác định trước đó. Trong bước tiếp theo, Presto có thể xác định trạng thái bộ nhớ cache của cụm bằng cách so sánh mối quan hệ kích thước giữa chúng, như thể hiện trong hình sau.

Khi H2 ở mức thấp, nó chỉ ra rằng không thể đạt được tốc độ truy cập bộ nhớ cache của ứng dụng trong cụm này ngay cả với không gian bộ nhớ cache không giới hạn. Điều này ngụ ý rằng ứng dụng này không thân thiện với bộ nhớ cache. Khi H2 ở mức cao và H1 ở mức thấp và C2> C1, nó chỉ ra rằng cụm được phân bổ dưới không gian bộ nhớ cache và tỷ lệ truy cập có thể được cải thiện hơn nữa nếu dung lượng bộ nhớ cache được mở rộng. Khi H2 cao và H1 cao và C2 <C1, bộ đệm cụm được phân bổ quá mức và tài nguyên bị lãng phí. Một cụm ở trạng thái tốt nếu H2> H1 và C2> C1 và C2> C1, nghĩa là không cần mở rộng bộ nhớ cache.

Thực hiện

Việc triển khai bộ lọc Bloom của Shadow Cache dựa trên Guava BloomFilter lib và hỗ trợ các cấu hình bộ lọc cụ thể dựa trên ngân sách chi phí bộ nhớ do người dùng xác định và cửa sổ bộ nhớ đệm ẩn. Hiện tại, Shadow Cache hỗ trợ kích thước tập hợp làm việc theo #pages và #byte, đại diện cho số lượng trang và bao nhiêu byte cụ thể mà tập hợp làm việc chứa, tương ứng. Để tính toán tỷ lệ truy cập, Shadow Cache hỗ trợ tỷ lệ truy cập byte kích thước vô hạn và tỷ lệ truy cập đối tượng.

Dưới đây là các cấu hình.

# Cửa sổ quá khứ để xác định nhóm làm việc

alluxio.user.client.cache.shadow.window=**24h**

# Tổng chi phí bộ nhớ cho các bộ lọc nở được sử dụng để theo dõi

alluxio.user.client.cache.shadow.memory.overhead=**125MB**

# Số lượng bộ lọc nở được sử dụng để theo dõi. Mỗi theo dõi một phân đoạn cửa sổ

alluxio.user.client.cache.shadow.bloomfilter.num=**4**

Kết quả kiểm tra

Chúng tôi đã thử nghiệm Shadow Cache và nhận thấy rằng chỉ với 125MB dung lượng, Shadow Cache có thể theo dõi 27TB bộ làm việc với tỷ lệ lỗi chỉ 3%. Hơn nữa, tỷ lệ lỗi có thể được giảm hơn nữa bằng cách sử dụng HyperLogLog, nhưng ước tính tỷ lệ lần truy cập kích thước vô hạn sẽ không được hỗ trợ nếu HyperLogLog được sử dụng.

Tối ưu hóa định tuyến trước

Để cải thiện hiệu suất, Presto cần một cách để điều chỉnh cụm kịp thời nếu nó học được trạng thái cụm cụ thể từ Shadow Cache. Bước tiếp theo của chúng tôi là mô tả thuật toán định tuyến Presto hiện tại và sau đó cung cấp một số tùy chọn để tối ưu hóa định tuyến sau khi giới thiệu Shadow Cache.

Định tuyến trước

Presto lưu trữ các bảng khác nhau trong các cụm khác nhau, chia sẻ bộ nhớ cache giữa các cụm theo tên bảng. Do đó, một truy vấn truy cập cùng một bảng sẽ luôn đi đến cùng một cụm đích để tối đa hóa bộ nhớ cache của nó. Bộ nhớ cache cụm sẽ chứa đầy các bảng khác nhau nếu điều này không được thực hiện. Dưới đây là sơ đồ của thuật toán định tuyến.

Như trong hình trên, bảng 1 đến bảng 4 có các tên bảng khác nhau và do đó được gán cho các cụm khác nhau. Khi yêu cầu dữ liệu từ table1, thuật toán định tuyến sẽ gửi yêu cầu đến cluster1 và khi yêu cầu dữ liệu từ table3, thuật toán định tuyến sẽ gửi yêu cầu đến cluster3.

Tùy chọn Tối ưu hóa Định tuyến

Thời gian phản hồi của một yêu cầu cụm là một cách đơn giản để xác định xem một cụm có đang hoạt động hay không. Khi cụm phản hồi chậm hoặc mất quá nhiều thời gian để phản hồi, chúng tôi giả định rằng cụm đang gặp sự cố. Với Shadow Cache, như đã đề cập ở trên, kết hợp với H1, H2, C1, C2, chúng ta có thể nhanh chóng xác định xem một cụm có đang bị suy giảm hiệu suất do căng thẳng bộ nhớ cache hay không.

Presto đề xuất ba tùy chọn tối ưu hóa định tuyến sau đây cho một cụm hoạt động kém hiệu quả như vậy. Tất nhiên, mỗi lựa chọn đều có sự cân bằng của nó.

• Tùy chọn 1: khi cụm chính đang bận, hãy có một cụm phụ được chỉ định với bộ đệm được bật cho các truy vấn đó. Tuy nhiên, cách tiếp cận này yêu cầu lưu trữ bộ đệm bảng bổ sung trên mỗi cụm.
• Tùy chọn 2: Cả hai cụm đều được coi là cụm chính để phục vụ các yêu cầu và cân bằng tải được thực hiện trong cả hai cụm. Tuy nhiên, tùy chọn này sẽ nhân lên việc sử dụng không gian đĩa đệm.
• Tùy chọn 3: Xây dựng Bản đồ từ các bảng thành các cụm và làm cho việc sử dụng CPU đồng đều hơn. Tuy nhiên, nó có thể làm cho việc phân phối bộ nhớ đệm không đồng đều và yêu cầu thêm dung lượng bộ nhớ đệm.

Bản tóm tắt

Thách thức của việc theo dõi và ước tính kích thước của bộ làm việc trong bộ nhớ cache là rất lớn, vì vậy chúng tôi đã phát triển một thành phần nhẹ của Alluxio Shadow Cache bằng cách sử dụng bộ lọc Bloom. Bởi vì chúng ta chỉ quan tâm đến trạng thái mới nhất của tập hợp làm việc, cần sử dụng mô hình cửa sổ thời gian để loại bỏ các mặt hàng lỗi thời. Shadow Cache chia cửa sổ thời gian thành bốn phân đoạn cho mục đích này. Mỗi phân đoạn được theo dõi bằng một bộ lọc Bloom khác nhau. Bộ lọc Bloom mới được tạo để theo dõi dữ liệu mới nhất, thay thế dữ liệu sớm nhất trong mỗi lần loại bỏ. Cuối cùng, khi kích thước tập hợp làm việc cần được cung cấp, chúng tôi sử dụng công thức được đề xuất của Swamidass & Baldi (2007) để ước tính cơ sở.

Nhìn chung, Shadow Cache cung cấp cho Presto bốn số liệu thuận tiện: H1, H2, C1, C2, trong đó H1 và C1 đại diện cho tỷ lệ truy cập bộ nhớ cache thực và mức sử dụng, trong khi H2 và C2 đại diện cho tỷ lệ truy cập giới hạn của bộ nhớ cache và kích thước của bộ làm việc của người dùng trong một khoảng thời gian. Presto có thể nhanh chóng xác định mối quan hệ giữa dung lượng bộ nhớ cache và hiệu suất ứng dụng và tối ưu hóa thuật toán định tuyến để cân bằng và hiệu quả hơn dựa trên bốn số liệu trên.

Liên kết

• Mã đã hợp nhất
• Phiên bản tiếng Trung của bài viết này

Giới thiệu về tác giả

Ke Wang là kỹ sư phần mềm tại Meta (Facebook), tập trung vào các truy vấn có độ trễ thấp trong nhóm Presto.

Zhenyu Song là tiến sĩ. ứng cử viên trong khoa Khoa học Máy tính tại Đại học Princeton, nghiên cứu máy học để cải thiện hiệu quả bộ nhớ đệm trong CDN.