http://hi.baidu.com/jrckkyy/blog/item/ee657b1772b7d91ac83d6de4.html

數(shù)據(jù)量的問題是很多面試筆試中經(jīng)常出現(xiàn)的問題，比如 google、淘寶、百度、 騰訊 這樣的一些涉及到海量數(shù)據(jù)的公司經(jīng)常會問到。

下面的方法是我對海量數(shù)據(jù)的處理方法進行了一個一般性的總結(jié)，當(dāng)然這些方法可能并不能完全覆蓋所有的問題，但是這樣的一些方法也基本可以處理絕大多數(shù)遇到的問題。下面的一些問題基本直接來源于公司的面試筆試題目，方法不一定最優(yōu)，如果你有更好的處理方法，歡迎與我討論。

1.Bloom filter

適用范圍：可以用來實現(xiàn)數(shù)據(jù)字典，進行數(shù)據(jù)的判重，或者集合求交集

基本原理及要點：
對于原理來說很簡單，位數(shù)組+k個獨立hash函數(shù)。將hash函數(shù)對應(yīng)的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有hash函數(shù)對應(yīng)位都是1說明存在，很明顯這個過程并不保證查找的結(jié)果是100%正確的。同時也不支持刪除一個已經(jīng)插入的關(guān)鍵字，因為該關(guān)鍵字對應(yīng)的位會牽動到其他的關(guān)鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了。

還有一個比較重要的問題，如何根據(jù)輸入元素個數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個數(shù)。當(dāng)hash函數(shù)個數(shù)k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應(yīng)該更大些，因為還要保證bit數(shù)組里至少一半為0，則m應(yīng)該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數(shù))。

舉個例子我們假設(shè)錯誤率為0.01，則此時m應(yīng)大概是n的13倍。這樣k大概是8個。

注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數(shù)為單位(準(zhǔn)確的說是不同元素的個數(shù))。通常單個元素的長度都是有很多bit的。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。

擴展：
Bloom filter將集合中的元素映射到位數(shù)組中，用k（k為哈希函數(shù)個數(shù)）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數(shù)組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)。SBF采用counter中的最小值來近似表示元素的出現(xiàn)頻率。

問題實例：給你A,B兩個文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？

根據(jù)這個問題我們來計算下內(nèi)存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個bit。現(xiàn)在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應(yīng)的，就可以轉(zhuǎn)換成ip，則大大簡單了。

2.Hashing

適用范圍：快速查找，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存

基本原理及要點：
hash函數(shù)選擇，針對字符串，整數(shù)，排列，具體相應(yīng)的hash方法。
碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。

擴展：
d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數(shù)，h1和h2。在存儲一個新的key時，同時用兩個哈希函數(shù)進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個位置已經(jīng)存儲的（有碰撞的）key比較多，然后將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進行兩次hash，同時查找兩個位置。

問題實例：
1).海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。

IP的數(shù)目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內(nèi)存，然后進行統(tǒng)計。

3.bit-map

適用范圍：可進行數(shù)據(jù)的快速查找，判重，刪除，一般來說數(shù)據(jù)范圍是int的10倍以下

基本原理及要點：使用bit數(shù)組來表示某些元素是否存在，比如8位電話號碼

擴展：bloom filter可以看做是對bit-map的擴展

問題實例：

1)已知某個文件內(nèi)包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)。

8位最多99 999 999，大概需要99m個bit，大概10幾m字節(jié)的內(nèi)存即可。

2)2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。

將bit-map擴展一下，用2bit表示一個數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現(xiàn)這個2bit-map。

4.堆

適用范圍：海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存

基本原理及要點：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當(dāng)前元素與最大堆里的最大元素，如果它小于最大元素，則應(yīng)該替換那個最大元素。這樣最后得到的n個元素就是最小的n個。適合大數(shù)據(jù)量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。

擴展：雙堆，一個最大堆與一個最小堆結(jié)合，可以用來維護中位數(shù)。

