分布式資料庫查詢演算法

『壹』 關於軟考中資料庫系統工程師

資料庫系統工程師級考試大綱
一、考試說明
1.考試要求
（1）掌握計算機體系結構以及各主要部件的性能和基本工作原理；
（2）掌握操作系統、程序設計語言的基礎知識，了解編譯程序的基本知識；
（3）熟練掌握常用數據結構和常用演算法；
（4）熟悉軟體工程和軟體開發項目管理的基礎知識；
（5）熟悉計算機網路的原理和技術；
（6）掌握資料庫原理及基本理論；
（7）掌握常用的大型資料庫管理系統的應用技術；
（8）掌握資料庫應用系統的設計方法和開發過程；
（9）熟悉資料庫系統的管理和維護方法，了解相關的安全技術；
（10）了解資料庫發展趨勢與新技術；
（11）掌握常用信息技術標准、安全性，以及有關法律、法規的基本知識；
（12）了解信息化、計算機應用的基礎知識；
（13）正確閱讀和理解計算機領域的英文資料。
2. 通過本考試的合格人員能參與應用信息系統的規劃、設計、構建、運行和管理，能按照用戶需求，設計、建立、運行、維護高質量的資料庫和數據倉庫；作為數據管理員管理信息系統中的數據資源，作為資料庫管理員建立和維護核心資料庫；擔任資料庫系統有關的技術支持，同時具備一定的網路結構設計及組網能力；具有工程師的實際工作能力和業務水平，能指導計算機技術與軟體專業助理工程師（或技術員）工作。
3. 本考試設置的科目包括
（1）信息系統知識，考試時間為150分鍾，筆試；
（2）資料庫系統設計與管理，考試時間為150分鍾，筆試。
二、考試范圍
考試科目1：信息系統知識
1. 計算機系統知識
1.1 硬體知識
1.1.1 計算機體系結構和主要部件的基本工作原理
•CPU和存儲器的組成、性能、基本工作原理
•常用I/O設備、通信設備的性能，以及基本工作原理
•I/O介面的功能、類型和特點
•CISC/RISC，流水線操作，多處理機，並行處理
1.1.2 存儲系統
•虛擬存儲器基本工作原理，多級存儲體系
•RAID類型和特性
1.1.3 安全性、可靠性與系統性能評測基礎知識
•診斷與容錯
•系統可靠性分析評價
• 計算機系統性能評測方法
1.2 數據結構與演算法
1.2.1 常用數據結構
•數組（靜態數組、動態數組）
•線性表、鏈表（單向鏈表、雙向鏈表、循環鏈表）
•棧和隊列
•樹（二叉樹、查找樹、平衡樹、遍歷樹、堆）、圖、集合的定義、存儲和操作
•Hash（存儲位置計算、碰撞處理）
1.2.2 常用演算法
•排序演算法、查找演算法、數值計算、字元串處理、數據壓縮演算法、遞歸演算法、圖的相關演算法
•演算法與數據結構的關系，演算法效率，演算法設計，演算法描述（流程圖、偽代碼、決策表），演算法的復雜性
1.3 軟體知識
1.3.1 操作系統知識
•操作系統的類型、特徵、地位、內核（中斷控制）、進程、線程概念
•處理機管理（狀態轉換、同步與互斥、信號燈、分時輪轉、搶占、死鎖）
•存儲管理（主存保護、動態連接分配、分段、分頁、虛存）
•設備管理（I/O控制、假離線、磁碟調度）
•文件管理（文件目錄、文件的結構和組織、存取方法、存取控制、恢復處理、共享和安全）
•作業管理（作業調度、作業控制語言（JCL）、多道程序設計）
•漢字處理，多媒體處理，人機界面
•網路操作系統和嵌入式操作系統基礎知識
•操作系統的配置
1.3.2 程序設計語言和語言處理程序的知識
• 匯編、編譯、解釋系統的基礎知識和基本工作原理
• 程序設計語言的基本成分：數據、運算、控制和傳輸，程序調用的實現機制
• 各類程序設計語言的主要特點和適用情況
1.4 計算機網路知識
•網路體系結構（網路拓撲、OSI/RM、基本的網路協議）
•傳輸介質，傳輸技術，傳輸方法，傳輸控制
•常用網路設備和各類通信設備
•Client/Server結構、Browser/Server結構、Browser/Web/Datebase結構
•LAN拓撲，存取控制，LAN的組網，LAN間連接，LAN-WAN連接
•網際網路基礎知識及應用
•網路軟體
•網路管理
•網路性能分析
•網路有關的法律、法規
2. 資料庫技術
2.1 資料庫技術基礎
2.1.1 資料庫模型
•資料庫系統的三級模式（概念模式、外模式、內模式），兩級映像（概念模式/外模式、外模式/內模式）
•資料庫模型：數據模型的組成要素，概念數據模型ER圖（實體、屬性、關系），邏輯數據模型（關系模型、層次模型、網路模型）
2.1.2 資料庫管理系統的功能和特徵
•主要功能（資料庫定義、資料庫操作、資料庫控制、事務管理、用戶視圖）
•特徵（確保數據獨立性、資料庫存取、同時執行過程、排它控制、故障恢復、安全性、完整性）
•RDB（關系資料庫），OODB（面向對象資料庫），ORDB（對象關系資料庫），NDB（網狀資料庫）
•幾種常用Web資料庫的特點
2.1.3 資料庫系統體系結構
• 集中式資料庫系統
• Client/Server資料庫系統
• 並行資料庫系統
• 分布式資料庫系統
• 對象關系資料庫系統
2.2 數據操作
2.2.1 關系運算
•關系代數運算（並、交、差、笛卡兒積、選擇、投影、連接、除）
•元組演算
•完整性約束
2.2.2 關系資料庫標准語言（sql）
•SQL的功能與特點
•用SQL進行數據定義（表、視圖、索引、約束）
•用SQL進行數據操作（數據檢索、數據插入/刪除/更新、觸發控制）
•安全性和授權
•程序中的API，嵌入SQL
2.3 資料庫的控制功能
•資料庫事務管理（ACID屬性）
•資料庫備份與恢復技術（UNDO、REDO）
•並發控制
2.4 資料庫設計基礎理論
2.4.1 關系資料庫設計
•函數依賴
•規范化（第一範式、第二範式、第三範式、BC範式、第四範式、第五範式）
•模式分解及分解應遵循的原則
2.4.2 對象關系資料庫設計
•嵌套關系、 復雜類型，繼承與引用類型
•與復雜類型有關的查詢
•SQL中的函數與過程
•對象關系
2.5 數據挖掘和數據倉庫基礎知識
•數據挖掘應用和分類
•關聯規則、聚類
•數據倉庫的成分
•數據倉庫的模式
2.6 多媒體基本知識
2.6.1 多媒體技術基本概念
•多媒體系統基礎知識
•常用多媒體文件格式
2.6.2 多媒體壓縮編碼技術
•多媒體壓縮編碼技術
•統計編碼
•預測編碼
•編碼的國際標准
2.6.3多媒體技術應用
•簡單圖形的繪制，圖像文件的處理方法
•音頻和視頻信息的應用
•多媒體應用開發過程
2.7 系統性能知識
•性能計算（響應時間、吞吐量、周轉時間）
•性能指標和性能設計
•性能測試和性能評估
2.8 計算機應用基礎知識
•信息管理、數據處理、輔助設計、科學計算，人工智慧等基礎知識
•遠程通信服務及相關通信協議基礎知識
3. 系統開發和運行維護知識
3.1 軟體工程、軟體過程改進和軟體開發項目管理知識
•軟體工程知識
•軟體開發生命周期階段目標和任務
•軟體開發項目基礎知識（時間管理、成本管理、質量管理、人力資源管理、風險管理等）及其常用管理工具
•主要的軟體開發方法（生命周期法、原型法、面向對象法、CASE）
•軟體開發工具與環境知識
•軟體質量管理基礎知識
•軟體過程改進基礎知識
•軟體開發過程評估、軟體能力成熟度評估的基礎知識
3.2 系統分析基礎知識
•系統分析的目的和任務
•結構化分析方法（數據流圖（DFD）和數據字典（DD），實體關系圖（ERD），描述加工處理的結構化語言）
•統一建模語言（UML）
•系統規格說明書
3.3 系統設計知識
•系統設計的目的和任務
•結構化設計方法和工具（系統流程圖、HIPO圖、控制流程圖）
•系統總體結構設計（總體布局，設計原則，模塊結構設計，數據存取設計，系統配置方案）
•系統詳細設計（代碼設計、資料庫設計、用戶界面設計、處理過程設計）
•系統設計說明書
3.4 系統實施知識
•系統實施的主要任務
•結構化程序設計、面向對象程序設計、可視化程序設計
•程序設計語言的選擇、程序設計風格
•系統測試的目的、類型，系統測試方法（黑盒測試、白盒測試、灰盒測試）
•測試設計和管理（錯誤曲線、錯誤排除、收斂、注入故障、測試試用例設計、系統測試報告）
•系統轉換基礎知識
3.5 系統運行和維護知識
•系統運行管理知識
•系統維護知識
•系統評價知識
4. 安全性知識
•安全性基本概念（網路安全、操作系統安全、資料庫安全）
•計算機病毒的防治，計算機犯罪的防範，容災
•訪問控制、防闖入、安全管理措施
•加密與解密機制
•風險分析、風險類型、抗風險措施和內部控制
5.標准化知識
•標准化意識，標准化的發展，標准出台過程
•國際標准、國家標准、行業標准、企業標准基本知識
•代碼標准、文件格式標准、安全標准軟體開發規范和文檔標准
•標准化機構
6.信息化基礎知識
•信息化意識
•全球信息化趨勢、國家信息化戰略、企業信息化戰略和策略
•有關的法律、法規
•遠程教育、電子商務、電子政務等基礎知識
•企業信息資源管理基礎知識
7.計算機專業英語
•掌握計算機技術的基本詞彙
•能正確閱讀和理解計算機領域的英文資料
考試科目2：資料庫系統設計與管理
1.資料庫設計
1.1理解系統需求說明
•了解用戶需求、確定系統范圍
•確定應用系統資料庫的各種關系
•現有環境與新系統環境的關系
•新系統中的數據項、數據字典、數據流
1.2 系統開發的准備
•選擇開發方法，准備開發環境，制訂開發計劃
1.3 設計系統功能
•選擇系統機構，設計各子系統的功能和介面，設計安全性策略、需求和實現方法，制定詳細的工作流和數據流
1.4 資料庫設計
1.4.1 設計數據模型
•概念結構設計（設計ER模型）
•邏輯結構設計（轉換成DBMS所能接收的數據模型）
•評審設計
1.4.2 物理結構設計
•設計方法與內容
•存取方法的選擇
•評審設計與性能預測
1.4.3 資料庫實施與維護
•數據載入與應用程序調試
•資料庫試運行
•資料庫運行與維護
1.4.4 資料庫的保護
•資料庫的備份與恢復
•資料庫的安全性
•資料庫的完整性
•資料庫的並發控制
1.5 編寫外部設計文檔
•編寫系統說明書（系統配置圖、各子系統關系圖、系統流程圖，系統功能說明、輸入輸出規格說明、數據規格說明、用戶手冊框架）
•設計系統測試要求
1.6 設計評審
2. 資料庫應用系統設計
2.1 設計資料庫應用系統結構
•信息系統的架構（如Client/Server）與DBMS
•多用戶資料庫環境（文件伺服器體系結構、Client/Server體系結構）
•大規模資料庫和並行計算機體系結構（SMP、MPP）
•中間件角色和相關工具
•按構件分解，確定構件功能規格以及構件之間的介面
2.2 設計輸入輸出
•屏幕界面設計，設計輸入輸出檢查方法和檢查信息
•資料庫交互與連接（掌握C程序設計語言，以及java、Visual Basic、Visual C＋＋、PowerBuilder、Delphi中任一種開發工具與資料庫互連的方法（如何與資料庫伺服器溝通））
2.3 設計物理數據
•分析事務在資料庫上運行的頻率和性能要求，確定邏輯數據組織方式、存儲介質，設計索引結構和處理方式
•將邏輯數據結構變換成物理數據結構，計算容量（空間代價），確定存取方法（時間效率）、系統配置（維護代價）並進行優化
2.4 設計安全體系
•明確安全等級
•資料庫的登錄方式
•資料庫訪問
•許可（對象許可、命令許可、授權許可的方法）
2.5 應用程序開發
2.5.1 應用程序開發
•選擇應用程序開發平台
•系統實施順序
•框架開發
•基礎小組的程序開發
•源代碼控制
•版本控制
2.5.2 模塊劃分（原則、方法、標准）
2.5.3 編寫程序設計文檔
•模塊規格說明書（功能和介面說明、程序處理邏輯的描述、輸入輸出數據格式的描述）
•測試要求說明書（測試類型和目標，測試用例，測試方法）
2.5.4 程序設計評審
2.6 編寫應用系統設計文檔
•系統配置說明、構件劃分圖、構件間的介面、構件處理說明、屏幕設計文檔、報表設計文檔、程序設計文檔、文件設計文檔、資料庫設計文檔
2.7 設計評審
3. 資料庫應用系統實施
3.1 整個系統的配置與管理
3.2 常用資料庫管理系統的應用（SQL Server、Oracle、Sybase、DB2、Access或Visual Foxpro）
•創建資料庫
•創建表、創建索引、創建視圖、創建約束、創建UDDT（用戶自定義類型）
•創建和管理觸發器
•建立安全體系
3.3 資料庫應用系統安裝
•擬定系統安裝計劃（考慮費用、客戶關系、雇員關系、後勤關系和風險等因素）
•擬定人力資源使用計劃（組織機構安排的合理性）
•直接安裝（安裝新系統並使系統快速進入運行狀態）
•並行安裝（新舊系統並行運行一段時間）
•階段安裝（經過一系列的步驟和階段使新系統各部分逐步投入運行）
3.4 資料庫應用系統測試
•擬定測試目標、計劃、方法與步驟
•數據載入，准備測試數據
•指導應用程序員進行模塊測試進行驗收
•准備系統集成測試環境測試工具
•寫出資料庫運行測試報告
3.5 培訓與用戶支持
4.資料庫系統的運行和管理
4.1 資料庫系統的運行計劃
•運行策略的確定
•確定資料庫系統報警對象和報警方式
•資料庫系統的管理計劃（執行，故障/恢復，安全性，完整性，用戶培訓和維護）
4.2 資料庫系統的運行和維護
•新舊系統的轉換
•收集和分析報警數據（執行報警、故障報警、安全報警）
•連續穩定的運行
•資料庫維護（資料庫重構、安全視圖的評價和驗證、文檔維護）
•資料庫系統的運行統計（收集、分析、提出改進措施）
•關於運行標准和標准改進一致性的建議
•資料庫系統的審計
4.3 資料庫管理
•數據字典和數據倉庫的管理
•數據完整性維護和管理（實體完整性、參照完整性）
•資料庫物理結構的管理（保證數據不推遲訪問）
•資料庫空間及碎片管理
•備份和恢復（順序、日誌（審計痕跡）、檢查點）
•死鎖管理（集中式、分布式）
•並發控制（可串列性、鎖機制、時間戳、優化）
•數據安全性管理（加密、安全、訪問控制、視圖、有效性確認規則）
•資料庫管理員（DBA）職責
4.4 性能調整
•SQL語句的編碼檢驗
•表設計的評價
•索引的改進
•物理分配的改進
•設備增強
•資料庫性能優化
4.5 用戶支持
•用戶培訓
•售後服務
5. SQL
5.1 資料庫語言
•資料庫語言的要素
•資料庫語言的使用方式（互動式和嵌入式）
5.2 SQL概述
•SQL語句的特徵
•SQL語句的基本成分
5.3 資料庫定義
•創建資料庫（Create Datebase）、創建表（Create Table）
•定義數據完整性
•修改表（Alter Table）、刪除表（Drop Table）
•定義索引（Create Index）、刪除索引（Drop Index）
•定義視圖（Create View）、刪除視圖（Drop View）、更新視圖
5.4 數據操作
•Select語句的基本機構
•簡單查詢
•SQL中的選擇、投影
•字元串比較，涉及空值的比較
•日期時間，布爾值，輸出排序
•多表查詢
•避免屬性歧義
•SQL中的連接、並、交、差
•SQL中的元組變數
•子查詢
5.5 完整性控制與安全機制
•主鍵（Primary Key）約束
•外鍵（Foreign Key）約束
•屬性值上的約束（Null、Check、Create Domain）
•全局約束（Create Assertions）
•許可權、授權（Grant）、銷權（Revoke）
5.6 創建觸發器（Create Trigger）
5.7 SQL使用方式
•互動式SQL
•嵌入式SQL
•SQL與宿主語言介面（Declare、共享變數、游標、卷游標）
•動態SQL
•API
5.8 SQL 標准化
6. 網路環境下的資料庫
6.1 分布式資料庫
6.1.1 分布式資料庫的概念
•分布式資料庫的特點與目標
6.1.2 分布式資料庫的體系結構
•分布式資料庫的模式結構
•數據分布的策略（數據分片、分布透明性）
•分布式資料庫管理系統
6.1.3 分布式查詢處理和優化
6.1.4 分布式事務管理
•分布式資料庫的恢復（故障、恢復、2段提交、3段提交）
•分布式資料庫的透明性（局部、分裂、復制、處理、並發、執行）
6.1.5 分布式資料庫系統的應用
6.2 網路環境下資料庫系統的設計與實施
•數據的分布設計
•負載均衡設計
•資料庫互連技術
6.3 面向Web的DBMS技術
•三層體系結構
•動態Web網頁
•ASP、JSP、XML的應用
7.資料庫的安全性
7.1 安全性策略的理解
•資料庫視圖的安全性策略
•數據的安全級別（最重要的、重要的、注意、選擇）
7.2 資料庫安全測量
•用戶訪問控制（採用口令等）
•程序訪問控制（包含在程序中的SQL命令限制）
•表的訪問控制（視圖機制）
•控制訪問的函數和操作
•外部存儲數據的加密與解密
8. 資料庫發展趨勢與新技術
8.1 面向對象資料庫（OODBMS）
8.1.1 OODBMS的特徵
8.1.2 面向對象數據模型
•對象結構、對象類、繼承與多重繼承、對象標識、對象包含、對象嵌套
8.1.3 面向對象資料庫語言
8.1.4 對象關系資料庫系統（ORDBMS）
•嵌套關系
•復雜類型
•繼承、引用類型
•與復雜類型有關的查詢
•函數與過程
•面向對象與對象關系
•ORDBMS應用領域
8.2 企業資源計劃（ERP）和資料庫
8.2.1 ERP概述
•基本MRP（製造資源計劃）、閉環MRP、ERP
•基本原理、發展趨勢
•ERP設計的總體思路（一個中心、兩類業務、三條干線）
8.2.2 ERP與資料庫
•運行資料庫與ERP數據模型之間的關系
•運行資料庫與ERP資料庫之間的關系
8.2.3 案例分析
8.3 決策支持系統的建立
•決策支持系統的概念
•數據倉庫設計
•數據轉移技術
•聯機分析處理（OLAP）技術
•企業決策支持解決方案
•聯機事務處理（OLTP）

