Sắp xếp lại thực hiện giao dịch để tăng cường các ứng dụng giao dịch tần suất cao

Data Science and Engineering - 2017
Ningnan Zhou1,2, Xuan Zhou3, Xiao Zhang1,2, Xiaoyong Du1,2, Shan Wang2,1
1MOE Key Laboratory of DEKE, Renmin University of China, Beijing, China
2School of Information, Renmin University of China, Beijing, China
3School of Data Science and Engineering, East China Normal University, Shanghai, China

Tóm tắt

Giao dịch tần suất cao (HFT) từ lâu đã được hoan nghênh vì không chỉ mang lại lợi ích cá nhân mà còn cho toàn bộ phúc lợi xã hội. Trong khi sự phát triển gần đây của việc lựa chọn danh mục trong thị trường HFT có khả năng mang lại lợi nhuận cao hơn, nó cũng tạo ra khối lượng công việc OLTP gây tranh cãi lớn. Đặc trưng bởi việc khai thác khả năng song song phong phú, ống dẫn giao dịch, cơ chế kiểm soát đồng thời (CC) tiên tiến nhất không thể xử lý đồng thời hiệu quả khi đối mặt với khối lượng công việc HFT. Các biến thể của nó cho phép thực thi song song hơn bằng cách tận dụng thông tin tranh chấp tinh vi cũng có hiệu quả hạn chế. Để giải quyết vấn đề này, lần đầu tiên chúng tôi quan sát và xác định nguồn gốc của khả năng đồng thời bị hạn chế là do thứ tự xử lý của các câu lệnh giao dịch gây hại. Để giải quyết thứ tự gây hại, chúng tôi đề xuất PARE, một phương pháp thực hiện lại có nhận thức ống dẫn, nhằm cải thiện hiệu suất ứng dụng bằng cách sắp xếp lại các câu lệnh theo mức độ tranh chấp của chúng. Cụ thể, hai cơ chế được thiết kế để đảm bảo tính chính xác của việc sắp xếp lại các câu lệnh và xác định mức độ tranh chấp của các câu lệnh, tương ứng. Chúng tôi cũng nghiên cứu bài toán sắp xếp lại ngoại tuyến. Chúng tôi chứng minh rằng vấn đề này thuộc NP-khó và trình bày một phương pháp sắp xếp lại ngoại tuyến để xấp xỉ chiến lược sắp xếp lại tối ưu. Kết quả thí nghiệm cho thấy PARE có thể cải thiện thông lượng giao dịch và giảm độ trễ giao dịch đối với các ứng dụng HFT lên đến một bậc so với cơ chế CC tiên tiến nhất.

Từ khóa

#Giao dịch tần suất cao #Sắp xếp lại giao dịch #Kiểm soát đồng thời #Hiệu suất ứng dụng #Khối lượng công việc OLTP

Tài liệu tham khảo

http://www.investopedia.com/articles/investing/091615/world-high-frequency-algorithmic-trading.asp (2015)

Alvaro P, Conway N, Hellerstein JM, Marczak WR (2011) Consistency analysis in bloom: a calm and collected approach. Fifth biennial conference on innovative data systems research. Online proceedings, CIDR 2011. Asilomar, CA, USA, 9–12 January 2011, pp 249--260

Bailis P, Fekete A, Franklin MJ, Ghodsi A, Hellerstein JM, Stoica I (2014) Coordination avoidance in database systems. PVLDB 8(3):185–196

Barbará-Millá D, Garcia-Molina H (1994) The demarcation protocol: A technique for maintaining constraints in distributed database systems. VLDB J 3(3):325–353

Bernstein AJ, Gerstl DS, Lewis PM (1999) Concurrency control for step-decomposed transactions. Inf Syst 24(9):673–698

Bernstein PA, Shipman DW (1980) The correctness of concurrency control mechanisms in a system for distributed databases (sdd-1). ACM Trans Database Syst 5(1):52–68

Bernstein PA, Shipman DW, Rothnie JB Jr (1980) Concurrency control in a system for distributed databases (sdd-1). ACM Trans Database Syst 5(1):18–51

Brandt MW (2010) Chapter 5—portfolio choice problems. In: Handbook of Financial Econometrics: Tools and Techniques vol 1, pp 269–336

Cheung A, Arden O, Madden S, Solar-Lezama A, Myers AC (2014) Using program analysis to improve database applications. EEE Data Eng Bull 37:186–213

Cheung A, Madden S, Arden O, Myers AC (2012) Automatic partitioning of database applications. PVLDB 5(11):1471–1482

Cheung A, Madden S, Solar-Lezama A (2014) Sloth: being lazy is a virtue (when issuing database queries). In: SIGMOD’14, pp 931–942

Creamer GG, Freund Y (2013) Automated trading with boosting and expert weighting. Quant Finance 4(10):401–420

Dashti M, John SB, Shaikhha A, Koch C (2016) Repairing conflicts among MVCC transactions. CoRR. arXiv:1603.00542

