Tối ưu hóa Join đệ quy trên tập dữ liệu lớn trong môi trường spark

 15,002 0.000000 
 Test 2 0.000101 50,000 8 21 1,050,000 15,053 0.000000 
 Test 3 0.000101 50,000 8 21 1,050,000 15,101 0.000000 
 Test 4 0.000101 50,000 8 21 1,050,000 15,121 0.000000 
Phan Thượng Cang, Trần Thị Tố Quyên, Phan Anh Cang 739 
D. Đánh giá ba hướng tiếp cận 
 Chúng tôi tiến hành so sánh giải thuật Semi-Naïve trên Hadoop, Semi-Naïve trên Spark và Semi-Naïve đã cải 
tiến để thấy được lượng dữ liệu trung gian, lượng dữ liệu đọc vào và thời gian thực thi, qua đó đánh giá mức độ cải tiến 
của đề xuất trong nghiên cứu này. 
 Bảng 3. Lượng dữ liệu trung gian của các tiếp cận (#records) 
 Tiếp cận 5GB.Test1 10GB.Test2 20GB.Test3 30GB.Test3 
 Semi-Naïve – Hadoop 73,339,332 146,668,049 293,330,613 421,466,111 
 Semi-Naïve – Spark 7,281,636 22,884,615 45,755,154 103,957,219 
 Semi-Naïve + Cache + Filter – Spark 1,139,985 4,158,931 9,152,159 24,870,278 
 Bảng 3 mô tả kết quả lượng dữ liệu trung gian cần vận chuyển qua mạng giữa ba hướng tiếp cận: 
 Hình 5. Lượng dữ liệu trung gian giữa ba hướng tiếp cận Hình 5. Lượng dữ liệu cần đọc của ba hướng tiếp cận 
 Kết quả so sánh thể hiện rất rõ về các cải tiến của Spark so với Hadoop trong Hình 4. Từ việc quản lý công việc 
lặp và phân chia các partitions trên bộ nhớ giúp giảm thiểu đáng kể lượng dữ liệu trung gian cần vận chuyển qua mạng. 
Bộ lọc Bloom và tính năng cache đã tiếp tục cải tiến, làm giảm thêm lượng dữ liệu dư thừa không tham gia vào quá 
trình Join, tối ưu được việc xử lý cho join đệ quy trên Spark. 
 Bảng 4 mô tả kết quả lượng dữ liệu cần đọc giữa ba hướng tiếp cận. 
 Bảng 4. Lượng dữ liệu cần đọc của các tiếp cận 
 Tiếp cận (s) 5GB.Test1 10GB.Test2 20GB.Test3 30GB.Test3 
 Semi-Naïve – Hadoop 147,615,684 295,213,667 590,437,461 975,000,351 
 Semi-Naïve – Spark 9,362,202 41,615,177 83,208,544 268,632,499 
 Semi-Naïve + Cache + Filter – Spark 2,080,330 8,317,760 16,627,752 34,850,020 
 Hình 6. Thời gian thực thi của ba hướng tiếp cận 
 Kết quả từ Hình 5 cho thấy từ tính năng lập lịch biểu để xử lý luồng dữ liệu và quản lý vòng lặp, Spark đã thực 
thi trực tiếp trên bộ nhớ tránh được việc quét lại dữ liệu nhiều lần. Bên cạnh đó, việc sử dụng cache đã tối ưu hơn nữa 
chi phí quét dữ liệu đầu vào. 
 Hình 6 cho thấy Spark cải thiện được rất nhiều về tốc độ xử lý so với Hadoop. Từ các nghiên cứu cải tiến đã 
giúp tối ưu hoá hơn nữa thời gian thực thi cho giải thuật Semi Naïve. Đối với giải thuật Semi-Naïve có cải tiến, dữ liệu 
càng lớn thì hiệu suất càng được cải thiện, dữ liệu nhỏ sẽ tốn chi phí cho việc xử lý bộ lọc. 
740 TỐI ƯU HÓA JOIN ĐỆ QUY TRÊN TẬP DỮ LIỆU LỚN VỚI SPARK 
 Bảng 5. Thời gian thực thi của các hướng tiếp cận (giây) 
 Tiếp cận (s) 5GB.Test1 10GB.Test2 20GB.Test3 30GB.Test3 
 Semi-Naïve – Hadoop 1,202 2,279 3,984 8,472 
 Semi-Naïve – Spark 844 1,251 2,669 6,583 
 Semi-Naïve + Cache + Filter – Spark 424 715 1,436 2,696 
 V. KẾT LUẬN VÀ KIẾN NGHỊ 
A. Kết luận nghiên cứu 
 Nhóm nghiên cứu đã đưa ra những giải pháp cải tiến hiệu quả cho vấn đề “Tối ưu hoá Join đệ quy trên tập dữ 
liệu lớn trong môi trường MapReduce”. Những kết quả đáng chú ý của nghiên cứu này bao gồm: 
 (1) Một điều tra các giải pháp hiện có cho Join đệ quy trên tập dữ liệu lớn trong môi trường MapReduce. Nó 
 cũng chỉ ra những hạn chế của các giải pháp và sự cần thiết cho những đề xuất của nghiên cứu này. 
 (2) Tối ưu hóa cho Join đệ quy trong MapReduce. Những giải pháp hiệu quả được dùng để cải tiến Join đệ quy 
 như sau: (a) Cơ chế xử lý lặp trên bộ nhớ với Spark RDD nhằm làm tăng hiệu quả thực thi; (b) Cơ chế 
 vùng nhớ đệm của Spark nhằm cache tập dữ liệu không đổi trong các lần lặp và giảm thiểu chi phí đọc viết 
 lại dữ liệu; (c) Bộ lọc giao và thuật toán Intersection Bloom Join nhằm loại bỏ dữ liệu dư thừa không tham 
 gia vào Join, cũng có nghĩa là làm giảm chi phí có liên quan đến việc đọc/viết và truyền thông cho dữ liệu 
 vô ích. 
 (3) Mô hình chi phí cho Join đệ quy trong MapReduce. Đây là cơ sở lý thuyết quan trọng để làm cơ sở cho việc 
 đánh giá và so sánh các giải pháp. 
 (4) Sự triển khai và phát triển ứng dụng trên các nền tảng xử lý dữ liệu lớn phổ biến nhất hiện nay như Hadoop 
 và thế hệ mới mới Spark. 
 (5) Các thực nghiệm và đánh giá cho Join đệ quy trong MapReduce với Hadoop và Spark. 
 Join đệ quy là một phép toán tiêu tốn nhiều chi phí, thời gian và tài nguyên. Thông qua mô hình chi phí và các 
thực nghiệm, chúng tôi đã chứng minh được rằng các giải pháp cải tiến của chúng tôi đã mang lại hiệu quả đáng kể hơn 
so với giải pháp hiện nay trong tính toán Join đệ quy trên tập dữ liệu lớn. Việc thực thi Join đệ quy trong môi trường 
Spark của chúng tôi đã khai thác được tối đa khả năng của Spark như xử lý song song phân tán, xử lý lặp, cơ chế bộ 
nhớ đệm và tính toán nhanh trên bộ nhớ. Hơn nữa, việc sử dụng bộ lọc Bloom để loại bỏ các phần tử không tham gia 
join của toàn bộ tập dữ liệu đầu vào đã làm giảm bớt gánh nặng đọc/viết và xử lý quá nhiều dữ liệu. 
 Những đóng góp của chúng tôi có ý nghĩa thực tiễn cao. Bộ lọc giao có thể được áp dụng để giải quyết các vấn 
đề phổ biến trong nhiều lĩnh vực như Join, sự hòa giải và chống trùng lắp dữ liệu (reconciliation and deduplication), 
sửa lỗi (error-correction), v.v. Tối ưu hóa Join đệ quy trong MapReduce với Spark mang lại lợi ích to lớn cho nhiều 
lĩnh vực như cơ sở dữ liệu lớn, mạng xã hội, tin sinh học, mạng sensor, giám sát mạng, máy học, v,v. Sau cùng, nghiên 
cứu này là bước đi quan trọng đóng góp vào ngữ cảnh tối ưu hóa quản lý dữ liệu lớn trên cơ sở hạ tầng đám mây. 
B. Hướng phát triển 
 Mặc dù, giải thuật đã giảm thiểu nhiều chi phí cho việc đọc/viết dữ liệu và tăng tốc cho quá trình xử lý. Tuy 
nhiên, việc tối ưu Join đệ quy trên tập dữ liệu lớn trong môi trường Spark vẫn còn tồn tại nhiều hạn chế. Để đạt được 
hiệu quả như mong muốn, đòi hỏi phải có một hệ thống cụm máy tính (cluster) đủ mạnh và chạy ổn định xử lý dữ liệu 
sau mỗi lần Join. Hơn nữa, vấn đề nghiêng dữ liệu là một thách thức rất lớn cho đề tài này và cho bài toán xử lý dữ liệu 
lớn nói chung. Đây cũng là hướng phát triển mà đề tài muốn hướng đến trong tương lai. 
 TÀI LIỆU THAM KHẢO 
[1] J. Dean and S. Ghemawat, “MapReduce: simplified data processing on large clusters,” Commun. ACM, vol. 51, no. 1, p. 107, 
 Jan. 2008. 
[2] “Apache Hive TM.” [Online]. Available: https://hive.apache.org/. [Accessed: 14-Jun-2016]. 
[3] K. Wiley, A. Connolly, S. Krughoff, J. Gardner, M. Balazinska, B. Howe, Y. Kwon, and Y. Bu, “Astronomical Image 
 Processing with Hadoop,” ResearchGate, Jul. 2011. 
[4] Page, Lawrence, Brin, Sergey, Motwani, Rajeev, Winograd, and Terry, “Page, L., et al.: The PageRank citation ranking: 
 Bringing order to the web,” ResearchGate, Jan. 1998. 
[5] J. M. Kleinberg, “Authoritative Sources in a Hyperlinked Environment,” J ACM, vol. 46, no. 5, pp. 604–632, Sep. 1999. 
[6] Bancilhon and R. Ramakrishnan, “An Amateur's Introduction to Recursive Query Processing Strategies,” 1986. . 
[7] A. K. Jain, M. N. Murty, and P. J. Flynn, Data Clustering: A Review. 1999. 
[8] M. T. Hagan, H. B. Demuth, M. H. Beale, and O. De Jess, Neural Network Design, 2nd ed. USA: Martin Hagan, 2014. 
Phan Thượng Cang, Trần Thị Tố Quyên, Phan Anh Cang 741 
[9] S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, 1994. 
[10] A. W. Moore and D. Zuev, “Internet Traffic Classification Using Bayesian Analysis Techniques,” in Proceedings of the 2005 
 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, New York, NY, USA, 
 2005, pp. 50–60. 
[11] E. F. Codd, “A Relational Model of Data for Large Shared Data Banks,” Commun ACM, vol. 13, no. 6, pp. 377–387, Jun. 
 1970. 
[12] E. F. Codd, “Relational Completeness of Data Base Sublanguages,” R Rustin Ed Database Syst. 65-98 Prentice Hall IBM 
 Res. Rep. RJ 987 San Jose Calif., 1972. 
[13] K.-L. Tan and H. Lu, “A Note on the Strategy Space of Multiway Join Query Optimization Problem in Parallel Systems,” 
 SIGMOD Rec, vol. 20, no. 4, pp. 81–82, Dec. 1991. 
[14] X. Lin and M. E. Orlowska, “An efficient processing of a chain join with the minimum communication cost in distributed 
 database systems,” Distrib. Parallel Databases, vol. 3, no. 1, pp. 69–83, Jan. 1995. 
[15] C. Ordonez, “Optimizing Recursive Queries in SQL,” in Proceedings of the 2005 ACM SIGMOD International Conference 
 on Management of Data, New York, NY, USA, 2005, pp. 834–839. 
[16] S. Idreos, E. Liarou, and M. Koubarakis, “Continuous Multi-way Joins over Distributed Hash Tables,” in Proceedings of the 
 11th International Conference on Extending Database Technology: Advances in Database Technology, New York, NY, 
 USA, 2008, pp. 594–605. 
[17] T.-C. Phan, L. d’Orazio, and P. Rigaux, “A Theoretical and Experimental Comparison of Filter-Based Equijoins in 
 MapReduce,” in Transactions on Large-Scale Data- and Knowledge-Centered Systems XXV, A. Hameurlain, J. Küng, and R. 
 Wagner, Eds. Springer Berlin Heidelberg, 2016, pp. 33–70. 
[18] “Apache SparkTM - Lightning-Fast Cluster Computing.” [Online]. Available:  [Accessed: 14-Jun-
 2016]. 
[19] “The Apache Cassandra Project.” [Online]. Available:  [Accessed: 14-Jun-2016]. 
[20] “Apache HBase – Apache HBaseTM Home.” [Online]. Available: https://hbase.apache.org/. [Accessed: 14-Jun-2016]. 
[21] “Amazon Simple Storage Service (S3) - Cloud Storage,” Amazon Web Services, Inc. [Online]. Available: 
 //aws.amazon.com/s3/. [Accessed: 14-Jun-2016]. 
[22] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: Cluster Computing with Working Sets,” in 
 Proceedings of the 2Nd USENIX Conference on Hot Topics in Cloud Computing, Berkeley, CA, USA, 2010, pp. 10–10. 
[23] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, and I. Stoica, “Resilient 
 Distributed Datasets: A Fault-tolerant Abstraction for In-memory Cluster Computing,” in Proceedings of the 9th USENIX 
 Conference on Networked Systems Design and Implementation, Berkeley, CA, USA, 2012, pp. 2–2. 
[24] F. Bancilhon, “Naive Evaluation of Recursively Defined Relations,” in On Knowledge Base Management Systems, M. L. 
 Brodie and J. Mylopoulos, Eds. Springer New York, 1986, pp. 165–178. 
[25] I. Balbin and K. Ramamohanarao, “A Generalization of the Differential Approach to Recursive Query Evaluation,” J Log 
 Program, vol. 4, no. 3, pp. 259–262, Sep. 1987. 
[26] F. Bancilhon, D. Maier, Y. Sagiv, and J. D. Ullman, “Magic Sets and Other Strange Ways to Implement Logic Programs 
 (Extended Abstract),” in Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 
 New York, NY, USA, 1986, pp. 1–15. 
[27] J. D. Ullman, Principles of Database and Knowledge-base Systems, Vol. I. New York, NY, USA: Computer Science Press, 
 Inc., 1988. 
[28] Y. E. Ioannidis, “On the Computation of the Transitive Closure of Relational Operators,” in Proceedings of the 12th 
 International Conference on Very Large Data Bases, San Francisco, CA, USA, 1986, pp. 403–411. 
[29] P. Valduriez and H. Boral, “Evaluation of Recursive Queries Using Join Indices,” in Expert Database Systems, 1986, pp. 
 271–293. 
[30] S. Warshall, “A Theorem on Boolean Matrices,” J ACM, vol. 9, no. 1, pp. 11–12, Jan. 1962. 
[31] H. S. Warren Jr., “A Modification of Warshall’s Algorithm for the Transitive Closure of Binary Relations,” Commun ACM, 
 vol. 18, no. 4, pp. 218–220, Apr. 1975. 
[32] F. N. Afrati, V. Borkar, M. Carey, N. Polyzotis, and J. D. Ullman, “Map-reduce Extensions and Recursive Queries,” in 
 Proceedings of the 14th International Conference on Extending Database Technology, New York, NY, USA, 2011, pp. 1–8. 
[33] F. N. Afrati, V. Borkar, M. Carey, N. Polyzotis, and J. D. Ullman, “Cluster Computing, Recursion and Datalog,” in 
 Proceedings of the First International Conference on Datalog Reloaded, Berlin, Heidelberg, 2011, pp. 120–144. 
[34] G. Malewicz, M. H. Austern, A. J. . Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski, “Pregel: A System for Large-
 scale Graph Processing,” in Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, New 
 York, NY, USA, 2010, pp. 135–146. 
[35] J. Chandar, “Join Algorithms using Map/Reduce,” University of Edinburgh, 2010. 
[36] Y. Bu, B. Howe, M. Balazinska, and M. D. Ernst, “The HaLoop Approach to Large-scale Iterative Data Analysis,” VLDB J., 
 vol. 21, no. 2, pp. 169–190, Apr. 2012. 
[37] T. T. Q. Tran, “Traitement de la jointure récursive en MapReduce,” Université Blaise Pascal-Clermont-Ferrand II, Clermont-
 Ferrand, 2014. 
742 TỐI ƯU HÓA JOIN ĐỆ QUY TRÊN TẬP DỮ LIỆU LỚN VỚI SPARK 
[38] M. Shaw, P. Koutris, B. Howe, and D. Suciu, “Optimizing Large-scale Semi-NaïVe Datalog Evaluation in Hadoop,” in 
 Proceedings of the Second International Conference on Datalog in Academia and Industry, Berlin, Heidelberg, 2012, pp. 
 165–176. 
[39] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Commun. ACM, vol. 13, no. 7, pp. 422–426, Jul. 
 1970. 
[40] D. Guo, J. Wu, H. Chen, and X. Luo, “Theory and Network Applications of Dynamic Bloom Filters,” in Proceedings IEEE 
 INFOCOM 2006. 25TH IEEE International Conference on Computer Communications, 2006, pp. 1–12. 
[41] T. C. Phan, L. d’Orazio, and P. Rigaux, “Toward Intersection Filter-based Optimization for Joins in MapReduce,” in 
 Proceedings of the 2Nd International Workshop on Cloud Intelligence, New York, NY, USA, 2013, p. 2:1–2:2. 
[42] A. Kirsch and M. Mitzenmacher, “Less Hashing, Same Performance: Building a Better Bloom Filter,” in Algorithms – ESA 
 2006, Y. Azar and T. Erlebach, Eds. Springer Berlin Heidelberg, 2006, pp. 456–467. 
 OPTIMIZATION FOR RECURSIVE JOINS 
 ON LARGE-SCALE DATASETS USING SPARK 
 Phan Thuong Cang, Tran Thi To Quyen, Phan Anh Cang 
ABSTRACT— MapReduce has recently become the dominant programming model for analyzing and processing large-scale data. 
However, the model has its own limitations. It does not completely support iterative computation, caching mechanism, and 
operations with multiple inputs. Besides, I/O and communication costs of the model are so expensive. One of notably complex 
operations used extensively and expensively in MapReduce is a recursive Join. It requires processing characteristics that are also 
the limitations of the MapReduce environment. Therefore, this research proposed efficient solutions of processing the recursive join 
on large-scale datasets using Spark, a next-generation processing engine of MapReduce. Our proposal eliminates a large amount of 
redundant data generated in repeated processing of the join, and takes advantages of in-memory computing means and cache 
mechanism. Through cost models and experiments, the present research shows that our solutions significantly improve the execution 
perfomance of the recursive Join in MapReduce.