Chương 1: Giới thiệu dé tài. Trong chương nay sẽ giới thiệu và trình bày tong quát về dé tài, bao gồm giới thiệu, mục tiêu nghiên cứu, nội dung nghiên cứu, đối tượng và phạm vi nghiên cứu, ý nghĩa khoa học và thực tiễn của đề tài. Sau cùng là câu trúc của luận văn. Chương 2: Các công trình nghiên cứu liên quan.
Trong chương này sẽ giới thiệu và trình bày các công trình nghiên cứu đã có liên quan mật thiết đến đề tài, những vân đề còn tôn tai mà đê tài cân tập trung nghiên cứu và giải quyét. Chương 3: Khao sát và phân tích. Trong chương nay sẽ trình bày về khảo sát các bài toán giao thông và nhu cầu sử dụng dữ liệu của các bài toán này, phân tích các đặc tính dữ liệu và các thao tác trên dữ liệu. Chương 4: Xây dựng hệ thống.
Trong chương này sẽ trình bày kiến trúc hệ thông, mô hình tô chức dữ liệu và các giao tác trên dữ liệu mà đề tài đê xuât. Nguyễn Phan Anh 4 Xây dựng hệ thống lưu trữ và truy xuất dữ liệu lớn cho các bài toán giao thông theo thời gian thực Chương 5: Thí nghiệm và đánh giá. Trong chương này sẽ trình bày việc cài đặt hệ thống, các thí nghiệm và đánh giá tương ứng với khả năng lưu trữ dữ liệu, khả năng truy xuất dữ liệu cũng như khả năng mở rộng của hệ thống. Chương 6: Tổng kết.
Trong chương này sẽ trình bày tổng kết, các đóng góp cũng như hướng phát triển trong tương lai của đề tài. Nguyễn Phan Anh 5 Xây dựng hệ thống lưu trữ và truy xuất dữ liệu lớn cho các bài toán giao thông theo thời gian thực CHƯƠNG 2: CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN Chương này sẽ giới thiệu và trình bày các công trình nghiên cứu đã có liên quan mật thiệt dén đề tài, những van đề còn tôn tại mà đề tài can tập trung nghiên cứu và giải quyết. Hệ thống mã hóa tọa độ không gian địa lý - Geohash Geohash{ 14] là hệ thống mã hóa cặp tọa độ không gian địa lý hai chiều vĩ độ - kinh độ thành một gia tri trong không gian một chiều là một chuỗi ký tự chữ và SỐ được phat minh bởi Gustavo Niemeyer vào năm 2008. Nó là một cau trúc dữ liệu không gian phân cấp, chia nhỏ không gian thành một hình lưới và là một trong những ứng dụng của đường cong Z-order.
Chuỗi Geohash là một chuỗi ký tự chữ và số được biếu diễn dưới dang Base32, chuỗi nay được sinh ra bang cách chuyền đổi từ chuỗi nhị phân, trong đó ký tự nhị phân dau tiên chia đôi không gian theo kinh độ thành hai phan (-180, 0) là 0 và (0, 180) là 1. Ký tự nhị phân thứ hai tiếp tục chia đôi không gian trên theo vĩ độ thành hai phan bac bán cau là 0 và nam bán cau là 1. Ký tự nhị phân thứ ba lại tiếp tục chia đôi không gian theo kinh độ và ký tự nhị phân thứ tư lại tiếp tục chia đôi không gian theo vĩ độ. Quá trình này tiếp tục cho đến khi đạt được độ dài mong muôn nhat định.
Các chuỗi Geohash có chung phan dau chuỗi (prefix) thì năm gần nhau trong không gian. Chuỗi Geohash có thé có độ dài bat kì, chuỗi càng dài thì kích thước không gian mà nó đại diện càng nhỏ. Sau đây là bảng so sánh kích thước không gian tương ứng theo độ dài chuỗi Geohash: Nguyễn Phan Anh 6 Xây dựng hệ thống lưu trữ và truy xuất dữ liệu lớn cho các bài toán giao thông theo thời gian thực Độ dài chuỗi Geohash | Chiều rộng | Chiều cao | 50094km | 4992,6 km 2 12523km | 624,1 km 3 156,5 km 156 km + 39,1 km 19,5 km 5 4,9 km 4.9 cm 12 3,7 cm 19cm Bảng 2.1: Kích thước không gian tương ứng theo độ dài chuỗi Geohash Chuỗi Geohash giúp cho việc xác định vị trí của một điểm hay một không gian địa lý trở nên đơn giản: - - Một chuỗi Geohash có thé xác định vị trí của một điểm dia lý thay thế cho phương pháp sử dụng cặp tọa độ địa lý vĩ độ - kinh độ. - - Một chuỗi Geohash có thé xác định vị trí của một không gian địa lý thay thé cho phương pháp sử dụng 2 cặp tọa độ địa lý vĩ độ - kinh độ để xác định một hình chữ nhật bao không gian địa lý đó.
Nguyễn Phan Anh 7 Xây dựng hệ thống lưu trữ và truy xuất dữ liệu lớn cho các bài toán giao thông theo thời gian thực 2. Các hệ thống cơ sở dữ liệu 2. Hệ thống cơ sở dữ liệu quan hệ Mô hình cơ sở dữ liệu quan hệ được phát minh bởi E. Mô hình này tổ chức dữ liệu dưới dạng bang (table), mỗi bảng bao gồm nhiều hàng (row) và mỗi hàng lại bao gồm nhiều cột (column).
Mô hình này giúp giảm thiểu việc dư thừa dữ liệu nhăm tiết kiệm không gian lưu trữ trên 6 đĩa và truy xuất dữ liệu hiệu quả. Các hệ thống cơ sở dữ liệu quan hệ có các đặc tính sau: - Cac giao tac (transaction) của hệ thong cơ sở dữ liệu quan hệ cần đảm bảo các thuộc tính ACID là tính nguyên tố (Atomicity), tính nhất quán (Consistency), tính tách biệt (Isolation), tính bên vững (Durability). - Dir liệu được tổ chức theo mô hình quan hệ phức tap. Một số hệ thong cơ sở dữ liệu quan hệ pho bién hiện nay: - MySQL - Microsoft SQL Server - Oracle Database Tuy nhiên, do phải đảm bảo các thuộc tính ACID nên tốc độ lưu trữ và truy xuất dữ liệu của các hệ thống này không cao.
Bên cạnh đó, việc tô chức dữ liệu theo mô hình quan hệ phức tạp cũng không khai thác hiệu quả được các đặc tính của dữ liệu định vi. Hệ thống cơ sở dữ liệu không quan hệ - NoSQL Hệ thông cơ sở dữ liệu không quan hệ - NoSQL là hệ thống cơ sở dữ liệu không sử dụng mô hình dữ liệu quan hệ. Một số hệ thong cơ sở dữ liệu không quan hệ - NoSQL phô biến hiện nay: Nguyễn Phan Anh 8 Xây dựng hệ thống lưu trữ và truy xuất dữ liệu lớn cho các bài toán giao thông theo thời gian thực MongoDB[16] là hệ thong cơ sở dữ liệu hướng van ban (document-oriented) đa nên tảng. MongoDB hỗ trợ mô hình dữ liệu cực kì mềm dẻo với các document theo định dang JSON.
MongoDB lưu trữ các document này dưới bộ nhớ thứ cấp theo một định dạng gọi là BSON. Cac document lưu trữ vào MongoDB không cần phải tuân theo một cấu trúc (schema) định sẵn. Các document được phân nhóm vào các bộ sưu tập (collection), tương tự các bảng của các hệ thông cơ sở dữ liệu quan hệ. Ban đầu được phát triển tại Facebook và trở thành mã nguồn mở vao năm 2008.
Apache Cassandra có mô hình dữ liệu kết hợp giữa key-value và cơ sở dữ liệu hướng cột (column- oriented). Các hệ thống lưu trữ dữ liệu dựa trên bộ nhớ chính 2. RAMCloud RAMCloud[18] là một công trình nghiên cứu của Dai hoc Stanford bắt đầu từ năm 2009. Công trình này xây dựng một nên tảng lưu trữ và truy xuất dữ liệu thế hệ mới có tôc độ lưu trữ và truy xuât dữ liệu siêu nhanh với khôi lượng lớn dữ liệu trên nên tảng lưu trữ của bộ nhớ chính.
Hệ thông RAMCloud lưu trữ toàn bộ dữ liệu của hệ thống vào bộ nhớ chính. Việc truy xuất đữ liệu được thực hiện toàn bộ trên bộ nhớ chính giúp cho RAMCloud có tốc độ truy xuất dữ liệu siêu nhanh, việc lưu trữ dữ liệu vào bộ nhớ thứ cấp chỉ với mục đích sao lưu dự phòng. RAMCloud có mô hình tô chức dữ liệu đơn giản là key-value. Tuy nhiên, công trình này chỉ đang trong giai đoạn nghiên cứu và thử nghiệm nên chỉ mới hỗ trợ xây dựng chỉ mục (index) một chiều.
Không thể xây dựng hệ thong theo như mục tiêu của dé tài nếu chỉ dựa vào RAMCloud. Redis Nguyễn Phan Anh 9 Xây dựng hệ thống lưu trữ và truy xuất dữ liệu lớn cho các bài toán giao thông theo thời gian thực Redis[19] là một hệ thống mã nguồn mở lưu trữ dữ liệu dựa trên bộ nhớ chính, được sử dụng như co sở dữ liệu hoặc bộ đệm (cache). - H6 trợ nhiều cấu trúc dữ liệu như chuỗi (string), bảng băm (hash), danh sách (list), tập hợp (set), tập hợp có thứ tự (sorted set) với truy vấn theo khoảng (range query),. - Redis được xây dựng san các tính năng nhân bản dự phòng (replication), giao tác, tính săn sàng cao và phân hoạch (partitioning) - H6 trợ việc lưu trữ dữ liệu persistence với nhiêu mức độ khác nhau.
- Dé đạt được mục tiêu hiệu năng siêu nhanh, Redis lưu trữ toàn bộ dữ liệu trên bộ nhớ chính.Công trình “Spatio-temporal Indexing in Non-relational Distributed Databases” Công trình “Spatio-temporal Indexing in Non-relational Distributed Databases”[6] của Anthony Fox và các tác giả dé xuất một giải pháp xây dựng chi mục cho dữ liệu không gian - thời gian (spatio-temporal) dựa trên cơ chế phân tán có san của hệ thống cơ sở dữ liệu không quan hệ - NoSQL là Apache Accumulo[20]. Apache Accumulo được xây dựng dựa trên thiết kế của BigTable của Google. Key Column Column Column Value Row ID : mm ngan Timestamp Family Qualifier Visibility Hình 2.1: Cau trúc của một cặp key-value của Apache Accumulo Nguyễn Phan Anh 10 Xây dựng hệ thống lưu trữ và truy xuất dữ liệu lớn cho các bài toán giao thông theo thời gian thực Giải pháp này sử dụng phương pháp GeoHash dé chuyên dữ liệu không gian 2 chiều thành một chuỗi nhị phân. Chuỗi nhị phân này được dùng để chỉ mục theo không gian.
Thời gian được mã hóa theo dạng “yyyyMMddhh”. Băng cách sử dụng chuỗi Geohash 35 bit (7 ký tự Base32) và chuỗi thời gian như trên, hệ thống chia dữ liệu thành các khối lập phương có một mặt biểu diễn không gian có diện tích 150m? và cạnh còn lại biểu diễn thời gian có giá trị là 1 giờ. Chuỗi GeoHash chia không gian thành các 6 tăng theo thứ tự Z, trong khi đó chuỗi thời gian tăng một cách tuyến tính, kết hợp 2 giá tri này lại tạo thành một chuỗi có thứ tự một chiều nhưng lap đầy không gian 3 chiều không gian - thời gian. Giải pháp này đề xuất xây dựng khóa chỉ mục (index key) gồm 3 thành phần là: Row ID, Column Family va Qualifier Key.
- Row ID được tao ra băng cách ghép 3 chuỗi con sau lại với nhau: o Chuỗi dau tiền là một số ngẫu nhiên (bin number), trợ giúp cho quá trình phân tải. Gia sử không có bin number, như ta đã biết dữ liệu được chia thành đơn vị nhỏ nhất là 150m? trong khoảng thời gian 1 tiếng.