Phân tích: Load Testing

Hiểu các trường hợp ví dụ

Để giải quyết bài toán này, trước tiên cần cảm nhận được những gì được yêu cầu, và xem xét các trường hợp ví dụ là một cách tốt để đạt được điều đó.

Hãy xem xét trường hợp ví dụ đầu tiên (\(L=50, P=700, C=2\)). Đáp án đưa ra là 2. Làm thế nào để đạt được kết quả chỉ với 2 bài kiểm tra tải? Hãy thử đưa ra một vài dự đoán. Giả sử chúng ta thực hiện một bài kiểm tra tải kiểm tra xem trang web có hỗ trợ 100 người dùng hay không. Nếu chúng ta biết rằng trang web không thể hỗ trợ 100 người dùng, thì chúng ta đã xong: chúng ta biết mình có thể hỗ trợ 50 người nhưng không thể hỗ trợ 100 người, mà \(100 = 50 \times 2\). Tuy nhiên, nếu chúng ta biết rằng trang web thực sự có thể hỗ trợ 100 người dùng, chúng ta sẽ gặp một nhiệm vụ rất khó khăn: chúng ta chỉ còn lại một bài kiểm tra tải, và chúng ta biết rằng trang web có thể hỗ trợ 100 người nhưng không thể hỗ trợ 700 người. Liệu có thể giải quyết được không?

Giả sử bây giờ chúng ta kiểm tra tải để xem trang web có hỗ trợ 300 người dùng hay không. Nếu chúng ta biết rằng trang web không thể hỗ trợ 300 người dùng, thì chúng ta đã thất bại trong việc giải quyết bài toán: chúng ta biết mình có thể hỗ trợ 100, nhưng không thể hỗ trợ 300 - nhưng 300 lớn hơn \(100 \times 2\), vì vậy chúng ta không có đủ kiến thức. Hơn nữa, điều này thực sự giúp chúng ta chứng minh rằng bài kiểm tra tải của chúng ta phải kiểm tra cho 200 người dùng trở xuống, nếu không chúng ta sẽ gặp vấn đề tương tự.

Bây giờ chúng ta biết rằng bài kiểm tra tải thứ hai của mình phải sử dụng tối đa 200 người dùng. Nhưng ngay cả khi nó chính xác là 200, giả sử chúng ta biết rằng trang web của mình thực sự có thể hỗ trợ tất cả họ. Khi đó chúng ta lại thất bại một lần nữa: chúng ta biết mình có thể hỗ trợ 200, nhưng không thể hỗ trợ 700 - mà 700 lớn hơn \(200 \times 2\).

Vì vậy, không có lựa chọn tốt nào cho bài kiểm tra tải thứ hai của chúng ta. Điều đó có nghĩa là lựa chọn bài kiểm tra tải đầu tiên là sai - 100 người dùng là quá ít.

Chúng ta đã học được gì?

Tuy nhiên, chúng ta đã học được một bài học quan trọng trong nỗ lực thất bại để hiểu trường hợp ví dụ: khi chúng ta chỉ còn lại một bài kiểm tra tải, và chúng ta biết rằng trang web có thể hỗ trợ \(L\) người nhưng không thể hỗ trợ \(P\) người, chúng ta phải kiểm tra tải với số \(X\) sao cho \(L \times C \ge X\), và đồng thời \(X \times C \ge P\). Bất đẳng thức đầu tiên sẽ giúp chúng ta giải quyết bài toán khi bài kiểm tra tải thất bại, và bất đẳng thức thứ hai hữu ích nếu bài kiểm tra tải thành công.

Vì không có số \(X\) nào như vậy cho \(L=100, P=700, C=2\), nên nỗ lực đầu tiên của chúng ta ở trên đã thất bại.

Câu hỏi bây giờ là: làm thế nào để kiểm tra xem \(X\) như vậy có tồn tại hay không? Từ phương trình đầu tiên, chúng ta có \(X \le L \times C\). Từ phương trình thứ hai, chúng ta có \(X \ge P/C\). Một số \(X\) như vậy tồn tại khi và chỉ khi \(L \times C \ge P/C\), tức là \(L \times C^2 \ge P\). Bỏ qua các công thức, giới hạn trên của phạm vi của chúng ta tối đa phải gấp \(C^2\) lần giới hạn dưới. Trong trường hợp đó, chúng ta chỉ cần lấy \(X = L \times C\) cho bài kiểm tra tải duy nhất của mình.

Nỗ lực thứ hai để hiểu trường hợp ví dụ đầu tiên

