Giới thiệu về Kiến trúc hệ thống của Facebook: Biểu đồ xã hội và TAO

Cách dữ liệu mạng xã hội của bạn trên Facebook được sắp xếp và lưu trữ

Không cần giới thiệu về Facebook. Facebook có hơn 1 tỷ người dùng tích cực ghi lại các mối quan hệ của họ, chia sẻ sở thích của họ, tải lên và bình luận về văn bản, hình ảnh và video. Trong blog này, tôi sẽ chủ yếu thảo luận về hai khía cạnh của hệ thống phụ trợ của Facebook:

• Cách lập mô hình và lưu trữ biểu đồ xã hội, tức là, lược đồ cơ sở dữ liệu được Facebook chấp nhận.
• Cách Facebook mở rộng cơ sở hạ tầng của mình, bao gồm máy chủ, bộ nhớ cache và cơ sở dữ liệu, để phục vụ 1 tỷ lượt đọc và hàng triệu lượt ghi mỗi giây.

Facebook lưu trữ phần lớn, nếu không muốn nói là tất cả, dữ liệu của người dùng, chẳng hạn như hồ sơ, bạn bè, bài đăng và nhận xét, bên trong một biểu đồ xã hội khổng lồ. Có hai yếu tố bên trong biểu đồ xã hội, các nút và các cạnh.

• Một nút đại diện cho một thực thể, chẳng hạn như một người dùng, một bài đăng, một nhận xét và một vị trí.
• Một cạnh thể hiện mối quan hệ giữa các nút. Ví dụ: một cạnh có thể có nghĩa là một người dùng cụ thể đã tạo một bài đăng cụ thể.

Alice: Đó là một bữa tiệc tuyệt vời! @ Bob

- - Cathey: Cảm ơn vì đã đến. (David thích điều này)

Bài đăng, nhận xét và lượt thích sẽ dẫn đến một vài thay đổi đối với biểu đồ xã hội, như được minh họa trong hình bên dưới. Giả sử những người dùng, Alice, Bob, Cathey và David đã là bạn bè. Bên trong biểu đồ xã hội, 4 nút đã tồn tại, 1 nút cho mỗi người dùng. Ví dụ: nút đại diện cho người dùng Alice có ID 105 và kiểu là Người dùng. (otype là chữ viết tắt của loại đối tượng. Trong hệ thống Facebook, nút được coi là đối tượng.) Có 2 cạnh giữa mỗi cặp người dùng đại diện cho một người là bạn của người kia. (Các cạnh đại diện cho tình bạn giữa Alice và Bob, v.v. được bỏ qua cho ngắn gọn.)

Khi người dùng Alice tạo bài đăng, những thay đổi sau sẽ được áp dụng cho biểu đồ xã hội. Một nút mới đại diện cho Bài đăng được thêm vào biểu đồ xã hội. Nút được gán một ID duy nhất là 632. 4 cạnh mới cũng được thêm vào biểu đồ xã hội. Các cạnh giữa Alice và bài đăng thể hiện rằng Alice là tác giả của bài đăng. Các cạnh giữa Bob và bài đăng có nghĩa là bài đăng đã gắn thẻ người dùng Bob.

Khi người dùng Cathey thêm nhận xét vào bài đăng, nó cũng sẽ thay đổi biểu đồ xã hội. Một nút mới đại diện cho nhận xét được thêm vào biểu đồ xã hội. 3 cạnh mới được tạo. Cạnh giữa bài đăng và bình luận cho thấy nút bình luận là bình luận cho bài đăng. Các nút giữa Cathey và bình luận chỉ ra rằng Cathey là tác giả.

Cuối cùng, khi David thích nhận xét, 2 cạnh mới được thêm vào biểu đồ xã hội cho thấy David thích nhận xét.

Thiết kế cơ sở dữ liệu cho biểu đồ xã hội

Đáng ngạc nhiên là Facebook chỉ sử dụng hai bảng cơ sở dữ liệu để đại diện cho biểu đồ xã hội ghi lại hoạt động của một tỷ người dùng, bảng đối tượng và bảng liên kết.

Trong các phần sau, đối tượng và nút có nghĩa giống nhau. Liên kết và cạnh cũng vậy.

Bảng đối tượng

Bảng đối tượng có một lược đồ rất đơn giản. Nó có 3 cột. Cột id lưu trữ id duy nhất của đối tượng. otype lưu trữ kiểu đối tượng. Ngoài ra, mỗi đối tượng / nút có thể có một danh sách các cặp khóa-giá trị. otype chỉ định các khóa và kiểu giá trị có thể. Ví dụ: kiểu Người dùng có nghĩa là có thể có một khóa namevới kiểu giá trị string. Danh sách các cặp khóa-giá trị được tuần tự hóa và lưu trữ trong cột dữ liệu.

id: int

otype: string

dữ liệu: byte

Đối với bài đăng, hàng sau sẽ được lưu trữ vào bảng đối tượng

632 | “Đăng” | {“Text”: “Đó là một bữa tiệc tuyệt vời! @ Bob ”}

Bảng liên kết

Lược đồ của bảng kết hợp cũng tương tự. Nó có 4 cột. id1 và id2 đại diện cho nguồn và đích của cạnh. atype là kiểu cạnh và dữ liệu lưu trữ danh sách tùy chọn các cặp khóa-giá trị được liên kết với cạnh.

id1: int

id2: int