『貳』 php的memcached分布式hash演算法,如何解決分布不均crc32這個演算法沒辦法把key值均勻的分布出去

memcached的總結和分布式一致性hash
當前很多大型的web系統為了減輕資料庫伺服器負載，會採用memchached作為緩存系統以提高響應速度。
目錄： （http://hounwang.com/lesson.html）
memchached簡介
hash
取模
一致性hash
虛擬節點
源碼解析
參考資料
1. memchached簡介
memcached是一個開源的高性能分布式內存對象緩存系統。
其實思想還是比較簡單的，實現包括server端（memcached開源項目一般只單指server端）和client端兩部分:
server端本質是一個in-memory key-value store，通過在內存中維護一個大的hashmap用來存儲小塊的任意數據，對外通過統一的簡單介面（memcached protocol）來提供操作。
client端是一個library，負責處理memcached protocol的網路通信細節，與memcached server通信，針對各種語言的不同實現分裝了易用的API實現了與不同語言平台的集成。
web系統則通過client庫來使用memcached進行對象緩存。
2. hash
memcached的分布式主要體現在client端，對於server端，僅僅是部署多個memcached server組成集群，每個server獨自維護自己的數據（互相之間沒有任何通信），通過daemon監聽埠等待client端的請求。
而在client端，通過一致的hash演算法，將要存儲的數據分布到某個特定的server上進行存儲，後續讀取查詢使用同樣的hash演算法即可定位。
client端可以採用各種hash演算法來定位server：
取模
最簡單的hash演算法
targetServer = serverList[hash(key) % serverList.size]
直接用key的hash值（計算key的hash值的方法可以自由選擇，比如演算法CRC32、MD5,甚至本地hash系統，如java的hashcode）模上server總數來定位目標server。這種演算法不僅簡單，而且具有不錯的隨機分布特性。
但是問題也很明顯，server總數不能輕易變化。因為如果增加/減少memcached server的數量，對原先存儲的所有key的後續查詢都將定位到別的server上，導致所有的cache都不能被命中而失效。
一致性hash
為了解決這個問題，需要採用一致性hash演算法（consistent hash）
相對於取模的演算法，一致性hash演算法除了計算key的hash值外，還會計算每個server對應的hash值，然後將這些hash值映射到一個有限的值域上（比如0~2^32）。通過尋找hash值大於hash(key)的最小server作為存儲該key數據的目標server。如果找不到，則直接把具有最小hash值的server作為目標server。
為了方便理解，可以把這個有限值域理解成一個環，值順時針遞增。
如上圖所示，集群中一共有5個memcached server，已通過server的hash值分布到環中。
如果現在有一個寫入cache的請求，首先計算x=hash(key)，映射到環中，然後從x順時針查找，把找到的第一個server作為目標server來存儲cache，如果超過了2^32仍然找不到，則命中第一個server。比如x的值介於A~B之間，那麼命中的server節點應該是B節點
可以看到，通過這種演算法，對於同一個key，存儲和後續的查詢都會定位到同一個memcached server上。
那麼它是怎麼解決增/刪server導致的cache不能命中的問題呢？
假設，現在增加一個server F，如下圖
此時，cache不能命中的問題仍然存在，但是只存在於B~F之間的位置（由C變成了F），其他位置（包括F~C）的cache的命中不受影響（刪除server的情況類似）。盡管仍然有cache不能命中的存在，但是相對於取模的方式已經大幅減少了不能命中的cache數量。
虛擬節點
但是，這種演算法相對於取模方式也有一個缺陷：當server數量很少時，很可能他們在環中的分布不是特別均勻，進而導致cache不能均勻分布到所有的server上。
如圖，一共有3台server – 1，2，4。命中4的幾率遠遠高於1和2。
為解決這個問題，需要使用虛擬節點的思想：為每個物理節點（server）在環上分配100～200個點，這樣環上的節點較多，就能抑制分布不均勻。
當為cache定位目標server時，如果定位到虛擬節點上，就表示cache真正的存儲位置是在該虛擬節點代表的實際物理server上。
另外，如果每個實際server的負載能力不同，可以賦予不同的權重，根據權重分配不同數量的虛擬節點。
// 採用有序map來模擬環
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5來計算key和server的hash值
// 計算總權重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 為每個server分配虛擬節點
for ( int i = 0; i < servers.length; i++ ) {
// 計算當前server的權重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用來控制每個server分配的虛擬節點數量
// 權重都相同時，factor=40
// 權重不同時，factor=40*server總數*該server權重所佔的百分比
// 總的來說，權重越大，factor越大，可以分配越多的虛擬節點
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每個server有factor個hash值
// 使用server的域名或IP加上編號來計算hash值
// 比如server - "172.45.155.25:11111"就有factor個數據用來生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每個hash值生成4個虛擬節點
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在環上保存節點
consistentBuckets.put( k, servers[i] );
}
}
// 每個server一共分配4*factor個虛擬節點
}
// 採用有序map來模擬環
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5來計算key和server的hash值
// 計算總權重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 為每個server分配虛擬節點
for ( int i = 0; i < servers.length; i++ ) {
// 計算當前server的權重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用來控制每個server分配的虛擬節點數量
// 權重都相同時，factor=40
// 權重不同時，factor=40*server總數*該server權重所佔的百分比
// 總的來說，權重越大，factor越大，可以分配越多的虛擬節點
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每個server有factor個hash值
// 使用server的域名或IP加上編號來計算hash值
// 比如server - "172.45.155.25:11111"就有factor個數據用來生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每個hash值生成4個虛擬節點
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在環上保存節點
consistentBuckets.put( k, servers[i] );
}
}
// 每個server一共分配4*factor個虛擬節點
}
// 用MD5來計算key的hash值
MessageDigest md5 = MD5.get();
md5.reset();
md5.update( key.getBytes() );
byte[] bKey = md5.digest();

