RocksDB系列十九:Iterator Implementation

RocksDB Iterator

??RocksDB Iterator提供用戶以有序的方式前向或者后向遍歷DB泌参,也可以seek 到DB的特定key上霎桅。為了做到這樣旅择,Iterator必須以有序流的方式訪問DB宣赔。RocksDB Iterator的實(shí)現(xiàn)類命名為DBIter预麸。

DBIter

  • Implementation: db/db_iter.cc
  • Interface: Iterator

??DBIter是InternalIterator的封裝。DBIter的任務(wù)就是解析由InternalIterator 暴露出來的InternalKeys儒将,最后以u(píng)ser key的形式展現(xiàn)吏祸。
Example:
The underlying InternalIterator exposed

InternalKey(user_key="Key1", seqno=10, Type=Put)    | Value = "KEY1_VAL2"
InternalKey(user_key="Key1", seqno=9,  Type=Put)    | Value = "KEY1_VAL1"
InternalKey(user_key="Key2", seqno=16, Type=Put)    | Value = "KEY2_VAL2"
InternalKey(user_key="Key2", seqno=15, Type=Delete) | Value = "KEY2_VAL1"
InternalKey(user_key="Key3", seqno=7,  Type=Delete) | Value = "KEY3_VAL1"
InternalKey(user_key="Key4", seqno=5,  Type=Put)    | Value = "KEY4_VAL1"

But what DBIter will expose to the user is

Key="Key1"  | Value = "KEY1_VAL2"
Key="Key2"  | Value = "KEY2_VAL2"
Key="Key4"  | Value = "KEY4_VAL1"

MergingIterator

  • implementation: table/merging_iterator.cc
  • Interface: InternalIterator
    MergingIterator 包括很多 child iterators,MergingIterator 是一個(gè)Iterators堆钩蚊。在MergingIterator 中贡翘,我們把所有的child Iterator放進(jìn)heap中,以一種有序的流形式暴露砰逻。
    Example:
    The underlying child Iterators exposed:
= Child Iterator 1 =
InternalKey(user_key="Key1", seqno=10, Type=Put)    | Value = "KEY1_VAL2"

= Child Iterator 2 =
InternalKey(user_key="Key1", seqno=9,  Type=Put)    | Value = "KEY1_VAL1"
InternalKey(user_key="Key2", seqno=15, Type=Delete) | Value = "KEY2_VAL1"
InternalKey(user_key="Key4", seqno=5,  Type=Put)    | Value = "KEY4_VAL1"

= Child Iterator 3 =
InternalKey(user_key="Key2", seqno=16, Type=Put)    | Value = "KEY2_VAL2"
InternalKey(user_key="Key3", seqno=7,  Type=Delete) | Value = "KEY3_VAL1"

MergingIterator 將所有的child Iterators 放到堆中鸣驱,以有序流的形式暴露。

InternalKey(user_key="Key1", seqno=10, Type=Put)    | Value = "KEY1_VAL2"
InternalKey(user_key="Key1", seqno=9,  Type=Put)    | Value = "KEY1_VAL1"
InternalKey(user_key="Key2", seqno=16, Type=Put)    | Value = "KEY2_VAL2"
InternalKey(user_key="Key2", seqno=15, Type=Delete) | Value = "KEY2_VAL1"
InternalKey(user_key="Key3", seqno=7,  Type=Delete) | Value = "KEY3_VAL1"
InternalKey(user_key="Key4", seqno=5,  Type=Put)    | Value = "KEY4_VAL1"

MemtableIterator

  • Implementation: db/memtable.cc
  • Interface: InternalIterator

MemtableIterator是MemtableRep::Iterator的封裝诱渤,內(nèi)存表實(shí)現(xiàn)自己Iterator都是以keys/values的有序流的形式暴露丐巫。

BlockIter

  • Implementation:table/block.h
  • Interface: InternalIterator

這個(gè)Iterator用來從SST file中讀取blocks,與blocks是Index blocks或者data block是無關(guān)勺美。由于递胧,SST file blocks是有序的且不可更變的,所以我們可以load block數(shù)據(jù)到memory總赡茸,然后為這個(gè)有序的數(shù)據(jù)創(chuàng)建一個(gè)BlockIter缎脾。

TwoLevelIterator

  • Implementation: table/two_level_iterator.cc
  • Interface: InternalIterator

一個(gè)TwoLevelIterator 包含兩個(gè)Iterators

  • First level Iterator (first_level_iter_)
  • Second level Iterator (second_level_iter_)

first_level_iter_用來計(jì)算出接下來要使用的second_level_iter_,second_level_iter_指向我們要讀取的實(shí)際數(shù)據(jù)占卧。
Example:
RocksDB使用TwoLevelIterator 來讀取SST file遗菠,first_level_iter_ 是SST File Index block上的BlockIter联喘,second_level_iter_ 是Data Block上的BlockIter。
下面看一個(gè)簡單的SST file辙纬,有4個(gè)Data blocks和1個(gè)Index Block

[Data block, offset: 0x0000]
KEY1  | VALUE1
KEY2  | VALUE2
KEY3  | VALUE3

[Data Block, offset: 0x0100]
KEY4  | VALUE4
KEY7  | VALUE7

