這是一個(gè)系統(tǒng)設(shè)計(jì)問題，要求從頭開始設(shè)計(jì)一個(gè)類似于TinyURL或Bitly的URL短鏈接工具。我們將涵蓋從設(shè)計(jì)需求、架構(gòu)和組件設(shè)計(jì)到高性能擴(kuò)展和安全最佳實(shí)踐的各個(gè)方面。

定義范圍：功能性和非功能性需求

首先，我們需要定義該系統(tǒng)的功能性和非功能性需求。

我們有兩個(gè)功能性需求：

• 給定一個(gè)長(zhǎng)URL時(shí)，我們必須創(chuàng)建一個(gè)短URL
• 給定一個(gè)短URL時(shí)，我們必須將用戶重定向到長(zhǎng)URL。

該服務(wù)的非功能性需求是優(yōu)先考慮低延遲（快速響應(yīng)）和高可用性（始終在線）。

明確業(yè)務(wù)問題

以下是一些我們可能需要明確的問題，以確保我們對(duì)系統(tǒng)的規(guī)模有一致的理解：

• 使用情況：估計(jì)我們每秒需要?jiǎng)?chuàng)建多少個(gè)URL（假設(shè)是1000個(gè)）。
• 字符：我們可以使用數(shù)字和字母（字母數(shù)字）還是其他符號(hào)？（我們假設(shè)使用字母數(shù)字字符）。
• 唯一性：每次生成的短URL是否唯一，即使多個(gè)用戶提交相同的長(zhǎng)URL？（在這個(gè)設(shè)計(jì)中，我們假設(shè)是唯一的）。

估算：數(shù)據(jù)計(jì)算

有了這些信息，我們需要計(jì)算縮短后的URL應(yīng)該有多長(zhǎng)。當(dāng)然，我們希望它盡可能短，但我們需要考慮到每年的URL創(chuàng)建數(shù)量。

首先，讓我們估算一個(gè)顯著時(shí)期內(nèi)所需的唯一URL數(shù)量。常見的方法是計(jì)劃至少幾年的運(yùn)營。為了簡(jiǎn)化計(jì)算，我們假設(shè)計(jì)算10年的數(shù)據(jù)。

• 一年中的秒數(shù)：每分鐘60秒 × 每小時(shí)60分鐘 × 每天24小時(shí) × 每年365天 = 31.536百萬秒
• 10年中的總秒數(shù)：31.536百萬 × 10 = 315.36百萬秒
• 10年中的總URL數(shù)：1000 × 315.36百萬 = 315.36十億個(gè)唯一URL

這意味著我們的數(shù)據(jù)庫每秒需要處理1000次寫入，每年將生成1000 × 60 × 60 × 24 × 365 = 31.5B個(gè)URL。如果我們假設(shè)讀取次數(shù)通常是寫入次數(shù)的10倍，這意味著我們每秒將獲得超過10 × 1000 = 10000次讀取。

現(xiàn)在，我們需要弄清楚多少個(gè)字符能為我們未來十年的量提供足夠的唯一短URL?？紤]到字符集大小為62，可以按如下計(jì)算URL標(biāo)識(shí)符的長(zhǎng)度：

• 621 = 62個(gè)唯一URL（1個(gè)字符）
• 622 = 3844個(gè)唯一URL（2個(gè)字符）?…等等。

繼續(xù)這種計(jì)算，我們看到62?（大約3.5萬億）是第一個(gè)大于我們預(yù)計(jì)的3150億URL所需的值。

因此，為了支持我們未來十年的預(yù)期增長(zhǎng)，我們的縮短URL需要至少7個(gè)字符。

高層次架構(gòu)

我們的系統(tǒng)將有以下關(guān)鍵組件：

• 用戶：用戶發(fā)送他們的長(zhǎng)URL以生成短URL，或發(fā)送短URL，我們需要將他們重定向到長(zhǎng)URL。
• 負(fù)載均衡器：所有這些請(qǐng)求通過負(fù)載均衡器，它將流量分配到多個(gè)Web服務(wù)器實(shí)例，以確保高可用性和負(fù)載均衡。
• Web服務(wù)器：這些服務(wù)器副本負(fù)責(zé)處理傳入的HTTP請(qǐng)求。
• URL短鏈接服務(wù)：我們還需要一個(gè)包含生成短URL、存儲(chǔ)URL映射和檢索原始URL以進(jìn)行重定向的核心邏輯的URL短鏈接服務(wù)。
• 數(shù)據(jù)庫：存儲(chǔ)短URL及其長(zhǎng)URL之間的連接。在設(shè)計(jì)數(shù)據(jù)庫之前，我們需要考慮縮短URL的潛在存儲(chǔ)需求。

