• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

BernsteinReliableQueues

Page history last edited by PBworks 16 years, 10 months ago

Paper

  • transactions have been studied, but what about the requests that come in?
  • exactly-once processing
  • queue manager: type of DB that stores elements, possibly with content -baed retrieval
  • allows for indirect communication between procs
  • a request is a data structure (record) that describes some work to be done by the DB
  • many requests are not idempotent
  • server queue, client queue. transactions: {client: enqueue request into server q}, {server: dequeue, process request, enqueue reply into client q}, {client: dequeue, process response}
  • instead of making the client's actions transactions, instead just provide information to the client so it can see what it did before a crash
  • upon connecting, client recieves RID of last quest it sent, and RID of last request processed by the server
  • Q: when in the Req-Sent state, it can't send more requests?
  • operations:
    • s-rid, r-rid, chpt = Connect(client): upon connect, get rid info, and optionally a checkpoint.  We don't need this info if we successfully Disconnected last time
    • Disconnect(client-id)
    • Send(r, s-rid): send a request r with id s-rid. Q: who generates s-rid?
    • p = Recieve(chkpt) recieve next reply, optionally piggy back chkpt info
    • p = Rerecieve: recieve the reply that we last asked for
  • guarantees:
    • request-reply matching
    • exactly-once request processing
    • at-least-once reply processing
  • queue: held in stable storage with elements
  • queue repository: set of disjoint queues
  • operations:
    • Enqueue: creates and inserts element. can be inside a T (only visibile after ACK) or not
    • Dqueue: destroy and return an element. Can set attributes such that n unsucessful dequeues will move the element to an error queue
    • Read: like peek
    • Register: a client can registere with a queue. kept until explecit deregister
    • Deregister: destroys all info about registrant
    • queue keeps track of registrant operations
  • each client uses a clerk library. library can handle remote calls if QM is elsewhere on the network.
    • Connect(client-id): Register client with request and reply queues. registering with these queues may return r-rid, s-rid, and chekpoint info
    • Disconnect: Deregister with request and reply queueus
    • Send(r, rid): Enqueue request, tag with rid
    • Recieve(chkpt) Dequeue the next reply in the reply queue
    • Rerecieve: Read the last recieved element
  • multi-transaction requeuest work like saga
  • could extend queues by
    • allowing for multiple transactions
    • allowing for concurrent transactions (isn't serializable, unless application sets locks itslef)
    • Kill_Element (remove a quest from the queue)
    • interactive requests, the server asks the client for more input
      • we can do this by treating the "conversation" like multiple requeust, then treating the final answer as the reply to the overall conversation
      • however, how do we abort? (use sagas)
  • implementation issues
    • don't implement as FIFO: it's too hard to guarantee that
    • scheduleing can be hard
    • queues may want/need to be distributed
  • tagging is a key new idea, very useful for recovery
  • interesting to think of parallels with DDBMS, such as presumed abort when the clients ask for replies
  •  

 

Lecture

  • motivation: robust, distributed, fault-tolerant, easy to program, scalable
  • started out trying to do transactional RPC
    • client RPC set TID that is added to the RPC
    • server logs begin/end
    • participants tracked
    • commit calls: client stupd says commit(TID)
    • TM uses 2PC
  • issues:
    • it's a synchonous call (tightly couples requestor and requestee)
    • but for longer running transactions, or disconnects, etc, we want asynchronous
    • queues seperate systems in time and space
  • client does enqueue op
  • reliable queue manager: keeps track of what's been queued in persistant store
  • server can come along and dequeue
  • disadvantages: extra overhead
  • each client is communicating with servers through queues instead of directly
  • elements in queue are stored transactinoally
  • msg "send" and "recieve" uses 2PC with the queue
  • examples:
    • MQ Series
    • MQS M$
    • tuxedo/q (BEA)
    • JMS
  • what we get:
    • messages are persistant
    • Qs can be shared between different types of clients (Q: how do you know the response is yours?)
    • replication (replicas can share a q) (same type of client/server)
  • for atomicity need to retry count/limit (in case we have bad data and it repeatedly fails)
  • similar to tables in DBMS
    • transactional
    • ACID like semantics (esp. concurrency)
    • may also want indexing and search
    • need to use special locking/concurrency control for queues (want to be able to dequeue something while enguquing an unrelated thing)
  • implementing
    • log-like file system
    • main-mem + log (speed needs)
    • DB like (rows, etc)
  • RSQs -> msg brokers
    • basis for enterprise aplication integration
    • use Qs to integrate systems
    • could also be doing routing, transformations
    •  

Comments (1)

Jim Blomo said

at 11:21 am on Oct 3, 2007

solid

You don't have permission to comment on this page.