Luận văn thạc sĩ: Giải pháp lưu trữ và truy xuất dữ liệu GPS với khối lượng lớn

Luận văn thạc sĩ kỹ thuật phân tích máy tính xây dựng giải pháp lưu trữ và truy xuất dữ liệu gps với khối lượng lớn, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi

• Tác giả: Nguyễn Tấn Bảo
• Người hướng dẫn: TS. Phạm Trần Vũ
• Trường học: Đại học Bách Khoa - ĐHQG TP.HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Giải Pháp Lưu Trữ Và Truy Xuất Dữ Liệu GPS Với Khối Lượng Lớn
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. Chương 1: Mở đầu
• 1.1. Lý do chọn đề tài
• 1.2. Nhiệm vụ nghiên cứu của đề tài
• 1.3. Ý nghĩa khoa học của đề tài
• 1.4. Phương pháp và đối tượng nghiên cứu
• 1.5. Giới hạn và phạm vi đề tài
• 1.6. Kết quả cần đạt được
• 2. Chương 2: Mô tả cụ thể bài toán
• 2.1. Vai trò và vị trí của hệ thống trong hệ thống tổng thể
• 2.2. Dữ liệu
• 2.3. Lưu trữ
• 2.4. Truy vấn
• 2.5. Hiệu suất mong muốn
• 3. Chương 3: Xây dựng giải pháp
• 3.1. Giải pháp dựa trên các hệ thống database hiện có
• 3.1.1. Cơ sở dữ liệu quan hệ - MySql
• 3.1.2. Cơ sở dữ liệu theo mô hình No-SQL
• 3.1.3. Một số kiểm tra định lượng trên các db có sẵn
• 3.1.4. Đánh giá chung
• 3.2. Các kĩ thuật và công trình nghiên cứu liên quan
• 3.2.1. Các kĩ thuật index địa lý
• 3.2.2. Một số kĩ thuật cân bằng tải
• 3.2.3. Kĩ thuật index dữ liệu đa thuộc tính
• 3.3. Đề xuất giải pháp
• 3.3.1. Kiến trúc hệ thống
• 3.3.1.1. Gom cụm dữ liệu
• 3.3.2. Lựa chọn Persistent Engine
• 3.3.2.1. Mô hình dữ liệu
• 3.3.2.2. Mô hình dữ liệu của Cassandra và dữ liệu dòng thời gian
• 3.3.3. Lựa chọn kĩ thuật index
• 3.3.3.1. Tại sao chọn kd-tree thay vì r-tree?
• 3.3.4. Lựa chọn kĩ thuật cache
• 4. Chương 4: Đo đạc và đánh giá
• 4.1. Tổ chức dữ liệu với MySQL và Mongodb
• 4.2. Đo đạc thời gian thực thi của lệnh Get(TS,TE, R(LatMin, LatMax, LonMin, LonMax))
• 4.2.1. Ảnh hưởng của diện tích vùng bao đến tốc độ thực thi
• 4.2.2. Ảnh hưởng của độ dài khung thời gian đến hiệu suất thực thi
• 4.3. Đo hiệu suất của lệnh truy vấn theo key dữ liệu, Get(TS,TE, K)
• 4.4. Đo hiệu suất của lệnh truy vấn theo key dữ liệu, có giới hạn vùng bao: Get(TS,TE, R(LatMin, LatMax, LonMin, LonMax), K)
• 5. Chương 5: Kết luận và đề xuất

Tóm tắt

I. Giới thiệu về lưu trữ và truy xuất dữ liệu GPS

Trong bối cảnh công nghệ ngày càng phát triển, việc sử dụng công nghệ GPS đã trở nên phổ biến trong nhiều lĩnh vực, từ giao thông đến nghiên cứu địa lý. Lưu trữ dữ liệu GPS trở thành một thách thức lớn, đặc biệt khi khối lượng dữ liệu được sinh ra từ các thiết bị GPS ngày càng tăng. Hệ thống cần phải có khả năng xử lý và lưu trữ một lượng lớn dữ liệu trong thời gian thực, đồng thời cho phép truy xuất dữ liệu một cách nhanh chóng và hiệu quả. Luận văn này tập trung vào việc xây dựng giải pháp cho việc quản lý dữ liệu lớn từ GPS, nhằm phục vụ cho các ứng dụng trong khoa học máy tính và giao thông. Đặc biệt, việc tối ưu hóa lưu trữ dữ liệu không gian và dữ liệu thời gian thực là rất quan trọng để đảm bảo hiệu suất của hệ thống.

II. Phân tích các giải pháp lưu trữ hiện có

Luận văn đã khảo sát nhiều hệ thống cơ sở dữ liệu hiện có để tìm ra giải pháp phù hợp cho việc lưu trữ dữ liệu GPS. Các hệ thống như MySQL và NoSQL đã được xem xét. MySQL, mặc dù phổ biến, nhưng không đáp ứng được yêu cầu về hiệu suất khi xử lý lượng lớn dữ liệu. Ngược lại, các hệ thống NoSQL như MongoDB cho thấy tiềm năng lớn hơn trong việc quản lý dữ liệu lớn nhờ khả năng mở rộng và linh hoạt trong mô hình dữ liệu. Hệ thống MongoDB hỗ trợ index địa lý và có khả năng truy vấn nhanh chóng, giúp cải thiện đáng kể hiệu suất truy xuất dữ liệu GPS. Việc lựa chọn giải pháp lưu trữ phù hợp sẽ ảnh hưởng lớn đến khả năng xử lý và phân tích dữ liệu GPS trong thời gian thực.

