Cách kiểm tra tên đăng ký đã được sử dụng trong tích tắc

Khi bạn nhập một tên đăng ký thông minh vào biểu mẫu đăng ký và—bam—trước khi bạn kịp chớp mắt, bạn đã được thông báo rằng tên đó đã được sử dụng.
Cảm giác phản hồi trong một giây đó có vẻ đơn giản, nhưng đối với các công ty có hàng tỷ tài khoản, điều đó không hề đơn giản.

Một truy vấn cơ sở dữ liệu ngây thơ như sau:

SELECT … WHERE username = ?

Sẽ nhanh chóng bị sụp đổ trước khối lượng truy cập toàn cầu. Để giữ cho mọi thứ nhanh chóng, các nền tảng lớn kết hợp nhiều kỹ thuật khác nhau, mỗi kỹ thuật được điều chỉnh cho tốc độ và quy mô.

Bước 1: Bộ nhớ cache tốc độ cao

Điểm dừng đầu tiên gần như luôn là một hệ thống lưu trữ trong bộ nhớ tốc độ cao như Redis hoặc Memcached.
Các hệ thống này giữ một danh sách tên người dùng được làm mới liên tục trong bộ nhớ để kiểm tra có thể được trả lời trong micro giây.

Hãy nghĩ về nó như một cuốn sổ tay siêu nhanh: nếu tên được yêu cầu đã được liệt kê, bạn nhận được một thông báo ngay lập tức rằng tên đó đã được sử dụng mà không cần chạm vào cơ sở dữ liệu chính.

Tuy nhiên, bộ nhớ thì đắt và có hạn. Bạn không thể thực tế giữ mọi tên đã được đăng ký trong một cụm bộ nhớ cache.
Đó là lý do tại sao bộ nhớ cache chỉ là cánh cổng phía trước.

Bước 2: Cây cho tìm kiếm tiền tố

Các tính năng như gợi ý các lựa chọn thay thế hoặc tự động hoàn thành cần nhiều hơn một câu trả lời đơn giản có/không.
Để làm điều đó, các kỹ sư thường sử dụng cây tiền tố, hay còn gọi là trie.

Thay vì lưu trữ mỗi tên người dùng như một chuỗi đơn, một trie sẽ phân tách chúng thành các ký tự chia sẻ các nhánh chung.
Việc kiểm tra một tên chỉ mất thời gian tương ứng với độ dài của nó, không phải tổng số người dùng.
Nó lý tưởng cho việc tìm “tất cả các tên bắt đầu bằng alex_”, nhưng các trie lớn có thể tăng trưởng về mức sử dụng bộ nhớ nếu có ít sự chồng lấn, vì vậy các nhóm thường sử dụng các phiên bản nén hoặc giới hạn kích thước của chúng.

Bước 3: Cây B+ cho tìm kiếm có thứ tự

Khi một hệ thống cần tìm tên người dùng “tiếp theo” có sẵn theo thứ tự chữ cái hoặc thực hiện các truy vấn theo khoảng, nó dựa vào các cây B+—công cụ chỉ mục chính đứng sau nhiều cơ sở dữ liệu quan hệ và NoSQL.

Các cấu trúc này giữ dữ liệu được sắp xếp để việc tìm kiếm xảy ra trong thời gian logarithmic.
Ngay cả với hàng tỷ bản ghi, cơ sở dữ liệu có thể xác định một tên người dùng chỉ trong vài lần đọc bộ nhớ hoặc đĩa.
Tại quy mô toàn cầu, các dịch vụ như Google Cloud Spanner phân phối các chỉ mục này trên nhiều máy để tốc độ này vẫn duy trì được trên toàn thế giới.

Bước 4: Bộ lọc Bloom — Siêu năng lực không được công nhận

Trước khi bộ nhớ cache hoặc cơ sở dữ liệu thậm chí bắt đầu làm việc, bộ lọc Bloom đã bước vào để thực hiện một điều gì đó đáng kinh ngạc:
chúng có thể cho bạn biết với tốc độ ánh sáng nếu một tên người dùng chắc chắn không được sử dụng—mà không cần lưu trữ một tên người dùng đầy đủ nào.

Hãy nghĩ về nó như một đội ngũ an ninh siêu nhỏ được tạo từ các bit.
Khi một tên mới được thêm vào, một vài hàm băm sẽ chuyển một vài bit cụ thể trong một mảng bit khổng lồ.
Sau đó, khi bạn kiểm tra một tên, những hàm băm đó sẽ chỉ đến những bit tương tự.
Nếu ngay cả một bit vẫn là 0, bạn nhận được một phán quyết ngay lập tức, vững chắc: “Không, tên đó không được sử dụng.”

Điều khiến mọi thứ thú vị là: Bộ lọc Bloom không bao giờ đưa ra kết quả sai âm tính.
Nếu chúng nói rằng một tên không có ở đó, bạn có thể hoàn toàn tin tưởng điều đó.
Điều duy nhất cần lưu ý là đôi khi có kết quả dương tính giả—một “có thể” thận trọng chỉ kích hoạt một kiểm tra sâu hơn.

