Mở đầu:

• Problem: Bạn là web programmer, bạn sở hữu một trang web đăng tin tức với rất nhiều users. Users của bạn sẽ vote up hoặc down cho một tin tức nào đó, Vấn đề là không gian hiển thị tin luôn là hữu hạn và nhỏ hơn rất nhiều so với số lượng tin được đăng. Do vậy việc sắp xếp tin nào hot lên trên , ít hot hơn xuông dưới là một bài toán cần giải quyết. Việc sắp xếp ở đây được thông qua độ hot hay là hot-score. Một thuật toán quyết định hot-score tốt sẽ giúp cho user luôn theo dõi được các trend hiện tại, và tìm ra được tin mình muốn theo dõi.

• Giải quyết: Định nghĩa về việc định nghĩa hot-score thế nào là tốt là một việc khá khó vì không có cách nào đánh giá cụ thể được, vì vậy ở bài viết này chúng ta sẽ tìm hiểu các thuật toán đã và đang được áp dụng trên reddit, hacker-news và trên lamernews ( một open source clone hackernews )

Idea để giải quyết bài toán hot-score

• Đầu tiên hãy nói về mặt ý tưởng. Thường với những hệ thống có chức năng vote, chúng ta sẽ nghĩ ngay đến công thức :

1

score = up_vote - down_vote

Tuy nhiên công thức trên có gì không tốt? Giả sử một item có 1000 up votes và 500 down votes, như vậy score của item đó sẽ là 500, tỉ lệ là 66.6% positive (1000/1500). Một item khác có 2000 up votes và 1300 down votes, có score là 700, nhưng tỉ lệ lại chỉ có 60.6% (2000/3300). So sánh 2 item trên thì về mặt logic thông thường chúng ta sẽ muốn item thứ nhất, với tỉ lệ positive cao hơn hẳn và số lượng sample (mẫu) votes không quá tầm thường (1500 votes).

• Từ ví dụ trên, chúng ta lại nảy ra ý nghĩ sử dụng tỉ lệ (portion) thay vì khoảng cách (distance) ở công thức trên

1

score = up_vote / down_vote

Tuy nhiên công thức trên không tốt ở đâu? Vấn đề thứ 1 của công thức trên chính là việc dùng phép chia. Vấn đề dùng phép chia sẽ gặp phải bài toán chia cho 0 (divide by zero), do đó là 1 item với 2 up votes và 0 down votes sẽ có giá trị là Inf, có độ lớn vô tận. Vấn đề này có thể giải quyết một cách đơn giản bằng cách cộng thêm 1 vào cả up votes và down votes.

1

score = (up_vote + 1) / (down_vote + 1)

Tuy nhiên mặc dù có cộng thêm một, vẫn còn một vấn đề nữa, là vấn đề thời gian. Công thức trên hoàn toàn không có parameter liên quan đến thời gian. Việc đó sẽ gây ra điều gì? Chúng ta dễ dàng nhận thấy là những item được post sớm sẽ có chiều hướng được rank cao hơn. Lý do là vì những item được post sớm sẽ được nhìn thấy nhiều hơn, được vote nhiều hơn, do đó nó dễ dàng ngự trị ở vị trí top-score một cách ổn định. Do đó việc có một parameter để quyết định độ “cũ” (stale) của một item là cần thiết.

Như vậy chúng ta cần một thuật toán tính toán hot-score dựa trên up votes, down votes, và thời gian (thời gian ở đây chính là khoảng thời gian từ lúc post bài cho đến thời điểm hiện tại).

Một số cách giải quyết của các website nổi tiếng

Reddit

• Đầu tiên đến với reddit. Reddit là một web-site chuyên đăng tin tức với comment vào dạng lớn nhất trên thế giới. Source code của reddit được open tại https://github.com/reddit/reddit. Thuật toán tính toán hot-score của reddit nằm tại đoạn code ./r2/r2/lib/db/_sorts.pyx :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

epoch = datetime(1970, 1, 1, tzinfo = g.tz)

cpdef double epoch_seconds(date):
    """Returns the number of seconds from the epoch to date. Should
       match the number returned by the equivalent function in
       postgres."""
    td = date - epoch
    return td.days * 86400 + td.seconds + (float(td.microseconds) / 1000000)