Davies CT (1978) Data processing spheres of control. IBM Syst J 17(2):179–198

Eswaran KP, Gray JN, Lorie RA, Traiger IL (1976) The notions of consistency and predicate locks in a database system. Commun ACM 19(11):624–633

Faleiro JM, Abadi D, Hellerstein JM (2017) High performance transactions via early write visibility. PVLDB 10(5):613–624

Garcia-Molina H (1983) Using semantic knowledge for transaction processing in a distributed database. ACM Trans Database Syst 8(2):186–213

Garcia-Molina H, Salem K (1987) Sagas. SIGMOD Rec 16(3):249–259

Garcia-Molina H, Salem K (1987) Sagas. In: Proceedings of the 1987 ACM SIGMOD international conference on management of data, SIGMOD’87, New York. ACM, pp 249–259

Garey MR, Johnson DS (1990) Computers and intractability; a guide to the theory of NP-completeness. W. H. Freeman & Co., New York

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680

Kumar A, Stonebraker M (1988) Semantics based transaction management techniques for replicated data. In: Proceedings of the 1988 ACM SIGMOD international conference on management of data, SIGMOD’88, New York. ACM, pp 117–125

Kung HT, Robinson JT (1981) On optimistic methods for concurrency control. ACM Trans Database Syst 6(2):213–226

Larson P-A, Blanas S, Diaconu C, Freedman C, Patel JM, Zwilling M (2011) High-performance concurrency control mechanisms for main-memory databases. PVLDB 5(4):298–309

Li C, Porto D, Clement A, Gehrke J, Preguiça N, Rodrigues R (2012) Making geo-replicated systems fast as possible, consistent when necessary. In: Proceedings of the 10th USENIX conference on operating systems design and implementation, OSDI’12. USENIX Association, Berkeley, pp 265–278

Marlowe TJ, Ryder BG (1990) Properties of data flow frameworks: a unified model. Acta Inf 28(2):121–163

Neumann T, Mühlbauer T, Kemper A. Fast serializable multi-version concurrency control for main-memory database systems. SIGMOD’15, pp 677–689

Olston C, Loo BT, Widom J (2001) Adaptive precision setting for cached approximate values. In: Proceedings of the 2001 ACM SIGMOD international conference on management of data, SIGMOD’01. ACM, New York, pp 355–366

Olston C, Widom J (2000) Offering a precision-performance tradeoff for aggregation queries over replicated data. In: Proceedings of the 26th international conference on very large data bases, VLDB’00. Morgan Kaufmann Publishers Inc, San Francisco, pp 144–155

Pandis I, Johnson R, Hardavellas N, Ailamaki A (2010) Data-oriented transaction execution. PVLDB 3(1–2):928–939

Pu C, Leff A (1991) Replica control in distributed systems: as asynchronous approach. In: Proceedings of the 1991 ACM SIGMOD international conference on management of data, SIGMOD’91. ACM, New York, pp 377–386

Ramamritham K, Pu C (1995) A formal characterization of epsilon serializability. IEEE Trans Knowl Data Eng 7(6):997–1007

Roy S, Kot L, Bender G, Ding B, Hojjat H, Koch C, Foster N, Gehrke J (2015) The homeostasis protocol: avoiding transaction coordination through program analysis. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data, SIGMOD’15. ACM, New York, pp 1311–1326

Shasha D, Llirbat F, Simon E, Valduriez P (1995) Transaction chopping: algorithms and performance studies. ACM Trans Database Syst 20(3):325–363

Shen W, Wang J, Jiang Y-G, Zha H. Portfolio choices with orthogonal bandit learning. In: IJCAI’15, pp 974–980

Wang Z, Mu S, Cui Y, Yi H, Chen H, Li J (2016) Scaling multicore databases via constrained parallel execution. In: Proceedings of the 2016 international conference on management of data, SIGMOD’16, pp 1643–1658

Weikum G, Vossen G (2001) Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Elsevier, Amsterdam

Whitley D (1994) A genetic algorithm tutorial. Stat Comput 4(2):65–85

Wolfe MJ, Shanklin S, Ortega L (1995) High performance compilers for parallel computing. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA

Wu K-L, Yu PS, Pu C (1992) Divergence control for epsilon-serializability. In: Proceedings of the 8th international conference on data engineering. IEEE Computer Society, pp 506–515, Washington

Wu Y, Chan C-Y, Tan K-L (2016) Transaction healing: scaling optimistic concurrency control on multicores. In: SIGMOD’16, pp 1689–1704

Yan C, Cheung A (2016) Leveraging lock contention to improve oltp application performance. PVLDB 9(5):444–455

Yu H, Vahdat A (2000) Design and evaluation of a continuous consistency model for replicated services. In: Proceedings of the 4th conference on symposium on operating system design & implementation, vol 4, OSDI’00. USENIX Association, Berkeley

Thông tin
Thông tin xuất bản

Data Science and Engineering

Thông tin tác giả