# US 11,442,777 B2 · Highly available distributed queue using replicated messages > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,442,777 B2 - Document ID: US11442777B2 - Status: Granted - Kind: B2 - Application number: 16/817,225 - Filed: 2020-03-12 - Published: 2020-07-02 - Granted: 2022-09-13 - Earliest claimed: 2015-06-26 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Andrew Ross Evenson; Ayan Kumar - Web page: https://patentgrep.com/patent/US11442777B2 ## CPC - G06F 9/50: Allocation of resources, e.g. of the central processing unit [CPU] - G06F 9/46: Multiprogramming arrangements - G06F 9/466: {Transaction processing} - G06F 9/48: Program initiating; Program switching, e.g. by interrupt - G06F 9/4843: {by program, e.g. task dispatcher, supervisor, operating system} - G06F 9/4862: {the task being a mobile agent, i.e. specifically designed to migrate} - G06F 9/4868: {with creation or replication} - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals} - G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)} - G06F 9/5083: {Techniques for rebalancing the load in a distributed system} - G06F 9/546: {Message passing systems or structures, e.g. queues} - G06F 16/00: Information retrieval; Database structures therefor; File system structures therefor - G06F 16/182: Distributed file systems - G06F 16/184: {implemented as replicated file system} - G06F 16/1844: {Management specifically adapted to replicated file systems} - G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor - G06F 16/273: {Asynchronous replication or reconciliation} - G06F 16/275: {Synchronous replication} - G06Q 10/10: Office automation; Time management - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR ## Abstract Methods and systems for implementing a highly available distributed queue using replicated messages are disclosed. An enqueue request is received from a client at a particular queue host of a plurality of queue hosts. The enqueue request comprises a message and a replica count greater than one. One or more copies of a replication request are sent from the particular queue host to one or more additional queue hosts. The replication request comprises the message. The quantity of copies of the replication request is determined based at least in part on the replica count. An initial replica of the message is enqueued at the particular queue host. One or more additional replicas of the message are enqueued at the one or more additional queue hosts. A quantity of the one or more additional replicas is determined based at least in part on the replica count. ## Claims ### Claim 1 A system, comprising: one or more processors and one or more memories that store computer-executable instructions that, when executed, implement a distributed queue system and cause the distributed queue system to: receive, via a client-accessible interface of the distributed queue system, a client enqueue request to enqueue a message; send, from a first queue host of the distributed queue system to one or more additional queue hosts of the distributed queue system, a replication request for the message; enqueue, by the first queue host, a first replica of the message in a local queue of the first queue host, wherein the first queue host is configured to return messages in the local queue in response to client dequeue requests received via the client-accessible interface; receive, by the first queue host from the one or more additional queue hosts, one or more acknowledgements of enqueuing one or more additional replicas of the message at the one or more additional queue hosts, wherein the one or more acknowledgements comprise one or more host identifiers of the one or more additional queue hosts; and store, by the first queue host, the one or more host identifiers in a host availability data structure associated with the first queue host. ### Claim 2 (depends on 1) The system as recited in claim 1, wherein the one or more additional queue hosts are selected by one or more load balancers for receipt of the replication request. ### Claim 3 (depends on 1) The system as recited in claim 1, wherein the client enqueue request comprises a replica count, and the one or more additional queue hosts are selected based at least in part on the replica count. ### Claim 4 (depends on 3) The system as recited in claim 3, wherein the one or more memories store additional computer-executable instructions that, when executed, cause the distributed queue system to: send, by the first queue host to the load balancer, an acknowledgement of the client enqueue request that comprises the one or more host identifiers. ### Claim 5 (depends on 1) The system as recited in claim 1, wherein the one or more memories store additional computer-executable instructions that, when executed, cause the distributed queue system to: select, by the first queue host, at least one of the additional queue hosts using the host availability data structure; and send, from the first queue host to the at least one of the additional queue hosts, an additional replication request for an additional message. ### Claim 6 (depends on 5) The system as recited in claim 5, wherein the one or more additional queue hosts are selected by one or more load balancers for receipt of the replication request, and wherein the one or more load balancers are bypassed in selecting the at least one of the additional queue hosts for receipt of the additional replication request. ### Claim 7 A computer-implemented method, comprising: receiving, via a client-accessible interface of a distributed queue system, a client enqueue request to enqueue a message; sending, from a first queue host of the distributed queue system to one or more additional queue hosts of the distributed queue system, a replication request for the message; enqueuing, by the first queue host, a first replica of the message in a local queue of the first queue host, wherein the first queue host is configured to return messages in the local queue in response to client dequeue requests received via the client-accessible interface; receiving, by the first queue host from the one or more additional queue hosts, one or more acknowledgements of enqueuing one or more additional replicas of the message at the one or more additional queue hosts, wherein the one or more acknowledgements comprise one or more host identifiers of the one or more additional queue hosts; and storing, by the first queue host, the one or more host identifiers in a host availability data structure associated with the first queue host. ### Claim 8 (depends on 7) The method as recited in claim 7, wherein the one or more additional queue hosts are selected by one or more load balancers for receipt of the replication request. ### Claim 9 (depends on 7) The method as recited in claim 7 wherein the client enqueue request comprises a replica count, and the one or more additional queue hosts are selected based at least in part on the replica count. ### Claim 10 (depends on 9) The method as recited in claim 9, further comprising: sending, by the first queue host to the load balancer, an acknowledgement of the client enqueue request that comprises the one or more host identifiers. ### Claim 11 (depends on 7) The method as recited in claim 7, further comprising: selecting, by the first queue host, at least one of the additional queue hosts using the host availability data structure; and sending, from the first queue host to the at least one of the additional queue hosts, an additional replication request for an additional message. ### Claim 12 (depends on 11) The method as recited in claim 11, wherein the one or more additional queue hosts are selected by one or more load balancers for receipt of the replication request, and wherein the one or more load balancers are bypassed in selecting the at least one of the additional queue hosts for receipt of the additional replication request. ### Claim 13 (depends on 7) The method as recited in claim 7, wherein the host availability data structure comprises data indicative of an availability of the one or more additional queue hosts for performing enqueuing tasks. ### Claim 14 One or more non-transitory computer-readable storage media storing program instructions that, when executed on or across one or more processors, perform: receiving, via a client-accessible interface of a distributed queue system, a client enqueue request to enqueue a message; sending, from a first queue host of the distributed queue system to one or more additional queue hosts of the distributed queue system, a replication request for the message; enqueuing, by the first queue host, a first replica of the message in a local queue of the first queue host, wherein the first queue host is configured to return messages in the local queue in response to client dequeue requests received via the client-accessible interface; receiving, by the first queue host from the one or more additional queue hosts, one or more acknowledgements of enqueuing one or more additional replicas of the message at the one or more additional queue hosts, wherein the one or more acknowledgements comprise one or more host identifiers of the one or more additional queue hosts; and storing, by the first queue host, the one or more host identifiers in a host availability data structure associated with the first queue host. ### Claim 15 (depends on 14) The one or more non-transitory computer-readable storage media as recited in claim 14, wherein the one or more additional queue hosts are selected by one or more load balancers for receipt of the replication request. ### Claim 16 (depends on 14) The one or more non-transitory computer-readable storage media as recited in claim 14, further comprising additional program instructions that, when executed on or across the one or more processors, perform: selecting the one or more additional queue hosts based at least in part on a replica count indicated by the client enqueue request. ### Claim 17 (depends on 16) The one or more non-transitory computer-readable storage media as recited in claim 16, further comprising additional program instructions that, when executed on or across the one or more processors, perform: sending, by the first queue host to the load balancer, an acknowledgement of the client enqueue request that comprises the one or more host identifiers. ### Claim 18 (depends on 14) The one or more non-transitory computer-readable storage media as recited in claim 14, further comprising additional program instructions that, when executed on or across the one or more processors, perform: selecting, by the first queue host, at least one of the additional queue hosts using the host availability data structure; and sending, from the first queue host to the at least one of the additional queue hosts, an additional replication request for an additional message. ### Claim 19 (depends on 18) The one or more non-transitory computer-readable storage media as recited in claim 18, wherein the one or more additional queue hosts are selected by one or more load balancers for receipt of the replication request, and wherein the one or more load balancers are bypassed in selecting the at least one of the additional queue hosts for receipt of the additional replication request. ### Claim 20 (depends on 14) The one or more non-transitory computer-readable storage media as recited in claim 14, wherein the host availability data structure comprises data indicative of an availability of the one or more additional queue hosts for performing enqueuing tasks.