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 thi 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ì và 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.

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ỏ hơn 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() và HourCount() quá chậm.

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().

Mặc dù có vẻ lạ, nhưng việc truyền thời gian hiện tại có một vài lợi ích. Đầu tiên, nó biến TrailingBucketCounter thành một lớp “không có đồng hồ”, nói chung là dễ kiểm tra hơn và ít có khả năng xảy ra lỗi hơn. Thứ hai, nó giữ tất cả các lệnh gọi đến time() bên trong MinuteHourCounter. Với các hệ thống nhạy cảm với thời gian, sẽ hữu ích nếu bạn có thể đặt tất cả các lệnh gọi để lấy thời gian ở một nơi.

Giả sử TrailingBucketCounter đã được triển khai, MinuteHourCounter rất dễ triển khai:

class MinuteHourCounter {
    TrailingBucketCounter minute_counts;
    TrailingBucketCounter hour_counts;

    public:
        MinuteHourCounter():
        minute_counts( /* num_buckets = */ 60, /* secs_per_bucket = */ 1),
        hour_counts( /* num_buckets = */ 60, /* secs_per_bucket = */ 60) {}

    void Add(int count) {
        time_t now = time();
        minute_counts.Add(count, now);
        hour_counts.Add(count, now);
    }

    int MinuteCount() {
        time_t now = time();
        return minute_counts.TrailingCount(now);
    }

    int HourCount() {
        time_t now = time();
        return hour_counts.TrailingCount(now);
    }
};

Mã này dễ đọc hơn nhiều và cũng linh hoạt hơn — nếu chúng ta muốn tăng số lượng buckets (để cải thiện độ chính xác nhưng tăng mức sử dụng bộ nhớ), điều đó sẽ dễ thực hiện.

Implementing TrailingBucketCounter

Bây giờ tất cả những gì còn lại là triển khai lớp TrailingBucketCounter. Một lần nữa, chúng ta sẽ tạo một lớp trợ giúp để phân tích vấn đề này sâu hơn nữa.

Chúng ta sẽ tạo một cấu trúc dữ liệu có tên là ConveyorQueue có nhiệm vụ xử lý các số đếm cơ bản và tổng số của chúng. Lớp TrailingBucketCounter có thể tập trung vào nhiệm vụ di chuyển ConveyorQueue theo thời gian đã trôi qua.

Sau đây là giao diện ConveyorQueue:

// A queue with a maximum number of slots, where old data "falls off" the end.
class ConveyorQueue {
    ConveyorQueue(int max_items);

    // Increment the value at the back of the queue. 
    void AddToBack(int count);

    // Each value in the queue is shifted forward by 'num_shifted'.
    // New items are initialized to 0.
    // Oldest items will be removed so there are <= max_items.
    void Shift(int num_shifted);

    // Return the total value of all items currently in the queue.
    int TotalSum();
};

Giả sử lớp này đã được triển khai, hãy xem TrailingBucketCounter dễ triển khai như thế nào:

class TrailingBucketCounter {
    ConveyorQueue buckets;
    const int secs_per_bucket;
    time_t last_update_time; // the last time Update() was called

    // Calculate how many buckets of time have passed and Shift() accordingly.
    void Update(time_t now) {
        int current_bucket = now / secs_per_bucket;
        int last_update_bucket = last_update_time / secs_per_bucket;

        buckets.Shift(current_bucket - last_update_bucket);
        last_update_time = now;
    }

    public:
        TrailingBucketCounter(int num_buckets, int secs_per_bucket):
        buckets(num_buckets),
        secs_per_bucket(secs_per_bucket) {}

        void Add(int count, time_t now) {
            Update(now);
            buckets.AddToBack(count);
        }

        int TrailingCount(time_t now) {
            Update(now);
            return buckets.TotalSum();
        }
};

Sự phân chia này thành hai lớp (TrailingBucketCounter và ConveyorQueue) là một ví dụ khác về những gì chúng ta đã thảo luận trong Chương 11, Một tác vụ tại một thời điểm. Chúng ta cũng có thể thực hiện mà không cần ConveyorQueue và triển khai mọi thứ trực tiếp bên trong TrailingBucketCounter. Nhưng theo cách này, mã dễ hiểu hơn.

Implementing ConveyorQueue

Bây giờ tất cả những gì còn lại là triển khai lớp ConveyorQueue:

// A queue with a maximum number of slots, where old data gets shifted off the end.
class ConveyorQueue {
    queue < int > q;
    int max_items;
    int total_sum; // sum of all items in q

