Cara Menangani Lalu Lintas yang Melonjak: Algoritma Leaky Bucket dan Token Bucket

API7.ai

January 5, 2023

OpenResty (NGINX + Lua)

Pada artikel sebelumnya, kita telah mempelajari tentang optimisasi kode dan desain cache, yang sangat terkait dengan performa keseluruhan aplikasi dan patut mendapatkan perhatian kita. Namun, dalam skenario bisnis nyata, kita juga perlu mempertimbangkan dampak dari lalu lintas yang meledak (burst traffic) terhadap performa. Lalu lintas yang meledak di sini bisa bersifat normal, seperti lalu lintas dari berita terbaru, promosi, dll., atau lalu lintas yang tidak normal, seperti serangan DDoS.

OpenResty saat ini terutama digunakan sebagai lapisan akses untuk aplikasi web seperti WAF (Web Application Firewall) dan API gateway, yang harus menangani lalu lintas yang meledak baik yang normal maupun yang tidak normal. Bagaimanapun, jika tidak dapat menangani lalu lintas yang meledak, layanan backend dapat dengan mudah jatuh, dan bisnis tidak akan merespons dengan tepat. Jadi, hari ini kita akan melihat cara-cara untuk menangani lalu lintas yang meledak.

Pengendalian Lalu Lintas

Pengendalian lalu lintas adalah fitur yang harus dimiliki oleh WAF dan API gateway. Ini memastikan bahwa layanan upstream dapat berfungsi dengan baik dengan mengarahkan dan mengontrol lalu lintas masuk melalui beberapa algoritma, sehingga menjaga sistem tetap sehat.

Karena kapasitas pemrosesan backend terbatas, kita perlu mempertimbangkan berbagai aspek seperti biaya, pengalaman pengguna, dan stabilitas sistem. Tidak peduli algoritma apa yang digunakan, hal itu pasti akan menyebabkan permintaan pengguna normal melambat atau bahkan ditolak, mengorbankan sebagian pengalaman pengguna. Oleh karena itu, kita perlu mengontrol lalu lintas sambil menyeimbangkan stabilitas bisnis dan pengalaman pengguna.

Sebenarnya, ada banyak kasus "pengendalian lalu lintas" dalam kehidupan nyata. Misalnya, selama musim liburan Tahun Baru Imlek di Tiongkok, arus orang memadati stasiun kereta bawah tanah, stasiun kereta api, bandara, dan pusat transportasi lainnya karena kapasitas penanganan kendaraan ini terbatas. Oleh karena itu, penumpang harus antri dan masuk ke stasiun secara bergiliran untuk memastikan keselamatan mereka dan operasi lalu lintas yang normal.

Hal ini secara alami memengaruhi pengalaman penumpang, tetapi secara keseluruhan, ini memastikan operasi sistem yang efisien dan aman. Misalnya, jika tidak ada antrian dan pengelompokan, tetapi semua orang diizinkan masuk ke stasiun secara berkerumun, hasilnya adalah seluruh sistem akan jatuh.

Kembali ke teknologi, misalnya, mari kita asumsikan bahwa layanan upstream dirancang untuk menangani 10.000 permintaan per menit. Pada saat puncak, jika tidak ada pengendalian aliran di titik masuk dan tumpukan tugas mencapai 20.000 per menit, performa pemrosesan layanan upstream ini akan menurun menjadi mungkin hanya 5.000 permintaan per menit dan terus memburuk, mungkin akhirnya menyebabkan layanan tidak tersedia. Ini bukan hasil yang ingin kita lihat.

Algoritma pengendalian lalu lintas umum yang kita gunakan untuk menghadapi lalu lintas yang meledak seperti ini adalah algoritma ember bocor (leaky bucket algorithm) dan algoritma ember token (token bucket algorithm).

Algoritma Ember Bocor

Mari kita mulai dengan melihat algoritma ember bocor, yang bertujuan untuk menjaga tingkat permintaan yang konstan dan melancarkan lalu lintas yang meledak. Tetapi bagaimana hal itu dicapai? Pertama, lihat abstraksi konseptual berikut dari pengenalan algoritma ember bocor di Wikipedia.

algoritma ember bocor

Kita dapat membayangkan lalu lintas klien sebagai air yang mengalir dari pipa air dengan laju aliran yang tidak pasti, kadang cepat dan kadang lambat. Modul pemrosesan lalu lintas eksternal, yaitu ember yang menerima air, memiliki lubang di bagian bawah untuk kebocoran. Ini adalah asal nama algoritma ember bocor, yang memiliki manfaat berikut:

Pertama, apakah aliran ke dalam ember berupa tetesan kecil atau banjir besar, dijamin bahwa laju air yang keluar dari ember adalah konstan. Lalu lintas yang stabil ini ramah terhadap layanan upstream, itulah yang dimaksud dengan pembentukan lalu lintas (traffic shaping).

Kedua, ember itu sendiri memiliki volume tertentu dan dapat menampung sejumlah air. Ini setara dengan permintaan klien yang dapat diantrekan jika tidak dapat diproses segera.

Ketiga, air yang melebihi volume ember tidak akan diterima oleh ember tetapi akan mengalir pergi. Metafora yang sesuai di sini adalah jika ada terlalu banyak permintaan klien yang melebihi panjang antrean, itu akan langsung mengembalikan pesan kegagalan kepada klien. Pada saat ini, sisi server tidak dapat menangani begitu banyak permintaan dan antrean menjadi tidak perlu.

Jadi, bagaimana algoritma ini harus diimplementasikan? Mari kita ambil library resty.limit.req yang disertakan dengan OpenResty sebagai contoh. Ini adalah modul pembatasan laju yang diimplementasikan oleh algoritma ember bocor. Kita akan membahas lebih lanjut tentangnya dalam artikel berikutnya. Hari ini kita akan mulai dengan melihat sekilas beberapa baris kode berikut, yang merupakan kunci:

local elapsed = now - tonumber(rec.last)
excess = max(tonumber(rec.excess) - rate * abs(elapsed) / 1000 + 1000,0)
if excess > self.burst then
    return nil, "rejected"
end
-- return the delay in seconds, as well as excess
return excess / rate, excess / 1000

Mari kita baca baris kode ini secara singkat. Di mana elapsed adalah jumlah milidetik antara permintaan saat ini dan terakhir, dan rate adalah laju yang kita tetapkan per detik. Karena unit terkecil dari rate adalah 0,001 s/r, kode yang diimplementasikan di atas perlu dikalikan dengan 1000 untuk menghitungnya.

excess menunjukkan jumlah permintaan yang masih dalam antrean, 0 berarti ember kosong, tidak ada permintaan dalam antrean, dan burst mengacu pada volume seluruh ember. Jika excess lebih besar dari burst, itu berarti ember penuh, dan lalu lintas yang masuk akan langsung dibuang; jika excess lebih besar dari 0 dan kurang dari burst, itu akan masuk ke antrean untuk menunggu pemrosesan, dan excess/rate yang dikembalikan di sini adalah waktu tunggu.

Dengan cara ini, kita dapat mengontrol panjang antrean lalu lintas yang meledak dengan menyesuaikan ukuran burst, sementara kapasitas pemrosesan layanan backend tetap tidak berubah. Tentu saja, tergantung pada skenario bisnis Anda, apakah Anda memberi tahu pengguna bahwa ada terlalu banyak permintaan dan untuk mencoba lagi nanti, atau membiarkan pengguna menunggu lebih lama.

Algoritma Ember Token

Baik algoritma ember token maupun algoritma ember bocor memiliki tujuan yang sama, yaitu memastikan bahwa layanan backend tidak kewalahan oleh lalu lintas yang meledak, meskipun keduanya tidak diimplementasikan dengan cara yang sama.

Algoritma ember bocor menggunakan alamat IP endpoint untuk melakukan dasar pengendalian lalu lintas dan pembatasan laju. Dengan cara ini, laju keluar setiap klien dari algoritma ember bocor adalah tetap. Namun, ini menimbulkan masalah:

Misalkan permintaan pengguna A sering dan permintaan pengguna lain jarang. Dalam hal ini, algoritma ember bocor akan memperlambat atau menolak beberapa permintaan A, meskipun layanan dapat menanganinya pada saat itu, meskipun tekanan layanan secara keseluruhan tidak terlalu tinggi.

Di sinilah ember token berguna.

Sementara algoritma ember bocor berkaitan dengan melancarkan lalu lintas, ember token memungkinkan lalu lintas yang meledak masuk ke layanan backend. Prinsip ember token adalah memasukkan token ke dalam ember dengan laju tetap dan terus memasukkannya selama ember tidak penuh. Dengan cara ini, semua permintaan yang datang dari endpoint perlu pergi ke ember token untuk mendapatkan token terlebih dahulu sebelum backend dapat memprosesnya; jika tidak ada token di dalam ember, maka permintaan akan ditolak.