// 取MD5值的低32位作為key的hash值
long hv = ((long)(bKey[3]&0xFF) << 24) | ((long)(bKey[2]&0xFF) << 16) | ((long)(bKey[1]&0xFF) << 8 ) | (long)(bKey[0]&0xFF);

// hv的tailMap的第一個虛擬節點對應的即是目標server
SortedMap tmap = this.consistentBuckets.tailMap( hv );
return ( tmap.isEmpty() ) ? this.consistentBuckets.firstKey() : tmap.firstKey();
更多問題到問題求助專區（http://bbs.hounwang.com/）

『叄』 分布式資料庫：2PL滿足可串列化嗎2PL和樂觀演算法的根本差別是什麼

1 滿足，2PL和樂觀演算法的思想不同，2PL的目的在於在事先預防沖突的發生，而樂觀演算法是在沖突發生之後再來進行彌補。
R*窮舉出所有可能的JN序列和全部可能的JN方法.只傳輸需要的元組，一次一個元組，每次傳輸都需要交換信息，無需臨時存儲器，適合高速網路

『肆』 它用分布式資料庫替代Oracle、SAS，讓銀行告別西方軟體「霸凌」

WPS成功上市代表了信息化企業軟體國產化的趨勢。在雷濤看來，WPS不是簡單復制後替代Windows office，而是找到了下一代產品需求。

