Chapter 15: Designing and Implementing a “Minute/Hour Counter”

Hãy xem 1 cấu trúc dữ liệu được sử dụng trong code production thực tế: một “minute/hour counter”. Chúng tôi sẽ đưa ra cho bạn quá trình tự suy nghĩ tự nhiên của 1 kĩ sư có thể trải qua, đầu tiên thử giải quyết vấn đề và sao đó cải thiện hiệu năng của nó và thêm các chức năng. Quan trọng nhất, chúng ta sẽ cố gắng để code dễ đọc , sử dụng các nguyên tắc trong cuốn sách này. Chúng tôi có thể có một số lượt sai trên đường đi hoặc phạm sai lầm khác. Hãy xem nếu bạn có thể làm theo và bắt được chúng.

The Problem

Chúng ta cần theo dõi số lượng bytes của 1 web server được truyền trong 1 phút và trong 1 giờ.

Đây là 1 vấn đề khác đơn giản, nhưng như bạn sẽ thấy, giải quyết nó hiệu quả là 1 thử thách thú vị. Hãy bắt đầu bằng việc định nghĩa class interface.

Defining the Class Interface

Đây là phiên bản đầu tiên của chúng ta với class interface trong C++:

class MinuteHourCounter {
    public:
    // Add a count
    void Count(int num_bytes);

    // Return the count over this minute
    int MinuteCount();

    // Return the count over this hour
    int HourCount();
};

Trước khi chúng ta thực thư lớp này, hãy xem về tên và comment nếu có 1 vài thứ gì đó chúng ta muốn thay đổi.

Improving the Names

Tên MinuteHourCounter khá tốt. Nó rõ ràng, cụ thể và dễ đọc.

Trong lớp này, phương thức MinuteCount() và HourCount() cũng hợp lý. Bạn cũng có thể gọi nó là GetMinuteCount() và GetHourCount() nhưng không giúp ích được nhiều. Như chúng tôi đã nói ở chương 3 Names That Can’t Be Misconstrued, “get” ngụ ý “lightweight accessor” (kiểu theo tác nhẹ nhàng thôi) với nhiều người. Và như bạn thấy, sự thực thi này không nhẹ nhàng, do đó tốt nhất là bỏ “get” đi.

Phương thức tên Count() thì có vấn đề. Chúng tôi đã hỏi đồng nghiệp là họ nghĩ Count() sẽ làm gì à 1 số người đã nghĩ nó là “trả về tổng số đếm trong mọi lúc”. Tên này có 1 chút phản trực giác (không có ý định chơi chữ). Vấn đề là Count vừa là danh từ vừa là động từ và có thể nghĩa là cả “Tôi muốn đếm số mẫu bạn đã thấy” hoặc “Tôi muốn bạn đếm mẫu này”.

Đây là 1 vài tên thay thế có thể cân nhắc với Count():
• Increment()
• Observe()
• Record()
• Add()

Increment() có thể gây hiểu nhầm vì nó có ý là giá trị này chỉ tăng (trong trường hợp của chúng ta, số giờ giao động theo thời gian)
Observe() okay, nhưng hơi mơ hồ.
Record() cũng vừa là danh từ, vừa là động từ, không tốt lắm.
Add() thú vị vì nó vừa có nghĩa “thêm số này” hoặc “thêm 1 danh sách của dữ liệu” - trong trường hợp của chúng ta, nó là 1 chút của cả 2 do đó vẫn hoạt động. Do đó chúng ta sẽ đổi tên phương thức thành void Add(int num_bytes)

Nhưng đối số với tên num_bytes quá cụ thể. Đúng, trường hợp sử dụng chính của chúng ta là đếm cố bytes nhưng MinuteHourCounter không cần biết điều đó. Chúng ta có thể sử dụng nhiều tên chung hơn như delta nhưng khái niệm delta thường được sử dụng cho cả số âm, và đó là điều chúng ta không muốn. Tên count nên được sử dụng - nó đơn giản, chung hơn và ngụ ý là “không âm”. Ngoài ra, nó còn cho phép chúng ta lén lút sử dụng từ “count” trong một bối cảnh ít mơ hồ hơn.