問題實例：
1)100w個數(shù)中找最大的前100個數(shù)。

用一個100個元素大小的最小堆即可。

5.雙層桶劃分 —-其實本質(zhì)上就是【分而治之】的思想，重在“分”的技巧上！

適用范圍：第k大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字

基本原理及要點：因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進行。可以通過多次縮小，雙層只是一個例子。

擴展：

問題實例：
1).2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。

有點像鴿巢原理，整數(shù)個數(shù)為2^32,也就是，我們可以將這2^32個數(shù)，劃分為2^8個區(qū)域(比如用單個文件代表一個區(qū)域)，然后將數(shù)據(jù)分離到不同的區(qū)域，然后不同的區(qū)域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。

2).5億個int找它們的中位數(shù)。

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)，之后我們根據(jù)統(tǒng)計結(jié)果就可以判斷中位數(shù)落到那個區(qū)域，同時知道這個區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后第二次掃描我們只統(tǒng)計落在這個區(qū)域中的那些數(shù)就可以了。

實際上，如果不是int是int64，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區(qū)域，然后確定區(qū)域的第幾大數(shù)，在將該區(qū)域分成2^20個子區(qū)域，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個數(shù)只有2^20，就可以直接利用direct addr table進行統(tǒng)計了。

6.數(shù)據(jù)庫索引

適用范圍：大數(shù)據(jù)量的增刪改查

基本原理及要點：利用數(shù)據(jù)的設(shè)計實現(xiàn)方法，對海量數(shù)據(jù)的增刪改查進行處理。
擴展：
問題實例：

7.倒排索引(Inverted index)

適用范圍：搜索引擎，關(guān)鍵字查詢

基本原理及要點：為何叫倒排索引？一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。

以英文為例，下面是要被索引的文本：
T0 = “it is what it is”
T1 = “what is it”
T2 = “it is a banana”
我們就能得到下面的反向文件索引：
“a”:      {2}
“banana”: {2}
“is”:     {0, 1, 2}
“it”:     {0, 1, 2}
“what”:   {0, 1}
檢索的條件”what”, “is” 和 “it” 將對應(yīng)集合的交集。

正向索引開發(fā)出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據(jù)了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關(guān)系。

擴展：

問題實例：文檔檢索系統(tǒng)，查詢那些文件包含了某單詞，比如常見的學(xué)術(shù)論文的關(guān)鍵字搜索。

8.外排序

適用范圍：大數(shù)據(jù)的排序，去重

基本原理及要點：外排序的歸并方法，置換選擇 敗者樹原理，最優(yōu)歸并樹

擴展：

問題實例：
1).有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16個字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。

這個數(shù)據(jù)具有很明顯的特點，詞的大小為16個字節(jié)，但是內(nèi)存只有1m做hash有些不夠，所以可以用來排序。內(nèi)存可以當(dāng)輸入緩沖區(qū)使用。

9.trie樹

適用范圍：數(shù)據(jù)量大，重復(fù)多，但是數(shù)據(jù)種類小可以放入內(nèi)存

基本原理及要點：實現(xiàn)方式，節(jié)點孩子的表示方式

擴展：壓縮實現(xiàn)。

問題實例：
1).有10個文件，每個文件1G， 每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復(fù)。要你按照query的頻度排序 。

2).1000萬字符串，其中有些是相同的(重復(fù)),需要把重復(fù)的全部去掉，保留沒有重復(fù)的字符串。請問怎么設(shè)計和實現(xiàn)？

3).尋找熱門查詢：查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個，每個不超過255字節(jié)。

10.分布式處理 mapreduce

適用范圍：數(shù)據(jù)量大，但是數(shù)據(jù)種類小可以放入內(nèi)存

基本原理及要點：將數(shù)據(jù)交給不同的機器去處理，數(shù)據(jù)劃分，結(jié)果歸約。

擴展：

問題實例：

1).The canonical example application of MapReduce is a process to count the appearances of

each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);