每個(gè)URL將包括唯一標(biāo)識(shí)符（大約7個(gè)字節(jié)）、長(zhǎng)URL（最多100個(gè)字節(jié)）和用戶元數(shù)據(jù)（估計(jì)為500個(gè)字節(jié)）。這意味著我們每個(gè)URL需要最多1000個(gè)字節(jié)。根據(jù)我們的預(yù)期量，這相當(dāng)于大約315TB的數(shù)據(jù)。

在繼續(xù)之前，讓我們先考慮一下單個(gè)Web服務(wù)器的API設(shè)計(jì)。

API設(shè)計(jì)

讓我們定義服務(wù)的基本API操作。根據(jù)我們的功能需求，我們將使用REST API，并需要兩個(gè)端點(diǎn)。

(1) 創(chuàng)建短URL (POST **/urls**)

• 輸入：包含長(zhǎng)URL的JSON負(fù)載 {“l(fā)ongUrl”: “[https://example.com/very-long-url](https://example.com/very-long-url)"}
• 輸出：帶有短URL的JSON負(fù)載 {“shortUrl”: “[https://tiny.url/3ad32p9](https://tiny.url/3ad32p9)"} 和 201 Created 狀態(tài)碼。

如果請(qǐng)求無效或格式錯(cuò)誤，我們將返回 400 Bad Request 響應(yīng)，如果請(qǐng)求的URL已經(jīng)存在于系統(tǒng)中，我們將返回 409 Conflict。

(2) 重定向到長(zhǎng)URL (GET **/urls/{shortUrlId}**)

• 輸入：shortUrlId 路徑參數(shù)
• 輸出：帶有 301 Moved Permanently 的響應(yīng)，響應(yīng)體中包含新創(chuàng)建的短URL作為JSON { "shortUrl": "https://tiny.url/3ad32p9" }

301狀態(tài)碼指示瀏覽器緩存信息，這意味著下次用戶輸入短URL時(shí)，瀏覽器會(huì)自動(dòng)重定向到長(zhǎng)URL而不需要再次訪問服務(wù)器。

然而，如果你想跟蹤每個(gè)請(qǐng)求的分析并確保它通過你的系統(tǒng)，可以使用302狀態(tài)碼。

數(shù)據(jù)庫：存儲(chǔ)短URL

下一部分是數(shù)據(jù)庫層。該層存儲(chǔ)短URL和長(zhǎng)URL之間的映射。它應(yīng)該針對(duì)快速讀寫操作進(jìn)行優(yōu)化。

模式可以很簡(jiǎn)單：短URL id的主鍵，以及長(zhǎng)URL和可能的創(chuàng)建元數(shù)據(jù)字段。

{
  "shortUrlId": "3ad32p9",
  "longUrl": "https://example.com/very-long-url",
  "creationDate": "2024-03-08T12:00:00Z",
  "userId": "user123",
  "clicks": 1023,
  "metadata": {
    "title": "Example Web Page",
    "tags": ["example", "web", "url shortener"],
    "expireDate": "2025-03-08T12:00:00Z"
  },
  "isActive": true
}

在這里，我們主要需要考慮數(shù)據(jù)庫的讀取次數(shù)。如果我們通常每秒有1000次寫入，那么我們可以假設(shè)至少每秒有10到100000次讀取。

在這種情況下，我們需要使用支持快速讀取和寫入的高性能數(shù)據(jù)庫。這意味著我們需要使用NoSQL數(shù)據(jù)庫（如MongoDB這樣的文檔存儲(chǔ)、Cassandra這樣的寬列存儲(chǔ)或DynamoDB這樣的鍵值存儲(chǔ)），因?yàn)樗鼈儗ｉT設(shè)計(jì)用于處理大量的擴(kuò)展。

它不會(huì)是ACID兼容的，但我們不關(guān)心這一點(diǎn)，因?yàn)槲覀儾粫?huì)進(jìn)行大量的JOIN或復(fù)雜的查詢，我們不需要那些ACID規(guī)則和原子事務(wù)。

URL短鏈接服務(wù)

該系統(tǒng)的核心部分之一是URL短鏈接服務(wù)。該服務(wù)生成短URL，且不會(huì)在不同的長(zhǎng)URL指向相同的短URL時(shí)引入沖突。

有多種方法可以實(shí)現(xiàn)這個(gè)服務(wù)；以下是其中一些：

• 哈希：生成長(zhǎng)URL的哈希，并使用其中的一部分作為標(biāo)識(shí)符。然而，哈希可能導(dǎo)致沖突。
• 自增ID：使用數(shù)據(jù)庫的自增ID并將其編碼為一個(gè)短字符串。這確保了唯一性，但可能是可預(yù)測(cè)的。
• 自定義算法：設(shè)計(jì)一個(gè)自定義算法，用字符的混合來生成唯一ID，以確保唯一性和不可預(yù)測(cè)性。

例如，為了避免沖突，有一個(gè)非常簡(jiǎn)單的方法——我們可以生成

所有可能的7字符鍵，并將它們存儲(chǔ)在數(shù)據(jù)庫中作為鍵，其中鍵是生成的URL，值是布爾值；如果為true，則表示該URL已被使用，如果為false，則可以使用該URL創(chuàng)建新映射。

因此，每當(dāng)用戶請(qǐng)求生成一個(gè)鍵時(shí)，我們可以從這個(gè)數(shù)據(jù)庫中找到一個(gè)當(dāng)前未使用的URL，并將其映射到請(qǐng)求體中的長(zhǎng)URL。

你認(rèn)為我們?cè)谶@種情況下會(huì)使用SQL還是NoSQL數(shù)據(jù)庫？考慮一種場(chǎng)景：兩個(gè)用戶請(qǐng)求縮短他們的長(zhǎng)URL，并且他們都被映射到這個(gè)數(shù)據(jù)庫中的同一個(gè)鍵。

