Chắc hẳn ai trong số chúng ta cũng đã từng dùng 1 số dịch vụ thiết kế URL Shortening (rút gọn link) như Bit.ly hay TinyURL.
Đang xem: Hệ thống rút gọn link
Đối với 1 software engineer thì việc dùng là 1 chuyện, nhưng làm thế nào để thiết kế được 1 hệ thống chịu tải hàng tỉ click mỗi tháng chắc hẳn cũng nhiều người quan tâm.
Loại Database nào nên sử dụng?
Thuật toán và thiết kế hệ thống cơ bản
Vấn đề cần giải quyết ở đây là làm thế nào có thể tạo ra được 1 link rút gọn và nó duy nhất từ 1 link gốc.
Trong phần đầu tiên mình đã lấy ra 1 ví dụ về link rút gọn: http://bit.ly/2VXBAw4
Thì phần này chúng ta sẽ đi thiết kể để tạo ra được phần rút gọn, chính là 2VXBAw4.
Encoding URL
Chúng ta có thể sử dụng 1 số hàm băm (như MD5 hay SHA256) để băm giá trị đầu vào URL. Sau đó sẽ dùng 1 số hàm mã hoá để hiển thị. Ví dụ như base36 (
1 câu hỏi được đặt ra ở đây là chúng ta sẽ dùng độ dài key là bao nhiêu? 6,8 hay là 10?
Nếu dùng base64 cho 6 kí tự thì tổng chúng ta có 64^6 = 68.7B URLNếu dùng base64 cho 8 kí tự thì tổng chúng ta có 64^8 = 281 nghìn tỉ URL
Do hệ thống của chúng ta có 500M URL được tạo ra mỗi tháng, hệ thống dùng trong 5 năm sẽ có tổng:
500M * 12 months * 5 = 30B URLs / 5 years.
Xem thêm: phần mềm rosetta stone english
Do đó với 68.7B URL (với 6 kí tự) là có thể dùng được trong 5 năm rồi.
Nếu chúng ta dùng thuật toán MD5 như hàm băm, thì khi đó nó sẽ tạo ra giá trị hash có chứa 128 bit. Sau đó base64 để encode giá trị băm, nó sẽ tạo ra ít nhất 21 kí tự (vì mỗi kí tự base64 sẽ encode 6 bits giá trị hash).
Trong khi đó không gian khoá của chúng ta chỉ cần 6 kí tự thôi. Vậy làm thế nào có thể chọn ra khoá? Chúng ta có thể chọn ra 6 kí tự đầu tiên cũng được. Mặc dù có trường hợp nó trùng nhau. nhưng mà xác suất chỉ tầm 1/(64^6). Nó rất là nhỏ. Nên có thể chấp nhận được.
Nếu an toàn thì mỗi lần generate ra thì sẽ check trong DB xem có hay chưa? Nếu chưa có thì ok, còn nếu có rồi thì sẽ thêm xâu random nào vào trước URL và lại lặp lại cho đến khi sinh ra unique thì thôi.
※ Cách lấy 6 kí tự đầu tiên này chỉ là 1 giải pháp thôi nhé. Các bạn có thể tự cài đặt cho mình thuật toán khác, miễn nó sinh ra được 6 kí tự unique là được.
Xem thêm: Web Tải Phim Miễn Phí Tốt Nhất 2021, Top 5 Website download Phim Miễn Phí
Đây là 1 ví dụ về trường hợp lấy 6 kí tự đầu tiên:
const crypto = require(“crypto”);module.exports = { generateShortURL: (longURL, startIndex, endIndex) => { const hash = crypto.createHash(“md5”).update(longURL).digest(“base64”); return hash.substring(startIndex, endIndex + 1); },};Giải pháp của chúng ta đang gặp vấn đề gì?
Nhiều người dùng có thể cùng dùng chung 1 link gốc, do đó link rút gọn sẽ bị trùng lặp. Và điều này không thể chấp nhận được.Điều gì sẽ xảy ra nếu như 1 phần nào đó trong URL bị mã hoá. Ví dụ như http://example.com/index.php?id=design và http://example.com/index.php%3Fid%3Ddesign là 2 URL hoàn toàn giống nhau nhưng mà 1 phần URL đã bị mã hoá.
Giải quyết vấn đề trên như thế nào?