void reduce(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially with a “1″ value by

the Map function, using the word as the result key. The framework puts together all the pairs

with the same key and feeds them to the same call to Reduce, thus this function just needs to

sum all of its input values to find the total appearances of that word.

2).海量數(shù)據(jù)分布在100臺電腦中，想個辦法高效統(tǒng)計出這批數(shù)據(jù)的TOP10。

3).一共有N個機器，每個機器上有N個數(shù)。每個機器最多存O(N)個數(shù)并對它們操作。如何找到N^2個數(shù)的中數(shù)(median)？

經(jīng)典問題分析

上千萬or億數(shù)據(jù)（有重復(fù)），統(tǒng)計其中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù),分兩種情況：可一次讀入內(nèi)存，不可一次讀入。

可用思路：trie樹+堆，數(shù)據(jù)庫索引，劃分子集分別統(tǒng)計，hash，分布式計算，近似統(tǒng)計，外排序

所謂的是否能一次讀入內(nèi)存，實際上應(yīng)該指去除重復(fù)后的數(shù)據(jù)量。如果去重后數(shù)據(jù)可以放入內(nèi)存，我們可以為數(shù)據(jù)建立字典，比如通過 map，hashmap，trie，然后直接進行統(tǒng)計即可。當(dāng)然在更新每條數(shù)據(jù)的出現(xiàn)次數(shù)的時候，我們可以利用一個堆來維護出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)，當(dāng)然這樣導(dǎo)致維護次數(shù)增加，不如完全統(tǒng)計后在求前N大效率高。

如果數(shù)據(jù)無法放入內(nèi)存。一方面我們可以考慮上面的字典方法能否被改進以適應(yīng)這種情形，可以做的改變就是將字典存放到硬盤上，而不是內(nèi)存，這可以參考數(shù)據(jù)庫的存儲方法。

當(dāng)然還有更好的方法，就是可以采用分布式計算，基本上就是map-reduce過程，首先可以根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash(md5)后的值，將數(shù)據(jù)按照范圍劃分到不同的機子，最好可以讓數(shù)據(jù)劃分后可以一次讀入內(nèi)存，這樣不同的機子負責(zé)處理各種的數(shù)值范圍，實際上就是map。得到結(jié)果后，各個機子只需拿出各自的出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)，然后匯總，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)，這實際上就是reduce過程。

實際上可能想直接將數(shù)據(jù)均分到不同的機子上進行處理，這樣是無法得到正確的解的。因為一個數(shù)據(jù)可能被均分到不同的機子上，而另一個則可能完全聚集到一個機子上，同時還可能存在具有相同數(shù)目的數(shù)據(jù)。比如我們要找出現(xiàn)次數(shù)最多的前100個，我們將1000萬的數(shù)據(jù)分布到10臺機器上，找到每臺出現(xiàn)次數(shù)最多的前 100個，歸并之后這樣不能保證找到真正的第100個，因為比如出現(xiàn)次數(shù)最多的第100個可能有1萬個，但是它被分到了10臺機子，這樣在每臺上只有1千個，假設(shè)這些機子排名在1000個之前的那些都是單獨分布在一臺機子上的，比如有1001個，這樣本來具有1萬個的這個就會被淘汰，即使我們讓每臺機子選出出現(xiàn)次數(shù)最多的1000個再歸并，仍然會出錯，因為可能存在大量個數(shù)為1001個的發(fā)生聚集。因此不能將數(shù)據(jù)隨便均分到不同機子上，而是要根據(jù)hash 后的值將它們映射到不同的機子上處理，讓不同的機器處理一個數(shù)值范圍。

而外排序的方法會消耗大量的IO，效率不會很高。而上面的分布式方法，也可以用于單機版本，也就是將總的數(shù)據(jù)根據(jù)值的范圍，劃分成多個不同的子文件，然后逐個處理。處理完畢之后再對這些單詞的及其出現(xiàn)頻率進行一個歸并。實際上就可以利用一個外排序的歸并過程。