以往無論是運營商還是銀行核心系統，大架構都壟斷在西方的 IOE（IBM、Oracle、EMC）這三座大山裡。直到2008年阿里提出去「IOE」運動，開始助推信息化軟體國產化浪潮。

天雲數據就是其中最早一批入場者。2010年為了建立中國完整的雲計算產業鏈，中國寬頻之父田溯寧投資建設雲基地昌燃，天雲數據便由此孵化，初備雛形。

2015年，雷濤帶領創始團隊們正式成立天雲數據，率先切入金融領域。天雲提供了國內領先的國產HTAP資料庫Hubble，完成了「去IOE」中最困難的部分，替代金融A類核心系統慣用的西方IOE架構，在銀行的聯機事務中解決A類核心系統減負問題。此外，為了降低AI使用門檻，天雲數據還推出AI PaaS平台MaximAI，逐步將數據價值逐漸擴展到能源、醫葯、軍事等其它行業。

目前天雲數據有70多家行業內大企業客戶，單筆合同200-500萬，純軟體年營收過億。

融資方面，天雲數據2018年曾獲得曦域資本、華映資本B輪1億人民幣投資。

作為行業老兵，雷濤在北美跨國公司有20多年的技術管理經驗， 2005年便入席SNIA存儲游槐工業協會中國區技術委員會聯合主席，CCF中國計算機學會大數據專委會委員。

