Khắc phục sự cố Production lúc 2 giờ sáng bằng Quy hoạch động trong Python

Cuộc gọi báo thức từ PagerDuty lúc 2:14 sáng

Điện thoại của tôi bắt đầu kêu inh ỏi lúc 2:14 sáng. Hệ thống logistics của chúng tôi—dịch vụ chịu trách nhiệm tính toán chi phí vận chuyển tối thiểu cho các đơn hàng đa kho—không chỉ chậm mà còn bị treo hoàn toàn. Chỉ số CPU của node prod-worker-04 hiển thị một đường thẳng tắp ở mức 100%. Trong khi đó, hàng đợi yêu cầu đã tăng vọt từ 20 mục thông thường lên hơn 8.500 chỉ trong chưa đầy ba phút.

Tôi SSH vào máy chủ và kiểm tra log. Việc tìm và sửa các điểm nghẽn hiệu năng cho thấy thủ phạm là một hàm cũ có tên calculate_min_cost. Nó đang vật lộn với một tập dữ liệu chỉ lớn hơn 15% so với tải thông thường của chúng tôi. Đây không phải là lỗi database deadlock hay sự cố mạng. Đó là một trường hợp kinh điển của thuật toán đệ quy sơ khai (naive recursion) bị sụp đổ dưới sức nặng của chính nó. Tại thời điểm đó, Quy hoạch động (Dynamic Programming – DP) không còn là lý thuyết trong sách giáo khoa nữa mà trở thành một kỹ năng sinh tồn bắt buộc.

Nguyên nhân gốc rễ: Cái bẫy Brute Force

Vấn đề là một biến thể của “Bài toán đổi tiền” (Change-Making Problem). Chúng tôi phải tìm số lượng container vận chuyển tối thiểu để đáp ứng một thể tích cụ thể. Một lập trình viên trước đó đã cố gắng viết logic sạch sẽ, dễ đọc bằng một hàm đệ quy như sau:

def calculate_min_containers(volumes, target):
    if target == 0:
        return 0
    if target < 0:
        return float('inf')

    res = float('inf')
    for v in volumes:
        sub_res = calculate_min_containers(volumes, target - v)
        if sub_res != float('inf'):
            res = min(res, sub_res + 1)
            
    return res

Logic rất thanh thoát, nhưng tính toán thì cực kỳ nặng nề. Nếu bạn muốn đạt được thể tích mục tiêu là 100 bằng các kích thước container [1, 5, 10], hàm này sẽ phân nhánh một cách chóng mặt.

Nó không chỉ tính toán chi phí cho thể tích 50 một lần; nó tính toán lại chính giá trị đó hàng ngàn lần trên các nhánh khác nhau. Tương tự như việc không tối ưu xử lý sự kiện và giảm tải API, sự dư thừa này nhanh chóng làm cạn kiệt tài nguyên. Độ phức tạp thời gian xấp xỉ O(V^T), trong đó V là số loại container và T là mục tiêu. Trong môi trường production, điều này có nghĩa là thời gian thực thi tăng theo cấp số nhân với mỗi kích thước container mới được thêm vào danh sách.

Giải pháp 1: Memoization (Bản vá Top-Down nhanh chóng)

Tôi cần một bản vá lúc 2:30 sáng mà không phải thay đổi toàn bộ kiến trúc. Cách nhanh nhất để tối ưu hóa đệ quy là Memoization. Bạn lưu trữ kết quả của mọi lần tính toán vào một “memo” (một dictionary hoặc mảng) để không bao giờ phải giải cùng một bài toán hai lần.

Python giúp việc này cực kỳ dễ dàng với functools.lru_cache có sẵn. Đây là bản vá tôi đã đẩy lên production:

from functools import lru_cache

def solve_with_memo(volumes, target):
    @lru_cache(None)  # Cache vô hạn trong suốt thời gian yêu cầu
    def helper(rem):
        if rem == 0: return 0
        if rem < 0: return float('inf')

        res = float('inf')
        for v in volumes:
            sub_problem = helper(rem - v)
            if sub_problem != float('inf'):
                res = min(res, sub_problem + 1)
        return res

    result = helper(target)
    return result if result != float('inf') else -1