另外還可以考慮近似計算，也就是我們可以通過結(jié)合自然語言屬性，只將那些真正實際中出現(xiàn)最多的那些詞作為一個字典，使得這個規(guī)模可以放入內(nèi)存。

轉(zhuǎn)載請注明出處：http://bbs.xjtu.edu.cn
作者phylips@bmy

參考文獻：
http://blog.csdn.net/jiaomeng/archive/2007/03/08/1523940.aspx       d-Left Hashing

http://blog.csdn.net/jiaomeng/archive/2007/01/27/1495500.aspx

http://en.wikipedia.org/wiki/Bloom_filter

http://hi.baidu.com/xdzhang_china/blog/item/2847777e83fb020229388a15.html 應(yīng)用Bloom Filter的幾個小技巧

http://zh.wikipedia.org/wiki/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95

辦理步驟：
1、預(yù)約
2、填表
3、準(zhǔn)備材料
4、面談
美國簽證辦理流程看似簡單，實則每一項都需要認(rèn)真準(zhǔn)備。拿材料準(zhǔn)備來講，像資產(chǎn)證明、家庭關(guān)系證明及工作證明都是非常重要的，千萬不可忽視哦！

赴美國旅游簽證所需材料準(zhǔn)備 
01、申請人有效護照原件（確認(rèn)有效期在半年以上，護照末頁要有本人簽名）。
02、申請人身份證原件。 
03、申請人戶口本原件（全家頁）。
04、申請人結(jié)婚證或相關(guān)機構(gòu)所開具的證明原件。
05、申請人本人或配偶名下由存款銀行開據(jù)的存折或存單原件，建議存期一年以上，金額人民幣十萬元以上。
06、申請人物產(chǎn)證明原件（如房產(chǎn)、車輛及證明個人財產(chǎn)的相關(guān)證明材料）。
07、申請人公司簡介并加蓋公章原件。
08、申請人在職證明信并加蓋公司公章原件。
09、申請人全家福照片原件。
10、申請人請?zhí)峁┰率杖胱C明原件如工資單需加蓋公司公章或工資卡請打印流水單并加蓋銀行公章。
11、申請人曾出訪去過國家的簽證頁及在國外拍的3-5張照片原件(要有境外標(biāo)志性建筑物的) 。
12、申請人公司營業(yè)執(zhí)照原件或復(fù)印件加蓋公司公章。
13、申請人50mm*50mm的免冠彩色白底相片2張原件（并在背面用鉛筆簽名）
14、申請人名片原件2張。
15、申請人曾使用的舊護照原件。
16、申請人詳細填寫的赴美申請表原件。
17、申請人若是十六歲以下孩子，需提供與父母關(guān)系的公證書。如一方帶孩子去，需要第三方委托公證書。

這2天接觸了一下Amazon Web Services(AWS)中的Amazon Simple Storage Service，簡稱Amazon S3（下稱S3）。S3站點上用下面的語句描述了自己的作用：

Amazon S3 is storage for the Internet. It is designed to make web-scale computing easier for developers.

Amazon S3 provides a simple web services interface that can be used to store and retrieve any amount of data, at any time, from anywhere on the web. It gives any developer access to the same highly scalable, reliable, fast, inexpensive data storage infrastructure that Amazon uses to run its own global network of web sites. The service aims to maximize benefits of scale and to pass those benefits on to developers.
通過S3這個接口，您可以把Amazon的存儲服務(wù)當(dāng)作一個硬盤，可以隨時隨地上傳，下載數(shù)據(jù)，不過您得付錢才可以使用，即使您只是準(zhǔn)備測試一 下。S3首頁上有價格表。在S3注冊并付費獲取2個數(shù)：Access Key ID和Secret Access Key，才可以使用S3的服務(wù)，因為所有的操作都需要這2個數(shù)進行身份驗證。

一、基本概念：Buckets，Objects，Keys，Operations

