一,ldap基本模型
DIT : ldap的樹結構,每個樹上的節點叫entry
DN (Distinguished
Name):從特定節點到樹的根的直接下級的節點的路徑序列為DN,差別于其他節點的名字,相當于節點的絕對路徑,由不同部分的rdn組成
RDN(Relative Distinguished Name): 差別于同層節點的名字叫RDN,相當于相對路徑
Attribute:每個節點屬性都有相應的value,存放在檔案中
objectClass: 對象類(ObjectClass)是屬性的集合,LDAP預想了很多人員組織機構中常見的對象,并将其封裝成對象類。
schema: 對象類、屬性類型、文法分别約定了條目、屬性、值。這些構成了模式(Schema),模式中的每一個元素都有唯一的OID編号
Cursor:遊标,指向查找的目前節點,有向前插入和向後插入兩種方式,通過此遊标可以存/取/删除資料項
search scope :查詢範圍,預設有三種。baseObject:作用域僅限于由命名的條目; singleLevel:baseobject的直接子節點一層; wholeSubtree: baseObject及其所有子樹集合
search filter:分10種操作情況,分為相應的過濾器
and/or/not/equalityMatch/substrings/greaterOrEqual/lessOrEqual/present/approcMarch/extensibleMatch
filterextensible
= ( attr [dnattrs]
[matchingrule] COLON EQUALS assertionvalue )
/ ( [dnattrs]
matchingrule COLON EQUALS assertionvalue )
二,底層搜尋操作
下圖是apacheds和fortress的關系結構圖，有助于我們了解整體架構
執行搜尋權限時的操作
用戶端通過guardian插件,經過guardian接入apacheds,通過傳入的perm資料會在後端提取資訊并通過這些資訊(datasource和component)得到一個自己具有唯一可差別的名稱Dn(getDn),對應于ladp目錄樹的一個節點,儲存在permObjDn中。
根據perm資料的prefix,substring,action形成一個過濾器字元串存在filterbuf中,scope和cookie單獨作為過濾條件傳到search部分。
于此同時拉取存在緩存中的該使用者對應的role和group權限,一并合并到filterbuf字段中。
将所有的過濾資訊建構一個searchcursor,每次把符合條件的目前節點解析到perm中,然後pop出去,進行下一輪查找,最後形成一個permlist
有繼承的情況會包裝成一個組,然後照上面的邏輯再進行一次perm的查詢過濾。ldap把請求資訊封裝成一個searchRequest, 具體結構見連結: https://tools.ietf.org/html/rfc4511
然後經過攔截器,apacheds總共有14個攔截器,search操作一共7個,每個Interceptor的調用會依據它的聲明順序依次執行。
然後接入ldap底層的lmdb,ldap的底層資料庫用的是LMDB搜尋操作,先通過優化器優化查詢語句(通過scan count字段,把索引關聯比較少的查詢節點放在前面)然後根據屬性的比對原則來定義evaluator,在cursor移動時執行設定的evaluate操作,實作節點過濾。最後根據節點的dn長度和接收請求的sortkey來确定傳回順序。
三，ldap底層資料庫
LMDB的全稱是LightningMemory-Mapped Database,即閃電般的記憶體映射資料庫。它檔案結構簡單,一個檔案夾,裡面一個資料檔案,一個鎖檔案。資料随意複制,随意傳輸。它的通路簡單,不需要運作單獨的資料庫管理程序,隻要在通路資料的代碼裡引用LMDB庫,通路時給檔案路徑即可。基于檔案映射IO和B+樹的key-value接口。通過mvcc事務處理保證讀取内容不被修改,進行目錄通路。
lmdb使用mmap,同時在建立env對象時,資料庫已經被整個映射進整個程序空間,是以系統在映射時,會給資料庫檔案保留全部位址空間,進而在根據上述算法擷取真實資料庫,系統觸發缺頁錯誤,進而從資料檔案中擷取整個頁面内容。
cursor對象是進行所有資料庫操作的對象,讀寫都是基于遊标進行。進行讀寫操作時,首先需要根據條件确定頁面位置,進而獲得一個遊标,應用程式根據遊标對象操作資料庫。
搜尋階段分為頁搜尋和cursor搜尋,時從B-Tree根節點檢索,根據key的值,從根節點開始周遊子樹擷取每一層對應的page,在page之内檢索key,再根據B-Tree查找方法确定下一層子節點的page,層層周遊,進而最終确定key的位置或者判斷B-Tree中沒有對應的key。同時将頁面存放到cursor頁堆棧中。這樣cursor将可以重用對應的頁面,為後續進行更新等操作提供便利。
lmdb的結構與底層搜尋參照:http://wiki.dreamrunner.org/public_html/C-C++/Library-Notes/LMDB.html
參考文獻: Chu H. MDB: A memory-mapped database and backend for OpenLDAP[C]//Proceedings of the 3rd International Conferenceon LDAP, Heidelberg, Germany. 2011: 35.