    public:
        ConveyorQueue(int max_items): max_items(max_items), total_sum(0) {}
        int TotalSum() {
            return total_sum;
        }

        void Shift(int num_shifted) {
            // In case too many items shifted, just clear the queue. 
            if (num_shifted >= max_items) {
                q = queue < int > (); // clear the queue
                total_sum = 0;
                return;
            }

            // Push all the needed zeros.
            while (num_shifted > 0) {
                q.push(0);
                num_shifted--;
            }

            // Let all the excess items fall off.
            while (q.size() > max_items) {
                total_sum -= q.front();
                q.pop();
            }
        }

    void AddToBack(int count) {
        if (q.empty()) Shift(1); // Make sure q has at least 1 item. q.back() += count;
        total_sum += count;
    }
};

Bây giờ chúng ta đã hoàn tất! Chúng ta có MinuteHourCounter nhanh và tiết kiệm bộ nhớ, cộng với TrailingBucketCounter linh hoạt hơn, dễ dàng tái sử dụng. Ví dụ, sẽ khá dễ dàng để tạo ra một RecentCounter linh hoạt hơn, có thể đếm nhiều khoảng thời gian, chẳng hạn như ngày cuối cùng hoặc mười phút cuối cùng.

Comparing the Three Solutions

Hãy so sánh các giải pháp mà chúng ta đã xem xét trong chương này. Bảng sau đây hiển thị kích thước mã và số liệu thống kê hiệu suất (giả sử trường hợp sử dụng lưu lượng truy cập cao là 100 Add()/giây):

Solution	Lines of code	Cost per HourCount()	Memory use	Error in HourCount()
Naive solution	33	O(#events-per-hour) (~3.6 million)	unbounded	1 part per 3600
Conveyor belt design	55	O(1)	O(#events-per-hour) (~5MB)	1 part per 3600
Time-bucketed design (60 buckets)	98	O(1)	O(#buckets) (~500 bytes)	1 part per 60

Lưu ý rằng tổng lượng mã cho giải pháp ba lớp cuối cùng của chúng tôi nhiều hơn bất kỳ nỗ lực nào khác. Tuy nhiên, hiệu suất vượt trội hơn nhiều và thiết kế linh hoạt hơn. Ngoài ra, mỗi lớp riêng lẻ dễ đọc hơn nhiều. Đây luôn là một thay đổi tích cực: có 100 dòng dễ đọc sẽ tốt hơn 50 dòng không dễ đọc.

Đôi khi, việc chia một vấn đề thành nhiều lớp có thể tạo ra sự phức tạp giữa các lớp (điều mà giải pháp một lớp sẽ không có). Tuy nhiên, trong trường hợp này, có một chuỗi sử dụng “tuyến tính” đơn giản từ lớp này sang lớp khác và chỉ một trong các lớp được hiển thị cho người dùng cuối. Nhìn chung, những lợi ích của việc chia nhỏ vấn đề này khiến đây trở thành một chiến thắng.

Summary

Hãy cùng xem lại các bước chúng ta đã trải qua để có được thiết kế MinuteHourCounter cuối cùng. Quá trình này là điển hình cho cách các đoạn mã khác phát triển.

Đầu tiên, chúng tôi bắt đầu bằng cách mã hóa một giải pháp ngây thơ. Điều này giúp chúng tôi nhận ra hai thách thức về thiết kế: tốc độ và sử dụng bộ nhớ.

Tiếp theo, chúng tôi đã thử thiết kế “băng chuyền”. Thiết kế này đã cải thiện tốc độ và sử dụng bộ nhớ nhưng vẫn chưa đủ tốt cho các ứng dụng hiệu suất cao. Ngoài ra, thiết kế này rất không linh hoạt: việc điều chỉnh mã để xử lý các khoảng thời gian khác sẽ tốn rất nhiều công sức.

Thiết kế cuối cùng của chúng tôi đã giải quyết các vấn đề trước đó bằng cách chia nhỏ mọi thứ thành các bài toán con. Sau đây là ba lớp chúng tôi đã tạo, theo thứ tự từ dưới lên, và bài toán con mà mỗi lớp giải quyết:

ConveyorQueue

Một hàng đợi có độ dài tối đa có thể được “chuyển” và duy trì tổng số của nó.

TrailingBucketCounter

Di chuyển ConveyorQueue theo thời gian đã trôi qua và duy trì số lượng của một khoảng thời gian duy nhất (mới nhất), với độ chính xác nhất định.

MinuteHourCounter

Chỉ chứa hai TrailingBucketCounter, một cho số phút và một cho số giờ.