Early bird, twitter realtime search
hardcore
17
White

huydx viết ngày 14/09/2016

Early bird, twitter realtime search

Là một người dùng twitter, tôi vẫn luôn băn khoăn tại sao twitter có thể làm được chức năng search hay đến thế. Cái hay nhất của twitter search là support tại realtime. Điều đó có nghĩa là gì? Là khi bạn tạo một search filter mới, giả sử là từ world cup, twitter sẽ trả về cho bạn tất cả những tweet có chứa từ đấy tại realtime.

Hình dưới là ví dụ cho một search filter của mình với từ khoá line

Những ai đã từng làm hệ thống tìm kiếm rồi sẽ biết việc này khó đến thế nào. Rất may là twitter đã publish paper liên quan đến hệ thống tìm kiếm của mình. Paper đó đặt tại http://www.umiacs.umd.edu/~jimmylin/publications/Busch_etal_ICDE2012.pdf

Mình sẽ tóm tắt lại những gì mình hiểu được từ paper này

Đầu tiên paper nêu lên 4 đặc tính cần thiết của 1 hệ thống tìm kiếm realtime:

  1. Low-latency, high-throughput query evaluation: Tóm lại là phải nhanh :P
  2. High ingestion rate and immediate data availability: Data thu được phải được tổng hợp rất nhanh, và available cho hệ thống search ngay lập tức
  3. Concurrent reads and writes. : Phải read và write đồng thời được, không bị block (cái này là CỰC KHÓ)
  4. Dominance of the temporal signal: một hệ thống tìm kiếm realtime phải chú trọng chronological order (thứ tự thời gian thực), do đó ngay cả tìm được các nội dung relevance hơn thì cũng phải đưa chronological order lên hàng đầu để sort lại cho đúng

Architecture của earlybird

alt text

Cụ thể về early bird

  • Dựa trên lucene search engine (bạn nào ko biết về lucene thì tự google nhé)
  • Ingestion pipeline : thực hiện tokenize cho nội dung của tweet + add thêm metadata (như language) vào nội dung tweet
  • EarlyBird server là indexing server
  • Tweet sẽ được phân tán ra các earlybird server khác nhau dựa vào hashing
  • EarlyBird sử dụng một khái niệm gọi là signal để personalize nội dung tweet. Theo như paper thì có 3 loại signal :
    • Static signals, directly added at indexing time
    • Resonance signals, dynamically updated over time (e.g., number of retweets a tweet receives).
    • Information about the searcher, provided at search time

Các signal không phải static sẽ được update bởi module Updater ở trên.

EarlyBird Query về cơ bản là base trên lucene query, dựa trên inverted index nên sẽ support các phép toán của set như là conjunctions (ANDs), disjunctions (ORs), negations (NOTs), and phrase queries.

Index organization

Index của early bird là phần thú vị nhất của bài viết. Index của earlybird phải đảm bảo:

must support low- latency, high-throughput retrieval (query evaluation) while concurrently indexing tweets.

Chiến lược của twitter là isolate and limit the scope of index updates., hay nói một cách khác là chia để trị.
Mỗi earlybird instance sẽ quản lý max là 12 index segments, Mỗi segment sẽ chứa tầm 2^23 là ~ 8.4 tr tweets.
Tweet được ném vào từ ingestion pipeline sẽ lấp đầy các segment, hết segment này thì nhảy sang segment khác. Điểm đáng chú ý ở đây là do mỗi segment chỉ chứa số nhỏ các tweet nên số lượng của early bird server sẽ cần là rất lớn. Do chiến thuật giống như WAL (write ahead log) của mysql như vậy, nên tại một thời điểm, có nhiều nhất 1 segment sẽ ở trong trạng thái là đang bị modified. Khi một segment được lấp đầy, thì nó sẽ được convert sang một datastructure khác optimized cho thao tác read chứ không phải write nữa.

Do sử dụng inverted index, tức là base trên term map với document, do đó để mô tả index này chúng ta cần một bảng hash. EarlyBird có lựa chọn là sử dụng default java hash table, tuy nhiên default hash table (HashMap) của java lại là chained hashing hash, tức là khi bị collide key thì sử dụng linked list để add thêm phẩn tử. Điều này gây ra việc phải quản lý thêm pointer cho linkedlist, dấn đến performance rất tồi cho GC của java. Do đó twitter đã implement lại hashtable sử dụng open addressing hash.

Term data sẽ được lưu trên một concurrent arrays, mà mỗi phần tử của array đó sẽ chứa

  • Số lượng post chứa term đó
  • Pointer đến tail của posting list.

Tiếp đến chúng ta sẽ nói đến segment layout (nhắc lại segment là tập hợp nhiều index). Như ở trên đã nói, segment sẽ có 2 trạng thái là write friendlyread friendly. Trạng thái read friendly đạt được khi một segment đã được fill đầy.

(còn tiếp ... )

huydx 13-09-2016

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

115 bài viết.
858 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
135 8
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết hơn 1 năm trước
135 8
White
109 14
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết gần 3 năm trước
109 14
White
86 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết hơn 2 năm trước
86 10
Bài viết liên quan
White
10 0
Hadoop là cái gì vậy? “Hadoop là một framework nguồn mở viết bằng Java cho phép phát triển các ứng dụng phân tán có cường độ dữ liệu lớn một cách ...
nguyenduyhao1111 viết hơn 1 năm trước
10 0
White
19 2
Tiếp nối phần 1 http://kipalog.com/posts/7concurrencymodelsinsevenweekphan1. Trong phần này chúng ta sẽ tiếp tục tìm hiểu về mô hình ThreadLock th...
huydx viết hơn 1 năm trước
19 2
White
71 34
Bài viết thuộc chủ đề nghiên cứu trong nhóm hardcore của Cộng đồng Ruby Việt Nam Đọc manga trên mobile là một nhu cầu rất lớn, nhưng hiện nay chư...
Huy Trần viết hơn 1 năm trước
71 34
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
115 bài viết.
858 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!