Qua bài viết đầu tiên về thiết kế hệ thống TinyURL, ta đã có cái nhìn tổng quan về các component trong hệ thống.

Đi vào chi tiết, ta sẽ phân tích sâu hơn về các vấn đề cần giải quyết thực tế. Các vấn đề kĩ thuật này giúp hệ thống hoạt động trơn tru, đáp ứng yêu cầu cao về performance

1. Sử dụng hash function?

1.1 What method do we use to generate the shortened URL?

Về URL, nội dung hash có thể sử dụng MD5 hoặc SHA1

MD5("https://parade.com/689217/km...") -> 2D9399993E3D6F54AFB13F8B114D674D

Hash với MD5 sẽ có base 36, có khả năng sẽ xảy ra đụng độ (collision). Để xử lí đụng độ khi hai chuỗi có cùng chung một nội dung hash, ta cần tìm một cách khác để hash nội dung từ original URL

1.2 The same URL added by different users will return the same TinyURL

• Thứ nhất, về lợi, khi sử dụng chung TinyURL vấn đề lưu trữ Storage sẽ giảm xuống. Lưu trữ ít hơn cho các URL giống nhau.
• Thứ hai, về hại, những URL thường được hay sử dụng (common) có thể sẽ có lượng traffic rất cao. Tuy là dữ liệu phân tán ở các database nhỏ, nhưng nếu chỉ truy xuất ở một phần database nhiều lần thì peformance sẽ giảm xuống.

Vấn đề thứ hai, nhiều user có thể tạo chung một URL. Các URL giống nhau này sẽ được trả về cùng một TinyURL sau khi đã rút gọn. Việc này phát sinh cả lợi lẫn hại

Về vấn đề peformance có thể sử dụng cached cho load balancing. Tuy nhiên nếu user tối ưu hóa cao, sẽ không thể thông báo tới từng user về link của họ. Link còn sống không, link truy cập bao nhiêu lần?.

Vì là common nên phải take care điều này.

1.3 Hash Table is overkill for our use case

Hash function rất tốt cho các trường hợp cần look với key hoặc value. Sử dụng hash table sẽ là tối ưu cho việc lưu trữ các nội dung string sau khi hash

1.4 Tạo chuỗi random (Generate random string)

Tạo chuỗi string cho original URL không phải là ý tưởng tồi. Cách làm này có nhiều lợi ích

• Chuỗi string random rất khó trùng nhau (xác xuất về đụng độ collision khá thấp)
• Có nhiều cách để tạo chuỗi string, có thể tạo UUID generators.

Tuy nhiên, khi tạo chuỗi random string, cần chú ý độ dài của string cần đáp ứng yêu cầu của TinyURL.

1.5 Sử dụng counter (using counter)

Counter cũng là một cách hay để hạn chế đụng độ collision khi generate chuỗi string. Ta có thể tạo key increment cho mỗi lần tạo ra short URL. Tuy nhiên, có khả năng số lượng từ id sẽ rất lớn.

Cũng có một cách khác là tạo key cho table mới key là timestamp. Thời gian tạo Short URL sẽ rất ngắn. Không quá dài.

Trường hợp String là base 36. Độ dài của chuỗi string cần thiết là bao nhiêu?

With 6: 36^6 = ~2 Billion URLs

With 7: 36^7 = ~78 Billion URLs 

With 8: 36^8 = ~2.8 Trillion URLs

2. Một số lưu ý

Để tăng peformance cho toàn hệ thống, trước khi call API tạo TinyURL ta có thể kiểm tra URL đó đã tồn tại hay chưa.

Các thức kiểm tra không nhất thiết phải send request tới Database, có thể lưu file cục bộ ở App Server. Mỗi lần thêm url mới, ta thêm vào file, kiểm tra URL trên file luôn dễ dàng và có tốc độ nhanh hơn.

Về location, có thể tạo các bản sao của Database cho từng khu vực vật lý, kết hợp với CDN và Cache tăng tốc độ cho toàn hệ thống trong trường hợp cần cache.

Về vấn đề redirect, lúc paste vào site ta cần xem xét về 302 Temporary Redirect Status. 302 thường không được add vào browser history. Nghĩa là sau khi đã enter để lấy original URL, ta không thể back lại TinyURL trước đó.

Có thể sử dụng redirect tag HTML trong các trường hợp cần back lại trên browser history

3. Database nào nên sử dụng cho TinyURL System

Trường hợp sử dụng NoSQL, cần cân nhắc về Consistency (tính nhất quán – C trong CAP Theorem), Row locking (khóa không cho phép truy cập đồng thời trên row)

Với Cassandra, dữ liệu có thể scaling rất nhanh, tuy nhiên cần lưu ý về tính nhất quán. Tất nhiên ta cũng có thể sử dụng Structure Database như MySQL, Postgresql. Tuy nhiên cần lưu ý về khả năng scaling trong các trường hợp handle một lượng lớn request

Sharding với NoSQL Database thường dễ dàng hơn

4. Lưu ý nhỏ

Reading a URL – When a user tries to access the TinyURL, the app server tries to read it from cache first. If not available, it reads it from the database and returns a 302 response with the actual URL.

Đọc URL – Khi user paste TinyURL vào browser, app server sẽ đọc từ cache trước. Nếu trong cache không tồn tại, đọc từ Database và trả về response 302 với actual URL.

Trường hợp thêm mới URL

Adding a URL – The load balancer sends the request to an app server. The app server reads a new pre-generated TinyURL from a local file (which is buffered in the RAM for quick access). It sends a write request to the distributed database. When the database returns, it sends back a success response with the new TinyURL.

Loadbalancer sẽ gửi request tới server. Server đọc file TinyURL từ Ram trước, local file (giúp tăng peformance. Gửi request tới hệ cơ sở dữ liệu phân tán. Thành xông, gửi response thành công với TinyURL ngắn cho user.

5. Tham khảo

• Distributed Systems – The Complete Guide
• What is the probability of collision with a 6 digit random alphanumeric code?

Done – Thank for reading everybody – Have a nice weekend!