注冊后，用戶通過名為bucket的容器來管理所有數(shù)據(jù)，這些數(shù)據(jù)稱之為對象(Object)。比如，一個名為20071211/logo- 320×240.gif的對象存放在livebaby這個bucket里，則可以通過URL：http: //s3.amazonaws.com/livebaby/20071211/logo-320×240.gif來訪問這個對象。bucket有3個基本 概念：1、不能刪除非空的bucket；2、bucket不能轉(zhuǎn)讓給其他用戶；3、每個用戶最多只能有100個buckets。簡單的說，bucket類 似硬盤分區(qū)中的第一層目錄。

這里還有一個key的概念，key是bucket中對象的唯一標(biāo)識符，每個對象對應(yīng)一個key。上例中，20071211/logo-320×240.gif稱為key。

每個對象都有一組鍵值對，稱為MetaData，分2種，系統(tǒng)metadata和 用戶metadata。S3不處理用戶metadata，只接收、存儲、返回給用戶，由用戶自己處理。REST下，系統(tǒng)metadata以x-amz-開 頭，用戶metadata以x-amz-meta-開頭。

Amazon提供2種API：Simple Object Access Protocol(SOAP)和Representational State Transfer(REST)來訪問AWS。這里一篇文章，其中簡單對比了一下2者的區(qū)別，區(qū)別后總結(jié)說：“ In fact, you can think of REST as a kind of data-access methodology whereas SOAP is a process-control methodology.”

通過SOAP和REST，最常用的操作(Operation)有這么幾個：

* 創(chuàng)建bucket；
* 上傳對象，上傳時必須指定一個key，同時還可以設(shè)置這個對象的訪問控制權(quán)限，默認(rèn)是私有的；
* 下載對象，有HTTP 和 BitTorrent2種方式；
* 刪除對象；
* 列表對象；列表時，可以通過一個前綴(prefix)來過濾顯示不同的對象。

