56算法實(shí)戰(zhàn)五如何用學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)短網(wǎng)址系統(tǒng)

56|算法實(shí)戰(zhàn)（五）：如何用學(xué)過(guò)的數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)一個(gè)短網(wǎng)址2019-02-0415:16大小ub從功能上講，短網(wǎng)址服務(wù)其實(shí)非常簡(jiǎn)單，就是把一個(gè)長(zhǎng)的網(wǎng)址轉(zhuǎn)化成一個(gè)短的網(wǎng)址。作為一名軟件工程師，你是否思考過(guò)，這樣一個(gè)簡(jiǎn)單的功能，是如何實(shí)現(xiàn)的呢？底層都依賴了哪些數(shù)據(jù)結(jié)構(gòu)和算法呢？剛剛我們講了，短網(wǎng)址服務(wù)的一個(gè)核心功能，就是把原始的長(zhǎng)網(wǎng)址轉(zhuǎn)化成短網(wǎng)址。除了這個(gè)功能之外，短網(wǎng)址服務(wù)還有另外一個(gè)必不可少的功能。那就是，當(dāng)用戶點(diǎn)擊短網(wǎng)址的時(shí)候，短網(wǎng)址服務(wù)會(huì)將瀏覽器重定向?yàn)樵季W(wǎng)址。這個(gè)過(guò)程是如何實(shí)現(xiàn)的呢？從圖中我們可以看出，瀏覽器會(huì)先訪問(wèn)短網(wǎng)址服務(wù)，通過(guò)短網(wǎng)址獲取到原始網(wǎng)址，再通過(guò)原始網(wǎng)址訪問(wèn)到頁(yè)面。不過(guò)這部分功能并不是我們今天要講的重點(diǎn)。我們重點(diǎn)來(lái)看，如何將長(zhǎng)網(wǎng)址轉(zhuǎn)化成短網(wǎng)址？前面我們已經(jīng)提過(guò)一些哈希算法了，比如M5SHA些復(fù)雜的哈希算法。在生成短網(wǎng)址這個(gè)問(wèn)題上，畢竟，我們不需要考慮反向解密的難度，所以我們只需要關(guān)心哈希算法的計(jì)算速度和沖突概率。MurmurHash算法。盡管這個(gè)哈希算法在2008到Redis、MemCache、Cassandra、HBase、Lucene等眾多著名的軟件中。MurmurHash算法提供了兩種長(zhǎng)度的哈希值，一種是32bits，一種是128bits。為了讓最終生成的短網(wǎng)址盡可能短，我們可以選擇32bits的哈希值。對(duì)于開頭那個(gè)GitHub網(wǎng)址，經(jīng)過(guò)MurmurHash計(jì)算后，得到的哈希值就是181338494。我們?cè)倨瓷隙叹W(wǎng)址服務(wù)的域名，就變成了最終的短網(wǎng)址/181338494（其中，是短網(wǎng)址服務(wù)的域名）不過(guò)，你可能已經(jīng)看出來(lái)了，通過(guò)MurHash我們可以將10進(jìn)制的哈希值，轉(zhuǎn)化成更高進(jìn)制的哈希值，這樣哈希值就變短了。我們知道，16進(jìn)制中，我們用A～E，來(lái)表示10～15。在網(wǎng)址URL中，常用的合法字符有0～9、a～z、A～Z這樣62個(gè)字符。為了讓哈希值表示起來(lái)盡可能短，我們可以將10進(jìn)制的哈希值轉(zhuǎn)化成62進(jìn)制。具體的計(jì)算過(guò)程，我寫在這里了。最終用62進(jìn)制表示的短網(wǎng)址就不過(guò)，我們前面講過(guò)，哈希算法無(wú)法避免的一個(gè)問(wèn)題，就是哈希沖突。盡管MurmurHash算法，沖突的概率非常低。但是，一旦沖突，就會(huì)導(dǎo)致兩個(gè)原始網(wǎng)址被轉(zhuǎn)化成同一個(gè)短網(wǎng)LRedi。我們SLL數(shù)據(jù)庫(kù)MurmurHash址。然后，我們拿這個(gè)新生成的短網(wǎng)址，在MySQL數(shù)據(jù)庫(kù)中查找。如果沒有找到相同的短網(wǎng)址，這也就表明，這個(gè)新生成的短網(wǎng)址沒有沖突。于是我們就將這個(gè)短網(wǎng)址返回給用戶（請(qǐng)求生成短網(wǎng)址的用戶），關(guān)系，存儲(chǔ)到SL如果我們?cè)跀?shù)據(jù)庫(kù)中，找到了相同的短網(wǎng)址，那也并不一定說(shuō)明就沖突了。我們從數(shù)據(jù)庫(kù)我們可以給原始網(wǎng)址拼接一串特殊字符，比如“[LICATED]”，然后跟再重新計(jì)算哈希OHMYGOD]”，再計(jì)算哈希值。然后把計(jì)算得到的哈希值，跟原始網(wǎng)址拼接了特殊字符串之后的文本，一并存儲(chǔ)在L數(shù)據(jù)庫(kù)當(dāng)用戶訪問(wèn)短網(wǎng)址的時(shí)候，短網(wǎng)址服務(wù)先通過(guò)短網(wǎng)址，在數(shù)據(jù)庫(kù)中查找到對(duì)應(yīng)的原始網(wǎng)址。如果原始網(wǎng)址有拼接特殊字符（這個(gè)很容易通過(guò)字符串匹配算法找到）為了判斷生成的短網(wǎng)址是否沖突，我們需要拿生成的短網(wǎng)址，在數(shù)據(jù)庫(kù)中查找。如果數(shù)據(jù)庫(kù)中存儲(chǔ)的數(shù)據(jù)非常多，那查找起來(lái)就會(huì)非常慢，勢(shì)必影響短網(wǎng)址服務(wù)的性能。那有沒有什么優(yōu)化的手段呢？還記得我們之前講的LB+通過(guò)短網(wǎng)址查詢?cè)季W(wǎng)址的速度就提高了很多。實(shí)際上，在真實(shí)的軟件開發(fā)中，我們還可以通過(guò)一個(gè)小技巧，來(lái)進(jìn)一步提高速度。在短網(wǎng)址生成的過(guò)程中，我們會(huì)跟數(shù)據(jù)庫(kù)打兩次交道，也就是會(huì)執(zhí)行兩條SQL語(yǔ)句。第一個(gè)SQL語(yǔ)句是通過(guò)短網(wǎng)址查詢短網(wǎng)址與原始網(wǎng)址的對(duì)應(yīng)關(guān)系，第二個(gè)SQL語(yǔ)句是將新生成的短我們知道，一般情況下，數(shù)據(jù)庫(kù)和應(yīng)用服務(wù)（只做計(jì)算不存儲(chǔ)數(shù)據(jù)的業(yè)務(wù)邏輯部分）在兩個(gè)獨(dú)立的服務(wù)器或者虛擬服務(wù)器上。那兩條LOL語(yǔ)句的執(zhí)行，才是整個(gè)短網(wǎng)址服務(wù)的性能瓶頸所在。所以，為了提高性能，我們需要盡量減少LL我們可以給數(shù)據(jù)庫(kù)中的短網(wǎng)址字段，添加一個(gè)唯一索引（）。當(dāng)有新的原始網(wǎng)址需要生成短網(wǎng)址的時(shí)候，我們并不會(huì)先拿生成的短網(wǎng)址，在數(shù)據(jù)庫(kù)中查找判重，而是直接將生成的短網(wǎng)址與對(duì)應(yīng)的原始網(wǎng)址，嘗試存儲(chǔ)到數(shù)據(jù)庫(kù)中。如果數(shù)據(jù)庫(kù)能夠?qū)?shù)據(jù)正常寫入，那說(shuō)明并沒有違反唯一索引，也就是說(shuō)，這個(gè)新生成的短網(wǎng)址并沒有沖突。L語(yǔ)句執(zhí)行的次數(shù)不減反增。但是，在大部分情況下，我們把新生成的短網(wǎng)L語(yǔ)句就可以了。所以，從整體上看，總的L實(shí)際上，我們還有另外一個(gè)優(yōu)化SQL種存儲(chǔ)結(jié)構(gòu)，長(zhǎng)度是10億的布隆過(guò)濾器，也只需要125MB左右的內(nèi)存空間。當(dāng)有新的短網(wǎng)址生成的時(shí)候，我們先拿這個(gè)新生成的短網(wǎng)址，在布隆過(guò)濾器中查找。如果查找的結(jié)果是不存在，那就說(shuō)明這個(gè)新生成的短網(wǎng)址并沒有沖突。這個(gè)時(shí)候，我們只需要再執(zhí)行寫入短網(wǎng)址和對(duì)應(yīng)原始網(wǎng)頁(yè)的L語(yǔ)句就可以了。通過(guò)先查詢布隆過(guò)濾器，總的L語(yǔ)句的執(zhí)行次數(shù)減少了。到此，利用哈希算法來(lái)生成短網(wǎng)址的思路，我就講完了。實(shí)際上，這種解決思路已經(jīng)完全滿足需求了，我們已經(jīng)可以直接用到真實(shí)的軟件開發(fā)中。不過(guò)，我們還有另外一種短網(wǎng)址的生成算法，那就是利用自增的ID何工作的？對(duì)于哈希算法生成短網(wǎng)址來(lái)說(shuō)，它又有什么優(yōu)勢(shì)和劣勢(shì)？ID我們可以維護(hù)一個(gè)ID自增生成器。它可以生成23…這樣自增的整數(shù)IDD生成器中取一個(gè)號(hào)碼，然后將2進(jìn)制表示法，拼接到短網(wǎng)址服務(wù)的域名（比如http://t）后面，就形成了最終的短網(wǎng)址。最后，我們還是會(huì)把生成的短網(wǎng)址和對(duì)應(yīng)的原始網(wǎng)址存儲(chǔ)到數(shù)據(jù)庫(kù)中。第一種處理思路是不做處理第二種處理思路是借助哈希算法生成短網(wǎng)址的處理思想，不過(guò)，這種處理思路有個(gè)問(wèn)題，我們需要給數(shù)據(jù)庫(kù)中的短網(wǎng)址和原始網(wǎng)址這兩個(gè)字段，都添加索引。短網(wǎng)址上加索引是為了提高用戶查詢短網(wǎng)址對(duì)應(yīng)的原始網(wǎng)頁(yè)的速度，原始網(wǎng)址上加原始網(wǎng)址對(duì)應(yīng)相同短網(wǎng)址”這樣一個(gè)需求，但是是有代價(jià)的：一方面兩個(gè)索引會(huì)占用更多的存儲(chǔ)空間，另一方面索引還會(huì)導(dǎo)致插入、刪除等操作性能的下降。IDIDD）。如何提高生成器的性能呢？關(guān)于這個(gè)問(wèn)題，實(shí)際上，有很多解決思路。我這里給出兩種思路。第一種思路是借助第54節(jié)中講的方法。我們可以給ID生成器裝多個(gè)前置發(fā)號(hào)器。我們批量地給每個(gè)前置發(fā)號(hào)器發(fā)送ID號(hào)碼。當(dāng)我們接受到短網(wǎng)址生成請(qǐng)求的時(shí)候，就選擇一個(gè)前第二種思路跟第一種差不多。不過(guò)，我們不再使用一個(gè)ID生成器和多個(gè)前置發(fā)號(hào)器這樣的架構(gòu)，而是，直接實(shí)現(xiàn)多個(gè)ID生成器同時(shí)服務(wù)。為了保證每個(gè)ID生成器生成的ID不重復(fù)。我們要求每個(gè)ID生成器按照一定的規(guī)則，來(lái)生成ID號(hào)碼。比如，第一個(gè)ID生成器只能生成尾號(hào)為0的，第二個(gè)只能生成尾號(hào)為1的，以此類推。這樣通過(guò)多個(gè)ID生成器同時(shí)工作，也提高了ID生成的效率。MurmurHash算法，并將計(jì)算得到的10進(jìn)制數(shù)，轉(zhuǎn)化成62進(jìn)制表示法，進(jìn)一步縮短短IDIDID個(gè)原始網(wǎng)址分配一個(gè)ID號(hào)碼，并且同樣轉(zhuǎn)成62進(jìn)制表示法，拼接到短網(wǎng)址服務(wù)的域名之后，如果我們還要額外支持用戶自定義短網(wǎng)址功能（/我們?cè)谥v通過(guò)D今天是農(nóng)歷的大年三十，我們專欄的正文到這里也就全部結(jié)束了。從明天開始，我會(huì)每天發(fā)布一篇練習(xí)題，內(nèi)容針對(duì)專欄涉及的數(shù)據(jù)結(jié)構(gòu)和算法。從初一到初七，幫你復(fù)習(xí)鞏固所學(xué)知識(shí)，拿下數(shù)據(jù)結(jié)構(gòu)和算法，打響新年進(jìn)步的第一槍！明天見！上一 55|算法實(shí)戰(zhàn)（四）：剖析微服務(wù)接口鑒權(quán)限流背后的數(shù)據(jù)結(jié)構(gòu)和算下一 春節(jié)7天練|Day1：數(shù)組和鏈 5 4微 2小 2一 1實(shí)驗(yàn)室清潔 ，62純潔的憎 純潔的憎 1為了避免散列沖突，需要在在建立新的對(duì)應(yīng)關(guān)系時(shí)，查詢數(shù)據(jù)庫(kù)中是否