2011年在雲基地時期，雷濤和創始團隊通過BDP大數據平台負責了眾多運營商業務，如聯通的數據魔方、移動總部、南方基地等，2015年天雲數據正式獨立後，雷濤為了避免同業競爭，選擇先聚焦在金融領域。

「天雲數據的目標是替代 Oracle 和 SAS 」。雲基地時期的積累讓天雲數據一開始就有高起點，首單就接下了光大銀行的核心系統——OLTP線交易系統。比如銀行能在全國所有營業廳實時實現OOTD交易，實時查詢存錢取錢數額，整個環節涉及的技術都是天雲數據早期對Oracle的一些替代。

但之後在多次的項目操作過程中雷濤發現，在幾百萬條交易規格的強一致性下，數據的移動性、計算框架的變化、聯機事務同時要做大規模並行計算，這對計算場景的神迅友通用性、即時性和全量數據要求極高，傳統 Oracle架構根本無法適應。

「在Oracle架構之上，還需要升級滿足新需求」。

於是天雲數據自主研發HTAP國產分布式資料庫Hubble。與傳統 IT 架構處理失誤需要聯機分析和分開處理不同，HTAP 資料庫能夠在一份數據上同時支撐業務系統運行並做 OLAP 場景，避免在線與離線資料庫之間大量的數據交互，為系統減負。