通過向AWS的服務(wù)端點(endpoint，http://s3.amazonaws.com/)發(fā)出PUT、GET、DELETE、HEAD等HTTP Requests，便可以操作S3上的數(shù)據(jù)。

如果通過web訪問S3服務(wù)來獲取數(shù)據(jù)（Object），則分頁、搜索等功能是比不可少的。而S3提供的4個參數(shù)，可以讓我們方便快捷的將數(shù)據(jù)取出來，這4個參數(shù)是基于key操作的。key的概念參見文章一。

1、prefix。比如http://bucket.s3.amazonaws.com/?prefix=123，則將key中以123開頭的列出來。

2、delimiter。比如http://bucket.s3.amazonaws.com/?delimiter=/，此時，S3可能會返回CommonPrefixes，將key中采用“/”分隔的列出來。

<Contents>
<Key>123/zzz.txt</Key>
<LastModified>2007-12-11T07:41:51.000Z</LastModified>
<ETag>”d725dfc2167445d1db23067de33ebd28″</ETag>
<Size>203</Size>
<StorageClass>STANDARD</StorageClass>
</Contents>
<Contents>
<Key>abc/ooo/yxx.txt</Key>
<LastModified>2007-12-12T05:34:35.000Z</LastModified>
<ETag>”4fdf8a4dd42bd4d24855eebd5c9b9434″</ETag>
<Size>41</Size>
<StorageClass>STANDARD</StorageClass>
</Contents>

用了“delimiter=/”返回，告訴你 有prefix為123/和abc/可用。

<CommonPrefixes>
<Prefix>123/</Prefix>
</CommonPrefixes>
<CommonPrefixes>
<Prefix>abc/</Prefix>
</CommonPrefixes>

這時輸入http://bucket.s3.amazonaws.com/?delimiter=/&prefix=123/則將prefix中有123/的全部列出來。

如果key有這樣的形式：ms_vb_5_src/sss.frm，ms_vb_6_src/ddd.frm，你可以把delimiter設(shè)為“_”來取數(shù)據(jù)。通過不同的delimiter和prefix可以非常靈活的獲取數(shù)據(jù)。

如果數(shù)據(jù)量很大，則可以用第三個和第四個參數(shù)

3、MaxKeys。這個告訴S3一次性返回多少數(shù)據(jù)，默認(rèn)返回1000個。URL輸入http://bucket.s3.amazonaws.com/?delimiter=/&prefix=123/&max-keys=10，則返回：

<Name>bucket</Name>
<Prefix>123/</Prefix>
<Marker />
<NextMarker>123/10.txt</NextMarker>
<MaxKeys>10</MaxKeys>
<Delimiter>/</Delimiter>
<IsTruncated>true</IsTruncated>
<Contents>
<Key>123/1.txt</Key>
<LastModified>2007-12-12T06:02:33.000Z</LastModified>
<ETag>”9dd4e461268c8034f5c8564e155c67a6″</ETag>
<Size>1</Size>
<StorageClass>STANDARD</StorageClass>
</Contents>

里面IsTruncated為true，表示按照delimiter和prefix和max-keys取出的數(shù)據(jù)不止10個；余下的數(shù)據(jù)怎么取？就用到了NextMarker元素中數(shù)據(jù)。

4、Marker。 URL輸入http://bucket.s3.amazonaws.com/?delimiter=/&prefix=123/&max -keys=10&marker=123/10.txt，marker的值就是NextMarker元素中數(shù)據(jù)。這樣S3就返回了下10條數(shù)據(jù)。

<Name>bucket</Name>
<Prefix>123/</Prefix>
<Marker>123/10.txt</Marker>
<NextMarker>123/19.txt</NextMarker>
<MaxKeys>10</MaxKeys>
<Delimiter>/</Delimiter>
<IsTruncated>true</IsTruncated>
<Contents>
<Key>123/1.txt</Key>
<LastModified>2007-12-12T06:02:33.000Z</LastModified>
<ETag>”9dd4e461268c8034f5c8564e155c67a6″</ETag>
<Size>1</Size>
<StorageClass>STANDARD</StorageClass>
</Contents>

如果IsTruncated仍為true，則表示還有數(shù)據(jù)，我們把marker改為marker=123/19.txt便可以繼續(xù)取下10條數(shù)據(jù)；如果IsTruncated為false，則表示按照條件已經(jīng)將數(shù)據(jù)全部取出來了。

S3文檔中，提供更為詳細的解釋。點擊查看：http://docs.amazonwebservices.com/AmazonS3/2006-03-01/

本文適用對象

您希望建立自己的英特網(wǎng)漫游隧道

您有一張可以刷外幣的信用卡，比如VISA。手機。

您有基本的英文閱讀技能

開始前需要注意

本文作者不對任何因本文造成的費用負責(zé)；

Amazon包含750小時的free tiers活動從2010年11月1日開始，10月20日后注冊的新用戶都可以享受此項服務(wù)；

Free tires包含10GB EBS，30GB帶寬（SSH proxy的話，實際上只有15GB），超出部分仍然需要付費；

本文作者不熟悉Amazon EC2等服務(wù)，部分描述或理解可能有差錯。

注冊Amazon AWS賬戶

注冊Amazon賬戶

啟動瀏覽器，訪問 http://aws.amazon.com/ ，點擊“Sign Up Now”：

轉(zhuǎn)入amazon賬戶登陸頁面，如果您已經(jīng)是amazon的用戶，可以直接登陸，本文假設(shè)您還沒有amazon賬戶，注冊新用戶：

輸入email地址

選中“I am a new user.

點擊”Sign in using secure server“

轉(zhuǎn)入新用戶注冊頁面：

姓名

email地址

重復(fù)email地址

賬戶密碼

重復(fù)密碼

點擊”Create account“

轉(zhuǎn)入聯(lián)系信息頁面：

聯(lián)系地址：街道，公司，必填

聯(lián)系地址：幾單元門牌號等，按需填寫

城市

省份

郵編

國家：china

電話號碼：直接填寫，無需 +86

協(xié)議

驗證碼

注冊AWS賬戶

聯(lián)系信息提交成功后轉(zhuǎn)入AWS登陸頁面，輸入email，密碼，登陸后，轉(zhuǎn)到AWS聯(lián)系信息頁面，雖然之前注冊Amazon賬戶已經(jīng)填寫過聯(lián)系信息，注冊Amazon AWS賬戶還是需要充填一遍，按照原先輸入的信息表單會自動補全。

聯(lián)系信息提交成功后，AWS賬戶注冊步驟完成了。Amazon AWS會email通知告訴你接下來如何如何。

填寫信用卡信息

Amazon EC2一般的付費模式是On Demand按需付費，不用不付費。在使用之前需要關(guān)聯(lián)信用卡信息到您的AWS賬戶。

點擊上面郵件中的account鏈接，或直接訪問：http://aws.amazon.com/account，點擊 Payment Method ，登陸后轉(zhuǎn)到支付方式頁面，輸入你的信用卡信息 Continue。

繼續(xù)轉(zhuǎn)到賬單地址頁面，選擇注冊AWS時提供的地址 Continue

信用卡驗證會刷掉1美金（我的理解是預(yù)付費，驗證不會真的扣錢，這點我并未去證實），如果沒有成功會收到郵件通知更正信用卡信息，Account Activity頁面也會提示你更新信用卡信息或者用已有信息重新驗證。

開通 AWS EC2 等服務(wù)

開通AWS相關(guān)服務(wù)需要登陸AWS管理后臺console。訪問 https://aws.amazon.com/console ，點擊 Sign in to the AWS Console，登陸后轉(zhuǎn)到AWS后臺。

默認(rèn)登陸console后轉(zhuǎn)到 Amazon S3 管理頁面，點擊 Amazon EC2 轉(zhuǎn)到 EC2 管理頁面，點擊 Sign Up For Amazon EC2

轉(zhuǎn)到電話驗證頁面

選擇China

填寫手機號碼，無需+86

點擊 ”Call Me Now“

點擊后，此頁面轉(zhuǎn)到第二步，顯示 PIN 驗證碼。

同時接收到亞馬遜電話驗證，輸入您瀏覽器頁面中的PIN碼，信息驗證完成。轉(zhuǎn)到第三步，點擊Continue。

轉(zhuǎn)到完成啟用服務(wù)確認(rèn)頁面，這個頁面展示不同機房不同服務(wù)的收費情況，并非配置頁面，直接Complete Sign Up

系統(tǒng)提示正在啟用訂閱，訂閱后會發(fā)送郵件到你的郵箱。 

至此EC2服務(wù)已經(jīng)開通。可以進入console跑instance啦！

啟動實例

打開 https://console.aws.amazon.com/ec2/home 進入 EC2 console：

Amazon S3： S3存儲服務(wù)，可不用

Amazon EC2： 類似傳統(tǒng)的VPS服務(wù)，可以在這里啟動Instance，增加EBS硬盤

Region： 四個可選區(qū)域，一般來講國內(nèi)連西海岸加州機房較快，如果對國內(nèi)提供web服務(wù)，也可以考慮新加坡機房，新加坡機房價錢要貴一些。

Instances： 所有實例（VPS）

AMIs： 所有AMIs，可以看成是不用安裝的操作系統(tǒng)，選擇一個啟動即得到一個 Instance。

Volumes：EBS硬盤，EC2默認(rèn)不帶存儲，雖然可以通過存儲在S3的AMI啟動，但當(dāng)你關(guān)閉或重啟Instance后，所有數(shù)據(jù)都會消失。而通過存儲在EBS的AMI啟動則不會有這個問題。所有數(shù)據(jù)變更保存到EBS中。您也可以添加額外的EBS掛在到某個Instance。

Snapshots： 增量備份的系統(tǒng)快照。

Elastic IP： EC2的Instance是變化的，如果你需要固定的IP，可以在這里設(shè)置，不過需要注意，如果你分配了固定IP但是沒有掛載到任何Instance上，你會被Amazon懲罰性收費。

Launch Instance： 點擊啟動新的Instance實例。

點擊 Launch Instance， 打開實例向?qū)Т翱冢?/p>

