it-swarm-vi.com

Bạn sẽ triển khai Google Search như thế nào?

Giả sử bạn đã được hỏi trong một cuộc phỏng vấn "Bạn sẽ triển khai Google Tìm kiếm như thế nào?" Làm thế nào bạn sẽ trả lời một câu hỏi như vậy? Có thể có các tài nguyên ngoài đó giải thích cách một số phần trong Google được triển khai (BigTable, MapReduce, PageRank, ...), nhưng điều đó không thực sự phù hợp trong một cuộc phỏng vấn.

Kiến trúc tổng thể nào bạn sẽ sử dụng và bạn sẽ giải thích điều này như thế nào trong khoảng thời gian 15-30 phút?

Tôi sẽ bắt đầu với việc giải thích cách xây dựng một công cụ tìm kiếm xử lý ~ 100 nghìn tài liệu, sau đó mở rộng điều này thông qua việc chuyển sang khoảng 50 triệu tài liệu, sau đó có lẽ là một bước nhảy vọt về kiến ​​trúc/kỹ thuật.

Đây là tầm nhìn 20.000 feet. Những gì tôi muốn là các chi tiết - làm thế nào bạn thực sự sẽ trả lời điều đó trong một cuộc phỏng vấn. Những cấu trúc dữ liệu bạn sẽ sử dụng. Những dịch vụ/máy móc là kiến ​​trúc của bạn bao gồm. Độ trễ truy vấn thông thường sẽ là gì? Những gì về failover/split não vấn đề? Vân vân...

47
ripper234

bài đăng trên Quora mang lại bài báo gốc được xuất bản bởi Serge Brin và Larry Page. Nó dường như là một tài liệu tham khảo tuyệt vời cho loại câu hỏi này.

Google Architecture

19
ripper234

Hãy xem xét điểm meta: người phỏng vấn đang tìm kiếm điều gì?

Một câu hỏi voi ma mút như thế không muốn bạn lãng phí thời gian của mình trong việc thực hiện thuật toán kiểu PageRank hoặc cách thực hiện lập chỉ mục phân tán. Thay vào đó, hãy tập trung vào bức tranh hoàn chỉnh về những gì nó sẽ chụp. Có vẻ như bạn đã biết tất cả các phần lớn (BigTable, PageRank, Map/Giảm). Vì vậy, câu hỏi là sau đó, làm thế nào để bạn thực sự nối chúng lại với nhau?

Đây là vết đâm của tôi.

Giai đoạn 1: Cơ sở hạ tầng lập chỉ mục (dành 5 phút để giải thích)

Giai đoạn đầu tiên triển khai Google (hoặc bất kỳ công cụ tìm kiếm nào) là xây dựng bộ chỉ mục. Đây là phần mềm thu thập dữ liệu và tạo ra kết quả trong cấu trúc dữ liệu hiệu quả hơn để thực hiện đọc.

Để thực hiện điều này, hãy xem xét hai phần: trình thu thập thông tin và trình chỉ mục.

Công việc của trình thu thập dữ liệu web là liên kết trang web nhện và kết xuất chúng thành một bộ. Bước quan trọng nhất ở đây là tránh bị cuốn vào vòng lặp vô hạn hoặc trên nội dung được tạo vô hạn. Đặt mỗi liên kết này trong một tệp văn bản lớn (bây giờ).

Thứ hai, người lập chỉ mục sẽ chạy như một phần của công việc Bản đồ/Giảm. (Ánh xạ một chức năng đến mọi mục trong đầu vào, sau đó Giảm kết quả thành một 'điều' duy nhất.) Người lập chỉ mục sẽ lấy một liên kết web duy nhất, truy xuất trang web và chuyển đổi nó thành một tệp chỉ mục. (Thảo luận tiếp theo.) Bước rút gọn sẽ chỉ đơn giản là tổng hợp tất cả các tệp chỉ mục này thành một đơn vị. (Thay vì hàng triệu tệp lỏng lẻo.) Vì các bước lập chỉ mục có thể được thực hiện song song, bạn có thể canh tác Bản đồ/Giảm công việc này qua một trung tâm dữ liệu lớn tùy ý.

