Περιορισμός ρυθμού με token bucket — έλεγχοι χωρίς πραγματική αναμονή

Συμπεριφορά του υλοποιημένου αλγορίθμου

Ο κάδος tokens επιτρέπει μικρές εκρήξεις αιτημάτων και αναπληρώνει σταδιακά τη διαθέσιμη χωρητικότητα. Στον υπάρχοντα κώδικα Python, capacity είναι το μέγιστο πλήθος tokens, rate είναι τα tokens που προστίθενται ανά μονάδα χρόνου και κάθε επιτρεπόμενο αίτημα καταναλώνει ένα. Η allow(now) ενημερώνει την κατάσταση με την ώρα που δίνει ο καλών. Η ώρα πρέπει να προέρχεται από μονοτονικό ρολόι και να χρησιμοποιεί σταθερές μονάδες μέτρησης.

Πραγματικά αρχεία και επαλήθευση

Ο βασικός κώδικας βρίσκεται στο 18_token_bucket.py. Εκτέλεσε πρώτα python3 18_token_bucket.py. Κατόπιν αποθήκευσε το παρακάτω παράδειγμα ως test_bucket.py στον ίδιο κατάλογο και εκτέλεσέ το. Η runpy επιτρέπει την ανάγνωση αρχείου που αρχίζει με αριθμό χωρίς μετονομασία.

from runpy import run_path
TokenBucket = run_path("18_token_bucket.py")["TokenBucket"]
b = TokenBucket(2, 1)
assert [b.allow(t) for t in (0, 0, 0, 0.5, 1, 1)] == [
    True, True, False, False, True, False
]
try:
    b.allow(0.25)
except ValueError:
    pass
else:
    raise AssertionError("time regression accepted")
assert TokenBucket(0.5, 1).allow(1) is False
print("PASS bucket: burst, refill, regression, sub-token capacity")

Ανάλυση της ακολουθίας

Με χωρητικότητα 2 και ρυθμό 1, οι πρώτες δύο κλήσεις στο 0 καταναλώνουν τα δύο tokens. Η τρίτη στο 0 απορρίπτεται. Στον χρόνο 0.5 έχει αναπληρωθεί μόνο μισό token και η νέα προσπάθεια απορρίπτεται. Στον χρόνο 1 υπάρχει ένα πλήρες token, που καταναλώνεται αμέσως· δεύτερο αίτημα στον ίδιο χρόνο απορρίπτεται. Αν ο νέος χρόνος είναι μικρότερος από τον προηγούμενο, η συνάρτηση προκαλεί ValueError. Επομένως, η αλλαγή ώρας συστήματος δεν πρέπει να επηρεάζει τον περιορισμό.

Όρια της τωρινής υλοποίησης

Ο κώδικας ελέγχει μόνο ότι capacity και rate είναι θετικά. Δεν απορρίπτει ρητά μη πεπερασμένες τιμές όπως NaN και infinity. Αν capacity είναι μικρότερη του ενός, κανένα αίτημα δεν μπορεί να εγκριθεί. Αυτά είναι συγκεκριμένα σημεία για βελτίωση, όχι εγγυήσεις που έχει ήδη ελεγχθεί ότι λειτουργούν. Όταν πολλές ασύγχρονες εργασίες μοιράζονται έναν κάδο, χρειάζεται προστασία της κοινής κατάστασης.

Εξειδικευμένες ασκήσεις

1. Πρόσθεσε math.isfinite για capacity, rate και now. Αποφάσισε αν θα επιτρέπεται χωρητικότητα κάτω του ενός και απόρριψε άκυρα δεδομένα πριν μεταβληθεί η κατάσταση.
2. Πρόσθεσε wrapper με time.monotonic και όχι με time.time. Προσομοίωσε άλμα του ρολογιού προς τα πίσω χωρίς πραγματική αναμονή.
3. Κατέγραψε σε πίνακα τον χρόνο και τα διαθέσιμα tokens για κάθε μία από τις έξι κλήσεις.
4. Προσομοίωσε δέκα δευτερόλεπτα κίνησης και μέτρησε εγκρίσεις ανά χρονικό παράθυρο. Εξήγησε γιατί ο κάδος δεν εγγυάται δίκαιη σειρά εξυπηρέτησης.

Παραδοτέα: επιτυχία και των δύο Python scripts, έξι σωστές αποφάσεις, απόρριψη χρονικής παλινδρόμησης και τεκμηριωμένος περιορισμός για NaN/infinity.