III. Đề xuất giải pháp lưu trữ và truy xuất dữ liệu GPS

Dựa trên phân tích các hệ thống hiện có, luận văn đề xuất một giải pháp lưu trữ mới mang tên GBStore, được thiết kế đặc biệt cho việc lưu trữ dữ liệu GPS. Giải pháp này bao gồm các thành phần chính như hệ thống tiếp nhận dữ liệu, hệ thống lưu trữ và hệ thống truy vấn. Hệ thống tiếp nhận sẽ tiếp nhận các tín hiệu GPS từ các thiết bị và chuyển chúng vào GBStore để lưu trữ. GBStore sẽ áp dụng các kỹ thuật index hóa để tối ưu hóa việc truy xuất dữ liệu. Các truy vấn sẽ được thực hiện theo nhiều điều kiện khác nhau, bao gồm thời gian, địa lý và loại dữ liệu, nhằm đảm bảo tính chính xác và hiệu suất cao. Giải pháp này không chỉ giúp tối ưu hóa lưu trữ mà còn đáp ứng nhanh chóng các yêu cầu truy vấn từ người dùng.

IV. Đánh giá hiệu suất của giải pháp

Để đánh giá hiệu suất của GBStore, các thử nghiệm đã được thực hiện nhằm đo lường thời gian thực thi của các lệnh truy xuất dữ liệu. Kết quả cho thấy rằng GBStore có khả năng xử lý trên 100 lệnh truy vấn mỗi giây với thời gian phản hồi dưới 100ms. Điều này cho thấy giải pháp đã đạt được yêu cầu về hiệu suất trong việc quản lý dữ liệu lớn từ GPS. Hệ thống cũng cho thấy khả năng mở rộng tốt khi lượng dữ liệu tăng lên, nhờ vào việc sử dụng các kỹ thuật cân bằng tải và cache. Kết quả này khẳng định giá trị thực tiễn của giải pháp trong việc phục vụ cho các ứng dụng giao thông và phân tích dữ liệu địa lý.

V. Kết luận và hướng phát triển

Luận văn đã đưa ra một giải pháp hiệu quả cho việc lưu trữ và truy xuất dữ liệu GPS lớn, đáp ứng nhu cầu ngày càng cao trong lĩnh vực khoa học máy tính. Giải pháp GBStore không chỉ tối ưu hóa việc quản lý dữ liệu lớn mà còn cung cấp khả năng truy vấn nhanh chóng và chính xác. Trong tương lai, cần tiếp tục nghiên cứu và phát triển các kỹ thuật mới nhằm nâng cao hơn nữa hiệu suất của hệ thống, đồng thời mở rộng khả năng ứng dụng của giải pháp trong các lĩnh vực khác nhau như phân tích dữ liệu thời gian thực và dữ liệu không gian. Việc này sẽ góp phần tạo ra nền tảng vững chắc cho các ứng dụng thông minh trong tương lai.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của các thiết bị di động thông minh và hệ thống định vị toàn cầu (GPS) đã tạo ra một khối lượng dữ liệu khổng lồ với tốc độ gia tăng nhanh chóng theo từng giây. Riêng trong phạm vi thử nghiệm hệ thống xe buýt tại Việt Nam, luồng dữ liệu thực tế ghi nhận tới 3.377.822 tín hiệu GPS chỉ trong vòng 24 giờ của một ngày hoạt động bình thường. Vấn đề nghiên cứu cốt lõi được đặt ra là các hệ quản trị cơ sở dữ liệu quan hệ truyền thống (RDBMS) như MySQL gặp phải nút thắt cổ chai nghiêm trọng về hiệu năng xử lý ghi và đọc do gánh nặng của các ràng buộc ACID. Trong khi đó, các cơ sở dữ liệu NoSQL dạng tài liệu như MongoDB lại bộc lộ độ trễ truy vấn không gian kết hợp thời gian lên tới hơn 8.200 ms, hoàn toàn không đáp ứng được yêu cầu phản hồi tức thời của các hệ thống giao thông thông minh.