cpdef long score(long ups, long downs):
    return ups - downs

cpdef double _hot(long ups, long downs, double date):
    """The hot formula. Should match the equivalent function in postgres."""
    s = score(ups, downs)
    order = log10(max(abs(s), 1))
    if s > 0:
        sign = 1
    elif s < 0:
        sign = -1
    else:
        sign = 0
    seconds = date - 1134028003
    return round(order + sign * seconds / 45000, 7)

Đoạn code trên được implement bằng cython. Đoạn code hơi dài, nhưng chúng ta chỉ cần chú ý đến dòng cuối cùng

1

  round(order + sign * seconds / 45000, 7)

Ở đây seconds chính là thời gian tính từ 1970/1/1 đến giờ theo seconds. sign là giá trị mà (-1) khi có số vote âm, (+1) khi có số vote dương và (0) khi có số vote 0. order chính là log10(số vote). Từ công thức trên chúng ta có thể thấy độ hot của một item, khi có số vote âm mà càng cũ (seconds lớn) thì sẽ tụt rất nhanh về phía dưới. Việc sử dụng log scale, và chia time-lapse cho một con số khá lớn (45000) giúp cho giá trị vote không ảnh hưởng quá nhiều đến ranking. Do đó chúng ta có thể thấy rằng ở công thức của reddit thì:

• Thời gian post bài có giá trị quan trọng nhất, thường thì bài mới hơn sẽ rank cao hơn bài cũ.
• Giá trị votes không quá ảnh hưởng đến bài, một bài viết với 10 up votes và một bài viết với 100 up votes không quá chênh lệch nhau về rank.

Hackernews