在這種情況下，URL將被映射到其中一個(gè)請(qǐng)求，另一個(gè)將被破壞。所以，我們將使用SQL，因?yàn)樗哂蠥CID屬性。我們可以為這里的每個(gè)會(huì)話創(chuàng)建一個(gè)事務(wù)，以在隔離中執(zhí)行這些步驟，在這種情況下我們不會(huì)有這種問題。

高可用性和低延遲

我們的當(dāng)前系統(tǒng)顯然無法處理每秒1000個(gè)URL的流量。

緩存

為了使其更具可擴(kuò)展性，我們首先需要一個(gè)緩存層（例如Redis）來緩存流行的URL，以便在內(nèi)存中快速檢索。

鑒于某些URL可能比其他URL訪問頻率更高，我們需要一種優(yōu)先考慮頻繁訪問項(xiàng)的逐出策略。兩種適合此場(chǎng)景的緩存逐出策略是：

• LRU逐出策略：首先刪除最近最少訪問的項(xiàng)目。對(duì)于URL短鏈接服務(wù)，這種策略非常有效，因?yàn)樗_保緩存保持最新和最頻繁訪問的URL，這可以顯著減少流行鏈接的訪問時(shí)間。
• 或者基于TTL的逐出策略：為每個(gè)緩存條目分配一個(gè)固定的生存時(shí)間（TTL）。一旦條目的TTL過期，它將從緩存中移除。對(duì)于只在短時(shí)間內(nèi)流行的URL，TTL策略對(duì)URL短鏈接服務(wù)很有用。

TTL還可以幫助我們自動(dòng)刷新緩存內(nèi)容，并可以與其他策略（如LRU）結(jié)合使用，以更有效地管理緩存。

數(shù)據(jù)庫擴(kuò)展：結(jié)合復(fù)制和分片

我們需要實(shí)現(xiàn)復(fù)制和分片策略，以確保數(shù)據(jù)庫支持高可用性、容錯(cuò)性和可擴(kuò)展性。

考慮到我們的7字符集有3.5T個(gè)唯一URL，我們可以使用基于鍵的分片將URL記錄均勻分布在多個(gè)分片上。

假設(shè)我們將其分布在3個(gè)分片上，每個(gè)分片將存儲(chǔ)大約1.16T個(gè)URL。這確保了隨著URL數(shù)量的增長(zhǎng)系統(tǒng)的可擴(kuò)展性。

我們還可以在每個(gè)分片內(nèi)實(shí)現(xiàn)主從復(fù)制，以確保高可用性和容錯(cuò)性。這種設(shè)置允許在節(jié)點(diǎn)故障時(shí)快速故障轉(zhuǎn)移和恢復(fù)。

另外，如果服務(wù)面向全球用戶，我們可以考慮地理分片和復(fù)制，以最小化延遲并改善不同地區(qū)的用戶體驗(yàn)。

這種組合允許服務(wù)處理大量URL縮短和重定向，并且?guī)缀鯖]有停機(jī)時(shí)間和快速響應(yīng)時(shí)間。

安全考慮

以下是我們服務(wù)的一些安全考慮：

• 輸入驗(yàn)證：我們必須對(duì)用戶提交的每個(gè)URL進(jìn)行消毒。我們必須檢查有效的協(xié)議（HTTP、HTTPS等）并確保URL格式正確。這有助于防止注入攻擊。
• 速率限制：我們可以通過限制單個(gè)源的請(qǐng)求次數(shù)來保護(hù)我們的服務(wù)免受DDoS攻擊?？梢钥紤]使用令牌桶算法。
• 監(jiān)控和日志記錄：需要一個(gè)強(qiáng)大的日志記錄系統(tǒng)（如ELK堆棧）。它允許我們分析日志以查找瓶頸和可疑活動(dòng)，并確保整體系統(tǒng)健康。
• 混淆：我們不希望輕易預(yù)測(cè)的短URL。為了阻止攻擊者猜測(cè)有效鏈接，我們可以在生成算法中添加隨機(jī)性。
• 鏈接到期：可選地，我們可以考慮允許用戶為他們的短URL設(shè)置到期日期。這可以限制潛在惡意鏈接的生命周期。