sequentialleader演算法中

⑴ zookeeper有什麼功能，選舉演算法如何進行

選舉機制(FastLeaderElection演算法)：sid最大且被超過集群中超過半數的機器擁護就會成為leader. 所以只有兩種情況無法選出leader： 整個集群只有2台伺服器（注意不是只剩2台，而是集群的總節點數為2） 整個集群超過半數機器掛掉。 所謂的偶數問題...

⑵ 問幾個關於計算機名人的問題

第一個不知道

悼念偉大的計算機科學家Edsger Wybe Dijkstra

又是一篇關於EWD的文章，

共享一下。

摘自孟岩的blog

悼念偉大的計算機科學家Edsger Wybe Dijkstra

2002年8月8日，我象往常一樣查看自己在extremeprogramming電子小組上訂閱的newsletter。突然看到這個小組上的稀客、OO教父Grady Booch的發言，題目是Dijkstra。我以為大家在討論Dijkstra教授提出的什麼難題，定睛一看，才知道是一篇類似生平介紹式的訃告——在與癌症進行了多年的斗爭之後，偉大的荷蘭計算機科學家Edsger Wybe Dijkstra已經於2002年8月6日在荷蘭Nuenen自己的家中與世長辭！終年72歲。

原來如此！

這個Dijkstra，就是那個提出"goto有害論"的Dijkstra，就是那個提出信號量和PV原語，解決了有趣的"哲學家聚餐"問題的Dijkstra，那個Dijkstra最短路徑演算法的創造者，第一個Algol 60編譯器的設計者和實現者，THE操作系統的設計者和開發者，那個與D. E. Knuth並稱為我們這個時代最偉大的計算機科學家的人。

阿蘭圖靈的自殺是在辦個世紀之前，馮諾依曼去世也已經多年，作為這個相對新興的行當中的從業者，我們似乎已經很習慣於從相信，從書上讀到的每個名字都是仍然在世的活生生的人，都是我們這個時代的驕傲。無論是仍然健碩的D. E. Knuth，Fred Brooks，Dennis Ritchie, Ken Thompson, Brian Kernighan, 還是正當盛年的Bjarne Stroustrup，Grady Booch，Steve McConnell, Andy Koenig, Robert Martin, Kent Becker, Martin Fowler, James Gosling, 再或者是青春年少，意氣風發的Linus Trovalds，Andrei Alexandrescu，我們似乎都習慣於認為，只要一封email，這些書本上的名字就會立刻成為你的朋友。Internet把地球變成了一個大村莊，每個人的距離都那麼的近。

但是可惜，Internet卻無法縮短跨越生與死的冥界。今天，一顆真正的巨星在我們的眼前隕落！作為一名普通的程序員，我從內心感到惋惜和悲痛。這種悲痛，兩年半前在我最初得知Richard Stevens的逝世時，也曾感受過，然而卻不如今天來得這么強烈。畢竟，當我對編程還是懵懵懂懂的時候，就知道有個叫Dijkstra的人勸告大家不要濫用goto，而在那之前，goto在我看來就是編程的全部奧秘所在。之後我在學習演算法、數據結構、操作系統等課程的時候，Dijkstra這個名字一次又一次從書里跳出來，我對於這個名字的崇敬也越來越深。我知道他晚年瘋狂的迷戀C++，這也幾乎是我這個C++ Fan所能感受到的最大榮幸。我曾想過，有朝一日，我會給他寫一封email，什麼也不說，只想表達我個人對他的感謝和敬意。沒想到，如今連這個機會也沒有了！

Dijkstra引導了並且將繼續引導這個星球上所有的程序員，他的貢獻和影響將與世長存，讓我們祝他安息！

【附】Grady Booch對Dijkstra的介紹