[Data Block, offset: 0x0250]
KEY8  | VALUE8
KEY9  | VALUE9

[Data Block, offset: 0x0350]
KEY11 | VALUE11
KEY15 | VALUE15

[Index Block, offset: 0x0500]
KEY3  | 0x0000
KEY7  | 0x0100
KEY9  | 0x0250
KEY15 | 0x0500

要想讀這個(gè)file豁遭,我們要?jiǎng)?chuàng)建一個(gè)TwoLevelIterator

  • first_level_iter_ => BlockIter over Index block
  • second_level_iter_ => BlockIter over Data block that will be determined by first_level_iter_

當(dāng)通過TwoLevelIterator seek到KEY8時(shí),首先使用first_level_iter_ (BlockIter over Index block)計(jì)算出哪個(gè)block可能包含這個(gè)key贺拣,結(jié)果是設(shè)置second_level_iter_ to be (BlockIter over data block with offset 0x0250)蓖谢。然后我們使用second_level_iter_ 在data block中讀取key &value

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市譬涡,隨后出現(xiàn)的幾起案子闪幽,更是在濱河造成了極大的恐慌,老刑警劉巖涡匀,帶你破解...
    沈念sama閱讀 211,376評(píng)論 6 491
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件盯腌,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡陨瘩,警方通過查閱死者的電腦和手機(jī)腕够,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,126評(píng)論 2 385
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來舌劳,“玉大人燕少,你說我怎么就攤上這事≥锒冢” “怎么了?”我有些...
    開封第一講書人閱讀 156,966評(píng)論 0 347
  • 文/不壞的土叔 我叫張陵崇决,是天一觀的道長材诽。 經(jīng)常有香客問我,道長恒傻,這世上最難降的妖魔是什么脸侥? 我笑而不...
    開封第一講書人閱讀 56,432評(píng)論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮盈厘,結(jié)果婚禮上睁枕,老公的妹妹穿的比我還像新娘。我一直安慰自己沸手,他們只是感情好外遇,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,519評(píng)論 6 385
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著契吉,像睡著了一般。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上娘摔,一...
    開封第一講書人閱讀 49,792評(píng)論 1 290
  • 那天,我揣著相機(jī)與錄音妄辩,去河邊找鬼。 笑死山上,一個(gè)胖子當(dāng)著我的面吹牛眼耀,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播佩憾,決...
    沈念sama閱讀 38,933評(píng)論 3 406
  • 文/蒼蘭香墨 我猛地睜開眼哮伟,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了鸯屿?” 一聲冷哼從身側(cè)響起澈吨,我...
    開封第一講書人閱讀 37,701評(píng)論 0 266
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎寄摆,沒想到半個(gè)月后谅辣,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,143評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡婶恼,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,488評(píng)論 2 327
  • 正文 我和宋清朗相戀三年桑阶,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片勾邦。...
    茶點(diǎn)故事閱讀 38,626評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡蚣录,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出眷篇,到底是詐尸還是另有隱情萎河,我是刑警寧澤,帶...
    沈念sama閱讀 34,292評(píng)論 4 329
  • 正文 年R本政府宣布蕉饼,位于F島的核電站虐杯,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏昧港。R本人自食惡果不足惜擎椰,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,896評(píng)論 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望创肥。 院中可真熱鬧达舒,春花似錦、人聲如沸叹侄。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,742評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽趾代。三九已至塔猾,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間稽坤,已是汗流浹背丈甸。 一陣腳步聲響...
    開封第一講書人閱讀 31,977評(píng)論 1 265
  • 我被黑心中介騙來泰國打工糯俗, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人睦擂。 一個(gè)月前我還...
    沈念sama閱讀 46,324評(píng)論 2 360
  • 正文 我出身青樓得湘,卻偏偏與公主長得像,于是被迫代替她去往敵國和親顿仇。 傳聞我的和親對(duì)象是個(gè)殘疾皇子淘正,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,494評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容

  • Prefix Seek Prefix seek是RocksDB的一種模式,主要影響Iterator的行為臼闻。在這種模...
    周肅閱讀 9,224評(píng)論 0 2
  • ??隨著DB/mem使用越來越多鸿吆,filter/index block的內(nèi)存空間變得不可忽視。雖然cache_in...
    薛少佳閱讀 4,116評(píng)論 1 3
  • 1述呐、簡介 RocksDB是FaceBook起初作為實(shí)驗(yàn)性質(zhì)開發(fā)的一個(gè)高效數(shù)據(jù)庫軟件惩淳,旨在充分實(shí)現(xiàn)快存上存儲(chǔ)數(shù)...
    薛少佳閱讀 17,250評(píng)論 0 32
  • 最近項(xiàng)目中用到這個(gè)nb的玩意,所以就花時(shí)間研究了下乓搬,同時(shí)整理下助自己記憶思犁。這個(gè)猛虎上山的logo就是rocksdb...
    小東_16d3閱讀 9,066評(píng)論 3 10
  • 第四次和大家畢業(yè)旅行,這次的目的地是野三坡进肯,帝都的西南角~出了京城激蹲,一路山巒疊翠,地勢(shì)越來越高江掩,穿過很多個(gè)漫長隧道...
    林夢(mèng)夕1987閱讀 278評(píng)論 2 0