15.2.2. Improving the Comments
Đây là class interface chúng ta có cho đến thời điểm hiện tại:

class MinuteHourCounter {
public:
    // Add a count
    void Add(int count);

    // Return the count over this minute
    int MinuteCount();

    // Return the count over this hour
    int HourCount();
};

Hãy xem mỗi comment và cải thiện chúng. Xem xét comment đầu tiên:

// Add a count
void Add(int count);

Comment này hoàn toàn dư thừa - nó nên được xóa hoặc cải thiện. Đây là phiên bản cải thiện của nó:

// Add a new data point (count >= 0).
// For the next minute, MinuteCount() will be larger by +count.
// For the next hour, HourCount() will be larger by +count.
void Add(int count);

Bây giờ xem xét comment cho MinuteCount():

// Return the count over this minute
int MinuteCount();

Khi chúng tôi hỏi đồng nghiệp rằng comment này có nghĩa là gì, có 2 sự giải thích mâu thuẫn:

1. Trả về số đếm trong đồng hồ, như là 12:13pm
2. Trả về số đếm trong 60 giây, bất kể ranh giới phút đồng hồ.
   Cách hiểu thử 2 là đúng cái mà nó đang hoạt động. Do đó để không bị hiểu nhầm, chúng ta sẽ thêm mô tả comment:

   // Return the accumulated count over the past 60 seconds.
   int MinuteCount();

   (Tương tự, bạn hoàn toàn có thể cải thiện comment cho HourCount())

Đây là định nghĩa lớp sau tất cả thay đổi cho đến thời điểm hiện tại, với các comment class-level:

// Track the cumulative counts over the past minute and over the past hour.
// Useful, for example, to track recent bandwidth usage.
class MinuteHourCounter {
    // Add a new data point (count >= 0).
    // For the next minute, MinuteCount() will be larger by +count.
    // For the next hour, HourCount() will be larger by +count.
    void Add(int count);

    // Return the accumulated count over the past 60 seconds.
    int MinuteCount();

    // Return the accumulated count over the past 3600 seconds.
    int HourCount();
};

(Để ngắn gọn, chúng tôi sẽ bỏ lại comment này từ bây giờ)

GETTING AN OUTSIDE PERSPECTIVE
Bạn đã nhận thấy rằng đã có 1 vài trường hợp chúng ta chạy các thứ bởi đồng nghiệp. Hỏi họ để có 1 vài quan điểm bên ngoài là cách tốt để kiểm tra xem code của bạn có “user-friendly” chưa. Cố gắng cởi mở với những ấn tượng đầu tiên của họ, vì những người khác có thể có thể đi đến kết luận tương tự. Và “người khác” ở đây có thể là chính bạn 6 tháng tới :D.

Attempt 1: A Naive Solution

Tiếp tục giải quyết vấn đề. Chúng ta sẽ bắt đầu với 1 giải pháp đơn giản: chỉ giữ danh sách sự kiện thời gian:

class MinuteHourCounter {
    struct Event {
        Event(int count, time_t time) : count(count), time(time) {}
        int count;
        time_t time;
    };

    list<Event> events;

    public:
        void Add(int count) {
            events.push_back(Event(count, time()));
        }

        ...
};

Chúng tôi có thể đếm qua sự kiện gần đây nhất nếu cần:

class MinuteHourCounter {
    ...

    int MinuteCount() {
        int count = 0;
        const time_t now_secs = time();
        for (list<Event>::reverse_iterator i = events.rbegin();
            i != events.rend() && i->time > now_secs - 60; ++i) {
            count += i->count;
        }
        return count;
    }

    int HourCount() {
        int count = 0;
        const time_t now_secs = time();
        for (list<Event>::reverse_iterator i = events.rbegin();
            i != events.rend() && i->time > now_secs - 3600; ++i) {
            count += i->count;
        }
        return count;
    }
};

Is the Code Easy to Understand?

Mặc dù giải pháp là “đúng” nhưng có 1 vài vấn đề quanh việc đọc code:

• Vòng lặp for có 1 chút lắm mồm =)). Nhiều người đọc sẽ phải chậm lại đáng kể trong khi họ đang đọc phần này của code (ít nhất họ nên vậy, nếu họ chắc chắc rằng chỗ này không có 1 vài lỗi)
• MinuteCount() và HourCount() gần như giống hệt. Bạn nên làm code nhỏ honwn nếu chúng bị lặp code. Chi tiết này cực kì quan trọng vì việc giảm thiểu code là tương đối phức tạp (Tốt hơn là có tất cả các code khó có giới hạn trong 1 chỗ)

An Easier-to-Read Version

Code của MinuteCount() và HourCount() giờ chỉ khác nhau hằng số (60 vs 3600). Tái cấu trúc mã rõ ràng, thêm helper để xử lý cả 2 trường hợp:

class MinuteHourCounter {
    list<Event> events;

    int CountSince(time_t cutoff) {
        int count = 0;
        for (list<Event>::reverse_iterator rit = events.rbegin();
            rit != events.rend(); ++rit) {

            if (rit->time <= cutoff) {
               break;
            }
            count += rit->count;
        }
        return count;
    }
    public:
        void Add(int count) {
            events.push_back(Event(count, time()));
        }

        int MinuteCount() {
            return CountSince(time() - 60);
        }

        int HourCount() {
            return CountSince(time() - 3600);
        }
};

Có 1 vài điểm đáng kể trong đoạn mã mới này.

Đầu tiên là CountSince() nhận vào 1 đối số cutoff tuyệt đối hơn là nhận vào 1 secs_ago tương đối với giá trị (60 hoặc 3600). Mặc dù cách này vẫn làm việc, nhưng cách này làm CountSince() có 1 công việc dễ dàng hơn 1 chút.

Thứ 2 là việc đặt tên vòng lặp từ i thành rit. Tên i thường được sử dụng cho chỉ số số nguyên. Chúng tôi suy ngẫm sử dụng tên it, là chung cho vòng lặp. Nhưng trường hợp này chúng tôi đang có 1 vòng lặp ngược lại và thực tế này quan trọng cho sự đúng đắn của code. Bằng cách có phần tiền tố tên biến với r, nó thêm 1 đối xứng thoải mái cho các câu lệnh kiểu rit != events.rend().

Cuối cùng, chúng tôi trích xuất điều kiện rit->time <= cutoff khỏi vòng lặp và làm nó tách biệt if. Tại sao? Bởi vì các vòng lặp “truyền thống” có dạng for(begin; end; advance) dễ đọc. Người đọc có thể hiểu ngay lập tức nó đang “đi qua tất cả các phần tử” và không nghỉ nhiều về nó.

Performance Problems

Mặc dù chúng ta đã cải thiện được thẩm mỹ của code, nhưng cách thiết kế này vẫn có 2 vấn đề về hiệu năng:

1. Nó chỉ tiếp tục phát triển.
   Class này giữ toàn bộ sự kiện nó từng thấy - nó sử dụng 1 bộ nhớ không giới hạn. Lý tưởng, MinuteHourCounter nên tự động được xóa các sự kiện cái mà cũ hơn 1 giờ sau vì chúng không cần thiết nữa.

2. MinuteCount() and HourCount() are too slow.
   Phương thức CountSince() cần O(n) lần, với n là số điểm dữ liệu trong cửa sổ thời gian liên quan. Tưởng tượng rằng server hiệu năng cao gọi Add() hàng trăm lần mỗi giây. Mỗi lần gọi HourCount() sẽ phải đếm qua 1 triệu điểm. Về lý tưởng, MinuteHourCounter nên giữ biến separate minute_count và hour_count, định kì với mỗi lần gọi Add().

Attempt 2: Conveyor Belt Design

Chúng tôi cần thiết kế để giải quyết cả 2 vấn đề trên

1. Xóa dữ liệu không cần thiết
2. Luôn cập nhật minute_count và hour_count

Đây là cách mà chúng tôi sẽ làm: Chúng tôi sẽ sử dụng list như 1 băng chuyền. Khi data mới đến và 1 cái kết thúc, chúng tôi sẽ thêm vào tổng. Và khi dữ liệu quá cũ, nó đã “rơi ra” khỏi đầu kia và chúng tôi trừ đi tổng số của chúng tôi.