Mục tiêu cụ thể của đề tài là xây dựng hệ thống GBStore (GPS Based data Store) với kiến trúc lai chuyên biệt cho việc lưu trữ và truy xuất dữ liệu không gian - thời gian (Spatio-temporal) quy mô lớn. Nghiên cứu xác định các chỉ số hiệu năng mục tiêu khắt khe: tốc độ tiếp nhận dữ liệu ghi đạt tối thiểu 100 lệnh/giây (put/s), thời gian phản hồi cho các truy vấn dữ liệu đa chiều đạt dưới 100 ms, đồng thời đảm bảo khả năng mở rộng quy mô linh hoạt khi lưu lượng phương tiện gia tăng. Phạm vi dữ liệu khảo sát bao gồm toàn bộ lộ trình xe buýt lưu thông thực tế tại Việt Nam trong khoảng thời gian liên tục 7 ngày, được thực nghiệm trực tiếp trên môi trường phần cứng máy tính tiêu chuẩn. Công trình mang ý nghĩa khoa học và thực tiễn sâu sắc, cung cấp nền tảng lưu trữ hiệu năng cao giúp giảm 90% độ trễ xử lý dữ liệu cho các ứng dụng cảnh báo ùn tắc, dự báo luồng xe và hiển thị hiện trạng giao thông thời gian thực.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng của hai lý thuyết kỹ thuật chính: Lý thuyết cơ sở dữ liệu phân tán NoSQL (mô hình BigTable, Accumulo, Cassandra Column Family) và Lý thuyết cấu trúc chỉ mục đa chiều (Multi-dimensional Indexing). Mô hình nghiên cứu trừu tượng hóa dữ liệu GPS thành một bộ năm thành phần toán học $D(T, Lat, Long, K, B)$, trong đó $T$ là mốc thời gian (kiểu số nguyên 64-bit), $Lat$ và $Long$ biểu diễn kinh độ và vĩ độ (kiểu số thực 64-bit), $K$ là khóa định danh phương tiện hoặc cảm biến, và $B$ là mảng byte chứa dữ liệu thô.

Nghiên cứu tập trung phân tích 4 khái niệm và cấu trúc kỹ thuật cốt lõi:

• Cấu trúc cây chỉ mục không gian: Đánh giá chuyên sâu giữa mô hình kd-Tree (cây nhị phân $k$-chiều chia cắt không gian) và R-Tree (cây B-tree đa chiều quản lý các khối bao chữ nhật nhỏ nhất MBB - Minimum Bounding Box).
• Mã hóa không gian GeoHash: Thuật toán chuyển đổi tọa độ địa lý hai chiều (kinh độ trong khoảng [-180, 180] và vĩ độ [-90, 90]) thành chuỗi nhị phân 35-bit hoặc chuỗi ký tự cơ số 32, phân chia bề mặt thành các ô lưới không gian có diện tích 150 m² theo thứ tự đường cong chữ Z ($z$-order curve).
• Mạng tìm kiếm đa thuộc tính (MAAN): Mở rộng giao thức Chord kết hợp hàm băm bảo toàn tính cục bộ (Locality Preserving Hash) để giải quyết các truy vấn khoảng giá trị trên nhiều chiều thuộc tính đồng thời.
• Mô hình hàng rào thời gian (Time-series Binning): Kỹ thuật kết hợp mã định danh phân tải (Bin Number) ngẫu nhiên với chuỗi thời gian định dạng 'yyyyMMddhh' để phân bổ đồng đều các khối dữ liệu vào các nút lưu trữ phân tán.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu sử dụng tập dữ liệu thực tế gồm 3.377.822 bản ghi hành trình GPS từ hệ thống giám sát xe buýt tại Việt Nam. Phương pháp chọn mẫu được tiến hành bằng kỹ thuật lấy mẫu ngẫu nhiên không hoàn lại (Simple Random Sampling) với quy mô 1.000 mốc thời gian độc lập và 1.000 vùng không gian hình chữ nhật có diện tích cố định 1.000 m² bao quanh các tọa độ ngẫu nhiên nhằm loại bỏ hoàn toàn sai số vị trí cục bộ.

Phương pháp phân tích dựa trên kiểm thử định lượng so chuẩn (Benchmarking) thực nghiệm trên 3 hệ thống đại diện: Cơ sở dữ liệu quan hệ MySQL, Cơ sở dữ liệu NoSQL MongoDB (sử dụng chỉ mục địa lý 2dsphere), và Hệ thống chỉ mục phân cấp trong bộ nhớ chính (Memory Cache Index gồm TimeTree B-Tree phân đoạn 1 phút, KeyTree B-Tree và R-Tree không gian). Lý do lựa chọn phương pháp đo đạc thực nghiệm này là nhằm đo lường trực tiếp các thông số kỹ thuật vật lý: thời gian xử lý vào/ra đĩa (Disk I/O), độ trễ truy vấn trung bình (Latency tính bằng mili-giây), và thông lượng xử lý giao dịch đồng thời (Throughput). Toàn bộ quá trình nghiên cứu, thiết kế kiến trúc và đo đạc thực nghiệm được thực hiện trong thời gian 6 tháng, hoàn thành bảo vệ vào tháng 6 năm 2014.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đo đạc định lượng đã đem lại 4 phát hiện quan trọng về hành vi của các hệ thống lưu trữ đối với dữ liệu không-thời gian:

• Thông lượng ghi dữ liệu (Put Throughput): Hệ thống Memory Cache đạt tốc độ ghi cao nhất với khả năng xử lý hàng chục nghìn đối tượng mỗi giây. MongoDB duy trì tốc độ ghi ở mức khá, trong khi MySQL đạt hiệu năng thấp nhất (thấp hơn khoảng 65% so với NoSQL) do phải duy trì các cơ chế khóa giao dịch và nhật ký ghi phục hồi (Write-Ahead Logging) để bảo toàn thuộc tính ACID.
• Hiệu năng truy vấn theo miền thời gian: Khi thực hiện lệnh truy vấn $Get(TS, TE)$ với các khung thời gian mở rộng dần từ 1 giây, 30 giây, 60 giây, 600 giây, 900 giây, 1.800 giây đến 3.600 giây trên tổng số 3.377.822 bản ghi, Memory Cache luôn duy trì độ phản hồi dưới 10 ms. MySQL và MongoDB có độ trễ tăng dần theo hàm tuyến tính tương ứng với dung lượng dữ liệu quét qua.
• Hiệu năng truy vấn giới hạn không gian: Thử nghiệm 1.000 truy vấn ngẫu nhiên với diện tích vùng bao 1.000 m² trên toàn bộ dữ liệu 24 giờ cho thấy sự phân hóa cực lớn. Memory Cache đạt thời gian phản hồi trung bình ấn tượng 46 ms (nhờ xử lý hoàn toàn trong RAM không phát sinh I/O đĩa). MySQL hoàn thành truy vấn ở mức 185 ms. Bất ngờ nhất, MongoDB có thời gian xử lý trung bình lên tới hơn 8.200 ms (hơn 8,2 giây), chậm hơn MySQL tới 44 lần (tương đương chênh lệch 4.432%).
• Hạn chế của chỉ mục 2dsphere trong NoSQL tài liệu: Mặc dù công cụ phân tích truy vấn (explain function) của MongoDB cho thấy hệ thống có kích hoạt chỉ mục 2dsphere, nhưng việc kết hợp quét thứ cấp trên tập dữ liệu hàng triệu điểm mà không có cơ chế phân vùng theo khóa thời gian đã gây ra tình trạng nghẽn I/O nghiêm trọng.

Thảo luận kết quả

Nguyên nhân cốt lõi khiến MongoDB phản hồi chậm ở mức 8.200 ms là do mô hình lưu trữ tài liệu BSON phải thực hiện giải mã và quét lọc đối chiếu từng bản ghi (document scan) khi không gian truy vấn bị giao thoa giữa miền thời gian rộng và tọa độ địa lý. Ngược lại, cấu trúc phân tầng bộ nhớ (Memory Index) giải quyết triệt để vấn đề này nhờ quy trình sàng lọc 3 bước: phân nhánh mốc thời gian 1 phút bằng TimeTree, lọc định danh bằng KeyTree và chỉ duyệt hình học trên R-Tree cục bộ, giúp giảm 99% không gian tìm kiếm.

Các kết quả thực nghiệm này được trình bày trực quan thông qua các dạng biểu đồ chuyên dụng:

• Biểu đồ cột so sánh thông lượng ghi: Thể hiện số lượng bản ghi chèn thành công mỗi giây (đơn vị 1.000 ops/s) giữa ba hệ thống.
• Biểu đồ đường biến thiên thời gian thực thi theo trục thời gian: Minh họa độ trễ tăng trưởng từ mốc 1 giây đến 3.600 giây của MySQL so với đường ngang ổn định của cấu trúc Memory Cache.
• Bảng số liệu tổng hợp thời gian phản hồi trung bình: Thể hiện rõ sự đối lập giữa 46 ms (Memory Cache), 185 ms (MySQL) và 8.200 ms (MongoDB) trên vùng không gian 1.000 m².

Ý nghĩa khoa học của kết quả chứng minh rằng không thể dựa hoàn toàn vào một hệ quản trị cơ sở dữ liệu đơn lẻ có sẵn trên thị trường. Thay vào đó, mô hình tối ưu cho hệ thống GBStore phải là một kiến trúc kết hợp: Sử dụng cơ sở dữ liệu phân tán dạng cột (như Apache Cassandra/CQL) làm Persistent Storage Engine để đảm bảo lưu trữ bền vững với khả năng mở rộng quy mô tuyến tính, kết hợp cùng hệ thống chỉ mục đa tầng trong RAM đóng vai trò Cache Engine để phục vụ các truy vấn thời gian thực có độ trễ dưới 100 ms.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu và thực nghiệm, 4 giải pháp cụ thể được đề xuất nhằm tối ưu hóa hạ tầng lưu trữ dữ liệu GPS quy mô lớn:

• Triển khai kiến trúc lưu trữ lai phân tầng (Hybrid Tiered Architecture): Kết hợp Apache Cassandra làm tầng lưu trữ bền vững lâu dài (Persistent Storage) với mô hình Column Family và xây dựng mô-đun Cache Engine trong bộ nhớ (In-Memory Index) để duy trì tốc độ ghi trên 500 ops/s và độ trễ truy vấn dưới 50 ms. Giải pháp do Đội ngũ Kỹ sư Hạ tầng Dữ liệu triển khai trong lộ trình 3 tháng.
• Tối ưu hóa thuật toán chỉ mục không gian bằng kd-Tree tùy biến: Áp dụng kd-Tree thay thế cho R-Tree trong các mô-đun xử lý điểm dữ liệu nhằm giảm thiểu 30% chi phí tính toán khi cân bằng cây và loại bỏ hiện tượng chồng lấn vùng bao hình chữ nhật. Nhiệm vụ do Chuyên viên Nghiên cứu Thuật toán thực hiện trong thời hạn 6 tuần.
• Chuẩn hóa quy chuẩn phân mảnh dữ liệu Spatio-temporal: Tích hợp kỹ thuật mã hóa GeoHash 35-bit kết hợp mã phân tải ngẫu nhiên (Bin Number) và chuỗi thời gian 1 giờ để phân bổ đồng đều dữ liệu trên các nút mạng, triệt tiêu 100% hiện tượng điểm nóng (hotspot) tại các khu vực trung tâm đô thị. Giải pháp do Kỹ sư Dữ liệu lớn hoàn thiện trong 2 tháng.
• Thiết lập cơ chế tự động giải phóng và nén dữ liệu nguội (Cold Data Offloading): Tự động chuyển đổi các khối dữ liệu GPS có thời gian lưu trữ trên 30 ngày sang định dạng nén cột để tiết kiệm 65% chi phí bộ nhớ đĩa cứng, duy trì hiệu năng ổn định cho cụm máy chủ. Cơ chế do Quản trị viên Hệ thống cấu hình định kỳ hàng quý.

Đối tượng nên tham khảo luận văn

Nội dung luận văn mang lại giá trị học thuật và ứng dụng thực tiễn cao cho 4 nhóm đối tượng chuyên môn:

• Kỹ sư Phần mềm và Kiến trúc sư Hệ thống Giao thông Thông minh (ITS): Tiếp cận mô hình thiết kế trung tâm điều hành vận tải có khả năng giám sát đồng thời hơn 100.000 phương tiện giao thông theo thời gian thực mà không gặp lỗi nghẽn cổ chai hệ thống.
• Chuyên gia Dữ liệu lớn và Quản trị Cơ sở dữ liệu (Database Administrators): Nắm vững kỹ thuật lập chỉ mục đa thuộc tính (Multi-attribute indexing), cách thức tối ưu hóa chỉ mục GeoHash, và phương pháp kết hợp giữa cấu trúc bộ nhớ đệm RAM với cơ sở dữ liệu phân tán NoSQL.
• Nhà nghiên cứu và Học viên Cao học ngành Khoa học Máy tính: Sử dụng công trình làm tài liệu tham khảo chuyên sâu về phương pháp đánh giá thực nghiệm định lượng giữa các hệ quản trị CSDL quan hệ (MySQL) và NoSQL (MongoDB, Cassandra, Accumulo) trên dữ liệu chuỗi thời gian 7 ngày.
• Doanh nghiệp Vận tải và Cơ quan Quản lý Đô thị: Ứng dụng giải pháp công nghệ để xây dựng hệ thống quản lý dữ liệu thiết bị giám sát hành trình xe buýt, xe taxi với chi phí đầu tư phần cứng máy chủ tối ưu nhất.

Câu hỏi thường gặp

Tại sao MongoDB lại có thời gian truy vấn không gian chậm hơn MySQL trong nghiên cứu này?

Mặc dù MongoDB tích hợp sẵn chỉ mục 2dsphere dựa trên thuật toán GeoHash, nhưng khi xử lý truy vấn kết hợp đồng thời cả miền thời gian 24 giờ và không gian 1.000 m² trên tập mẫu 3.377.822 bản ghi, hệ thống phải thực hiện quét và lọc thứ cấp trên lượng lớn tài liệu BSON. Quá trình này gây tắc nghẽn I/O đĩa cứng, khiến độ trễ lên tới hơn 8.200 ms, trong khi MySQL đạt 185 ms nhờ cây B-tree tối ưu hóa tốt hơn cho các truy vấn cục bộ.

Cấu trúc Memory Cache trong nghiên cứu được thiết kế như thế nào để đạt độ trễ 46 ms?

Hệ thống sử dụng mô hình cây phân cấp 3 tầng trong bộ nhớ chính: Gốc là TimeTree (B-Tree) chia nhỏ thời gian theo từng khung 1 phút, mỗi nút lá trỏ đến một KeyTree (B-Tree) quản lý mã định danh phương tiện, và tầng dưới cùng là R-Tree quản lý không gian địa lý. Cấu trúc này loại bỏ hoàn toàn việc đọc/ghi đĩa cứng, giúp 1.000 truy vấn ngẫu nhiên đạt thời gian phản hồi trung bình chỉ 46 ms.

Hệ thống GBStore đặt ra các yêu cầu hiệu năng định lượng nào?

GBStore xác định ba chỉ số mục tiêu bắt buộc: Tốc độ ghi dữ liệu (Put) đạt tối thiểu 100 lệnh/giây, độ trễ phản hồi truy vấn đa điều kiện (Get) không vượt quá 100 ms, và hệ thống duy trì tính sẵn sàng cao, cho phép mở rộng quy mô tuyến tính khi lưu lượng luồng dữ liệu GPS đầu vào gia tăng liên tục theo thời gian thực.

Ưu điểm vượt trội của Apache Cassandra khi áp dụng cho dữ liệu GPS là gì?