> Professor Edsger Wybe Dijkstra, a noted pioneer of the science and
> instry of computing, died after a long struggle with cancer on 6
> August 2002 at his home in Nuenen, the Netherlands.
>
> Dijkstra was born in 1930 in Rotterdam, The Netherlands, the son of a
> chemist father and a mathematician mother. He graated from the
> Gymnasium Erasmianum in Rotterdam and obtained degrees in mathematics
> and theoretical physics from the University of Leyden and a Ph.D. in
> computing science from the University of Amsterdam. He worked as a
> programmer at the Mathematisch Centrum, Amsterdam, 1952-62; was
> professor of mathematics, Eindhoven University of Technology,
> 1962-1984; and was a Burroughs Corporation research fellow, 1973-1984.
> He held the Schlumberger Centennial Chair in Computing Sciences at the
> University of Texas at Austin, 1984-1999, and retired as Professor
> Emeritus in 1999.
>
> Dijkstra is survived by his wife of over forty years, Maria (Ria) C.
> Dijkstra Debets, by three children, Marcus J., Femke E., and computer
> scientist Rutger M. Dijkstra, and by two grandchildren.
>
> Dijkstra was the 1972 recipient of the ACM Turing Award, often viewed
> as the Nobel Prize for computing. He was a member of the Netherlands
> Royal Academy of Arts and Sciences, a member of the American Academy
> of Arts and Sciences, and a Distinguished Fellow of the British
> Computer Society. He received the 1974 AFIPS Harry Goode Award, the
> 1982 IEEE Computer Pioneer Award, and the 1989 ACM SIGCSE Award for
> Outstanding Contributions to Computer Science Ecation. Athens
> University of Economics awarded him an honorary doctorate in 2001. In
> 2002, the C&C Foundation of Japan recognized Dijkstra "for his
> pioneering contributions to the establishment of the scientific basis
> for computer software through creative research in basic software
> theory, algorithm theory, structured programming, and semaphores".
>
> Dijkstra is renowned for the insight that mathematical logic is and
> must be the basis for sensible computer program construction and for
> his contributions to mathematical methodology. He is responsible for
> the idea of building operating systems as explicitly synchronized
> sequential processes, for the formal development of computer programs,
> and for the intellectual foundations for the disciplined control of
> nondeterminacy. He is well known for his amazingly efficient shortest
> path algorithm and for having designed and coded the first Algol 60
> compiler. He was famously the leader in the abolition of the GOTO
> statement from programming.
>
> Dijkstra was a prodigious writer. His entire collection of over
> thirteen hundred written works was digitally scanned and is accessible
> at http://www.cs.utexas.e/users/EWD. He also corresponded regularly
> with hundreds of friends and colleagues over the years --not by email
> but by conventional post. He strenuously preferred the fountain pen to
> the computer in procing his scholarly output and letters.
>
> Dijkstra was notorious for his wit, eloquence, and way with words,
> such as in his remark "The question of whether computers can think is
> like the question of whether submarines can swim"; his advice to a
> promising researcher, who asked how to select a topic for research:
> "Do only what only you can do"; and his remark in his Turing Award
> lecture "In their capacity as a tool, computers will be but a ripple
> on the surface of our culture. In their capacity as intellectual
> challenge, they are without precedent in the cultural history of
> mankind."
>
> Dijkstra enriched the language of computing with many concepts and
> phrases, such as structured programming, separation of concerns,
> synchronization, deadly embrace, dining philosophers, weakest
> precondition, guarded command, the excluded miracle, and the famous
> "semaphores" for controlling computer processes. The Oxford English
> Dictionary cites his use of the words "vector" and "stack" in a
> computing context.
>
> Dijkstra enjoyed playing Mozart for his friends on his Boesendorfer
> piano. He and his wife had a fondness for exploring state and national
> parks in their Volkswagen bus, bbed the Touring Machine, in which he
> wrote many technical papers.
>
> Throughout his scientific career, Dijkstra formulated and pursued the
> highest academic ideals of scientific rigour untainted by commercial,
> managerial, or political considerations. Simplicity, beauty, and
> eloquence were his hallmarks, and his uncompromising insistence on
> elegance in programming and mathematics was an inspiration to
> thousands. He judged his own work by the highest standards and set a
> continuing challenge to his many friends to do the same. For the rest,
> he willingly undertook the role of Socrates, that of a gadfly to
> society, repeatedly goading his native and his adoptive country by
> remarking on the mistakes inherent in fashionable ideas and the
> dangers of time-serving compromises. Like Socrates, his most
> significant legacy is to those who engaged with him in small group
> discussions or scientific correspondence about half-formulated ideas
> and emerging discoveries. Particularly privileged are those who
> attended his reading groups in Eindhoven and Austin, known as the
> "Tuesday Afternoon Clubs".
>
> At Dijkstra's passage, let us recall Phaedo's parting remark about
> Socrates: "we may truly say that of all the men of his time whom we
> have known, he was the wisest and justest and best."

