METHOD AND SYSTEM FOR DYNAMIC QUEUE SPLITTING FOR MAXIMIZING THROUGHPUT OF QUEUE BASED OPERATIONS WHILE MAINTAINING PER-DESTINATION ORDER OF OPERATIONS

摘要

A system for providing dynamic queue splitting to maximize throughput of queue entry processing while maintaining the order of queued operations on a per-destination basis. Multiple queues are dynamically created by splitting heavily loaded queues in two. As queues become dormant, they are re-combined. Queue splitting is initiated in response to a trigger condition, such as a queue exceeding a threshold length. When multiple queues are used, the queue in which to place a given operation is determined based on the destination for that operation. Each queue in the queue tree created by the disclosed system can store entries containing operations for multiple destinations, but the operations for a given destination are all always stored within the same queue. The queue into which an operation is to be stored may be determined as a function of the name of the operation destination. Just as a single queue may be split into two queues, if one of the two queues starts backing up, the disclosed system may further split that queue into two. Thus each queue in the queue tree may be split into two new queues if its performance falls below a threshold level. Successively more bits from a function applied to destination names for operations may be used to determine specific queues into which operations should be placed as the depth of the queue tree increases.