Queue

A queue is a kind of abstract data type, a collection, in which the entities are kept in order and its main operations are enqueuing additional entities to the rear terminal position, dequeuing entities from the front. Hence a queue is a sequential, first in first out (FIFO) data structure.

A bounded queue is a queue with a fixed (limited) size.

An efficient implementation of a queue should perform the operations - enqueuing and dequeuing - in O(1) time. There are several implementations;

  • A doubly linked list has O(1) insertion and deletion at both ends.
  • A sinly linked list only has efficient insertion and deletion at one end, however keeping a pointer to the last note in addition to the first one allows one to implement a more efficient queue.
  • A deque implemented using a modified dynamic array.

Message Queues

Message queues provide an asynchronous communication protocol where the sender and receiver do not need to interact with the queue at the same time. Messages inserted into the queue are stored until the recipient retrieves them.

You could consider a queue as a line of tasks waiting to be handled in a sequential order. A message queue is a list of messages sent between applications. A message is the transported data between the sender and receiver applications. Essentially it is a byte array with some headers. A message could tell a system to start processing a task or contain a response from a finished task or just be a plaintext.

The consumer application connects to the queue and gets the messages to be placed, until then the messages are stored within the queue.

Consider an email.

When an email is sent the sender keeps processing other things without an instant response from the receiver. This decouples producers and consumers of a message, allowing them to interact with the queue separately from each other.

Imagine you have a service that receives many requests every second, where no request is affordable to lose and all requests need to be processed by a process that consumes plenty of time. If you want your service to always be highly available and ready to receive more requests instead of being locked processing the previous requests, it is very ideal to implement a queue between the services that take and process requests.

Scaling such a system can be done now by adding more workers and receivers to work on queues faster.

AMQP - Advanced Message Queuing Protocol

An open standard application layer protocol for message-oriented middleware, featuring message orientation, queuing, routing (pub-sub, point-to-point), reliability and security. AMQP mandates the behavior of the messaging provider and client to the extent that implementations from different vendors are interoperable, in the same way as SMTP, HTTP, FTP, etc.

The basic unit of data in AMQP is a frame. There are nine AMQP frame bodies defined that are used to initiate, control and tear down the transfer of messages between two peers. These are:

  • open
  • begin
  • attach
  • transfer
  • flow
  • disposition
  • detach
  • end
  • close

The link protocol is at the heart of AMQP.

An attach frame body is sent to initiate a new link; a detach to tear down a link. Links may be established in order to receive or send messages.

Messages are sent over an established link using the transfer frame. Messages on a link flow in only one direction.

Transfers are subject to a credit based flow control scheme, managed using flow frames. This allows a process to protect itself from being overwhelmed by too large a volume of messages or more simply to allow a subscribing link to pull messages as and when desired.

AMQP 0-9-1 Model

According to this model messages are published to exchanges, which are often compared to mailboxes. Exchanges then distribute message copies to queues using bindings. Then AMQP brokers either deliver messages to consumers subscribed to the queues or consumers fetch/pull messages from queues on demand.

AMQP 0-9-1 Model

Networks are unreliable and applications may fail to process messages therefore the AMQP model has a notion of message acknowledgements: when a message is delivered to a consumer the consumer notifies the broker, either automatically or as soon as the application developer chooses to do so. When message acknowledgements are in use, a broker will only completely remove a message from a queue when it receives a notification for that message (or group of messages).

STOMP - Streaming Text Oriented Message Protocol

STOMP/TTMP, is a simple text-based protocol, designed for working with message-oriented middleware. It provides an interoperable wire format that allows STOMP clients to talk with any message broker supporting the protocol. It is thus language-agnostic, meaning a broker developed for one programming language or platform can receive communications from client software developed in another language.

Being very similar to HTTP, it works over TCP using the following commands

  • CONNECT
  • SEND
  • SUBSCRIBE
  • UNSUBSCRIBE
  • BEGIN
  • COMMIT
  • ABORT
  • ACK
  • NACK
  • DISCONNECT

Communication between client and server is through a frame consisting of a number of lines. The first line contains the command, followed by headers in the form : (one per line), followed by a blank line and then the body content, ending in a `null character`. Communication between server and client is through a `MESSAGE`, `RECEIPT` or `ERROR frame` with a similar format of headers and body content.

POSIX message queues

POSIX message queues allow processes to exchange data in the form of messages, providing similar functionality to System V message queues (msgget, msgsnd, msgrcv).

  • Message queues are created with mq_open which returns a message queue descriptor (mqd_t) which is used to refer to the opened message queue in later calls.
  • Two processes can operate on the same queue by passing the same name to mq_open.
  • Messages are transferred to and from a queue using mq_send and mq_receive.
  • When a process has finished using the queue, it closes it using mq_close, and when the queue is no longer required, it can be deleted using mq_unlink.
  • Queue attributes can be retrieved and (in some cases) modified using mq_getattr and mq_setattr.
  • A process can request asynchronous notification of the arrival of a message on a previously empty queue using mq_notify.
  • On Linux, a message queue descriptor is actually a file descriptor, and can be monitored using select, poll, or epoll.

Next: Message Queues: RabbitMQ

Resources