這里我們用的是默認(rèn)的第一個 AMI， Basic 32-bit Amazon Linux AMI 1.0，大致解釋一下：

Amazon Linux是Amazon基于fedora為EC2定制的AMI，默認(rèn)禁止root ssh密碼方式登陸，去除不需要的服務(wù)等，默認(rèn)配置更加安全。安全。

自帶 Amazon 工具包。

Amazon每個Region都為Amazon Linux提供了軟件倉庫，更新軟件不造成帶寬費用。

micro instance更適合跑32-bit linux。

EBS boot，默認(rèn)配合10GB的EBS。

使用此instance沒有額外費用。

選擇Windows instance，需按使用支付Windows授權(quán)費用。

這里沒有選擇ubuntu的原因是因為我發(fā)現(xiàn)Ubuntu的AMI默認(rèn)是15GB的EBS，而free tier 只提供了10GB的EBS硬盤。

點擊Select，進入向?qū)У诙剑?/p>

實例數(shù)，默認(rèn)為1，free tiers包含每月750小時的micro instance，如果不間斷運行的話，正好夠跑一個instance。

可用區(qū)域，這里用了默認(rèn)的，無特別喜好。

實例類型，必須選擇Micro，除非你不準(zhǔn)備使用免費的micro instance。

啟動實例，對應(yīng)的另外一個選項是”Request Spot Instances“，類似競價方式在空閑的機器上跑Instance，這個用默認(rèn)的。