atype: string

dữ liệu: byte

Cạnh từ bài đăng đến nhận xét sẽ dẫn đến hàng sau trong bảng liên kết

632 | 731 | Nhận xét | vô giá trị

Các phần phụ trợ có khả năng mở rộng cao phân phát biểu đồ xã hội

Có hai thành phần chính trong hệ thống phụ trợ của Facebook, TAO và cơ sở dữ liệu.

TAO

TAO là kho dữ liệu phân tán của Facebook. Nó phục vụ hai mục đích chính:

1. Xác định API truy cập dữ liệu

* API đối tượng

API đối tượng cung cấp các hoạt động để cấp phát một đối tượng và id mới, đồng thời truy xuất, cập nhật hoặc xóa đối tượng được liên kết với một id.

* API liên kết

API liên kết cung cấp các hoạt động tương tự để thêm, sửa đổi và xóa một liên kết. Tuy nhiên, nó cung cấp một bộ API phong phú hơn nhiều để truy vấn các liên kết. Một số ví dụ

assoc_get (id1, atype) - Trả về tất cả các liên kết có nguồn gốc từ id1 và với kiểu, atype.

assoc_count (id1, atype) - Trả về kích thước của danh sách liên kết cho (id1, atype)

Để hiển thị bài đăng và bình luận trên dòng thời gian, trước tiên máy chủ ứng dụng Facebook sẽ gọi obj_get (632) để lấy nội dung của bài đăng và assoc_get (632, “Bình luận”) để lấy id của tất cả các bình luận. Sau đó, nó sẽ tìm nạp nội dung của các bình luận bằng obj_get (comment_id) và lượt thích các bình luận bằng assoc_get (comment_id, “Like”).

2. Bộ nhớ đệm

Ngoài ra, TAO hoạt động như một bộ nhớ cache ghi qua. Nó tích cực lưu trữ các đối tượng và liên kết để giảm độ trễ và tải trên hệ thống cơ sở dữ liệu.

Tuy nhiên, như chúng ta có thể tưởng tượng, có rất nhiều thách thức để thiết kế một bộ nhớ đệm cho hàng petabyte dữ liệu được phân phối theo địa lý. Làm thế nào để chúng tôi duy trì tính nhất quán? Làm cách nào để chúng tôi quản lý và nhanh chóng làm mất hiệu lực bộ nhớ cache được lưu trữ ở Châu Mỹ cho một bài đăng được lưu trữ ở Châu Âu? Làm thế nào để chúng tôi xử lý các lỗi đúng cách? TAO như một bộ nhớ đệm phân tán cho petabyte dữ liệu do đó khá phức tạp và chúng tôi sẽ có một blog riêng để thảo luận về nó. Vậy nên hãy chờ trong giây lát!

Cơ sở dữ liệu

Cơ sở dữ liệu của Facebook dựa trên cơ sở dữ liệu MySQL. Rõ ràng là cơ sở dữ liệu MySQL không thể phục vụ hàng chục petabyte dữ liệu. Facebook đã thực hiện hai sửa đổi đối với cơ sở dữ liệu

1. Làm sắc nét cơ sở dữ liệu

Một tối ưu hóa mà Facebook đã thực hiện là luôn lưu trữ liên kết trên cùng một phân đoạn của id1. Đây là kết quả của các mô hình lưu lượng truy cập phổ biến của Facebook. Ví dụ, khi chúng ta xem một bài đăng, Facebook sẽ hiển thị các bình luận của nó. Bằng cách đồng định vị các đối tượng (bài đăng) và các cạnh từ đối tượng (chú thích của bài đăng), chúng ta có thể lấy dữ liệu bằng cách truy vấn một cá thể cơ sở dữ liệu duy nhất.

2. Công cụ lưu trữ cây LSM

Đây là một cách tối ưu hóa cơ sở dữ liệu khác mà Facebook đã làm. Ban đầu, Facebook sử dụng công cụ InnoDB. Công cụ InnoDB sử dụng cây B +. Tuy nhiên cây B + dẫn đến phân mảnh chỉ mục (bộ nhớ bị lãng phí. Nó không chứa bất kỳ dữ liệu hữu ích nào cũng như không thể sử dụng cho dữ liệu mới). Vấn đề này ngày càng trở nên nghiêm trọng hơn khi Facebook thay thế HDD bằng Flash hoặc SSD (dung lượng bị lãng phí đắt hơn). Facebook đã phát triển một công cụ lưu trữ mới, MyRocks DB, dựa trên cây Hợp nhất cấu trúc nhật ký (LSM). Nó đã giúp giảm 50% việc sử dụng bộ nhớ và giảm độ trễ của cơ sở dữ liệu. MyRocks DB là một chủ đề liên quan và tôi sẽ viết một blog riêng cho nó. Giữ nguyên.

Người giới thiệu

Venkataramani, Venkateshwaran, et al. "Tao: cách facebook phục vụ biểu đồ xã hội." Kỷ yếu Hội nghị Quốc tế ACM SIGMOD 2012 về Quản lý Dữ liệu . 2012.

Sharma, Yogeshwer, et al. “Wormhole: Pub-sub đáng tin cậy để hỗ trợ các dịch vụ internet sao chép theo địa lý.” Hội nghị chuyên đề {USENIX} thứ 12 về Thiết kế và Triển khai Hệ thống Mạng ({NSDI} 15) . Năm 2015.