Apache Cassandra sở hữu kiến trúc phân tán ngang hàng không có điểm lỗi đơn lẻ (Masterless P2P), cung cấp khả năng ghi thông lượng cực cao và hỗ trợ mô hình Column Family rất phù hợp với dữ liệu chuỗi thời gian. Cassandra cho phép bổ sung nút máy tính động vào cụm mạng đang vận hành mà không cần dừng hệ thống, đảm bảo độ sẵn sàng dịch vụ đạt mức 99,99%.

Kỹ thuật GeoHash kết hợp Bin Number giải quyết bài toán phân tải như thế nào?

Dữ liệu GPS thường có mật độ phân bố không đều, tập trung dày đặc ở khu vực trung tâm đô thị. Việc bổ sung số phân vùng ngẫu nhiên (Bin Number) vào đầu chuỗi khóa kết hợp cùng ký tự GeoHash và mốc thời gian sẽ phân tán các khối dữ liệu 150 m² sang nhiều máy chủ vật lý khác nhau, giúp triệt tiêu hiện tượng quá tải cục bộ tại một nút mạng duy nhất.

Kết luận

• Luận văn hoàn thành việc đánh giá thực nghiệm toàn diện trên tập dữ liệu thực tế gồm 3.377.822 tín hiệu GPS xe buýt, so chuẩn chi tiết giữa 3 cơ chế lưu trữ đại diện là MySQL, MongoDB và Memory Cache.
• Phát hiện và chứng minh hạn chế nghiêm trọng của cơ sở dữ liệu MongoDB trong các truy vấn không-thời gian đa chiều với độ trễ lên đến 8.200 ms, đồng thời xác lập ưu thế vượt trội của cấu trúc bộ nhớ đệm đa tầng (46 ms).
• Đề xuất thành công kiến trúc hệ thống GBStore lai ghép phân tầng, kết hợp giữa Persistent Storage phân tán (Apache Cassandra) và Cache Engine đa cấp trong RAM.
• Ứng dụng xuất sắc các kỹ thuật chỉ mục tiên tiến như kd-Tree, R-Tree, GeoHash và MAAN, giải quyết triệt để mục tiêu đưa độ trễ truy xuất dữ liệu xuống dưới ngưỡng 100 ms và thông lượng ghi trên 100 ops/s.
• Tạo lập cơ sở khoa học và nền tảng hạ tầng dữ liệu vững chắc cho các hệ thống giám sát, điều hành và phân tích giao thông thông minh trong tương lai.

Lộ trình phát triển trong 6 đến 12 tháng tiếp theo sẽ tập trung vào việc triển khai thử nghiệm hệ thống trên cụm phân tán 10 nút máy chủ vật lý, đồng thời tích hợp các mô hình học máy trực tuyến để dự báo tình trạng ùn tắc giao thông. Hãy áp dụng ngay các nguyên lý kiến trúc của GBStore để nâng tầm hiệu năng hạ tầng dữ liệu lớn trong tổ chức của bạn!

Trích đoạn nội dung tài liệu

Mở đầu .1 Lý do chọn đề tài.2 Nhiệm vụ nghiên cứu của đề tài.3 Ý nghĩa khoa học của đề tài .4 Phương pháp và đối tượng nghiên cứu .5 Giới hạn và phạm vi đề tài.6 Kết quả cần đạt được. 12 2 Mô tả cụ thể bài toán: .1 Vai trò và vị trí của hệ thống trong hệ thống tổng thể.5 Hiệu suất mong muốn. 17 3 Xây dựng giải pháp.1 Giải pháp dựa trên các hệ thống database hiện có.1 Cơ sở dữ liệu quan hệ - MySql .2 Cơ sở dữ liệu theo mô hình No-SQL .3 Một số kiểm tra định lượng trên các db có sẵn .4 Đánh giá chung .2 Các kĩ thuật và công trình nghiên cứu liên quan.1 Các kĩ thuật index địa lý .2 Một số kĩ thuật cân bằng tải .3 Kĩ thuật index dữ liệu đa thuộc tính .3 Đề xuất giải pháp .1 Kiến trúc hệ thống. 49 Gom cụm dữ liệu .2 Lựa chọn Persistent Engine.

54 Mô hình dữ liệu. 55 Mô hình dữ liệu của Cassandra và dữ liệu dòng thời gian .3 Lựa chọn kĩ thuật index. 57 Tại sao chọn kd-tree thay vì r-tree? .4 Lựa chọn kĩ thuật cache. 63 4 Đo đạc và đánh giá .1 Tổ chức dữ liệu với MySQL và Mongodb .2 Đo đạc thời gian thực thi của lệnh Get(TS,TE, R(LatMin, LatMax, LonMin, LonMax)).1 Ảnh hưởng của diện tích vùng bao đến tốc độ thực thi.2 Ảnh hưởng của độ dài khung thời gian đến hiệu suất thực thi .3 Đo hiệu suất của lệnh truy vấn theo key dữ liệu, Get(TS,TE, K) .4 Đo hiệu suất của lệnh truy vấn theo key dữ liệu, có giới hạn vùng bao: Get(TS,TE, R(LatMin, LatMax, LonMin, LonMax), K).

