Infinite Resources for Optimistic Concurrency Control

ABSTRACT

Optimistic concurrency control (OCC) is inefficient for high-contention workloads. When concurrent transactions conflict, an OCC system wastes CPU resources verifying transactions, only to abort them. This paper presents a new system, called Network Optimistic Concurrency Control (NOCC), which reduces load on storage servers by identifying transactions that will abort as early as possible, and aborting them before they reach the store. NOCC leverages recent advances in network data plane programmability to speculatively execute transaction verification logic directly in network devices. NOCC examines network traffic to observe and log transaction requests. If NOCC suspects that a transaction is likely to be aborted at the store, it aborts the transaction early by re-writing the packet header, and routing the packets back to the client. For high-contention workloads, NOCC improves transaction throughput, and reduces server load.

References

1. Agrawal, R., Carey, M.J., and Livny, M. Concurrency control performance modeling: Alternatives and implications. ACM Trans. Database Syst. 12, 4 (Nov. 1987), 609--654.
2. Agrawal, R., and Dewitt, D. J. Integrated concurrency control and recovery mechanisms: Design and performance evaluation. ACM Trans. Database Syst. 10, 4 (Dec. 1985), 529--564.
3. Anderson, T. E., Dahlin, M. D., Neefe, J. M., Patterson, D. A., Roselli, D. S., and Wang, R. Y. Serverless Network File Systems. ACM Transactions on Computer Systems (TOCS) 14, 1 (Feb. 1996), 41--79.
4. Bernstein, P. A., Hadzilacos, V., and Goodman, N. Concurrency Control and Recovery in Database Systems. Addison-Wesley Longman Publishing Co., Inc., 1987.
5. Bosshart, P., Daly, D., Gibb, G., Izzard, M., McKeown, N., Rexford, J., Schlesinger, C., Talayco, D., Vahdat, A., Varghese, G., and Walker, D. P4: Programming Protocol-Independent Packet Processors. SIGCOMM Computer Communication Review (CCR) 44 (July 2014), 87--95.
6. Bosshart, P., Gibb, G., Kim, H.-S., Varghese, G., McKeown, N., Izzard, M., Mujica, F., and Horowitz, M. Forwarding Metamorphosis: Fast Programmable Match-Action Processing in Hardware for SDN. In SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM) (Aug. 2013), pp. 99--110.
7. Brewer, E. A., Katz, R. H., Amir, E., Balakrishnan, H., Chawathe, Y., Fox, A., Gribble, S. D., Hodes, T., Nguyen, G., Padmanabhan, V. N., Stemm, M., Seshan, S., and Henderson, T. A Network Architecture for Heterogeneous Mobile Computing. Tech. rep., University of California at Berkeley, 1998.
8. Carey, M. J., and Stonebraker, M. The performance of concurrency control algorithms for database management systems. In Proceedings of the 10th International Conference on Very Large Data Bases (San Francisco, CA, USA, 1984), VLDB '84, Morgan Kaufmann Publishers Inc., pp. 107--118.
9. Council, T. TPC-C Benchmark, revision 5.11, 2010.
10. Cowling, J., and Liskov, B. Granola: Low-overhead distributed transaction coordination. In USENIX Annual Technical Conference (ATC) (2012).
11. Dang, H. T., Canini, M., Pedone, F., and Soulé, R. Paxos Made Switch-y. SIGCOMM Computer Communication Review (CCR) 44 (Apr. 2016), 87--95.
12. Dang, H. T., Sciascia, D., Canini, M., Pedone, F., and Soulé, R. NetPaxos: Consensus at Network Speed. In ACM SIGCOMM Symposium on SDN Research (SOSR) (June 2015), pp. 59--73.
13. Franaszek, P., and Robinson, J. T. Limitations of concurrency in transaction processing. ACM Trans. Database Syst. 10, 1 (Mar. 1985), 1--28.
14. Freedman, M. J., Freudenthal, E., and Mazières, D. Democratizing content publication with coral. In USENIX Symposium on Networked Systems Design and Implementation (NSDI) (Mar. 2004), pp. 18--18.
15. Grimm, R., Lichtman, G., Michalakis, N., Elliston, A., Kravetz, A., Miller, J., and Raza, S. Na Kika: Secure Service Execution and Composition in an Open Edge-Side Computing Network. In USENIX Symposium on Networked Systems Design and Implementation (NSDI) (San Jose, California, May 2006), pp. 169--182.
16. István, Z., Sidler, D., Alonso, G., and Vukolić, M. Consensus in a Box: Inexpensive Coordination in Hardware. In USENIX Symposium on Networked Systems Design and Implementation (NSDI) (Mar. 2016), pp. 103--115.
17. Jin, X., Li, X., Zhang, H., Foster, N., Lee, J., Soulé, R., Kim, C., and Stoica, I. Netchain: Scale-free sub-rtt coordination. In USENIX Symposium on Networked Systems Design and Implementation (NSDI) (Apr. 2018).
18. Jin, X., Li, X., Zhang, H., Soulé, R., Lee, J., Foster, N., Kim, C., and Stoica, I. Netcache: Balancing key-value stores with fast in-network caching. In ACM Symposium on Operating Systems Principles (SOSP) (Oct. 2017), ACM, pp. 121--136.
19. Joseph, A. D., deLespinasse, A. F., Tauber, J. A., Gifford, D. K., and Kaashoek, M. F. Rover: A Toolkit for Mobile Information Access. In ACM Symposium on Operating Systems Principles (SOSP) (Dec. 1995), pp. 156--171.
20. Knutsson, B., Lu, H., Mogul, J., and Hopkins, B. Architecture and Performance of Server-Directed Transcoding. ACM Transactions on Internet Technology (TOIT) 3, 4 (Nov. 2003), 392--424.
21. Kung, H. T., and Robinson, J. T. On optimistic methods for concurrency control. ACM Transactions on Database Systems (TODS) 6, 2 (June 1981), 213--226.
22. Lamport, L. Fast Paxos. Distributed Computing 19 (Oct. 2006), 79--103.
23. Li, J., Michael, E., and Ports, D. R. K. Eris: Coordination-free consistent transactions using in-network concurrency control. In ACM Symposium on Operating Systems Principles (SOSP) (Oct. 2017), ACM, pp. 104--120.
24. Li, X., Sethi, R., Kaminsky, M., Andersen, D. G., and Freedman, M. J. Be fast, cheap and in control with switchkv. In USENIX Symposium on Networked Systems Design and Implementation (NSDI) (Mar. 2016), pp. 31--44.
25. Nottingham, M., and Liu, X. Edge Architecture Specification, 2001. http://www.esi.org/architecture_spec_1--0.html.
26. Pavlo, A. Python TPC-C. https://github.com/apavlo/py-tpcc, 2017.
27. Ports, D. R. K., Li, J., Liu, V., Sharma, N. K., and Krishnamurthy, A. Designing Distributed Systems Using Approximate Synchrony in Data Center Networks. In USENIX Symposium on Networked Systems Design and Implementation (NSDI) (Mar. 2015), pp. 43--57.
28. Shapiro, M. Structure and Encapsulation in Distributed Systems: the Proxy Principle. In 6th IEEE International Conference on Distributed Computing Systems (ICDCS) (May 1986), pp. 198--204.
29. Stonebraker, M., Madden, S., Abadi, D. J., Harizopoulos, S., Hachem, N., and Helland, P. The end of an architectural era: (it's time for a complete rewrite). In 33th International Conference on Very Large Data Bases (2007), pp. 1150--1160.
30. Tay, Y. C., Goodman, N., and Suri, R. Locking performance in centralized databases. ACM Trans. Database Syst. 10, 4 (Dec. 1985), 415--462.
31. Barefoot Tofino. https://www.barefootnetworks.com/products/brief-tofino/.
32. Wang, L., Pai, V., and Peterson, L. The Effectiveness of Request Redirection on CDN Robustness. In USENIX Symposium on Operating Systems Design and Implementation (OSDI) (Dec. 2002), pp. 345--360.
33. XPliant Ethernet Switch Product Family. www.cavium.com/XPliant-Ethernet-Switch-Product-Family.html.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Distributed database transactions

• Networks

  • Network services

    • In-network processing