Namun, OpenResty tidak mengimplementasikan ember token untuk membatasi lalu lintas dan laju dalam library-nya. Jadi, berikut adalah pengenalan singkat tentang modul pembatasan laju berbasis ember token lua-resty-limit-rate, yang diopen-source oleh UPYUN, sebagai contoh:

local limit_rate = require "resty.limit.rate"

-- global 20r/s 6000r/5m
local lim_global = limit_rate.new("my_limit_rate_store", 100, 6000, 2)

-- single 2r/s 600r/5m
local lim_single = limit_rate.new("my_limit_rate_store", 500, 600, 1)

local t0, err = lim_global:take_available("__global__", 1)
local t1, err = lim_single:take_available(ngx.var.arg_userid, 1)

if t0 == 1 then
    return -- global bucket is not hungry
else
    if t1 == 1 then
        return -- single bucket is not hungry
    else
        return ngx.exit(503)
    end
end

Dalam kode ini, kita menyiapkan dua ember token: ember token global, dan ember token dengan ngx.var.arg_userid sebagai key, dibagi berdasarkan pengguna. Ada kombinasi dari dua ember token ini, yang memiliki manfaat utama berikut:

  • Tidak perlu menentukan ember token pengguna jika masih ada token dalam ember token global, dan melayani sebanyak mungkin permintaan yang meledak dari pengguna jika layanan backend dapat berjalan dengan baik.
  • Jika tidak ada ember token global, permintaan tidak dapat ditolak secara sembarangan, jadi perlu menentukan ember token pengguna individu dan menolak permintaan dari pengguna dengan lebih banyak permintaan yang meledak. Dengan cara ini, permintaan dari pengguna lain tidak terpengaruh.

Jelas, ember token lebih fleksibel daripada ember bocor, memungkinkan situasi di mana lalu lintas yang meledak diteruskan ke layanan backend. Tentu saja, keduanya memiliki kelebihan dan kekurangan, dan Anda dapat memilih untuk menggunakannya sesuai dengan situasi Anda.

Modul Pembatasan Laju NGINX

Setelah membahas kedua algoritma ini, mari kita lihat bagaimana mengimplementasikan pembatasan laju di NGINX. Di NGINX, modul limit_req adalah modul pembatasan laju yang paling umum digunakan, dan berikut adalah konfigurasi sederhana:

limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;

server {
    location /search/ {
        limit_req zone=one burst=5;
    }
}

Kode ini mengambil alamat IP klien sebagai key, meminta ruang memori 10M yang disebut one, dan membatasi laju menjadi 1 permintaan per detik.

Di lokasi server, aturan pembatasan laju one juga dirujuk, dan brust diatur ke 5. Jika laju melebihi 1r/s, 5 permintaan dapat diantrekan secara bersamaan, memberikan area penyangga tertentu. Jika brust tidak diatur, permintaan yang melebihi laju akan langsung ditolak.

Modul NGINX ini didasarkan pada ember bocor, jadi pada dasarnya sama dengan resty.limit.req di OpenResty, yang telah kita jelaskan di atas.

Ringkasan

Masalah terbesar dari pembatasan laju di NGINX adalah mereka tidak dapat dimodifikasi secara dinamis. Bagaimanapun, Anda perlu me-restart file konfigurasi setelah memodifikasinya untuk membuatnya efektif, yang tidak dapat diterima dalam lingkungan yang berubah dengan cepat. Oleh karena itu, artikel berikutnya akan melihat implementasi pembatasan lalu lintas dan laju secara dinamis di OpenResty.

Terakhir, mari kita pertimbangkan sebuah pertanyaan. Dari perspektif WAF dan API gateway, apakah ada cara yang lebih baik untuk mengidentifikasi apa yang merupakan permintaan pengguna normal dan apa yang merupakan permintaan jahat? Karena, untuk lalu lintas yang meledak dari pengguna normal, kita dapat dengan cepat meningkatkan layanan backend untuk meningkatkan kapasitas layanan, sementara untuk permintaan jahat, lebih baik menolaknya langsung di lapisan akses.

Anda dipersilakan untuk meneruskan artikel ini kepada rekan dan teman Anda untuk belajar dan berkembang bersama.