76 8 5 Kết luận và đề xuất .1 Lý do chọn đề tài. Trong thời gian gần đây, số lượng các thiết bị có tính năng GPS được sử dụng ngày càng lớn. Dữ liệu GPS sản sinh ra từ các thiết bị này có thể được rút trích và chuyển đổi thành dữ liệu giao thông, và được sử dụng cho các giải pháp về giao thông, chẳng hạn như biểu diễn hiện trạng giao thông tại một thời điểm nào đó, dự báo giao thông, cảnh báo hiện trạng giao thông, v. Vấn đặt ra là với số lượng lớn các thiết bị tham gia vào hệ thống, một khối lượng dữ liệu sẽ được chuyển về hệ thống trong thời gian thực để lưu trữ.

Đồng thời, hệ thống cũng phải cung cấp dữ liệu một cách tức thời đến các ứng dụng liên quan. Các hệ quản trị cơ sở dữ liệu truyền thống dựa trên SQL thường chậm và không đáp ứng được yêu cầu này. Nhiệm vụ của luận văn là tìm ra một giải pháp hiệu quả cho việc lưu trữ và truy xuất lượng dữ liệu này một cách hiệu quả.2 Nhiệm vụ nghiên cứu của đề tài. Đưa ra một giải pháp có thể giải quyết bài toán truy xuất và lưu trữ dữ liệu dạng GPS trong thời gian thực.

Giải pháp có thể là một hệ thống có sẵn trên thị trường hoặc một hệ thống tự xây dựng. - Nếu là hệ thống có sẵn phải mô tả kĩ thuật lưu trữ trên hệ thống đó. Mô tả thủ tục cài đặt. Có số liệu đo đạc chứng minh hệ thống hệ thống có thể thỏa mãn yêu cầu của luận văn.

- Nếu là hệ thống tự xây dựng, phải có thiết kế kiến trúc, mô tả cách hiện thực hệ thống. Có các số liệu đo đạc cụ thể chứng minh hệ thống thỏa mãn yêu cầu lưu trữ như trong luận văn.3 Ý nghĩa khoa học của đề tài Hiện nay với sự phổ biến của các thiết bị định GPS cũng như các thiết bị cầm tay, lượng dữ liệu có gắn kèm thông tin địa lý sinh ra với tốc độ ngày càng lớn. Các giải pháp DBMS truyền thống tỏ ra không phù hợp với loại dữ liệu này. Một số giải pháp chuyên về dữ liệu địa lý tuy nhiên bỏ qua yếu tố thời gian, một số quan tâm đến yếu tố thời gian và địa lý lại tỏ ra quá tải khi dòng dữ liệu đưa vào hệ thống là trong thời gian thực.

Luận văn tìm kiếm một giải pháp giải quyết vấn đề lưu trữ dữ liệu địa lý và thời gian theo thời gian thực nhằm tạo ra nền tảng cho các hệ thống khác như: phân tích, dự báo… 1.4 Phƣơng pháp và đối tƣợng nghiên cứu - Khảo sát các hệ thống DBMS hiện có, tìm hiểu mô hình dữ liệu. Tìm cách đưa dữ liệu mẫu vào hệ thống và đưa ra các đo đạc để xem xét tính phù hợp của hệ thống. Nếu hệ thống tỏ ra quá chậm thì đưa ra biện pháp khắc phục, nếu giải pháp khắc phục quá phức tạp hoặc không hiệu quả thì chuyển qua khảo sát hệ thống khác. Các hệ thống được khảo sát chủ yếu là các hệ thống theo mô hình NoSQL.

- Trong trường hợp không tìm ra hệ thống không phù hợp, tìm hiểu các kĩ thuật index dữ liệu địa lý và thời gian dựa trên các bài báo khoa học. Xây dựng hệ thống mới dựa trên các lý thuyết đã tìm hiều được. - Đưa ra các tiêu chí và thực hiện kiểm tra hệ thống đã xây dựng được.5 Giới hạn và phạm vi đề tài - Dữ liệu để khảo sát giải pháp là dữ liệu lộ trình của xe buýt lưu thông tại Việt Nam trong vòng một tuần. - Máy tính để cài đặt là máy tính cá nhân, không phải server chuyên dụng.6 Kết quả cần đạt đƣợc - Có báo cáo khảo sát các hệ thống, giải pháp tương tự.

- Báo cáo về các lý thuyết, giải thuật căn bản của bài toán index dữ liệu theo không gian và bài toán index dữ liệu theo nhiều thuộc tính. - Có kết quả chạy thử với dữ liệu mẫu từ đó đưa ra tính khả thi của giải pháp khi triển khai. 12 2 Mô tả cụ thể bài toán: 2.1 Vai trò và vị trí của hệ thống trong hệ thống tổng thể. Từ giờ hệ thống cần xây dựng được gọi là GBStore (GPS Based data Store).

