Queue — elementlar odatda First In, First Out (FIFO) tartibida qayta ishlanadigan ma’lumotlar tuzilmasi. Yangi element orqa tomonga qo‘shiladi, element old tomondan olinadi. Queue dastur ichidagi vaqtinchalik tartib, operatsion tizim tasklari, tarmoq paketlari va tarqatilgan message brokerlarda ishlatiladi. Ayrim queue turlari qat’iy FIFOdan farqli priority yoki delay qoidalariga ega.
Asosiy amallar
Enqueue elementni navbatga qo‘shadi, dequeue oldingi elementni olib tashlaydi va qaytaradi. Peek elementni o‘chirmasdan ko‘radi. Array asosidagi oddiy queue elementlarni har safar siljitmaslik uchun circular bufferdan foydalanishi mumkin. Head va tail indekslari massiv oxiriga yetganda boshiga qaytadi.
Linked list asosidagi queue dinamik elementlar uchun alohida node yaratadi. Enqueue va dequeue bosh hamda oxir pointerlari bilan O(1) vaqtda bajarilishi mumkin. Array cache locality bo‘yicha qulay, linked list esa har element uchun pointer va allocation xarajati keltiradi.
Concurrency
Bir nechta thread bir queue bilan ishlasa, holat race conditiondan himoyalanadi. Mutex asosidagi blocking queue bo‘sh paytda consumer threadni, to‘la paytda producer threadni condition variable orqali kutishi mumkin. Lock-free queue atomic compare-and-swap amallaridan foydalanadi, lekin memory ordering va ABA muammosi sababli implementatsiyasi murakkab.
Bounded queue maksimal sig‘imga ega. Producer consumerdan tez bo‘lsa navbat to‘ladi. Bunday holatda producer bloklanishi, element rad etilishi yoki eski element o‘chirilishi mumkin. Ushbu qaror backpressure siyosatining bir qismidir. Cheksiz deb ko‘rilgan queue esa yuk ortganda xotirani tugatishi mumkin.
Message queue
Tarqatilgan tizimdagi message queue producer bilan consumerni vaqt bo‘yicha ajratadi. Producer xabarni brokerga yozadi, consumer keyinroq oladi. Broker xabarni diskka saqlashi, bir nechta consumerga taqsimlashi va acknowledgement kutishi mumkin.
At-most-once yetkazishda xabar yo‘qolishi mumkin, lekin takrorlanmaydi. At-least-once xabarni qayta yuborishi mumkin, shuning uchun consumer idempotent ishlashi kerak. “Exactly-once” kafolati aniq tizim chegarasi va transaction mexanizmiga bog‘liq; tashqi side effectlar bilan uni ta’minlash murakkab.
Visibility timeout consumer olgan xabarni vaqtincha boshqalardan yashiradi. Consumer belgilangan vaqtda ACK bermasa xabar yana ko‘rinadi. Doim xato beradigan xabar cheksiz qayta urinish o‘rniga dead-letter queuega ko‘chirilishi mumkin.
Tartib va partition
Bir queue ichida FIFO bo‘lsa ham, bir nechta consumer parallel ishlaganda natijalar tugash tartibi o‘zgarishi mumkin. Partitionlangan broker odatda faqat bitta partition ichida tartibni kafolatlaydi. Bir obyektga tegishli xabarlar bir xil key bilan bitta partitionga yo‘naltiriladi, lekin bu yukning notekis taqsimlanishiga sabab bo‘lishi mumkin.
Priority va delay queue
Priority queue elementni kelish vaqtiga emas, priority qiymatiga qarab chiqaradi. Teng prioritydagi elementlar uchun FIFO saqlanishi implementatsiyaga bog‘liq. Binary heap priority queue uchun keng ishlatiladi va eng yuqori ustuvor elementni ko‘rish O(1), qo‘shish hamda olib tashlashni O(log n) vaqtda bajarishi mumkin.
Delay queue xabarni belgilangan vaqtdan oldin consumerga bermaydi. U rejalashtirilgan retry, reminder yoki timeout uchun ishlatiladi. Uzoq vazifani queuega qo‘yishda xabarning o‘zi katta faylni saqlamasdan, object storage identifikatorini tashishi mumkin. Queue payload limiti va retention muddati broker konfiguratsiyasiga bog‘liq.
Bog‘liq tushunchalar
FIFO, circular buffer, message broker, backpressure, acknowledgement, dead-letter queue, idempotentlik