Máy tính Erlang C trả lời câu hỏi gì?
"Cần bao nhiêu nhân viên trực tổng đài?" và "cần bao nhiêu máy chủ khi ra mắt?" thực chất là cùng một bài toán. Yêu cầu đến ngẫu nhiên, mỗi yêu cầu chiếm một máy chủ trong một khoảng thời gian, ai đến lúc mọi máy chủ đều bận thì phải xếp hàng. Công cụ này mô hình hoá tình huống đó bằng hàng đợi M/M/c và dùng công thức Erlang C, do kỹ sư người Đan Mạch A. K. Erlang công bố năm 1917, để tính xác suất phải chờ, thời gian chờ trung bình, độ dài hàng đợi và tỷ lệ lượt đến được phục vụ trong thời gian mục tiêu.
Sau đó công cụ tính ngược: tìm số máy chủ nhỏ nhất đạt mức phục vụ mục tiêu (và thời gian chờ trung bình tối đa nếu bạn đặt), kèm bảng ngắn quanh con số đó để thấy thêm hoặc bớt một máy chủ thay đổi ra sao.
Cách sử dụng
- Tốc độ đến λ: số cuộc gọi, phiên chat, phiếu hỗ trợ hoặc request mỗi giây, phút hoặc giờ. Hãy dùng tốc độ của khung giờ cao điểm, không dùng trung bình cả ngày.
- Thời gian phục vụ trung bình: thời gian xử lý trung bình cho mỗi lượt (thời gian nói chuyện cộng thời gian hoàn tất sau cuộc gọi ở tổng đài, hoặc thời gian xử lý request ở máy chủ). Bạn cũng có thể nhập tốc độ phục vụ μ của mỗi máy chủ.
- Số máy chủ c: số nhân viên, worker, luồng hoặc máy phục vụ song song. Để trống nếu muốn xem kết quả ở số lượng được đề xuất.
- Mục tiêu mức phục vụ: tỷ lệ lượt đến phải chờ không quá T. Giá trị mặc định 80% trong 20 giây chỉ là ví dụ thường gặp, không phải quy định hay tiêu chuẩn. Hãy nhập mục tiêu của bạn.
Công cụ cũng dùng được cho bài toán năng lực hệ thống IT: nhập số request mỗi giây, thời gian phục vụ tính bằng mili giây, và hiểu "máy chủ" là số worker chạy đồng thời.
Công thức
Với tốc độ đến λ và thời gian phục vụ trung bình s (tốc độ phục vụ μ = 1/s), lưu lượng tải là A = λ/μ erlang và hệ số sử dụng là ρ = A/c. Hàng đợi chỉ ổn định khi A < c. Nếu không, hàng đợi dài mãi và công cụ báo rõ điều đó thay vì hiện một con số.
Xác suất một lượt đến phải chờ là Erlang C, C(c, A). Công cụ tính qua đệ quy Erlang B: Bk = A·Bk−1 / (k + A·Bk−1) và C = c·B / (c − A(1 − B)). Cách này không dùng giai thừa nên vẫn chính xác với hàng nghìn máy chủ. Từ C suy ra:
- thời gian chờ trung bình trong hàng Wq = C / (cμ − λ), thời gian trung bình trong hệ thống W = Wq + 1/μ;
- độ dài hàng đợi trung bình Lq = λWq, số lượt trung bình trong hệ thống L = Lq + A;
- mức phục vụ P(Wq ≤ T) = 1 − C·e−(cμ−λ)T (đến trước phục vụ trước).
Các kết quả thoả định luật Little L = λW, được hiện ngay trong kết quả để đối chiếu. Bạn có thể kiểm tra chéo bằng công cụ tính throughput (định luật Little).
Ví dụ minh hoạ
Một bộ phận hỗ trợ nhận 120 cuộc gọi mỗi giờ (2 cuộc mỗi phút), thời gian xử lý trung bình 4 phút, nên A = 2 × 4 = 8 erlang. Với 10 nhân viên, hệ số sử dụng là 80%, 40,9% người gọi phải chờ, thời gian chờ trung bình khoảng 49 giây và chỉ 65,4% cuộc gọi được trả lời trong 20 giây. Với 11 nhân viên, xác suất phải chờ giảm còn 24,5%, thời gian chờ trung bình còn 19,6 giây và mức phục vụ lên 80,9%. Vậy 11 nhân viên đạt mục tiêu 80% trong 20 giây. Với 12 nhân viên con số là 90,0%.
Đối chiếu sách giáo khoa: trong Teletraffic Engineering and Network Planning của Iversen (Ví dụ 9.3.1), hệ thống có lưu lượng 20 erlang, thời gian phục vụ trung bình 100 giây và 32 kênh có thời gian chờ trung bình 0,075 giây. Công cụ này cho 0,0747 giây.
Ví dụ IT: 5.000 request mỗi giây, mỗi request 120 ms, tức A = 600 erlang. Để 99% request bắt đầu được xử lý trong 50 ms, cần 610 worker đồng thời. Khi đó hệ số sử dụng là 98,4% và thời gian chờ trung bình khoảng 7 ms.
Giả định và giới hạn
- Lượt đến ngẫu nhiên và độc lập (quá trình Poisson), thời gian phục vụ có phân phối mũ.
- Các máy chủ giống nhau, phục vụ theo thứ tự đến trước, hàng chờ không giới hạn.
- Không ai bỏ cuộc. Thực tế người gọi có cúp máy, khi đó Erlang C ước lượng thời gian chờ và số nhân sự cần cao hơn thực tế. Mô hình Erlang A (M/M/N+M, Garnett, Mandelbaum & Reiman, 2002) có tính đến việc bỏ cuộc.
- Kết quả là số nhân viên thực sự sẵn sàng nghe máy. Cần cộng thêm thời gian nghỉ, đào tạo và vắng mặt (shrinkage).
- Lưu lượng dồn cục, gửi lại request và thời gian phục vụ dao động mạnh thường làm hàng đợi tệ hơn mô hình. Hãy coi kết quả là mức tối thiểu và kiểm chứng bằng tải thật.
Muốn xem giới hạn tăng tốc khi chạy song song một tác vụ, dùng máy tính định luật Amdahl.