⑶ 大魚吃小魚游戲中用到過哪些演算法

大魚吃小魚游戲中用到過ZooKeeper的演算法。

ZooKeeper是一個分布式的，開放源碼的分布式應用程序協調服務，是Google的Chubby一個開源的實現（Chubby是不開源的），它是集群的管理者，監視著集群中各個節點的狀態根據節點提交的反饋進行下一步合理操作。最終，將簡單易用的介面和性能高效、功能穩定的系統提供給用戶 。

Zookeeper一個最常用的使用場景就是用於擔任服務生產者和服務消費者的注冊中心，服務生產者將自己提供的服務注冊到Zookeeper中心，服務的消費者在進行服務調用的時候先到Zookeeper中查找服務，獲取到服務生產者的詳細信息之後，再去調用服務生產者的內容與數據。

ZooKeeper 的架構圖中我們需要了解和掌握的主要有：

（1）ZooKeeper分為伺服器端（Server） 和客戶端（Client），客戶端可以連接到整個 ZooKeeper服務的任意伺服器上（除非 leaderServes 參數被顯式設置， leader 不允許接受客戶端連接）。

（2）客戶端使用並維護一個 TCP 連接，通過這個連接發送請求、接受響應、獲取觀察的事件以及發送信息。如果這個 TCP 連接中斷，客戶端將自動嘗試連接到另外的 ZooKeeper伺服器。

客戶端第一次連接到 ZooKeeper服務時，可以接受這個連接的 ZooKeeper伺服器會為這個客戶端建立一個會話。當這個客戶端連接到另外的伺服器時，這個會話會被新的伺服器重新建立。

（3）上圖中每一個Server代表一個安裝Zookeeper服務的機器，即是整個提供Zookeeper服務的集群（或者是由偽集群組成）。

⑷ 請教個etcd中的raft演算法問題

etcd是一個高可用的鍵值存儲系統，主要用於共享配置和服務發現。etcd是由CoreOS開發並維護的，靈感來自於 ZooKeeper 和 Doozer，它使用Go語言編寫，並通過Raft一致性演算法處理日誌復制以保證強一致性。Raft是一個來自Stanford的新的一致性演算法，適用於分布式系統的日誌復制，Raft通過選舉的方式來實現一致性，在Raft中，任何一個節點都可能成為Leader。Google的容器集群管理系統Kubernetes、開源PaaS平台Cloud Foundry和CoreOS的Fleet都廣泛使用了etcd。

⑸ cutleader中異形排版演算法是什麼意思

cut leader
切的領導者

⑹ zookeeper怎麼實現分布式鎖

1. 利用節點名稱的唯一性來實現共享鎖
ZooKeeper抽象出來的節點結構是一個和unix文件系統類似的小型的樹狀的目錄結構。ZooKeeper機制規定：同一個目錄下只能有一個唯一的文件名。例如：我們在Zookeeper目錄/test目錄下創建，兩個客戶端創建一個名為Lock節點，只有一個能夠成功。
演算法思路: 利用名稱唯一性，加鎖操作時，只需要所有客戶端一起創建/test/Lock節點，只有一個創建成功，成功者獲得鎖。解鎖時，只需刪除/test/Lock節點，其餘客戶端再次進入競爭創建節點，直到所有客戶端都獲得鎖。
基於以上機制，利用節點名稱唯一性機制的共享鎖演算法流程如圖所示：

該共享鎖實現很符合我們通常多個線程去競爭鎖的概念，利用節點名稱唯一性的做法簡明、可靠。
由上述演算法容易看出，由於客戶端會同時收到/test/Lock被刪除的通知，重新進入競爭創建節點，故存在"驚群現象"。
使用該方法進行測試鎖的性能列表如下：

總結 這種方案的正確性和可靠性是ZooKeeper機制保證的，實現簡單。缺點是會產生「驚群」效應，假如許多客戶端在等待一把鎖，當鎖釋放時候所有客戶端都被喚醒，僅僅有一個客戶端得到鎖。