Hình dưới mô tả vị trí và vai trò cuả GBStore trong hệ thống tổng thể. Hệ thống khách 1 1 1 2 (Client) UDP server 4 5 3 GBStore Hình 1 Vai trò của hệ thống trong hệ thống tổng thể - UDP server tiếp nhận các tín hiệu GPS, hình ảnh và các loại dữ liệu khác và truyền vào hệ thống lưu trữ để xử lý sau này. - GBStore là hệ thống cần xây dựng. - Hệ thống khách(Client): Các ứng dụng dự đoán giao thông, hiển thị thông tin và các ứng dụng khác truy vấn thông tin từ hệ thống lưu trữ để phục vụ cho mục đích của chúng.

Các mũi tên mô tả các luồng dữ liệu: 13 1) Các tín hiệu GPS và các dữ liệu khác từ các phương tiện giao thông, các thiết bị có tích hợp định vị GPS hoặc các loại cảm biến khác truyền thẳng vào hệ thống tiếp nhận. 2) Hệ thống tiếp nhận này có thể forward thẳng thông tin nhận được cho các hệ thống khách để xử lý ngay trong thời gian thực. 3) Hệ thống tiếp nhận đưa các tín hiệu chứa dữ liệu nhận được vào GBStore để lưu trữ phục vụ cho tổng hợp, phân tích sau này. 4) Luồng dữ liệu đáp ứng các truy vấn từ hệ thống khách.

5) Luồng dữ liệu từ hệ thống khách đưa vào GBStore. Các dữ liệu này có thể là dữ liệu tạm sinh ra trong quá trình xử lý như tốc độ trung bình , mật độ giao thông theo từng khu vực.2 Dữ liệu Một đối tượng dữ liệu lưu trữ trong hệ thống phải có các thông tin sau đây: key: khóa do người dùng định nghĩa, time: thời gian của dữ liệu, latitude và longtitude: tọa độ địa lý của dữ liệu, dữ liệu (dạng chuỗi byte thô, hệ thống không quan tâm đến nội dung chuỗi byte này), type: kiểu dữ liệu (để phân loại dữ liệu, tương tự phân loại dữ liệu thành các bảng trong các CSDL quan hệ). Ngoài kiểu dữ liệu có gắn kèm thời gian, còn có kiểu dữ liệu không phụ thuộc thời gian. Với kiểu dữ liệu này, ta xem như một trường hợp đặc biệt của kiểu dữ liệu phụ thuộc thời gian.

Mọi đơn vị dữ liệu thuộc kiểu độc lập thời gian sẽ được gắn một trị thời gian đặc biệt nào đó để phân biệt với các đơn vị dữ liệu phụ thuộc thời gian. 14 Một đối tượng dữ liệu D (Data) được kí hiệu bằng một bộ D(T, Lat,Long, K, B) với T là thời gian, Lat và Long hợp thành tọa độ địa lý, K là khóa của dữ liệu, B là dữ liệu thô được gắn với đối tượng này. Với dữ liệu không phụ thuộc thời gian, T nhận giá trị đặc biệt kí hiệu là t0. Do thời gian thực hiện luận văn có giới hạn, do đó, để đơn giản bài toán, giả thiết mọi đơn vị dữ liệu đưa vào hệ thống đủ nhỏ và mọi đơn vị dữ liệu đều có kích thước bằng nhau để một thao tác đưa dữ liệu vào hệ thống có thể thực hiện trong một lệnh, không phải chia nhỏ dữ liệu ra nhiều phần.3 Lƣu trữ Hệ thống phải có khả năng đáp ứng dòng dữ liệu đầu vào liên tục, do đó yêu cầu lưu trữ là phải đảm bảo đáp ứng tốc độ dòng dữ liệu đầu vào lớn, tức là thời gian lưu trữ một đơn vị dữ liệu phải đủ nhỏ, nếu tốt hơn nên có khả năng lưu trữ đồng thời nhiều đơn vị dữ liệu cùng lúc trong trường hợp hệ thống có nhiều luồng dữ liệu vào.

Hệ thống phải có khả năng hoạt động tốt với dòng dữ liệu đầu vào có mật độ phân bố không đều cả về không gian lẫn thời gian (dữ liệu mẫu có phân bố không đều theo cả không gian và thời gian). Dữ liệu lưu trong hệ thống được đưa vào liên lục do đó hệ thống phải có khả năng sao lưu các dữ liệu cũ để tránh quá tải. Một thao tác đưa dữ liệu D vào hệ thống kí hiệu là Put(D). Tạm thời luận văn không xét đến thao tác xóa dữ liệu khỏi hệ thống.4 Truy vấn Hệ thống phải có thời gian đáp ứng (latency) nhanh với các yêu cầu truy xuất dữ liệu (thời gian từ lúc nhận yêu cầu đến lúc trả về kết quả).

Latency này cũng không được tăng khi có nhiều dữ liệu trong hệ thống. 15 Các điều kiện trong truy xuất: - Điều kiện về thời gian: dữ liệu trả về trong trong khoảng thời gian [t1, t2]. - Điều kiện về khóa: dữ liệu trả về có khóa bằng một số xác định. - Điều kiện về địa lý: Có 2 kiểu điều kiện địa lý: o Được bao bởi một hình chữ nhật xác định.

o Được bao bởi một hình tròn có bán kính và tâm xác định.