Giai đoạn 2: Cụ thể về thuật toán lập chỉ mục (dành 10 phút để giải thích)

Khi bạn đã nêu cách bạn sẽ xử lý các trang web, phần tiếp theo sẽ giải thích cách bạn có thể tính toán các kết quả có ý nghĩa. Câu trả lời ngắn ở đây là 'nhiều bản đồ/Giảm hơn', nhưng hãy xem xét các loại việc bạn có thể làm:

  • Đối với mỗi trang web, hãy đếm số lượng liên kết đến. (Các trang được liên kết nhiều hơn sẽ là 'tốt hơn'.)
  • Đối với mỗi trang web, hãy xem cách liên kết được trình bày. (Liên kết trong <h1> hoặc <b> nên quan trọng hơn các liên kết được chôn trong <h3>.)
  • Đối với mỗi trang web, hãy xem số lượng liên kết ngoài. (Không ai thích người gửi thư rác.)
  • Đối với mỗi trang web, hãy xem các loại từ được sử dụng. Ví dụ: 'băm' và 'bảng' có thể có nghĩa là trang web có liên quan đến Khoa học Máy tính. 'Băm' và 'brownies' mặt khác sẽ ngụ ý trang web là về một cái gì đó khác xa.

Thật không may, tôi không biết đủ về các cách phân tích và xử lý dữ liệu trở nên siêu hữu ích. Nhưng ý tưởng chung là các cách có thể mở rộng để phân tích dữ liệu của bạn .

Giai đoạn 3: Kết quả phục vụ (dành 10 phút giải thích)

Giai đoạn cuối cùng thực sự là phục vụ kết quả. Hy vọng rằng bạn đã chia sẻ một số hiểu biết thú vị về cách phân tích dữ liệu trang web, nhưng câu hỏi là làm thế nào để bạn thực sự truy vấn nó? Thông thường 10% truy vấn tìm kiếm của Google mỗi ngày chưa từng thấy trước đây. Điều này có nghĩa là bạn không thể lưu trữ các kết quả trước đó.

Bạn không thể có một 'tra cứu' từ các chỉ mục web của mình, vậy bạn sẽ thử cái nào? Làm thế nào bạn sẽ nhìn qua các chỉ số khác nhau? (Có lẽ kết hợp các kết quả - có lẽ từ khóa 'stackoverflow' đã đưa ra nhiều chỉ số.)

Ngoài ra, làm thế nào bạn sẽ tìm kiếm nó dù sao? Những cách tiếp cận nào bạn có thể sử dụng để đọc dữ liệu từ khối lượng thông tin khổng lồ một cách nhanh chóng? . (Ví dụ: tìm số thứ hạng cho 'stackoverflow.com' bên trong tệp 200 GB.)

Sự cố ngẫu nhiên (thời gian còn lại)

Khi bạn đã bao phủ 'xương' của công cụ tìm kiếm của mình, hãy thoải mái để chuột vào bất kỳ chủ đề cá nhân nào mà bạn đặc biệt am hiểu.

  • Hiệu suất của trang web frontend
  • Quản lý trung tâm dữ liệu cho Bản đồ/Giảm việc làm của bạn
  • Cải tiến công cụ tìm kiếm thử nghiệm A/B
  • Tích hợp khối lượng/xu hướng tìm kiếm trước đó vào việc lập chỉ mục. (Ví dụ: hy vọng máy chủ frontend tải tăng đột biến 9-5 và chết vào sáng sớm.)

Rõ ràng có hơn 15 phút tài liệu để thảo luận ở đây, nhưng hy vọng nó là đủ để bạn bắt đầu.

46
Chris Smith