2. 利用臨時順序節點實現共享鎖的一般做法
首先介紹一下，Zookeeper中有一種節點叫做順序節點，故名思議，假如我們在/lock/目錄下創建節3個點，ZooKeeper集群會按照提起創建的順序來創建節點，節點分別為/lock/0000000001、/lock/0000000002、/lock/0000000003。
ZooKeeper中還有一種名為臨時節點的節點，臨時節點由某個客戶端創建，當客戶端與ZooKeeper集群斷開連接，則開節點自動被刪除。
利用上面這兩個特性，我們來看下獲取實現分布式鎖的基本邏輯：
客戶端調用create()方法創建名為「locknode/guid-lock-」的節點，需要注意的是，這里節點的創建類型需要設置為EPHEMERAL_SEQUENTIAL。
客戶端調用getChildren(「locknode」)方法來獲取所有已經創建的子節點，同時在這個節點上注冊上子節點變更通知的Watcher。
客戶端獲取到所有子節點path之後，如果發現自己在步驟1中創建的節點是所有節點中序號最小的，那麼就認為這個客戶端獲得了鎖。
如果在步驟3中發現自己並非是所有子節點中最小的，說明自己還沒有獲取到鎖，就開始等待，直到下次子節點變更通知的時候，再進行子節點的獲取，判斷是否獲取鎖。
釋放鎖的過程相對比較簡單，就是刪除自己創建的那個子節點即可。
上面這個分布式鎖的實現中，大體能夠滿足了一般的分布式集群競爭鎖的需求。這里說的一般性場景是指集群規模不大，一般在10台機器以內。
不過，細想上面的實現邏輯，我們很容易會發現一個問題，步驟4，「即獲取所有的子點，判斷自己創建的節點是否已經是序號最小的節點」，這個過程，在整個分布式鎖的競爭過程中，大量重復運行，並且絕大多數的運行結果都是判斷出自己並非是序號最小的節點，從而繼續等待下一次通知——這個顯然看起來不怎麼科學。客戶端無端的接受到過多的和自己不相關的事件通知，這如果在集群規模大的時候，會對Server造成很大的性能影響，並且如果一旦同一時間有多個節點的客戶端斷開連接，這個時候，伺服器就會像其餘客戶端發送大量的事件通知——這就是所謂的驚群效應。而這個問題的根源在於，沒有找准客戶端真正的關注點。
我們再來回顧一下上面的分布式鎖競爭過程，它的核心邏輯在於：判斷自己是否是所有節點中序號最小的。於是，很容易可以聯想的到的是，每個節點的創建者只需要關注比自己序號小的那個節點。

3、利用臨時順序節點實現共享鎖的改進實現
下面是改進後的分布式鎖實現，和之前的實現方式唯一不同之處在於，這里設計成每個鎖競爭者，只需要關注」locknode」節點下序號比自己小的那個節點是否存在即可。
演算法思路：對於加鎖操作，可以讓所有客戶端都去/lock目錄下創建臨時順序節點，如果創建的客戶端發現自身創建節點序列號是/lock/目錄下最小的節點，則獲得鎖。否則，監視比自己創建節點的序列號小的節點（比自己創建的節點小的最大節點），進入等待。
對於解鎖操作，只需要將自身創建的節點刪除即可。
具體演算法流程如下圖所示:

使用上述演算法進行測試的的結果如下表所示：

該演算法只監控比自身創建節點序列號小(比自己小的最大的節點)的節點，在當前獲得鎖的節點釋放鎖的時候沒有「驚群」。
總結 利用臨時順序節點來實現分布式鎖機制其實就是一種按照創建順序排隊的實現。這種方案效率高，避免了「驚群」效應，多個客戶端共同等待鎖，當鎖釋放時只有一個客戶端會被喚醒。