HTAP國產分布式資料庫Hubble替代了Oracle一體機,核心表2000餘張80T左右、400億條交易數據、提供56隻服務應用交易、滿足500個用戶並發、500ms交易服務響應、每天在線交易量超200萬、占整個銀行核心交易量的10%，讓銀行面向櫃面系統可提供7*8小時A類實時核心交易，面向手機網銀系統可提供7*24小時A類實時核心交易。

從集中式Oracle切換到分布式HTAP，也解決了資料庫擴展性的問題。比如天雲數據讓光大銀行解決了 歷史 數據查詢問題，以往 歷史 查詢只能查到2年前，但在分布式技術上線後，可以查詢15年前所有交易數據，同時讓銀行櫃面系統以及手機APP可以無數人同時查詢。

而在BI逐步轉向AI的過程中，復雜的商業流程經演算法重構。過去要把數據拿到SAS平台先分析，一層一層地把數據提出來搭建。但現在通過分布式技術，流程趨於扁平化，可以實現毫秒級的服務響應。

天雲數據一開始就撬動的是行業頭部資源。目前天雲數據有光大銀行、興業銀行、中信銀行、中泰證券、中國石油、國家統計局等70餘家行業內大企業客戶，分布在金融、能源、醫葯、政府軍事等領域，單筆合同級別超百萬

針對每個垂直行業，天雲數據都會成立一個子公司來專注賽道。目前天雲數據有160人，技術人員超六成。

在雷濤看來，如果一年600個項目，全是5萬、15萬等碎片化的訂單，公司總是重復滿足初級客戶的簡單需求，技術很難沉澱和深入。「在當下成長階段，打造產品需要在用戶想要什麼和你想做什麼中找到平衡」。

對於雷濤而言，專注頭部大B發展有兩大發展潛力。一方面，大B擁有機器學習的普遍能力和實驗室，更容易接受新產品。另一方面，天雲數據交付產品和交付服務的同時也在轉移大B客戶的數據價值。

「AI本身是一個知識生產過程，它能把大型企業規則、流程的經驗價值快速地抽樣出來進行復制，賦能行業內其它客戶甚至類似的其它行業。」

但在頭部客戶更定製化、個性化的情況下，天雲數據是否失去了很強的復制能力？

雷濤解釋到，雖然每個企業要求不盡相同，但都在不大的池子里找資料庫。企業從海量數據中對數據進行遷徙、清洗、去重，可以去找合適的AI方法讓它產生業務的價值，此過程具有通用性。

談到核心壁壘，雷濤認為天雲數據壁壘就是數據的復制價值。

壁壘的構建可分為兩個階段。第一個階段是前沿 科技 本身的壁壘，比的是效率和產品核心價值，誰能夠扎得深和更好的交付，誰就能拔得頭籌。而作為國內最早研發大數據和人工智慧的團隊，天雲數據有一定的技術先發優勢。

第二個階段是推理端的服務。數據資源的價值需要通過機器學習進行提煉，形成知識，進而封裝成推理服務服務於行業。比如某保險公司20年長周期發生的重疾賠付定價上學習出來的特徵和內容能夠快速地移植到保險行業，而頭部大企業客戶給天雲數據帶來很優質的訓練資料庫。

未來AI將引爆萬億級大市場，但目前滲透率不到1%，這給各企業留有眾多機會和想像空間。但無論哪種圈地方式，最終比的是速度、服務的穩定性以及產品化的能力。

『伍』 mysql如何做成分布式

MySQL做分布式需要通過ndb的Cluster來實現。 MySQLCluster是MySQL適合於分布式計算環境的高實用、高冗餘版本。 實現的步驟比較復雜，網路雲案例:《MySQLCluster(MySQL集群)分布式》 下載地址:

『陸』 資料庫分庫分表（二）Twitter-Snowflake（64位分布式ID演算法）分析與JAVA實現

Twitter-Snowflake演算法產生的背景相當簡單，為了滿足Twitter每秒上萬條消息的請求，每條消息都必須分配一條唯一的id，這些id還需要一些大致的順序（方便客戶端排序），並灶核且在掘頃分布式系統中不同機器產生的id必須不同。各種主鍵ID生成策略對比，見 常見分布式主鍵ID生成策略

把 41位的時間前綴 ， 10位的節點標識 ， 12位的sequence 組合在一起。
除了最高位bit標記為不可用以外，其餘三組bit佔位均可浮動，看具體的業務需求而定。 默認情況下41bit的時間戳，1970年算起可以支持該演算法使用到2038年，10bit的工作機器id可以支持1024台機器，序列號支持1毫秒產生4096個自增序列id 。

