Semantic Idempotency for Exactly-Once Business Effects in At-Least-Once Distributed Messaging Systems
Article Sidebar
Main Article Content
Abstract
At-least-once delivery is the dominant message-delivery paradigm in distributed messaging infrastructures, because stronger transport-level guarantees require blocking coordination that compromises availability and throughput. This paper gathers, from the foundational and modern literature, the concepts of message delivery semantics, of idempotency theory and of distributed coordination patterns, articulating a conceptual framework, called semantic idempotency, where exactly-once business effects are achieved on top of an at-least-once transport, by relying on deduplication performed on the receiver side instead of on the transmitter side. It starts by tracing the history of the various studies that led to the development of logical clocks and consensus impossibility theorems, quorum-based replication, log-structured messaging, snapshot algorithms, saga-based compensation, and conflict-free replicated data types, and how each addresses a partial solution to the duplicate-delivery problem. The analysis reveals that redelivery probability increases non-linearly with the number of retries at realistic acknowledgment-loss rates, the idempotency-key registry adds approximately one millisecond of median latency compared with mid-single-digit milliseconds for two-phase commit, and windowed key-store retention can maintain over 95 percent accuracy of duplicate-catching while keeping state growth under control. Idempotent receivers preserve the availability and horizontal scalability of at-least-once transport, at the cost of weaker native consistency guarantees than two-phase commit provides. The paper also presents the formalization of semantic idempotency using an operator-oriented notation that separates redelivery at the transport level from application of effects at the business level. These results suggest that architects should regard idempotency as a first-class contract between product and consumer, while the future of messaging systems might be a platform that includes a deduplication registry as a first-class citizen rather than an ad hoc application programming feature.
Article Details
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
References
[1] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of Distributed Consensus with One Faulty Process,” J. ACM, vol. 32, no. 2, pp. 374–382, 1985, doi: 10.1145/3149.214121.
[2] P. Helland, “Idempotence Is Not a Medical Condition: An Essential Property for Reliable Systems,” Queue, vol. 10, no. 4, pp. 30–46, 2012, doi: 10.1145/2181796.2187821.
[3] Y. Huang and H. Garcia-Molina, “Exactly-Once Semantics in a Replicated Messaging System,” in Proceedings of the 17th International Conference on Data Engineering, 2001, pp. 3–12. doi: 10.1109/ICDE.2001.914808.
[4] L. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Commun. ACM, vol. 21, no. 7, pp. 558–565, 1978, doi: 10.1145/359545.359563.
[5] K. M. Chandy and L. Lamport, “Distributed Snapshots: Determining Global States of Distributed Systems,” ACM Trans. Comput. Syst., vol. 3, no. 1, pp. 63–75, 1985, doi: 10.1145/214451.214456.
[6] P. Carbone, G. Fóra, S. Ewen, S. Haridi, and K. Tzoumas, “Lightweight Asynchronous Snapshots for Distributed Dataflows,” 2015. doi: 10.48550/arXiv.1506.08603.
[7] S. Chernyak et al., “MillWheel,” Proc. VLDB Endow., vol. 6, no. 11, pp. 1033–1044, 2013, doi: 10.14778/2536222.2536229.
[8] J. Kreps, N. Narkhede, and J. Rao, “Kafka: A distributed messaging system for log processing,” in Proceedings of the NetDB, 2011, vol. 11, no. 2011, pp. 1–7.
[9] G. DeCandia et al., “Dynamo: Amazon’s Highly Available Key-Value Store,” in Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP ’07), 2007, pp. 205–220. doi: 10.1145/1294261.1294281.
[10] W. Vogels, “Eventually Consistent,” Commun. ACM, vol. 52, no. 1, pp. 40–44, 2009, doi: 10.1145/1435417.1435432.
[11] S. Burckhardt, “Principles of Eventual Consistency,” Found. Trends Program. Lang., vol. 1, no. 1–2, pp. 1–150, 2014, doi: 10.1561/2500000011.
[12] G. Ramalingam and K. Vaswani, “Fault Tolerance via Idempotence,” in Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’13), 2013, pp. 249–262. doi: 10.1145/2429069.2429100.
[13] M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski, “Conflict-Free Replicated Data Types,” in Stabilization, Safety, and Security of Distributed Systems, 2011, pp. 386–400. doi: 10.1007/978-3-642-24550-3_29.
[14] Y. Mao, Z. Liu, and H.-A. Jacobsen, “Reversible conflict-free replicated data types,” in Proceedings of the 23rd ACM/IFIP International Middleware Conference, 2022, pp. 295–307. doi: 10.1145/3528535.3565252.
[15] J. N. Gray, “Notes on data base operating systems,” in Operating systems: An advanced course, Springer, 2005, pp. 393–481. doi: 10.1007/3-540-08755-9_9.
[16] D. Skeen, “Nonblocking Commit Protocols,” in Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, 1981, pp. 133–142. doi: 10.1145/582318.582339.
[17] H. Garcia-Molina and K. Salem, “Sagas,” in Proceedings of the 1987 ACM SIGMOD International Conference on Management of Data, 1987, pp. 249–259. doi: 10.1145/38713.38742.
[18] E. Daraghmi, C.-P. Zhang, and S.-M. Yuan, “Enhancing Saga Pattern for Distributed Transactions within a Microservices Architecture,” Appl. Sci., vol. 12, no. 12, p. 6242, 2022, doi: 10.3390/app12126242.
[19] T. Górski, “UML Profile for Messaging Patterns in Service-Oriented Architecture, Microservices, and Internet of Things,” Appl. Sci., vol. 12, no. 24, p. 12790, 2022, doi: 10.3390/app122412790.
[20] D. Ongaro and J. Ousterhout, “In Search of an Understandable Consensus Algorithm,” in 2014 USENIX Annual Technical Conference (USENIX ATC 14), 2014, pp. 305–319. [Online]. Available: https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro
[21] P. Hunt, M. Konar, F. P. Junqueira, and B. Reed, “ZooKeeper: Wait-Free Coordination for Internet-Scale Systems,” 2010. [Online]. Available: https://www.usenix.org/conference/usenix-atc-10/zookeeper-wait-free-coordination-internet-scale-systems
[22] S. Gilbert and N. Lynch, “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services,” ACM SIGACT News, vol. 33, no. 2, pp. 51–59, 2002, doi: 10.1145/564585.564601.
[23] L. Lamport, “The Part-Time Parliament,” ACM Trans. Comput. Syst., vol. 16, no. 2, pp. 133–169, 1998, doi: 10.1145/279227.279229.
[24] T. Akidau et al., “The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing,” Proc. VLDB Endow., vol. 8, no. 12, pp. 1792–1803, 2015, doi: 10.14778/2824032.2824076.