Kết quả đến ngay lập tức. Thay vì tính toán lại chi phí cho thể tích còn lại là 50, hàm chỉ việc lấy nó từ cache. Điều này đã thay đổi độ phức tạp từ cấp số nhân sang O(V * T) có thể kiểm soát được. Chỉ vài giây sau khi triển khai, mức sử dụng CPU trên worker node đã giảm mạnh từ 100% xuống còn 4%.

Giải pháp 2: Tabulation (Cách tiếp cận Bottom-Up chuyên nghiệp)

Memoization đã cứu vãn đêm đó, nhưng nó không phải là giải pháp lâu dài hoàn hảo. Python có giới hạn đệ quy mặc định là 1.000. Nếu một khách hàng đặt hàng với thể tích mục tiêu là 5.000, phiên bản memoization của chúng tôi sẽ kích hoạt lỗi RecursionError và vẫn bị sụp đổ. Để xây dựng một hệ thống mạnh mẽ, chúng tôi cần Tabulation.

Tabulation là một cách tiếp cận “từ dưới lên”. Thay vì chia nhỏ một mục tiêu lớn, chúng ta bắt đầu với bài toán con nhỏ nhất có thể—mục tiêu bằng không—và lấp đầy một bảng cho đến khi đạt được mục tiêu cuối cùng.

def solve_with_tabulation(volumes, target):
    # Khởi tạo một bảng với các giá trị lớn hơn bất kỳ kết quả khả thi nào
    dp = [float('inf')] * (target + 1)
    dp[0] = 0

    # Lấp đầy bảng theo vòng lặp từ 1 đến target
    for i in range(1, target + 1):
        for v in volumes:
            if i - v >= 0:
                dp[i] = min(dp[i], dp[i - v] + 1)

    return dp[target] if dp[target] != float('inf') else -1

Đây là tiêu chuẩn cho các ứng dụng Python hiệu năng cao. Nó loại bỏ chi phí của hàng ngàn lần gọi hàm và hoàn toàn bỏ qua giới hạn đệ quy. Nó có tính lặp lại, dễ dự đoán và dễ dàng đo lường hiệu năng hơn trong quá trình stress test.

So sánh hai chiến lược

Cách tiếp cận tốt nhất: Khi nào nên dùng loại nào?

Sau khi báo cáo sự cố được nộp và tôi đã uống chút cà phê, tôi ngồi lại với nhóm để thiết lập một số tiêu chuẩn. Hiện tại chúng tôi tuân theo một quy tắc ngón tay cái đơn giản cho các bài toán DP:

• Chọn Memoization nếu “không gian trạng thái” (state space) thưa thớt. Nếu bạn chỉ cần tính toán 50 giá trị cụ thể trong số 10.000 giá trị có thể, đừng lãng phí thời gian xây dựng một bảng đầy đủ. Chỉ tính toán những gì bạn cần.
• Chọn Tabulation nếu bạn cần giải quyết hầu hết mọi bài toán con để có câu trả lời. Nó tiết kiệm bộ nhớ hơn trong Python vì không thêm hàng ngàn khung (frame) vào call stack.

Những gì tôi học được lúc 3 giờ sáng

Những công việc dư thừa là kẻ sát nhân thầm lặng của khả năng mở rộng (scalability). Khi tôi tái cấu trúc dịch vụ logistics, tôi đã thay thế logic đệ quy bằng phương pháp Tabulation. Kể từ đó, chúng tôi không còn thấy CPU spike trong module đó nữa, ngay cả trong kỳ nghỉ lễ cao điểm khi lưu lượng tăng gấp ba lần.

Nếu bạn đang viết một hàm đệ quy trả về một giá trị tối ưu, hãy dừng lại và kiểm tra lại phép toán của mình. Hãy tự hỏi: “Mình có đang giải cùng một bài toán con hai lần không?” Nếu câu trả lời là có, bạn đang gặp một bài toán Quy hoạch động. Hãy lập bản đồ trạng thái, chọn chiến lược của bạn, và bản thân bạn trong tương lai sẽ cảm ơn bạn khi chiếc máy nhắn tin (pager) im lặng lúc 2 giờ sáng.

Việc chuyển từ “chạy được” sang “chạy được ở quy mô lớn” thường nằm ở những thay đổi nhỏ về thuật toán này. Python cung cấp cho bạn các công cụ, nhưng hiểu cách bảng đó được xây dựng mới là điều phân biệt một lập trình viên với một kỹ sư hệ thống.