Pertanyaan Secara efisien menggunakan API dengan tingkat terbatas (Echo Nest) dengan klien terdistribusi


Latar Belakang

Sarang Echo memiliki tingkat terbatas API. Aplikasi yang diberikan (diidentifikasi dalam permintaan menggunakan kunci API) dapat membuat hingga 120 panggilan REST satu menit. Respons layanan mencakup perkiraan jumlah panggilan yang dilakukan pada menit terakhir; penyalahgunaan API berulang (melebihi batas) dapat menyebabkan kunci API dicabut.

Ketika digunakan dari satu mesin (server web yang menyediakan layanan kepada klien), mudah untuk mengontrol akses - server memiliki pengetahuan penuh tentang riwayat permintaan dan dapat mengatur dirinya sendiri dengan benar.

Tetapi saya sedang mengerjakan suatu program di mana didistribusikan, klien independen membuat permintaan secara paralel.

Dalam kasus seperti itu, kurang jelas apa solusi yang optimal. Dan secara umum masalah tampaknya tidak dapat diputuskan - jika lebih dari 120 klien, semua tanpa riwayat sebelumnya, membuat permintaan awal pada saat yang sama, maka tarif akan terlampaui.

Tapi karena ini adalah proyek pribadi, dan penggunaan klien diharapkan menjadi sporadis (bursty), dan proyek saya tidak pernah berhasil, yang tidak diharapkan menjadi masalah besar. Masalah yang lebih mungkin adalah bahwa ada kalanya sejumlah kecil klien ingin membuat banyak permintaan secepat mungkin (misalnya, klien mungkin perlu, secara luar biasa, untuk membuat beberapa ribu permintaan ketika memulai untuk pertama kalinya - adalah mungkin dua klien akan mulai sekitar waktu yang sama, jadi mereka harus bekerja sama untuk membagi bandwidth yang tersedia).

Mengingat semua hal di atas, apa algoritma yang cocok untuk klien sehingga mereka menilai-batas dengan tepat?  Perhatikan bahwa kerjasama terbatas aku s mungkin karena API mengembalikan jumlah total permintaan pada menit terakhir semua klien.

Solusi Saat Ini

Solusi saya saat ini (ketika pertanyaan itu ditulis - pendekatan yang lebih baik diberikan sebagai jawaban) cukup sederhana. Setiap klien memiliki catatan waktu panggilan terakhir dibuat dan jumlah panggilan yang dilakukan di menit terakhir, seperti yang dilaporkan oleh API, pada panggilan itu.

Jika jumlah panggilan kurang dari 60 (setengah batas) klien tidak mencekik. Hal ini memungkinkan semburan cepat untuk sejumlah kecil permintaan.

Jika tidak (yaitu ketika ada permintaan yang lebih banyak), klien menghitung tingkat pembatasan yang perlu dikerjakannya (mis period = 60 / (120 - number of previous requests)) dan kemudian menunggu sampai jarak antara panggilan sebelumnya dan waktu saat ini melebihi periode tersebut (dalam detik; 60 detik dalam satu menit; 120 permintaan maks per menit). Ini secara efektif mengurangi laju sehingga, jika itu bertindak sendiri, itu tidak akan melampaui batas.

Tetapi hal di atas memiliki masalah. Jika Anda memikirkannya dengan hati-hati Anda akan melihat bahwa untuk sejumlah besar permintaan, satu klien berosilasi dan tidak mencapai hasil maksimum (ini sebagian karena "semburan awal" yang tiba-tiba "jatuh di luar jendela" dan sebagian lagi karena Algoritma tidak memanfaatkan sepenuhnya sejarahnya). Dan banyak klien akan bekerja sama sampai batas tertentu, tetapi saya ragu bahwa itu optimal.

Solusi Lebih Baik

Saya dapat membayangkan solusi yang lebih baik yang menggunakan sejarah lokal lengkap klien dan model klien lain dengan, katakanlah, Model Markov Tersembunyi. Jadi setiap klien akan menggunakan laporan API untuk memodelkan klien lain (tidak diketahui) dan menyesuaikan tarifnya sesuai.

Saya juga bisa membayangkan suatu algoritma untuk klien tunggal yang secara progresif bertransisi dari perilaku tak terbatas untuk semburan kecil menjadi optimal, perilaku terbatas untuk banyak permintaan tanpa memperkenalkan osilasi.

Apakah ada pendekatan semacam itu? Adakah yang bisa memberikan implementasi atau referensi? Adakah yang bisa memikirkan heuristik yang lebih baik?

Saya membayangkan ini adalah masalah yang diketahui di suatu tempat. Di bidang apa? Teori antrian?

Saya juga menebak (lihat komentar sebelumnya) bahwa tidak ada solusi optimal dan mungkin ada beberapa pengetahuan / tradisi / heuristik yang diterima yang bekerja dengan baik dalam praktek. Saya ingin tahu apa ... Saat ini saya berjuang untuk mengidentifikasi masalah serupa dalam protokol jaringan yang dikenal (saya membayangkan Perlman akan memiliki solusi yang indah jika demikian).