點擊Continue轉(zhuǎn)到高級實例選項設(shè)定，這里全部默認(rèn)。

點擊Continue轉(zhuǎn)到Tag設(shè)定頁面，可以不設(shè)定直接跳過。

點擊Continue進入”Create Key Pair“：

指定一個密鑰名稱，如： fookey

點擊生成并下載密鑰，這個密鑰需要妥善保存，有了這個密鑰，可以隨時打開（登陸）您跑在amazon aws上的機器。

點擊Continue進入”CONFIGURE FIREWARE“：

配置防火墻頁面，這個設(shè)置安全組別為”Web“， 并添加了”http“， ”https“，允許此臺服務(wù)器提供web服務(wù)。

點擊Continue進入”Review“：

注意一下，Instance Type為 Micro （t1.micro）

點擊”Launch“啟動Instance。基于EBS的AMI啟動大約需要1分鐘。

點擊View your instances on the Instances page察看Instance狀態(tài)。

您應(yīng)該已經(jīng)看到有一個 t1.micro status為Running，至此您的micro intance已經(jīng)啟動，意味這您有一臺可以ssh登陸的linux服務(wù)器啦。

用它來做什么

用來做web服務(wù)器，跑php， python， ruby網(wǎng)站

用來跑SSH proxy， VPN

更多。..

SSH proxy在Linux下很簡單，一條命令即可：

系統(tǒng)只允許通過key密鑰登陸

我們安裝的AMI，默認(rèn)登陸用戶為 ec2-user

用你的Public DNS代替 YOUR_AMAZON_PUBLIC_DNS

跑了一個ssh forward監(jiān)聽本地10003端口

Public DNS可以在Instances詳細信息中找到，

Windows用戶

Windows默認(rèn)沒有ssh客戶端，需要下載putty。putty默認(rèn)不支持Amazon ec2的key，需要做轉(zhuǎn)換，具體過程參考官方文檔。

做tunnel的話還需要在putty中設(shè)定tunnel選項，如端口，動態(tài)，自動等。具體還請大家自行測試。

進一步學(xué)習(xí)Linux

一本linux書籍

看看 fedora文檔：http://fedoraproject.org/

去國內(nèi)的社區(qū)尋求幫助，如linuxsir

 原文地址：http://yinhm.appspot.com/2010/10/amazon-ec2-micro-instance-and-tunnel-guide