Snowflake是Twitter在2010年用Scala語言寫的一套主鍵生成策略，用Thrift對外發布主鍵生成服務，其中依賴了Twitter內部的Infrastructure，後來Twitter用 Twitter-server 代替了Snowflake，自2012年起就未更新。見 Twitter-Snowflake項目地址（Tags:snowflake-2010）
之前寫了一個Java的實現，改自網上一個版本: Twitter的分布式自增ID演算法Snowflake實現分析及其Java、Php和Python版 。後來看到當當網的 Sharding-JDBC 分庫分表中間件已實現了此演算法。就直接在其中添隱散掘加了一些新特性，已merge。( 具體實現 , 說明文檔 )
添加3種IdGenerator實現。

用筆記本（i7-3632QM 2.2GHz 四核八線程）測試了下，每秒生成409萬（理論上的峰值），CPU佔用率18.5%。

『柒』 分布式存儲中，怎樣使用paxos演算法保證數據的一致性

在分布式系統中，我們經常遇到多數據副本保持一致的問題，在我們所能找到的資料中該問題講的很籠統，模模糊糊的，把多個問題或分類糅合在一起，難以理解。在思考和翻閱資料後，通俗地把一致性的問題可分解為2個問題：
1、任何一次修改保證數據一致性。
2、多次數據修改的一致性。
在弱一致性的演算法，不要求每次修改的內容在修改後多副本的內容是一致的，對問題1的解決比較寬松，更多解決問題2，該類演算法追求每次修改的高度並發性，減少多副本之間修改的關聯性，以獲得更好的並發性能。例如最終一致性，無所謂每次用戶修改後的多副本的一致性及格過，只要求在單調的時間方向上，數據最終保持一致，如此獲得了修改極大的並發性能。
在強一致性的演算法中，強調單次修改後結果的一致，需要保證了對問題1和問題2要求的實現，犧牲了並發性能。本文是討論對解決問題1實現演算法，這些演算法往往在強一致性要求的應用中使用。
解決問題1的方法，通常有兩階段提交演算法、採用分布式鎖服務和採用樂觀鎖原理實現的同步方式,下面分別介紹這幾種演算法的實現原理。

兩階段提交演算法

在兩階段提交協議中，系統一般包含兩類機器（或節點）：一類為協調者（coordinator），通常一個系統中只有一個；另一類為事務參與者（participants，cohorts或workers），一般包含多個，在數據存儲系統中可以理解為數據副本的個數。兩階段提交協議由兩個階段組成，在正常的執行下，這兩個階段的執行過程如下所述：
階段1：請求階段（commit-request phase，或稱表決階段，voting phase）。
在請求階段，協調者將通知事務參與者准備提交或取消事務，然後進入表決過程。在表決過程中，參與者將告知協調者自己的決策：同意（事務參與者本地作業執行成功）或取消（本地作業執行故障）。
階段2：提交階段（commit phase）。
在該階段，協調者將基於第一個階段的投票結果進行決策：提交或取消。當且僅當所有的參與者同意提交事務協調者才通知所有的參與者提交事務，否則協調者將通知所有的參與者取消事務。參與者在接收到協調者發來的消息後將執行響應的操作。
舉個例子：A組織B、C和D三個人去爬長城：如果所有人都同意去爬長城，那麼活動將舉行；如果有一人不同意去爬長城，那麼活動將取消。用2PC演算法解決該問題的過程如下：
首先A將成為該活動的協調者，B、C和D將成為該活動的參與者。
階段1：A發郵件給B、C和D，提出下周三去爬山，問是否同意。那麼此時A需要等待B、C和D的郵件。B、C和D分別查看自己的日程安排表。B、C發現自己在當日沒有活動安排，則發郵件告訴A它們同意下周三去爬長城。由於某種原因，D白天沒有查看郵件。那麼此時A、B和C均需要等待。到晚上的時候，D發現了A的郵件，然後查看日程安排，發現周三當天已經有別的安排，那麼D回復A說活動取消吧。
階段2：此時A收到了所有活動參與者的郵件，並且A發現D下周三不能去爬山。那麼A將發郵件通知B、C和D，下周三爬長城活動取消。此時B、C回復A「太可惜了」，D回復A「不好意思」。至此該事務終止。
兩階段提交演算法在分布式系統結合，可實現單用戶對文件（對象）多個副本的修改，多副本數據的同步。其結合的原理如下：
1、客戶端（協調者）向所有的數據副本的存儲主機（參與者）發送：修改具體的文件名、偏移量、數據和長度信息，請求修改數據，該消息是1階段的請求消息。
2、存儲主機接收到請求後，備份修改前的數據以備回滾，修改文件數據後，向客戶端回應修改成功的消息。 如果存儲主機由於某些原因（磁碟損壞、空間不足等）不能修改數據，回應修改失敗的消息。
3、客戶端接收發送出去的每一個消息回應，如果存儲主機全部回應都修改成功，向每存儲主機發送確認修改的提交消息；如果存在存儲主機回應修改失敗，或者超時未回應，客戶端向所有存儲主機發送取消修改的提交消息。該消息是2階段的提交消息。
4、存儲主機接收到客戶端的提交消息，如果是確認修改，則直接回應該提交OK消息；如果是取消修改，則將修改數據還原為修改前，然後回應取消修改OK的消息。
5、 客戶端接收全部存儲主機的回應，整個操作成功。
在該過程中可能存在通信失敗，例如網路中斷、主機宕機等諸多的原因，對於未在演算法中定義的其它異常，都認為是提交失敗，都需要回滾，這是該演算法基於確定的通信回復實現的，在參與者的確定回復（無論是回復失敗還是回復成功）之上執行邏輯處理，符合確定性的條件當然能夠獲得確定性的結果哲學原理。

分布式鎖服務