Có 1 vài cách chúng tôi có thể thực thi thiết kế dây chuyền này. Một cách là duy trì 2 danh sách độc lập, 1 cho past minute, 1 cho past hour. Khi 1 sự kiện mới đến, nó thêm 1 bản copy vào cả 2 danh sách

Cách này khá đơn giản, nhưng nó không hiệu quả vì nó tạo ra 2 bản copy cho mỗi sự kiện.

Một cách khác để duy trì 2 lists nơi mà sự kiện được khởi tạo vào list đầu tiên (the “last minute events”) và sau đó sẽ cho ăn vào danh sách thứ 2 (the “last hour [nhưng không phải minute cuối cùng nhé] events”)

Thiết kế theo dây chuyển “2 giai đoạn” dường như hiệu quả hơn, do đó sẽ thực thi cái này.

Implementing the Two-Stage Conveyor Belt Design

Hãy bắt đầu bằng cách liệt kê các thành phần của class:

class MinuteHourCounter {
    list<Event> minute_events;
    list<Event> hour_events; // only contains elements NOT in minute_events

    int minute_count;
    int hour_count; // counts ALL events over past hour, including past minute
};

Điểm mấu chốt của thiết kế băng chuyền này là có thể “dịch chuyển” các sự kiện khi thời gian trôi qua, do đó các sự kiện di chuyển từ minute_events tới hour_events và minute_count và hour_count nhận các cập nhật phù hợp. Để làm điều này, chúng ta sẽ tạo 1 phương thức helper tên là ShiftOldEvents(). Một khi chúng ta có phương thức này, phần còn lại của lớp này khá dễ thực thi:

void Add(int count) {
    const time_t now_secs = time();
    ShiftOldEvents(now_secs);

    // Feed into the minute list (not into the hour list--that will happen later)
    minute_events.push_back(Event(count, now_secs));
    minute_count += count;
    hour_count += count;
}

int MinuteCount() {
    ShiftOldEvents(time());
    return minute_count;
}

int HourCount() {
    ShiftOldEvents(time());
    return hour_count;
}

Rõ ràng, chúng ta đã trì hoãn được tất cả các công việc bẩn thỉu vào ShiftOldEvents():

// Find and delete old events, and decrease hour_count and minute_count accordingly.
void ShiftOldEvents(time_t now_secs) {
    const int minute_ago = now_secs - 60;
    const int hour_ago = now_secs - 3600;

    // Move events more than one minute old from 'minute_events' into 'hour_events'
    // (Events older than one hour will be removed in the second loop.)
    while (!minute_events.empty() && minute_events.front().time <= minute_ago) {
        hour_events.push_back(minute_events.front());

        minute_count -= minute_events.front().count;
        minute_events.pop_front();
    }

    // Remove events more than one hour old from 'hour_events'
    while (!hour_events.empty() && hour_events.front().time <= hour_ago) {
        hour_count -= hour_events.front().count;
        hour_events.pop_front();
    }
}

Are We Done?

Chúng ta đã giải quyết 2 vấn đề liên quan đến hiệu năng, và giải pháp này đã hoạt động. Với nhiều ứng dụng, giải pháp này là đủ tốt. Nhưng vẫn có 1 số thiếu sót.

Đầu tiên, thiếu kế thì rất không linh hoạt. Giả sử bạn muốn tiếp tục đếm trong 24h qua. Điều này yêu cầu thay đổi nhiều trong code. Và như bạn có thể thấy ShiftOldEvents() là 1 hàm khá nặng, với sự tương tác tinh tế giữa dữ liệu phút và giờ.

Thứ 2, lớp này có 1 bộ nhớ khá lớn. Giả sử bạn có 1 server high-traffic gọi Add() 100 lần mỗi giây. Vì chúng ta giữ tất cả các dữ liệu trong 1h qua, đoạn code này sẽ kết thúc và yêu cầu tầm 5M bộ nhớ