Saya juga tertarik (pada tingkat yang lebih rendah, untuk referensi di masa mendatang jika program menjadi populer) dalam solusi yang membutuhkan server pusat untuk membantu kolaborasi.

Penolakan

Pertanyaan ini tidak dimaksudkan untuk mengkritik Echo Nest sama sekali; layanan dan kondisi penggunaannya luar biasa. Tetapi semakin saya memikirkan cara terbaik untuk menggunakan ini, semakin kompleks / menariknya ...

Juga, setiap klien memiliki cache lokal yang digunakan untuk menghindari pengulangan panggilan.

Pembaruan

Mungkin kertas yang relevan.


11
2017-08-28 06:56


asal


Jawaban:


Di atas bekerja, tetapi sangat bising, dan kode itu berantakan. Saya sekarang menggunakan pendekatan yang lebih sederhana:

  • Menelpon
  • Dari tanggapan, catat batas dan hitungannya
  • Menghitung

    barrier = now() + 60 / max(1, (limit - count))**greedy
    
  • Di panggilan berikutnya, tunggu sampai barrier

Idenya cukup sederhana: bahwa Anda harus menunggu beberapa waktu sebanding dengan berapa sedikit permintaan yang tersisa di menit itu. Misalnya, jika hitungannya adalah 39 dan batasnya adalah 40, maka Anda menunggu satu menit penuh. Tetapi jika hitungannya nol maka Anda dapat segera mengajukan permintaan. Itu greedy parameter adalah trade-off - ketika lebih besar dari 1 panggilan "pertama" dibuat lebih cepat, tetapi Anda lebih mungkin mencapai batas dan akhirnya menunggu 60-an.

Kinerja ini mirip dengan pendekatan di atas, dan itu banyak lebih kuat. Ini sangat baik ketika klien "bursty" karena pendekatan di atas menjadi bingung dengan mencoba memperkirakan tingkat linear, sementara ini dengan senang hati akan membiarkan klien "mencuri" beberapa permintaan cepat ketika permintaan rendah.

Kode di sini.


3
2018-02-09 16:08



Setelah beberapa kali bereksperimen, tampaknya hal yang paling penting adalah mendapatkan perkiraan sebaik mungkin untuk batas atas tarif sambungan saat ini.

Setiap klien dapat melacak milik mereka sendiri (lokal) kecepatan koneksi menggunakan antrian cap waktu. Stempel waktu ditambahkan ke antrean pada setiap sambungan dan stempel waktu yang lebih lama dari satu menit dibuang. Tingkat rata-rata "jangka panjang" (lebih dari satu menit) kemudian ditemukan dari cap waktu pertama dan terakhir dan jumlah entri (minus satu). Tingkat "jangka pendek" (instan) dapat ditemukan dari waktu dua permintaan terakhir. Batas atas adalah maksimum dari dua nilai ini.

Setiap klien juga dapat memperkirakan luar tingkat koneksi (dari klien lain). Tingkat "jangka panjang" dapat ditemukan dari jumlah koneksi "digunakan" pada menit terakhir, seperti yang dilaporkan oleh server, dikoreksi oleh jumlah koneksi lokal (dari antrean yang disebutkan di atas). Tingkat "jangka pendek" dapat diperkirakan dari nomor "digunakan" sejak permintaan sebelumnya (minus satu, untuk koneksi lokal), diskalakan oleh perbedaan waktu. Sekali lagi, batas atas (maksimum dua nilai ini) digunakan.

Setiap klien menghitung dua tarif ini (lokal dan eksternal) dan kemudian menambahkannya untuk memperkirakan batas atas ke tingkat total koneksi ke server. Nilai ini dibandingkan dengan band rate target, yang saat ini ditetapkan antara 80% dan 90% dari maksimum (0.8 untuk 0.9 * 120 per menit).

Dari perbedaan antara perkiraan dan tingkat target, setiap klien memodifikasi tingkat koneksi mereka sendiri. Ini dilakukan dengan mengambil delta sebelumnya (waktu antara koneksi terakhir dan yang sebelumnya) dan menskalakannya 1.1 (jika nilai melebihi target) atau 0.9 (jika tarifnya lebih rendah dari target). Klien kemudian menolak untuk membuat koneksi baru sampai delta yang berskala tersebut telah berlalu (dengan tidur jika diminta koneksi baru).

Akhirnya, tidak ada yang di atas memaksa semua klien untuk sama-sama berbagi bandwidth. Jadi saya menambahkan 10% tambahan ke perkiraan tarif lokal. Ini memiliki efek lebih tinggi dari perkiraan tingkat untuk klien yang memiliki tingkat tinggi, yang membuat mereka lebih mungkin untuk mengurangi tingkat mereka. Dengan cara ini, klien yang "tamak" memiliki tekanan yang sedikit lebih kuat untuk mengurangi konsumsi yang, dalam jangka panjang, tampaknya cukup untuk menjaga distribusi sumber daya tetap seimbang.