• Tiếp theo chúng ta sẽ đến với thuật toán của hacker-news. Source code của hacker-news (ycombinator) được viết bằng Arc, một ngôn ngữ gần giống Lisp và được open source ở http://arclanguage.org/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(= gravity* 1.8 timebase* 120 front-threshold* 1
       nourl-factor* .4 lightweight-factor* .17 gag-factor* .1)

    (def frontpage-rank (s (o scorefn realscore) (o gravity gravity*))
      (* (/ (let base (- (scorefn s) 1)
              (if (> base 0) (expt base .8) base))
            (expt (/ (+ (item-age s) timebase*) 60) gravity))
         (if (no (in s!type 'story 'poll))  .8
             (blank s!url)                  nourl-factor*
             (mem 'bury s!keys)             .001
                                            (* (contro-factor s)
                                               (if (mem 'gag s!keys)
                                                    gag-factor*
                                                   (lightweight s)
                                                    lightweight-factor*
                                                   1)))))

Đoạn code trên viết theo poland notation nên hơi khó nhìn một chút, về mặt bản chất thì đoạn code trên tương đương với

1
2

def score(votes, age, gravity=1.8):
  (votes - 1) / pow((age+2), gravity);

Chúng ta có thể rút ra được 2 điều:

• Thời gian càng tăng (age >>) thì score càng giảm với tốc độ rất nhanh theo hàm power
• Bài viết càng cũ thì dù up votes có tăng nhanh nhưng cũng không thể kéo được rank.

Công thức của ycombinator đã phản ánh rất đúng power law về pupularity ranking, là popularity của một data source bao giờ cũng có dạng long-tail. Định lý này nói lên rằng tỉ lện những item dominate (có rank cao) chỉ chiếm tầm 20% so với tổng số item, nên rule này còn được gọi là 80/20 rule.

Lamernews

• Lamernews được viết bởi creator của redis, và được open source tại https://github.com/antirez/lamernews. Lamernews được viết bằng ruby (sinatra) và thuật toàn của lamernews được viết khá đơn giản như sau:

1
2
3
4
5
6

def compute_news_rank(news)
    age = (Time.now.to_i - news["ctime"].to_i)
    rank = ((news["score"].to_f)*1000000)/((age+NewsAgePadding)**RankAgingFactor)
    rank = -age if (age > TopNewsAgeLimit)
    return rank
end

Chúng ta có thể thấy thuật toán này khá giống với ycombinator nên sẽ không bàn thêm về hiệu quả của nó ở đây

Kết luận

Như vậy chúng ta đã lướt qua một số thuật toán ranking được implement bởi các web service nổi tiếng. Việc quyết định thuật toán nào tùy thuộc vào chúng ta muốn chú trọng đến cái gì. Với một service có tốc độ post bài và comment rất nhanh như reddit thì nên dùng một thuật toán base chủ yếu vào aging. Còn nếu muốn chú trọng hơn vào số lương votes và giữ một tốc độ giảm rank đều với các bài viết cũ, thì chúng ta có thể sử dụng thuật toán của ycombinator

Chi tiết các bạn có thể tham khảo:

• http://amix.dk/blog/post/19588
• http://possiblywrong.wordpress.com/2011/06/05/reddits-comment-ranking-algorithm/
• http://amix.dk/blog/post/19574
• http://www.evanmiller.org/how-not-to-sort-by-average-rating.html

Như đã giới thiệu ở phần trước, chúng ta có thể làm giảm load của chương trình bằng cách tính toán trước chiều cao của các table cell. Ở phần này, chúng ta sẽ cùng xem chi tiết vấn đề này thông qua 1 ví dụ nhỏ.

Hãy xét 1 tình huống chúng ta có 1 table view để hiện thị 1 danh sách tin tức (có thể lấy từ sv về). Các bản tin này bao gồm ảnh, tiêu đề và nội dung. Phần tiêu đề chỉ hiện thị trên 1 dòng, vì thế chiều cao của bản tin sẽ phụ thuộc vào phần nội dung. Để cho đơn giản, trong ví dụ này, nội dung của tin sẽ được set cứng, lưu vào và lấy ra trong NSUserDefault.

Trước hết, hãy tạo ra 1 custom TableView Cell tương tự như trong bài viết 1. Cell này có 3 thành phần: avatar, nameLabel, contentLabel tương ứng với 3 thành phần của bài viết.

Chúng ta khởi tạo cell dựa vào 1 dictionary chứa thông tin của bài viết, thông qua hàm: -(void)setupCellWithDictionary:(NSDictionary *)dictionary

1
2
3
4
5
6
7
8

    nameLabel.text = dictionary[@"name"];
    contentLabel.text = dictionary[@"content"];
    avatarImg.image = [UIImage imageNamed:dictionary[@"avatar"]];

    float contentLabelWidth = 228;
    CGSize constraint = CGSizeMake(contentLabelWidth, 20000.0f);
    CGSize size = [contentLabel.text sizeWithFont:contentLabel.font constrainedToSize:constraint lineBreakMode:NSLineBreakByWordWrapping];
    contentLabel.frame = CGRectMake(contentLabel.frame.origin.x, contentLabel.frame.origin.y, contentLabel.frame.size.width, size.height);

và tính toán chiều cao của cell bằng cách tính chiều cao của contentLabel qua hàm: +(float)heightForCellWithDictionary:(NSDictionary *)dictionary

1
2
3
4
5

    NSString *content = dictionary[@"content"];
    float contentLabelWidth = 228;
    CGSize constraint = CGSizeMake(contentLabelWidth, 20000.0f);
    CGSize size = [content sizeWithFont:[UIFont systemFontOfSize:17] constrainedToSize:constraint lineBreakMode:NSLineBreakByWordWrapping];
    return size.height + 34 + 10;

Vậy là xong cho table cell, tiếp đến sẽ là sử dụng các cell này cho hiệu quả. Trước hết là lấy danh sách các bản tin:

1
2
3
4

    listNews = [[NSUserDefaults standardUserDefaults] objectForKey:@"list_news"];
    [self calculateCellHeights];

    [myTableView reloadData];

Sau khi lấy được listNews, chúng ta sẽ tính toán luôn height cho từng cell và lưu vào database (ở đây là NSUserDefault) qua hàm calculateCellHeights, và khi lấy ra các height này qua hàm -(float)tableView:(UITableView )tableView heightForRowAtIndexPath:(NSIndexPath )indexPath chúng ta sẽ lấy ra từ database dựa vào Id của cell chứ không phải tính toán lại như thông thường:

1
2
3

    NSString *key = [NSString stringWithFormat:@"cell_%@", cellId];
    float height = [[NSUserDefaults standardUserDefaults] floatForKey:key];
    return height;

Điểm đặc biệt của phương pháp này là các cell height sẽ chỉ phải tính 1 lần cho từng cell_ID, vì thế nếu lần load sau, nếu có cùng dữ liệu thì các height này sẽ không phải tính lại. Nếu bộ dữ liệu lớn, hoặc là các cell này được sử dụng lại nhiều lần, thì phương pháp này sẽ vô cùng hữu hiệu.

Hàm -(void)calculateCellHeights

1
2
3
4
5
6
7
8
9
10

        for (int i=0; i<listNews.count; i++) {
        NSDictionary *cellDict = listNews[i];
        NSString *cellId = cellDict[@"cellId"];
        // Chỉ tính toán cho các cell chưa tồn tại
        if (![self isCellIdExisted:cellId]) {
            NSLog(@"calculate cell height");
            float height = [CustomTableCell heightForCellWithDictionary:cellDict];
            [self saveCellHeight:height forCellId:cellId];
        }
}

Lưu ý là trong ví dụ này, các cell height được lưu trong NSUserDefault, bạn hoàn toàn có thể lưu trong database như sqlite hoặc core data với nhiều tính năng hơn. Toàn bộ code của bài viết có thể được download tại đây https://github.com/toandk/NewsFeedExample

1. Giới thiệu

Trong các bài viết trước mình đã trình bày về cách redis sao lưu dữ liệu cũng như framework lập trình hướng sự kiện của redis. Trong bài viết này mình trình bày về các đối tượng và kiểu dữ liệu trong redis.

2. Khái quát

Redis là một hệ thống cơ sở dữ liệu key-value - mỗi giá trị được quản lý bởi 1 cặp khóa và giá trị (key-value). Khi ghi dữ liệu, ta phải chỉ định rõ cặp khóa và giá trị. Khi đọc dữ liệu, ta phải chỉ ra ta muốn đọc dữ liệu của khóa nào. Trong Redis, khóa (key) có thể là một chuỗi. giá trị của dữ liệu (value) có thể là một trong một số kiểu dữ liệu thông dụng

• tập hợp (set)
• tập hợp đã sắp xếp (sorted set)
• chuỗi (string)
• danh sách (list)

Để hỗ trợ các kiểu dữ liệu ở trên, đồng thời đảm bảo tính mở rộng (phát triển thêm các kiểu dữ liệu mới) cũng để dễ dàng quản lý đối tượng trong phần core db, redis thêm 1 layer mô tả dữ liệu trung gian gọi là robj. Các thao tác của core db (đọc, ghi, hash, encoding…) sẽ được thao tác trực tiếp với robj. Các kiểu dữ liệu người dùng ở trên sẽ được chuyển đổi (convert) qua lại đến robj. Nói cách khác, phần core db chỉ biết đến sự tồn tại của robj, các kiểu dữ liệu ở trên muốn được quản lý bởi coredb cần phải được chuyển qua robj.

Về mặt tổ chức mã, bạn có thể tham khảo sơ đồ dưới đây:

╒===============╕
|  t_hash.c     |
|  t_list.c     |       ╒============╕      ╒=====================╕
|  t_set.c      |   <=> |  object.c  |  <=> |  db.c (robj -> sds) | 
|  t_string.c   |       ╘============╛      ╘=====================╛
|  t_zset.c     |
╘===============╛

3. Chi tiết về robj

Chi tiết về cấu trúc của robj được khai báo trong file redis.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/* A redis object, that is a type able to hold a string / list / set */

/* The actual Redis Object */
#define REDIS_LRU_CLOCK_MAX ((1<<21)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 10 /* LRU clock resolution in seconds */
typedef struct redisObject {
    unsigned type:4;
    unsigned notused:2;     /* Not used */
    unsigned encoding:4;
    unsigned lru:22;        /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

/* Macro used to initialize a Redis object allocated on the stack.
 * Note that this macro is taken near the structure definition to make sure
 * we'll update it when the structure is changed, to avoid bugs like
 * bug #85 introduced exactly in this way. */
#define initStaticStringObject(_var,_ptr) do { \
    _var.refcount = 1; \
    _var.type = REDIS_STRING; \
    _var.encoding = REDIS_ENCODING_RAW; \
    _var.ptr = _ptr; \
} while(0);

Qua đó ta có thể thấy robj gồm có các trường như:

• kiểu dữ liệu type
• loại encoding: kiểu dữ liệu type có thể hiểu là kiểu dữ liệu người dùng, còn encoding có thể hiểu là kiểu dữ liệu ở backend được quản lý ở core db của redis để đảm bảo hiệu năng.
• lru (least-recently used): là trường đại diện cho thời gian tồn tại tương đối của redis object. Redis hỗ trợ 1 tính năng đối với các đối tượng được ghi vào cơ sở dữ liệu redis: expire. Các đối tượng quá thời gian chỉ định trước sẽ được loại bỏ khỏi cơ sở dữ liệu. Trường này dùng để quản lý thời gian hết hiệu lực này.
• refcount: là một biến kiểu số nguyên, đại diện cho số lượng reference đến robj này. Mỗi lần có một truy cập đến robj, đại lượng reference sẽ được tăng lên 1, và sẽ bị giảm đi 1 mỗi khi đối tượng expired hoặc không được tiếp tục tham chiếu.
• *ptr: con trỏ trỏ trực tiếp đến dữ liệu
• notused??

Ở đây, ta gặp một kiểu khai báo rất lạ đặt ra nhiều câu hỏi. Thay vì khai báo unsigned type tác giả sử dụng unsigned type:4, điều này có ý nghĩa là gì? Sử dụng cả trường notused và lru:22 có ý nghĩa là gì?

Thực chất khai báo :số nguyên sau kiểu dữ liệu unsigned trong C biểu thị số bit mà trường này muốn sử dụng. Như vậy kiểu type ở trên có độ dài 4 bits. Tương tự như vậy độ dài của encoding là 4 bits. Với độ dài này, redis có thể hỗ trợ tối đa 2^4 = 16 kiểu dữ liệu khác nhau! LRU có độ dài 22 bits. Thực chất trường LRU này đại diện cho thời gian tương đối tính từ server.lruclock. Thời gian này được tính bằng số phút theo thời gian tương đối này. Để ý với 4 bits cho type, 4 bits cho encoding và 22 bits cho lru, ta mới dùng có 30 bits cho cấu trúc robj này. Do các hệ thống x86 thường căn chỉnh cấu trúc dữ liệu theo bội số của 16 (liên quan đến cơ chế làm việc của CPU cache) nên ta cần padding thêm 2 bits và việc padding 2 bits này chính là nhiệm vụ của notused!

Mã của robj khá gọn gàng, trong sáng, ngắn gọn và dễ hiểu. Bạn có thể tham khảo tại file object.c. Ở đây tôi sẽ trình bày 2 điểm quan trọng về robj:

• Tại sao phải encode robj
• Vai trò của refcount.

Tại sao phải encode robj? Như trong danh sách các kiểu dữ liệu người dùng ở trên, ta thấy có chuỗi là kiểu dữ liệu cơ bản. Các kiểu dữ liệu còn lại (hast, set, list) đều là kiểu dữ liệu xoay quanh chuỗi, số nguyên hoặc các kiểu dữ liệu khác. Bản thân chuỗi thường có nhiều ký tự lặp lại, vì vậy bằng việc encoding chuỗi dữ liệu ta sẽ tiết kiệm được lượng bộ nhớ mà redis sử dụng. Encoding ở đây thực chất là làm giảm kích thước các object. Thuật toán encode chuỗi có thể tham khảo thủ tục tryObjectEncoding và và các thủ tục trong file util.c. Thử tưởng tượng bạn có 1 key trỏ đến danh sách gồm 100 chuỗi, mỗi chuỗi chỉ cần tiết kiệm được 1 byte, thì việc encode này sẽ giúp bạn tiết kiệm được 100 bytes bộ nhớ. Lượng bộ nhớ tiết kiệm này sẽ có ý nghĩa khi bạn có hàng triệu key và value!

Vai trò của refcount Refcount thường được dùng để chia sẻ dữ liệu giống nhau của các đối tượng khác nhau. Ví dụ bạn có 2 xâu a, b cùng giá trị “Chào Thế giới!” thì không việc gì ta phải có 2 chuỗi “Chào Thế giới!” trong bộ nhớ. Chuỗi a và b có thể cùng trỏ tới 1 chuỗi trên bộ nhớ và chỉ thật sự cần có 1 bản copy riêng khi mà 2 chuỗi khác nhau. Đây là cách sử dụng thường gặp của “reference count idiom”. Tuy vậy ở redis hiếm khi ta thấy 2 object cùng chia sẻ giá trị như trường hợp ở trên. Vậy vai trò của reference count ở đây là gì?

Thực chất tác giả sử dụng refcount ở đây 1 cách khá sáng tạo (dù mình không biết là có thật sự là 1 cách dùng mới hay không). Thử tưởng tượng 1 trường hợp sau đây: 1 thread đang đọc giá trị của robj trong khi 1 thread khác đang gửi command del robj. Nếu command del được tiến hành ngay lập tức, thread đọc robj có thể bị lỗi và trả về giá trị không đúng (1 list có 10 phần tử nhưng phần tử nhưng khi đọc thì redis báo giá trị không tồn tại :-)). Nếu như command del không được thực thi, khóa trên sẽ vẫn tồn tại trong bộ nhớ, và kết quả thực hiện del sẽ thất bại. Chắc là bạn không muốn command del thất bại liên tục (khi số lượng đọc ghi cực lớn, khả năng xảy ra lỗi này là khá cao!). Để giải quyết bài toán trên, tác giả của redis sử dụng refcount. Khi một object được truy cập bởi nhiều thread, refcount của object sẽ được tăng lên 1 đơn vị và giảm 1 khi không được tham chiếu nữa. Như vậy command del sẽ chỉ giảm refcount của robj đi 1. Nếu như tại thời điểm này không có tham chiếu nào đến robj này, robj này sẽ bị thu hồi ngay lập tức. Tuy vậy nếu có 1 thread khác đang tham chiếu robj này, refcount của robj sẽ lớn hơn 1, và do đó tại thời điểm command del được thực thi, giá trị của refcount giảm xuống còn 1. Khi thread khác hoàn thành công việc, thread này sẽ giảm refcount xuống tiếp 1 đơn vị nữa, lúc này robj refcount sẽ về 0 và robj sẽ được giải phóng!

4. Các cấu trúc dữ liệu người dùng

Tôi gọi các cấu trúc dữ liệu người dùng để phân biệt chúng với cấu trúc dữ liệu redis dùng để tăng hiệu năng ở core. Các cấu trúc dữ liệu này gồm list, hash, set và string được viết ở các file có tiền tố t_ tương ứng. Như trình bày ở trên phần db core không biết gì ngoài robj vì vậy các cấu trúc dữ liệu này có nhiệm vụ là convert cách biểu diễn dữ liệu về robj.

Nếu xem các file này, bạn sẽ thấy mỗi file đều có các hàm convert sang robj như: hashTypeConvert, listTypeConvert, … Mỗi cấu trúc dữ liệu có cách viết khác nhau, nhưng đều cùng cấu trúc và khá ngắn gọn và đơn giản. Bạn có thể tham khảo từng file trên để tìm hiểu rõ hơn về cách redis hỗ trợ các kiểu dữ liệu.

src git:(unstable) wc -l t_*.c
   761 t_hash.c
  1149 t_list.c
   913 t_set.c
   459 t_string.c
  2205 t_zset.c
  5487 total

5. Kết luận:

Bài viết trình bày về cách redis tổ chức các kiểu dữ liệu người dùng cũng như cách tổ chức phần “frontend” của redis db. Bài viết cũng trình bày chi tiết về robj, về ý nghĩa và vai trò của các trường trong robj cũng như vai trò của robj với backend db. Trong bài viết sau, mình sẽ cố gắng trình bày chi tiết về phần backend server.