海量數(shù)據(jù)問題的處理方法：
1.hash map
就是把任意長(zhǎng)度的輸入通過(guò)散列算法編程固定長(zhǎng)度的輸出。這種轉(zhuǎn)換時(shí)一種壓縮映射
哈希表，用來(lái)快速查找刪除，通常要求總的數(shù)據(jù)量可以放入內(nèi)存，散列值空間通常要小于輸入空間载萌，哪些問題可以用到hash表呢物臂。
2.bit map用一個(gè)bit位來(lái)表示某個(gè)元素對(duì)應(yīng)的value瘟滨，而key是該元素锯蛀。由于采用了bit為單位來(lái)存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面可以大大節(jié)省馅精。
3.bloom filter
4.heap堆是一種特殊的二叉樹严嗜，每個(gè)節(jié)點(diǎn)的值都大于其子節(jié)點(diǎn)的值，樹是完全平衡的洲敢，而且最后一層的樹葉都在最左邊漫玄，海量數(shù)據(jù)前n大，并且n比較小沦疾，堆可以放入內(nèi)存称近、
5.雙層桶，算法設(shè)計(jì)思想哮塞，無(wú)法處理的時(shí)候分成一個(gè)個(gè)小的單元刨秆，然后根據(jù)一定的策略來(lái)處理這些小單元，從而達(dá)到目的忆畅。第k大衡未，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字家凯。因?yàn)樵胤秶艽蠡捍祝荒芾弥苯訉ぶ繁怼Ｋ酝ㄟ^(guò)多次劃分逐步確定范圍绊诲，然后最后在一個(gè)可以接受的范圍內(nèi)進(jìn)行送粱，可以通過(guò)多次縮小。雙層只是一個(gè)例子掂之，分治才是其根本抗俄。
6.數(shù)據(jù)庫(kù)索引好比是一本書前面的目錄，能加快數(shù)據(jù)庫(kù)的查詢速度世舰，select * from table1 where id = 44如果沒有索引必須遍歷整個(gè)表动雹，知道id等于44這一行被找到為止，有了索引以后必須是在id這一列上建立的所以跟压，直接在索引里找44胰蝠，也就是在id這一列找，就可以得知這一行的為止震蒋，也就是找到了這一行茸塞，由此可見索引是用來(lái)定位的。它還可以建立表和表之間的連接索引有這么多優(yōu)點(diǎn)喷好，那是不是可以給所有類建立一個(gè)索引呢翔横。索引的缺點(diǎn)有創(chuàng)建維護(hù)索引的時(shí)候肯定要消耗時(shí)間的，比如插入或刪除的時(shí)候梗搅，索引還要占據(jù)物理空間禾唁。
7.倒排索引是一種縮影方法效览，被用來(lái)存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。單詞指向包含的文檔荡短，查詢包含的單詞
8.外排序外排序的歸并方法丐枉，置換選擇敗者樹，最優(yōu)歸并樹
9.B+樹掘托，其構(gòu)建過(guò)程中引入了有序數(shù)組瘦锹，從而有效降低了樹的高度，一次性取出一個(gè)連續(xù)的數(shù)組闪盔，這個(gè)操作在磁盤上比取出與數(shù)組相同數(shù)量的離散數(shù)據(jù)要便宜的多弯院，所以磁盤上基本都是B+樹的結(jié)構(gòu)。比較次數(shù)比較少泪掀，存儲(chǔ)系統(tǒng)一次性要讀大塊的數(shù)據(jù)听绳，比一次性讀小塊數(shù)據(jù)要快，這里面可以做很多事情异赫，可以查找一個(gè)區(qū)間椅挣。可以查找一個(gè)數(shù)塔拳，增加一個(gè)節(jié)點(diǎn)很容易鼠证，復(fù)雜度可控，hash表的話性能就要下降靠抑。
10.Trie tree又稱字典樹量九，字典查找樹或者前綴樹，是一種用于快速檢索的多叉樹結(jié)構(gòu)颂碧，如英文字母的字典樹是一個(gè)26叉樹娩鹉，數(shù)字的字典樹是一個(gè)10叉樹。適用范圍是數(shù)據(jù)量大稚伍，重復(fù)多，但是數(shù)據(jù)種類小可以放入內(nèi)存的時(shí)候戚宦。利用字符串的公共前綴來(lái)節(jié)省空間个曙。
11.分布式mapreduce，適用范圍受楼、：數(shù)據(jù)量大垦搬，數(shù)據(jù)種類小可以放入內(nèi)存、
海量數(shù)據(jù)案例1.
上千萬(wàn)艳汽，或者億數(shù)據(jù)猴贰，里面有重復(fù)，統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)河狐，分兩種情況米绕，可一次讀入內(nèi)存瑟捣，不可一次讀入。
能否一次性讀入內(nèi)存是去除重復(fù)數(shù)據(jù)量栅干，建立一個(gè)字典迈套，hash map來(lái)進(jìn)行一個(gè)統(tǒng)計(jì)。當(dāng)你在更新每條數(shù)據(jù)的時(shí)候碱鳞，可以用堆來(lái)維護(hù)桑李。這樣會(huì)導(dǎo)致你維護(hù)的次數(shù)增多，如果你是無(wú)法放入內(nèi)存的窿给，可以考慮能不能加以改進(jìn)贵白。出現(xiàn)次數(shù)最多的前100個(gè)。你歸并了以后不能保證找到的是真正最多的一百個(gè)崩泡。外排序會(huì)消耗大量的IO禁荒。效率不高≡驶可以考慮近似統(tǒng)計(jì)圈浇，把實(shí)際中出現(xiàn)最多的放入內(nèi)存。
設(shè)計(jì)一個(gè)可控制規(guī)模的社交網(wǎng)絡(luò)系統(tǒng)靴寂，可以查找兩個(gè)用戶之間的關(guān)系磷蜀。
在數(shù)據(jù)量不大的情況下，所有數(shù)據(jù)可以存放在同一臺(tái)機(jī)器上百炬，那查找兩個(gè)用戶的關(guān)系是單純的搜索褐隆。
當(dāng)數(shù)據(jù)量大的情況下，可以用相似的思路剖踊，用hash庶弃，用戶的前幾位數(shù)字決定存儲(chǔ)在哪個(gè)機(jī)器上，獲得用戶的好友列表德澈，ID機(jī)器名歇攻，再去訪問機(jī)器ID的節(jié)點(diǎn)。訪問另一臺(tái)機(jī)器的成本可能比較高梆造。所以相關(guān)的數(shù)據(jù)要一次讀取完畢缴守。節(jié)點(diǎn)有沒有被訪問過(guò)，防止重復(fù)的訪問镇辉，可以建立hashmap屡穗，如果用戶三層關(guān)系才可以聯(lián)系上，可以判斷兩個(gè)用戶是陌生的忽肛。
一個(gè)服務(wù)器有一個(gè)訪問村砂，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)可以判斷上一秒，上一分和上一小時(shí)的訪問量屹逛。
對(duì)每一個(gè)請(qǐng)求分配當(dāng)前的一個(gè)時(shí)間戳础废，對(duì)時(shí)間戳進(jìn)行排序汛骂，那就是有序序列。用二分查找通過(guò)快速的定位色迂。一分鐘之內(nèi)訪問到哪里香缺。找到了對(duì)應(yīng)的request,如何知道request已經(jīng)進(jìn)行了多少次請(qǐng)求，request可以計(jì)數(shù)歇僧，第幾個(gè)图张。可以知道一共發(fā)生了多少次诈悍。復(fù)雜度祸轮。二分搜索某個(gè)特定時(shí)間request是log n
電商網(wǎng)站，單個(gè)機(jī)器MVC侥钳，在初期一臺(tái)機(jī)器能承受的時(shí)候适袜，CS和BS兩種模型，browser的協(xié)議更加標(biāo)準(zhǔn)一些舷夺。MVC是一個(gè)分層的框架苦酱。簡(jiǎn)單的認(rèn)為client提一個(gè)請(qǐng)求到web server上面，用一個(gè)控制器去請(qǐng)求數(shù)據(jù)庫(kù)和文件資源再返還給用戶给猾。典型的網(wǎng)站結(jié)構(gòu)疫萤，開源的技術(shù)。技術(shù)的選型
login: session和cookie
web server: apache/php/nginx
mvc: templates, spring
db: mysql
登陸的時(shí)候有session表敢伸。Cookie是在瀏覽器端的設(shè)置扯饶，通過(guò)cookie傳遞給server看看session是不是存在，可以認(rèn)為cookie是明碼池颈，session是設(shè)立在服務(wù)器端的尾序。
Nginx在異步和大規(guī)模并發(fā)的時(shí)候有很好的性能。
Mvc模板類
電商網(wǎng)站2.0版本躯砰。SOA
服務(wù)指向結(jié)構(gòu)每币。
Cache APP server，DB server琢歇，fileserver.
遇到性能問題脯爪，第一反應(yīng)就是加cache
SOA的一些特點(diǎn)，
Scaling
規(guī)模矿微，graceful degradatron平穩(wěn)地降級(jí)。
如果一個(gè)模塊比方說(shuō)評(píng)論或者廣告宕機(jī)了尚揣，不能影響到整個(gè)網(wǎng)站的訪問涌矢。要保證基本的核心能保證穩(wěn)定的。
Reuse復(fù)用性快骗。當(dāng)我們搭建一些小的服務(wù)可以搭積木可以變成更強(qiáng)大的服務(wù)娜庇。
Ownership有責(zé)任塔次。從設(shè)計(jì)到代碼的完成，到監(jiān)控和alert名秀，
Simplification通過(guò)接口的方式励负。REST
電商網(wǎng)站3.0版本，多了一些組件匕得，前面加了router反向代理继榆。不同的請(qǐng)求放到app server上去。
海量數(shù)據(jù)案例2
聊天系統(tǒng)
facebook message wechat
工作流
Q2get new message
Pull和push汁掠，pull每隔三秒
Online status上次在線的時(shí)間略吨。
Heart beat
每隔一分鐘，自動(dòng)去update
conversation list
數(shù)據(jù)抽樣考阱，長(zhǎng)度為N的鏈表翠忠，不知道n有多大，遍歷一次平均概率取出k個(gè)元素乞榨。
蓄水池抽樣秽之，保存k個(gè)元素，k+1開始
一次掃描每個(gè)元素吃既，top k的算法考榨。
Ab兩個(gè)文件各存放50億個(gè)url,每個(gè)占64字節(jié)，內(nèi)存限制4G态秧，找到ab文件共同的URL董虱，存儲(chǔ)到1000個(gè)小文件里，每個(gè)小文件
Bloom filter
有十個(gè)文件申鱼，每個(gè)文件1G愤诱，每一行是用戶的query,每隔query都可能重復(fù)，按照query的頻度排序
