專科生阿里大數(shù)據(jù)一面面經(jīng)「已過」「附詳細(xì)答案」
這篇文章是我學(xué)習(xí)群里一個(gè)小兄弟的面試總結(jié),他是??拼笕?/strong>,很早之前找我指導(dǎo)了學(xué)習(xí)路線,學(xué)習(xí)很認(rèn)真努力,目前他已經(jīng)過了阿里一面。


這部分由于內(nèi)容太多,只提供部分重點(diǎn)答案。
spark shuffle:因?yàn)榫哂心撤N共同的特征的一類數(shù)據(jù)需要最終匯聚 (aggregate)到一個(gè)計(jì)算節(jié)點(diǎn)進(jìn)行計(jì)算 ,這個(gè)數(shù)據(jù)重新打亂然后匯聚到不同節(jié)點(diǎn)的過程就是 shuffle。
兩階段提交分為兩個(gè)階段,第一階段是提交事務(wù)請(qǐng)求,第二階段是執(zhí)行事務(wù)提交。首先是提交事務(wù)請(qǐng)求,它分為三小步:1.首先就是事務(wù)詢問,協(xié)調(diào)者向參與者發(fā)送事務(wù)內(nèi)容,詢問是否可以執(zhí)行事務(wù)提交操作,并開始等待各參與者響應(yīng)。2.然后就是執(zhí)行事務(wù),各參與者節(jié)點(diǎn)執(zhí)行事務(wù)操作,并將undo和redo信息計(jì)入事務(wù)日志中。3.最后就是各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng),如果參與者成功執(zhí)行了事務(wù)操作,那么就反饋反饋給協(xié)調(diào)者YES響應(yīng),表示事務(wù)可以執(zhí)行;如果參與者沒有成功執(zhí)行事務(wù),那么反饋給協(xié)調(diào)者NO響應(yīng),表示事務(wù)不可以執(zhí)行。如果所有參與者都響應(yīng)YES,那么就開始第二階段1.首先由協(xié)調(diào)者向所有參與者節(jié)點(diǎn)發(fā)出commit請(qǐng)求。
2.參與者接收到commit請(qǐng)求后,會(huì)正式執(zhí)行事務(wù)提交操作,并在完成提交后釋放在整個(gè)事務(wù)執(zhí)行期間占用的事務(wù)資源。
3.然后參與者在完成事務(wù)提交之后,向協(xié)調(diào)者發(fā)送確認(rèn)ack消息。
4.協(xié)調(diào)者接收到所有參與者反饋的ack消息后,完成事務(wù)。
優(yōu)點(diǎn)是:原理簡(jiǎn)單,實(shí)現(xiàn)方便。缺點(diǎn):同步阻塞,單點(diǎn)問題,腦裂,太過保守。3PC:
三階段提交分為三個(gè)階段,分別是cancommit, precommit, docommit.1.首先是cancommit階段,協(xié)調(diào)者向所有參與者發(fā)送事務(wù)內(nèi)容在內(nèi)的cancommit請(qǐng)求。并等待參與者的反饋。2.參與者收到cancommit請(qǐng)求后,若判斷自己可以順利執(zhí)行事務(wù),則向協(xié)調(diào)者發(fā)送ack響應(yīng),否則反饋NO相應(yīng)。3.然后就是precommit階段,若協(xié)調(diào)者收到了所有參與者的ACK響應(yīng),則向所有的參與者發(fā)送precommit請(qǐng)求。4.參與者收到后執(zhí)行事務(wù),并將操作寫入本地事務(wù)日志中,成功后向協(xié)調(diào)者發(fā)送ACK響應(yīng)。若協(xié)調(diào)者在第一階段的反饋中有NO,或者協(xié)調(diào)者等待超時(shí),則向所有的參與者發(fā)送中斷請(qǐng)求。5最后是docommit,如果協(xié)調(diào)者收到第二階段的所有參與者的ack請(qǐng)求,則向參與者發(fā)送docommit請(qǐng)求,執(zhí)行事務(wù)的提交。參與者收到docommit請(qǐng)求后執(zhí)行事務(wù)的提交,成功后釋放事務(wù)資源,并向協(xié)調(diào)者發(fā)送ACK反饋。協(xié)調(diào)者收到所有的參與者反饋后,完成事務(wù)的提交。若協(xié)調(diào)者等待超時(shí),或者第二階段中有參與者發(fā)送NO反饋,則向所有參與者發(fā)送中斷請(qǐng)求。參與者收到后執(zhí)行事務(wù)回滾,回滾結(jié)束后釋放事務(wù)資源。參與者向協(xié)調(diào)發(fā)送ACK響應(yīng),協(xié)調(diào)者收到所有的ACK響應(yīng)后中斷事務(wù)。缺點(diǎn):?jiǎn)吸c(diǎn)故障,數(shù)據(jù)不一致。優(yōu)點(diǎn):解決了同步阻塞問題(超時(shí)提交策略,第三階段參與者等待超時(shí)后會(huì)提交事務(wù))。由于precommit解決同步阻塞的問題。Paxos:
paxos算法是一種基于消息傳遞的且具有高度容錯(cuò)性的一種算法,解決的問題是一個(gè)分布式系統(tǒng)如何就某個(gè)值或者某個(gè)協(xié)議達(dá)成一致,該算法的前提是假設(shè)不存在拜占庭將軍問題。在該算法中一共有三種角色:proposer, accpetor和learner。proposer負(fù)責(zé)提出提案,acceptor負(fù)責(zé)對(duì)該提案做出裁決,learner負(fù)責(zé)學(xué)習(xí)得到的提案。為了避免單點(diǎn)故障,會(huì)有一個(gè)acceptor集合,proposer向該集合發(fā)送提案,acceptor集合中的每個(gè)成員都有可能同意該提案且每個(gè)acceptor只能批準(zhǔn)一個(gè)提案,當(dāng)有一半以上的成員同意,則同意該提案。它主要分為兩個(gè)階段:分別是prepare階段和accept階段。首先是prepare階段,先由proposer提出編號(hào)為Mn的提案,向accpetor集合發(fā)送prepare請(qǐng)求。Accept做出反饋:保證不會(huì)再接受編號(hào)比Mn小的提案;如果acceptor已經(jīng)批準(zhǔn)過某提案,會(huì)向proposer返回已經(jīng)批準(zhǔn)的編號(hào)最大的提案的value值。如果acceptor收到一個(gè)編號(hào)為Mn的請(qǐng)求且編號(hào)大于accpetor已經(jīng)響應(yīng)的所有prepare請(qǐng)求的編號(hào),則它會(huì)將自己已經(jīng)批準(zhǔn)過的編號(hào)最大的提案值反饋給proposer,同時(shí)acceptor承諾不會(huì)再接受編號(hào)比Mn小的提案。(優(yōu)化:忽略編號(hào)小于已批準(zhǔn)的提案的請(qǐng)求)。如果proposer收到了集合至少一半的響應(yīng),則會(huì)發(fā)送一個(gè)針對(duì)Mn Vn的accept請(qǐng)求給Accpetor。Vn為收到的所有響應(yīng)中編號(hào)最大的提案的值。如果響應(yīng)不包括值,則可以由proposer選擇任意值。然后就是accpet階段,accpet階段是接受提案的要求。當(dāng)Acceptor收到accpet請(qǐng)求后,只要未收到任何編號(hào)大于Mn的prepare請(qǐng)求,則通過該提案。優(yōu)化:為了避免死循環(huán),比如兩個(gè)proposer一次提出一系列編號(hào)遞增的提案,可以產(chǎn)生一個(gè)主proposer,提案只能由主proposer負(fù)責(zé)提出。paxos算法的應(yīng)用:chubby(分布式鎖服務(wù)、GFS中master選舉)。六、說說一致性哈希算法?https://juejin.im/post/5ae1476ef265da0b8d419ef2
為什么會(huì)發(fā)生誤判:假如此時(shí)再查詢X3這個(gè)元素是否屬于集合,通過3個(gè)哈希函數(shù)計(jì)算后的位置數(shù)為 2,7,11 ,而這時(shí)這3個(gè)位置都為1,BF會(huì)認(rèn)為X3屬于集合,這樣豈不是誤判了。
漏判:會(huì)發(fā)生誤判但一定不會(huì)發(fā)生漏判,因?yàn)檎麄€(gè)過程不存在將 1 改為 0的情況。
影響誤判率的因素:1.集合大小 n。因?yàn)榧蟦越大,其它條件固定的情況下,位數(shù)組中就會(huì)有更多比例的位置被設(shè)成1,誤判率就會(huì)增大。2. 哈希函數(shù)的個(gè)數(shù)k。個(gè)數(shù)越多,位數(shù)組中更多比例的位置被設(shè)置為1,即增大了 誤判率。但在查詢時(shí),顯然個(gè)數(shù)越多的時(shí)候誤判率會(huì)越低。3. 位數(shù)組的大小 m。位數(shù)組大小 m越大,那么在 n和k固定的情況下,位數(shù)組中剩余0的比特位就越高,誤判率就會(huì)減小。
已知 k,n,m 即可計(jì)算出對(duì)應(yīng)的誤判率。已知 n,m 最優(yōu)的哈希函數(shù)個(gè)數(shù)為:k = n/m * ln2已知集合大小n,并設(shè)定好誤判率 p, 問:m的大小如何確定?m = - n*lnp / (ln2)^2
缺點(diǎn):無法刪除集合成員,只能增加成員并對(duì)其查詢。改進(jìn):計(jì)數(shù) BF (Counting Bloom Filter)
思考:為什么基本BF無法實(shí)現(xiàn)刪除?答:其基本信息單位是 1 個(gè)比特位。所以只能表達(dá)兩種狀態(tài)。計(jì)數(shù)BF 的 基本信息單元 由多個(gè)比特位組成,一般為3到4個(gè)。
使用過程:將集合成員加入 位數(shù)組時(shí),根據(jù)k個(gè)哈希 函數(shù)進(jìn)行計(jì)算,只需要將原先的數(shù)值 +1 即可。查詢集合成員時(shí),只要對(duì)應(yīng)位置的信息單元都不為 0 ,即判定該成員屬于集合。
刪除成員:只要將對(duì)應(yīng)位置的計(jì)數(shù) -1 即可。改進(jìn)的代價(jià):位數(shù)組大小倍數(shù)增加。另外存在計(jì)數(shù)溢出的可能,因?yàn)楸忍匚槐磉_(dá)能力仍然有限,計(jì)數(shù)很大的時(shí)候存在計(jì)數(shù)溢出的問題。
1.父類靜態(tài)變量初始化。
2.父類靜態(tài)代碼塊。
3.子類靜態(tài)變量初始化。
4.子類靜態(tài)語句塊。
5.父類變量初始化。
6.父類代碼塊。
7.父類構(gòu)造函數(shù)。
8.子類變量初始化。
9.子類語句塊。
10.子類構(gòu)造函數(shù)。
static {
name="大數(shù)據(jù)肌肉猿";
}
private static String name=null;
上面這段代碼,把name打印出來是null
-------
private static String name=null;
static {
name="大數(shù)據(jù)肌肉猿";
}
上面這段代碼,把name打印出來是 大數(shù)據(jù)肌肉猿
--------
static {
name="大數(shù)據(jù)肌肉猿";
}
private static String name;
上面這段代碼,把name打印出來是大數(shù)據(jù)肌肉猿由此可見,變量名首先被加載,而賦值的時(shí)候,無論是直接在變量上賦值還是在靜態(tài)代碼塊中賦值,都是按照代碼的順序賦值的。
十、Mysql問的比較少,只問了索引的數(shù)據(jù)結(jié)構(gòu)?
十一、Synchronized 與volatile 關(guān)鍵字的區(qū)別?
Synchronized 解決執(zhí)行控制問題,它會(huì)其它線程獲取當(dāng)前對(duì)象的監(jiān)控鎖,使得當(dāng)前對(duì)象中被Synchronized關(guān)鍵字保護(hù)的代碼塊無法被并發(fā)執(zhí)行,并且Synchronized 還會(huì)創(chuàng)建一個(gè) 內(nèi)存屏障,保證了所有CPU操作結(jié)果都會(huì)直接刷到主存中去,從而保證了可見性。
內(nèi)存可見:控制的是線程執(zhí)行結(jié)果在內(nèi)存中對(duì)其它線程的可見性,根據(jù)Java內(nèi)存模型的實(shí)現(xiàn),Java線程在具體執(zhí)行時(shí),會(huì)先拷貝主存中的數(shù)據(jù) 到線程本地(CPU緩存),操作完成后再把結(jié)果從線程刷到主存中;
volatile 解決了內(nèi)存可見,所有對(duì)volatile關(guān)鍵字的讀寫都會(huì)直接刷到主存中去,保證了變量的可見性,適用于對(duì)變量可見性有要求而對(duì)讀取順序沒有要求的場(chǎng)景。
兩者區(qū)別:1. volatile 不會(huì)造成線程的阻塞,Synchronized 會(huì)造成線程的阻塞。2. volatile僅能使用在變量級(jí)別,Synchronized 可以使用在變量,方法,類級(jí)別上。3. volatile 標(biāo)記的變量不會(huì)被編譯器優(yōu)化,Synchronized標(biāo)記的變量會(huì)被編譯器優(yōu)化。4. Volatile 僅能保證變量的修改可見性,不能保證原子性,而Synchronized 可以保證變量修改的可見性和原子性。5. Volatile本質(zhì)告訴JVM 當(dāng)前變量在寄存器(工作內(nèi)存)中的值是不確定的,需要從主存中去讀取 ,Synchronized則是鎖定當(dāng)前變量,只有當(dāng)前線程可以訪問該變量,其它線程不可以。
BlockingQueue接口定義了一種阻塞的FIFO queue,每一個(gè)BlockingQueue都有一個(gè)容量,讓容量滿時(shí)往BlockingQueue中添加數(shù)據(jù)時(shí)會(huì)造成阻塞,當(dāng)容量為空時(shí)取元素操作會(huì)阻塞。
ArrayBlockingQueue實(shí)現(xiàn)的隊(duì)列中的鎖是沒有分離的,即生產(chǎn)和消費(fèi)用的是同一個(gè)鎖;
這題留言區(qū)求解答!!
推薦閱讀:
喜歡我可以給我設(shè)為星標(biāo)哦

好文章,我?在看?