分布式鎖是對數據被外界修改持保守態度，在整個數據處理過程中將數據處於鎖定狀態，在用戶修改數據的同時，其它用戶不允許修改。
採用分布式鎖服務實現數據一致性，是在操作目標之前先獲取操作許可，然後再執行操作，如果其他用戶同時嘗試操作該目標將被阻止，直到前一個用戶釋放許可後，其他用戶才能夠操作目標。分析這個過程，如果只有一個用戶操作目標，沒有多個用戶並發沖突，也申請了操作許可，造成了由於申請操作許可所帶來的資源使用消耗，浪費網路通信和增加了延時。
採用分布式鎖實現多副本內容修改的一致性問題， 選擇控制內容顆粒度實現申請鎖服務。例如我們要保證一個文件的多個副本修改一致， 可以對整個文件修改設置一把鎖，修改時申請鎖，修改這個文件的多個副本，確保多個副本修改的一致，修改完成後釋放鎖；也可以對文件分段，或者是文件中的單個位元組設置鎖， 實現更細顆粒度的鎖操作，減少沖突。
常用的鎖實現演算法有Lamport bakery algorithm （俗稱麵包店演算法）， 還有Paxos演算法。下面對其原理做簡單概述。

Lamport麵包店演算法

是解決多個線程並發訪問一個共享的單用戶資源的互斥問題的演算法。 由Leslie Lamport（英語：Leslie Lamport）發明。
Lamport把這個並發控制演算法可以非常直觀地類比為顧客去麵包店采購。麵包店只能接待一位顧客的采購。已知有n位顧客要進入麵包店采購，安排他們按照次序在前台登記一個簽到號碼。該簽到號碼逐次加1。根據簽到號碼的由小到大的順序依次入店購貨。完成購買的顧客在前台把其簽到號碼歸0. 如果完成購買的顧客要再次進店購買，就必須重新排隊。
這個類比中的顧客就相當於線程，而入店購貨就是進入臨界區獨占訪問該共享資源。由於計算機實現的特點，存在兩個線程獲得相同的簽到號碼的情況，這是因為兩個線程幾乎同時申請排隊的簽到號碼，讀取已經發出去的簽到號碼情況，這兩個線程讀到的數據是完全一樣的，然後各自在讀到的數據上找到最大值，再加1作為自己的排隊簽到號碼。為此，該演算法規定如果兩個線程的排隊簽到號碼相等，則線程id號較小的具有優先權。
把該演算法原理與分布式系統相結合，即可實現分步鎖。

Paxos演算法

該演算法比較熱門，參見WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos演算法解決的問題是一個分布式系統如何就某個值(決議)達成一致。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。節點通信存在兩種模型：共享內存(Shared memory)和消息傳遞(Messages passing)。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。BigTable使用一個分布式數據鎖服務Chubby，而Chubby使用Paxos演算法來保證備份的一致性。

採用樂觀鎖原理實現的同步

我們舉個例子說明該演算法的實現原理。如一個金融系統，當某個操作員讀取用戶的數據，並在讀出的用戶數據的基礎上進行修改時（如更改用戶帳戶余額），如果採用前面的分布式鎖服務機制，也就意味著整個操作過程中（從操作員讀出數據、開始修改直至提交修改結果的全過程，甚至還包括操作員中途去煮咖啡的時間），資料庫記錄始終處於加鎖狀態，可以想見，如果面對幾百上千個並發，這樣的情況將導致怎樣的後果。
樂觀鎖機制在一定程度上解決了這個問題。樂觀鎖，大多是基於數據版本（ Version）記錄機制實現。何謂數據版本？即為數據增加一個版本標識，在基於資料庫表的版本解決方案中，一般是通過為資料庫表增加一個 「version」 欄位來實現。讀取出數據時，將此版本號一同讀出，之後更新時，對此版本號加一。此時，將提交數據的版本數據與資料庫表對應記錄的當前版本信息進行比對，如果提交的數據版本號大於資料庫表當前版本號，則予以更新，否則認為是過期數據。
對於上面修改用戶帳戶信息的例子而言，假設資料庫中帳戶信息表中有一個 version 欄位，當前值為 1 ；而當前帳戶余額欄位（ balance ）為 $100 。
操作員 A 此時將其讀出（version=1 ），並從其帳戶余額中扣除 $50（$100-$50 ）。
在操作員 A 操作的過程中，操作員B也讀入此用戶信息（ version=1 ），並從其帳戶余額中扣除 $20 （ $100-$20 ）。
操作員 A 完成了修改工作，將數據版本號加一（ version=2 ），連同帳戶扣除後余額（ balance=$50 ），提交至資料庫更新，此時由於提交數據版本大於資料庫記錄當前版本，數據被更新，資料庫記錄 version 更新為 2 。
操作員 B 完成了操作，也將版本號加一（ version=2 ）試圖向資料庫提交數據（ balance=$80 ），但此時比對資料庫記錄版本時發現，操作員 B 提交的數據版本號為 2 ，資料庫記錄當前版本也為 2 ，不滿足 「 提交版本必須大於記錄當前版本才能執行更新 「 的樂觀鎖策略，因此，操作員 B 的提交被駁回。這樣，就避免了操作員 B 用基於 version=1 的舊數據修改的結果覆蓋操作員A 的操作結果的可能。
樂觀鎖機制與分布式系統相結合上， 我整理了偽代碼如下：
obj 操作的目標
vlaue 修改的值
atom_update_ver 每個目標上的版本，每次修改該值遞增
set( obj, value)
{
//從每個節點上取出修改前的對象版本
get original_ver = obj.atom_update_ver from each node;
//將值賦到每個節點的obj目標
set obj = value from each node;
//條件修改每個節點的obj版本，目標版本加一
//比較和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功遞歸修改

該演算法未考慮節點下線、失效等問題，在後續我將分析採用樂觀鎖原理實現一致性演算法，解決問題2、節點失效、通信失敗等問題。