Và hiệu quả là vô cùng ấn tượng.
Với việc điều chỉnh cẩn thận, khoảng 1 GB bộ nhớ có thể đại diện cho một tỷ tên người dùng—một phần rất nhỏ của không gian bạn cần để lưu trữ các chuỗi thực tế.
Đối với các nền tảng lớn, đó giống như nén một cuốn sổ điện thoại của cả một thành phố vào một cái thimble và vẫn có thể tra cứu tên trong micro giây.

Bộ lọc Bloom không chỉ là một mẹo thông minh; chúng là một trong những công cụ thầm lặng giúp các hệ thống quy mô toàn cầu cảm thấy tức thì.

Bước 5: Bộ cân bằng tải và cơ sở dữ liệu phân phối

Tất cả các kiểm tra này diễn ra trên nhiều máy.

Một bộ cân bằng tải toàn cầu sẽ gửi yêu cầu của bạn đến trung tâm dữ liệu gần nhất, và một bộ cân bằng cục bộ sẽ chia sẻ công việc giữa các máy chủ ứng dụng.
Mỗi máy chủ giữ một bộ lọc Bloom hiện tại trong bộ nhớ.
Nếu bộ lọc không thể loại trừ tên, máy chủ kiểm tra bộ nhớ cache trong bộ nhớ của nó.
Chỉ khi bộ nhớ cache không có kết quả, nó mới truy cập vào cơ sở dữ liệu phân phối dưới—ví dụ như Cassandra hoặc DynamoDB—mà phân phối dữ liệu trên hàng trăm hoặc hàng ngàn nút.

Truy vấn cuối cùng đó là nguồn thông tin chính xác, nhưng nhờ vào các lớp trước đó, nó chỉ được thực hiện khi thực sự cần thiết.

Những điều cần nhớ khi bạn thấy “Đã được sử dụng…”

Hãy nhớ về những bước nhảy múa vô hình giúp phản hồi tức thời đó trở nên khả thi:

• Bộ lọc Bloom loại bỏ những tên rõ ràng không có.
• Bộ nhớ cache trả về các tên gần đây trong micro giây.
• Cây trie và cây B+ xử lý gợi ý và quét có thứ tự.
• Cơ sở dữ liệu phân phối cung cấp câu trả lời chính xác.

Điều mà có vẻ như một thông báo pop-up đơn giản thực sự là một hệ thống được sắp xếp cẩn thận kết hợp các thuật toán thông minh với hạ tầng quy mô lớn—tất cả đều để bạn biết, gần như ngay lập tức, liệu tên người dùng mơ ước của bạn có còn trống hay không.

Thực hành tốt nhất

• Sử dụng bộ lọc Bloom: Khi thiết kế hệ thống kiểm tra tên người dùng, hãy xem xét việc sử dụng bộ lọc Bloom để giảm tải cho cơ sở dữ liệu.
• Tối ưu hóa bộ nhớ cache: Cần cập nhật thường xuyên danh sách tên người dùng trong bộ nhớ cache để đảm bảo tính chính xác.

Những cạm bẫy phổ biến

• Quá nhiều tên trong bộ nhớ cache: Đặt giới hạn cho số lượng tên được lưu trữ để tránh lãng phí tài nguyên.
• Không kiểm tra đủ: Luôn luôn kiểm tra kết quả từ bộ lọc Bloom trước khi thực hiện truy vấn cơ sở dữ liệu.

Mẹo hiệu suất

• Tối ưu hóa cây trie: Sử dụng các phiên bản nén để tiết kiệm bộ nhớ và cải thiện hiệu suất.
• Phân phối tải hợp lý: Đảm bảo rằng các máy chủ ứng dụng không bị quá tải để duy trì thời gian phản hồi nhanh.

Câu hỏi thường gặp

Bộ lọc Bloom là gì?

Bộ lọc Bloom là một cấu trúc dữ liệu cho phép kiểm tra nhanh chóng xem một phần tử có tồn tại trong một tập hợp mà không cần lưu trữ toàn bộ các phần tử.

Tại sao không sử dụng truy vấn cơ sở dữ liệu đơn giản?

Truy vấn cơ sở dữ liệu đơn giản có thể không đủ nhanh cho các hệ thống quy mô lớn, dẫn đến thời gian phản hồi chậm và tải nặng cho cơ sở dữ liệu.

Làm thế nào để cải thiện hiệu suất hệ thống?

Sử dụng kết hợp bộ nhớ cache, cây trie và bộ lọc Bloom để tối ưu hóa thời gian phản hồi và giảm tải cho cơ sở dữ liệu.

Hãy áp dụng những kiến thức này để tối ưu hóa hệ thống kiểm tra tên người dùng của bạn, giúp cải thiện trải nghiệm người dùng và hiệu suất hệ thống.