Được trang bị kiến thức này, chúng ta quay lại trường hợp ví dụ đầu tiên. 100 là sai vì \(100 \times 2^2 = 100 \times 4 < 700\). Có lẽ chúng ta nên kiểm tra tải cho 300 người trước? Nếu bài kiểm tra tải thành công, thì chúng ta sẽ còn lại một bài kiểm tra tải, 300 người OK, 700 người không OK, và vì \(300 \times 4 \ge 700\), chúng ta có thể giải quyết bài toán. Tuy nhiên, điều gì sẽ xảy ra nếu bài kiểm tra tải không thành công? Chúng ta biết rằng hệ thống của mình có thể hỗ trợ 50 người nhưng không thể hỗ trợ 300 người và chỉ còn lại một bài kiểm tra tải. Vì \(50 \times 4 < 300\), chúng ta không thể làm điều đó. Vì vậy, lựa chọn 300 cũng sai.

Nếu chúng ta thử 200 làm bài kiểm tra tải đầu tiên thì sao? Trong trường hợp nó thành công, chúng ta có một bài kiểm tra, 200 OK, 700 không OK, \(200 \times 4 \ge 700\) - chúng ta có thể làm điều đó. Trong trường hợp nó thất bại, chúng ta có 50 OK, 200 không OK, \(50 \times 4 \ge 200\) - chúng ta cũng có thể làm điều đó. Vì vậy, cuối cùng chúng ta đã tìm ra thuật toán để giải quyết trường hợp ví dụ đầu tiên chỉ bằng 2 bài kiểm tra tải:

Loadtest for 200 people. If the site can support 200 people:
  Loadtest for 400 people.
If the site can't support 200 people:
  Loadtest for 100 people.

Chúng ta đã học được gì tiếp theo?

Vậy làm thế nào để chúng ta biết liệu hai bài kiểm tra tải có đủ hay không? Điều này thực sự tương tự một cách đáng ngạc nhiên với việc nghiên cứu trường hợp một bài kiểm tra tải.

Khi chúng ta còn lại hai bài kiểm tra tải, và chúng ta biết rằng trang web có thể hỗ trợ \(L\) người nhưng không thể hỗ trợ \(P\) người, chúng ta phải kiểm tra tải với số \(X\) sao cho \(L \times C^2 \ge X\), và đồng thời \(X \times C^2 \ge P\). Bất đẳng thức đầu tiên sẽ giúp chúng ta giải quyết bài toán bằng cách sử dụng một bài kiểm tra tải còn lại khi bài kiểm tra tải hiện tại thất bại, và bất đẳng thức thứ hai hữu ích nếu nó thành công.

Sử dụng cùng một lập luận như trên, người ta có thể thấy rằng số \(X\) như vậy tồn tại khi và chỉ khi \(L \times C^4 \ge P\) (chúng ta có \(C^4\) là \(C^2 \times C^2\)).

Nhiều bài kiểm tra tải hơn?

Bây giờ không quá khó để tìm ra điều gì xảy ra với nhiều hơn hai bài kiểm tra tải. Có thể giải quyết bài toán bằng ba bài kiểm tra tải khi và chỉ khi \(L \times C^8 \ge P\). Đối với bốn bài kiểm tra tải, chúng ta có \(L \times C^{16} \ge P\). Và cứ tiếp tục như vậy. Điều đó mô tả khá đầy đủ giải pháp cho bài toán này.

Hiểu các trường hợp ví dụ, nỗ lực 3

Bây giờ cuối cùng chúng ta có thể tìm ra thuật toán để giải quyết trường hợp ví dụ thứ ba: \(L=1, P=1000, C=2\). Để thực hiện việc này trong bốn bài kiểm tra tải, bài kiểm tra tải đầu tiên của chúng ta có thể dành cho \(L \times C^8 = 256\):

Loadtest for 256 people. If the site can support them:
  Loadtest for 512 people.
If we can't support 256 people:
  Loadtest for 16 people. If the site can support them:
    Loadtest for 64 people. If the site can support them:
      Loadtest for 128 people.
    If we can't support 64 people:
      Loadtest for 32 people.
  If we can't support 16 people:
    Loadtest for 4 people. If the site can support them:
      Loadtest for 8 people.
    If we can't support 4 people:
      Loadtest for 2 people.

Điều này trông khá giống với thuật toán tìm kiếm nhị phân, nhưng được thực hiện trên thang đo lũy thừa.

Kết luận

Chúng ta bắt đầu giải quyết bài toán này bằng cách cố gắng hiểu các câu trả lời cho các trường hợp ví dụ, và vào thời điểm chúng ta thực sự hiểu chúng, chúng ta đã có một giải pháp hoàn chỉnh. Điều duy nhất còn lại là triển khai giải pháp một cách cẩn thận để tránh các vấn đề tràn số nguyên.

Dựa trên phân tích chính thức của Google Code Jam.