Nói chung, khi Add() thường xuyên được gọi, chúng ta sẽ cần nhiều bộ nhớ hơn. Trên môi trường sản phẩm, thư việc sử dụng bộ nhớ lớn, không thể đoán trước là không tốt. Lý tưởng, MinuteHourCounter sẽ sử dụng 1 lượng bộ nhớ nhất định mà không quan tâm hàm này được gọi bao nhiêu lần.

Attempt 3: A Time-Bucketed Design

Bạn có thể nhận thấy, cả 2 cách thực thi trên có 1 bug nhỏ. Chúng ta sử dụng time_t để lưu timestamp, cái mà lữu trữ số giây dưới dạng 1 số nguyên. Vì điều làm tròn này MinuteCount() thực sự trả về gì đó giữa 59 và 60 giây, dựa vào khi nào bạn gọi nó.

Ví dụ nếu 1 sự kiện diễn ra tạo time = 0.99 giây, thời gian trả về được làm tròn là 0s. Và nếu bạn gọi MinuteCount() tại time = 60.1 giây, nó sẽ trả về tổng các sự kiện có t=1,2,3,...60. Do đó sự kiện đầu tiên sẽ bị mất, mặc dù về mặt kĩ thuật đang chậm hơn 1 phút.

Trung bình, MinuteCount() sẽ trả về 59.5s giá trị của dữ liệu. Và HourCount() sẽ trả về 3599.5s giá trị dữ liệu (một lỗi không đáng kể).

Chúng ta có thể sửa lỗi này bằng cách sử dụng 1 thời gian với subsecond granularity. Nhưng một cách thú vị, đa số ứng dụng sử dụng 1 MinuteHourCounter không cần mức độ chính xác ở lần nhìn đầu tiên. Chúng ta sẽ khai thác sự thật này với 1 MinuteHourCounter mới, cái mà nhanh hơn nhiều mà sử dụng ít không gian hơn. Đó là sự đánh đổi độ chính xác cho hiệu năng sẽ rất xứng đáng.

Ỷ tưởng chính là kết hợp tất cả các sự kiện trong 1 cửa sổ nhỏ lại với nhau, và tóm tắt các sự kiện này với 1 tổng số duy nhất. Ví dụ các Sự kiện trong 1 phút qua có thể được thêm vào trong 60 xô rời rạc, độ rộng là 1 giây. Các sự kiện trong 1 giờ qua có thể được thêm vào 60 các xô rời rạc, độ rộng là 1 phút.

Sử dụng các xô như hình trên, phương thức MinuteCount() và HourCount() sẽ chính xác cho 1 phần trên 60, điều này là hợp lý.

Nếu cần nhiều độ chính xác hơn, nhiều buckets có thể được sử dụng để đổi lấy dung lượng bộ nhớ lớn hơn. Nhưng thứ quan trọng nhất các thiết kế này đã sửa được, sử dụng bộ nhớ đoán trước được.

Implementing the Time-Bucketed Design

Thực thi theo các thiết kế này chỉ có 1 lớp sẽ tạo nhiều code phức tạp cái mà khó để nhớ. Thay vào đó, chúng tôi sẽ theo lời khuyên trong Chapter 11, One Task at a Time và tạo ra các lớp riêng biệt để xử lý các phần khác nhau của vấn đề.

Để bắt đầu, tạo 1 lớp tách biệt để đếm khoảng thời gian duy nhất (như giờ trước). Chúng tôi sẽ gọi nó là TrailingBucketCounter. Đây thực chất là 1 phiên bản chung của MinuteHourCounter xử lý chỉ 1 khoảng thời gian:

// A class that keeps counts for the past N buckets of time.
class TrailingBucketCounter {
    public:
        // Example: TrailingBucketCounter(30, 60) tracks the last 30 minute-buckets of time.
        TrailingBucketCounter(int num_buckets, int secs_per_bucket);

        void Add(int count, time_t now);

        // Return the total count over the last num_buckets worth of time
        int TrailingCount(time_t now);
};

Bạn có thể tự hỏi tại sao Add() và TrailingCount() yêu cầu thời gian hiện tại (time_t_now) như 1 đối số - Tại sao nó không chỉ đơn giản là tự gọi current time()