Wawasan penting adalah:

  • Dengan mengambil maksimum "jangka panjang" dan "jangka pendek" memperkirakan sistem ini konservatif (dan lebih stabil) ketika klien tambahan memulai.

  • Tidak ada klien yang tahu jumlah total klien (kecuali nol atau satu), tetapi semua klien menjalankan kode yang sama sehingga dapat "mempercayai" satu sama lain.

  • Diberikan di atas, Anda tidak dapat membuat "tepat" perhitungan tentang tingkat apa yang digunakan, tetapi Anda dapat membuat koreksi "konstan" (dalam hal ini, +/- 10% faktor) tergantung pada tingkat global.

  • Penyesuaian ke frekuensi koneksi klien dibuat ke delta antara dua koneksi terakhir (menyesuaikan berdasarkan rata-rata selama seluruh menit terlalu lambat dan mengarah ke osilasi).

  • Konsumsi yang seimbang dapat dicapai dengan menghukum klien yang tamak sedikit.

Dalam (terbatas) percobaan ini bekerja dengan cukup baik (bahkan dalam kasus terburuk dari beberapa klien mulai sekaligus). Kelemahan utama adalah: (1) tidak memungkinkan untuk "ledakan" awal (yang akan meningkatkan keluaran jika server memiliki beberapa klien dan klien hanya memiliki beberapa permintaan); (2) sistem masih terombang-ambing lebih dari ~ satu menit (lihat di bawah); (3) menangani sejumlah besar klien (dalam kasus terburuk, misalnya jika semuanya dimulai sekaligus) membutuhkan keuntungan yang lebih besar (misalnya koreksi 20%, bukan 10%) yang cenderung membuat sistem kurang stabil.

plot

Jumlah "digunakan" yang dilaporkan oleh server (test), diplot terhadap waktu (Unix epoch). Ini untuk empat klien (berwarna), semua mencoba untuk mengkonsumsi data sebanyak mungkin.

Osilasi berasal dari sumber yang biasa - koreksi sinyal lag. Mereka diredam oleh (1) menggunakan batas atas tarif (memprediksi tingkat jangka panjang dari nilai sesaat) dan (2) menggunakan pita target. Inilah sebabnya jawaban yang diinformasikan oleh seseorang yang memahami teori kontrol akan dihargai ...

Tidak jelas bagi saya bahwa memperkirakan tarif lokal dan eksternal secara terpisah adalah penting (mereka dapat membantu jika tingkat jangka pendek untuk satu tinggi sedangkan tingkat jangka panjang untuk yang lain tinggi), tapi saya ragu menghapusnya akan memperbaiki keadaan.

Kesimpulannya: ini semua cukup banyak seperti yang saya harapkan, untuk pendekatan semacam ini. Ini jenis pekerjaan, tetapi karena ini adalah pendekatan umpan balik sederhana hanya stabil dalam rentang parameter terbatas. Saya tidak tahu alternatif apa yang mungkin.


1
2018-03-01 20:16



Karena Anda menggunakan API Echonest, mengapa Anda tidak memanfaatkan header batas laju yang dikembalikan dengan setiap panggilan API?

Secara umum Anda mendapatkan 120 permintaan per menit. Ada tiga header yang dapat membantu Anda mengatur sendiri konsumsi API Anda:

X-Ratelimit-Used
X-Ratelimit-Remaining
X-Ratelimit-Limit

** (Perhatikan 'ell' huruf kecil di 'Ratelimit' - dokumentasi membuat Anda berpikir itu harus dikapitalisasi, tetapi dalam prakteknya itu adalah huruf kecil.)

Ini menghitung akun untuk panggilan yang dilakukan oleh proses lain menggunakan kunci API Anda.

Cukup rapi, ya? Yah, aku takut ada gosok ...

Permintaan 120-per-menit itu benar-benar batas atas. Anda tidak dapat mengandalkannya. Dokumentasi menyatakan bahwa nilai dapat berfluktuasi sesuai dengan beban sistem. Saya telah melihat serendah 40ish dalam beberapa panggilan yang saya buat, dan dalam beberapa kasus terlihat di bawah nol (saya benar-benar berharap itu adalah bug di API yang paling tidak bergejolak!)

Salah satu pendekatan yang dapat Anda lakukan adalah memperlambat hal-hal setelah pemanfaatan (digunakan dibagi dengan batas) mencapai ambang tertentu. Namun perlu diingat, bahwa pada panggilan berikutnya batas Anda mungkin sudah disesuaikan unduhan cukup signifikan yang 'digunakan' lebih besar dari 'batas'.

Ini bekerja dengan baik sampai titik tertentu. Karena Echonest tidak menyesuaikan batas dalam mannar yang dapat diprediksi, sulit untuk menghindari 400 dalam praktiknya.

Berikut beberapa tautan yang menurut saya bermanfaat:

http://blog.echonest.com/post/15242456852/managing-your-api-rate-limit http://developer.echonest.com/docs/v4/#rate-limits


0