4、使用menagerie
其實就是對方案3的一個封裝，不用自己寫代碼了。直接拿來用就可以了。
menagerie基於Zookeeper實現了java.util.concurrent包的一個分布式版本。這個封裝是更大粒度上對各種分布式一致性使用場景的抽象。其中最基礎和常用的是一個分布式鎖的實現： org.menagerie.locks.ReentrantZkLock，通過ZooKeeper的全局有序的特性和EPHEMERAL_SEQUENTIAL類型znode的支持，實現了分布式鎖。具體做法是：不同的client上每個試圖獲得鎖的線程，都在相同的basepath下面創建一個EPHEMERAL_SEQUENTIAL的node。EPHEMERAL表示要創建的是臨時znode，創建連接斷開時會自動刪除； SEQUENTIAL表示要自動在傳入的path後面綴上一個自增的全局唯一後綴,作為最終的path。因此對不同的請求ZK會生成不同的後綴，並分別返回帶了各自後綴的path給各個請求。因為ZK全局有序的特性，不管client請求怎樣先後到達，在ZKServer端都會最終排好一個順序，因此自增後綴最小的那個子節點，就對應第一個到達ZK的有效請求。然後client讀取basepath下的所有子節點和ZK返回給自己的path進行比較，當發現自己創建的sequential node的後綴序號排在第一個時，就認為自己獲得了鎖；否則的話，就認為自己沒有獲得鎖。這時肯定是有其他並發的並且是沒有斷開的client/線程先創建了node。

⑺ etcd是什麼東西它和ZooKeeper有什麼區別

• etcd
  

1. etcd作為最近很火的一個高可用性?鍵值對服務發現系統被Kubernetes等系統廣泛使用

2. 他相比與zookeeper來說更加簡單，在面對較小集群時可能會效率更高些?，而且他的編寫語言Go本身就是一種多線程編程語言，確實有很大吸引人的地方（雖然我不懂Go語言，但是在學習docker時也是一睹其風采了）

3. 在Raft中，任何時候一個伺服器可以扮演下面角色之一：

   Leader: 處理所有客戶端交互，日誌復制等，一般一次只有一個Leader.

   Follower: 類似選民，完全被動

   Candidate候選人: 類似Proposer律師，可以被選為一個新的領導人。

4. leader選舉階段

5. 消息同步階段

6. Leader要求Followe遵從他的指令，都將這個新的日誌內容追加到他們各自日誌中：

7. 大多數follower伺服器將日誌寫入磁碟文件後，確認追加成功，發出Commited Ok:

8. 在下一個心跳heartbeat中，Leader會通知所有Follwer更新commited 項目。對於每個新的日誌記錄，重復上述過程。

• zookeeper：

1. zookeeper是基於paxos的簡化版zab，我覺得確實很難理解?，以前看了好多遍《從paxos到zookeper》才感覺似懂非懂了，然而過了幾個月發現又一臉蒙蔽了，在這里在整理一下（僅表示我自己的理解）

2. ZAB協議中存在著三種狀態，每個節點都屬於以下三種中的一種：

   Looking ：系統剛啟動時或者Leader崩潰後正處於選舉狀態

   Following ：Follower節點所處的狀態，Follower與Leader處於數據同步階段；

   Leading ：Leader所處狀態，當前集群中有一個Leader為主進程；

3. 在開始時，所有的節點都是looking狀態並且每個節點都希望自己能成為leader節點，所有每個節點都會向集群中發送一個提案內容是選取自己作為leader節點，提案編號是ZXID(ZAB協議中使用ZXID作為事務編號，ZXID為64位數字，低32位為一個遞增的計數器，每一個客戶端的一個事務請求時Leader產生新的事務後該計數器都會加1，高32位為Leader周期epoch編號，當新選舉出一個Leader節點時Leader會取出本地日誌中最大事務Proposal的ZXID解析出對應的epoch把該值加1作為新的epoch，將低32位從0開始生成新的ZXID；ZAB使用epoch來區分不同的Leader周期),如果得到的提案的zxid比自己的大則說明發出這個題案的節點數據更新，則進行同意的投票，否則繼續投自己，先得到多數的同意的節點當選為leader

4. 現在leader就可以進行管理了，zookeeper也是兩段提交的實現，客戶端提交事務請求時Leader節點為每一個請求生成一個事務Proposal，將其發送給集群中所有的Follower節點，收到過半Follower的反饋後開始對事務進行提交，ZAB協議使用了原子廣播協議