超长键膨胀击垮LSM内存索引 系统须设尺寸上限与布隆过滤器

超长键膨胀易击垮LSM内存索引：系统须设尺寸上限与布隆过滤器 当写入超长键时，LSM树内存块索引会因急剧膨胀耗尽物理内存并引发系统换页崩溃，底层存储必须设置硬性键长阈值并引入布隆过滤器以阻断空查导致的读放大。 面试围绕高写吞吐、支持复合主键与事务隔离的分布式 KV 存储展开，深入探讨了存储引擎与分布式架构的设计细节。双方首先基于 LSM-Tree 架构深入剖析了 WAL、MemTable、SSTable 分层落盘与 Compaction 机制，并针对超大 Key 引发的内存交换、读放大及布隆过滤器的优化展开了探讨。随后，讨论进一步扩展到使用一致性哈希进行数据路由分片、基于 MVCC 的读写互不阻塞并发控制，以及 LSM-Tree 与 B-Tree 的性能权衡。最后，面试官与候选人梳理了动态网络下的节点迁移成本，并对比了单对象事务与基于两阶段提交（2PC）的分布式多对象事务的复杂度与隔离级别。 针对写密集型（Write-heavy）分布式 KV 存储，采用 LSM-Tree 架构通过 WAL 追加写和内存 MemTable 缓冲提供高吞吐低延迟写能力，后台借助 Compaction 异步回收旧版本和墓碑（Tombstone）。 (4:24) 存储引擎必须对 Key/Value 设置硬性边界防护，生产级 SSTable 通常切分为 10MB 至 100MB，避免过长 Key 导致内存块索引膨胀并引发频繁的操作系统页面置换（Page Swap Thrashing）。 (36:24) 点查非存在记录会触发全层 SSTable 遍历与最恶劣的读放大，系统需借助布隆过滤器（Bloom Filter）在内存中提前拦截无效磁盘 I/O。 (50:18) 分布式路由应通过 Partition Key 和一致性哈希管理逻辑分片，而非在业务主键中硬编码机架等物理拓扑；跨节点多对象事务则需权衡性能并引入两阶段提交（2PC）。 (54:24)

在系统设计模拟面试中，面试官 Scott Shi 与候选人推导了面向高写吞吐的分布式 KV 存储架构。核心论点在于：系统应采用 LSM-Tree 结合追加写日志与分层合并以压榨写入性能，同时必须通过布隆过滤器、内存与 Key 边界防护规避读放大，并在分布式层解耦逻辑键路由与物理网络拓扑。 LSM-Tree 写入架构与记录生命周期 (4:24) 候选人主张借鉴 Cassandra 的 LSM-Tree 架构应对高写吞吐需求：写操作先追加至磁盘 Commit Log (WAL) 保证持久性，再写入内存 MemTable；达到容量阈值后冻结下刷为磁盘 SSTable，后台通过 Compaction 异步多路归并。更新与删除采用新版本写入及带时间戳的墓碑标记（Tombstone），由后台合并任务物理清理过期记录。 针对内存结构，候选人一度提议使用 8 GB 纯追加数组以提升写入效率，但面试官指出无序数组在点查时会退化为 O(N) 线性扫描，且无边界限制会直接耗尽资源导致系统崩溃。双方最终确定单条记录必须设立硬性尺寸上限，并采用哈希表等支持快速检索的结构组织内存数据。 读放大防御、大 Key 风险与检索优化 (33:14) 当查询不存在的记录时，LSM-Tree 需逐层检索 MemTable 与磁盘 SSTable，造成严重的读放大。针对长 URL 作 Key、计数器作 Value 的场景，面试官指出大 Key 会导致常驻内存的 SST 块索引急剧膨胀，超出物理内存后将引发操作系统持续的换页抖动（Swap Thrashing）。因此，生产引擎（如 RocksDB）通常将单个 SST 控制在 10 MB 至 100 MB，并限制 Key 尺寸（如 1 KB 上限）。 在 SST 检索优化上，候选人主张读取文件头元数据与偏移量实现局部 Seek，反对全量加载磁盘块；面试官则引入布隆过滤器（Bloom Filter），在未命中时直接短路判定，避免无效的多层磁盘 I/O 穿透。 复合主键设计与物理拓扑解耦 (51:10) 针对地理位置、用户与活动信息的复合主键，系统需将其拆解为路由分片键与内部排序列。候选人提议将 ZIP Code 与 User ID 组合为分片键，但随后尝试将不同字段硬编码映射至数据中心、机架与物理节点。 面试官纠正指出，存储上层逻辑严禁直接耦合物理网络拓扑，机器存在随时漂移、下线与 DNS 动态解析的现实。业务键仅需对接协调节点（Coordinator）并基于一致性哈希分发，物理路由与副本选址应交由类似 Cassandra Snitch 的网络探测组件在底层动态完成，从而保障水平平滑扩容。 MVCC 并发控制与事务隔离边界 (61:14) 为满足“读写互不阻塞”的要求，系统采用多版本并发控制（MVCC）。写线程在独立快照中更新并打上事务标签，读请求依据快照时间戳读取历史已提交版本，事务提交后新状态才对外部可见。 在事务作用域上，讨论明确划分了边界：单对象事务局限于本地分片即可高速原子提交；而跨分片的多对象事务必须引入两阶段提交（2PC），带来显著的协调延迟与锁争用开销。面试官强调应依据实际业务所需隔离级别设计事务，避免盲目引入重量级分布式一致性机制。 该方案完整梳理了单机 LSM-Tree 存储引擎与分布式路由分片的推导逻辑，但在深层容灾与高级事务细节上仍存留白。候选人在全库快照导出（Dump snapshot）机制及跨分片事务恢复的具体实现上明确表示缺乏准备，凸显出分布式基础设施设计在解耦抽象之外，对系统边界防护与故障恢复完整性的严格要求。

[36:24] Scott Shi: basically just page swap, page swap always [40:05] Scott Shi: You don't really actually tell what application developer do... you should assume that application developer can do whatever they like. [40:05] Candidate: deliberately making up the question hard [42:25] Scott Shi: I'm talking about something very simple: you just give a record 501, you're looking for this single node. [45:21] Candidate: loading all from disk to memory that is a huge cost [50:18] Candidate: Bloom filter is the best solution [54:24] Scott Shi: too much information for server to know which rack [58:38] Candidate: I think I got confused here, some concept get confused. [65:40] Candidate: I still haven't read about this part... familiar, not familiar... I still haven't read about this part. [65:40] Candidate: No idea, no idea [72:04] Candidate: The read for the B-Tree will be definitely faster, but the write of the B-Tree will be much slower than this design. [77:18] Candidate: give me 10 second let me see... I don't see a issue here.

[0:23] experience [0:42] valem [1:00] okay uh okay you share one [1:05] uh [1:08] [Music] [1:14] share [1:19] okay okay [1:38] okay [1:53] so the past project [1:56] background okay so let's today let's [1:58] let's actually work on key value of data [2:01] storage let's let's design something [2:04] from [2:07] scratch yeah so I actually I actually [2:10] add list all the requirement here uh I [2:13] think it's a basically several levels [2:15] the requirement first from API level you [2:17] should support like write ke and value [2:20] and read ke and value the value here can [2:22] be uh any of the uh encoding format uh [2:27] should be support like any format it's [2:29] probably you probably want to do [2:31] compression here and also you want to [2:33] support delete and additionally we want [2:36] to support something like Cassandra so [2:38] you can control which paration the data [2:40] living so you you have the comp [2:42] composite composite primary K you can [2:45] Define the primary K and K so the [2:48] partition K will decided where to sh the [2:50] data and uh so you have full control [2:53] over your data location um for isolation [2:57] level uh we want to make sure that you [2:59] don't have rate block right and you [3:00] don't have right block rate and you you [3:03] uh let's let's try with a single object [3:05] transaction and we can also discuss [3:08] what's what's what's required for [3:09] multiple object transaction and uh [3:13] additionally we want to make sure that [3:15] we can dump a snapshot so we can recover [3:18] from this [3:19] snapshot yeah so in case there is a data [3:22] failure we can [3:24] still feure recover from the snapshot U [3:28] from system require level let's try to [3:31] optimize on rest throughput okay yeah [3:34] and also this database also it's um so [3:37] let's focus on this database more like a [3:39] transactional database so u means that [3:42] it's going to be it's going to be serve [3:44] like transactional [3:46] request and uh we want to we want to [3:49] make sure the database is a horizontal [3:52] scalable as well so you know if there is [3:55] new request we can just add new notes [3:58] and at last that uh we want to make sure [4:01] it's highly configurable so you can you [4:03] can set different level of configur uh [4:05] different level of um persistency so [4:09] basically you can see you know I don't [4:10] care about data loss and you can speed [4:12] up performance if you do care about data [4:15] loss you can have your data persistent [4:18] like uh like a SQ DP or [4:21] something yeah so so according to this [4:24] requirement it seems uh it seems [4:26] Cassandra is the yeah best uh database [4:30] to fit this Sho except there might be [4:34] some uh there might be even more uh a [4:38] strict requirement like a transaction [4:41] support uh support Dum slam shot I'm not [4:44] sure if Cassandra have kind kind of Dum [4:46] slam [4:47] shot uh yeah [4:51] but but generally speaking it seems the [4:54] yeah if I use Cassandra LS lsmt uh [5:00] to to answer this question I think yeah [5:03] it seems uh it seems the correct it seem [5:06] the uh correct [5:09] direction [5:10] uh yeah um so support the right uh key [5:16] read and [5:17] delete um so this is all1 so we can use [5:22] uh we can use [5:24] uh lsmt uh log structured merge tree [5:31] uh so [5:33] uh so the the first level so so we we we [5:37] have the uh we have the [5:39] uh we have the uh com log and then then [5:45] we have M table uh then we have SS table [5:50] uh sorry the stram table and then uh we [5:53] can do uh compaction there and then [6:01] Yeah so basically basically it is a uh [6:04] it is a big hash [6:06] table a big hash table [6:11] uh yeah we just St even pair in hash [6:14] table but [6:16] uh but with the uh with [6:21] the log structure emerge tree [6:25] uh yeah so this is I think this should [6:28] be the uh correct [6:30] direction [6:32] um so the partition queue will decide [6:35] where to share the [6:38] [Music] [6:39] data yeah so just to use the um the [6:43] white [6:45] column the center actually the is a raw [6:48] oriented database but it has the it has [6:52] the this uh the [6:54] the the key uh this key [7:01] the and and then it has yeah so let's [7:05] pause a second uh could you please work [7:07] into details about what's a log [7:08] structure merch tree let's spend like [7:10] one minute I'll explain what's the log [7:12] structure merch tree here log structured [7:14] merch tree uh so [7:19] uh so basically uh you uh so it's C [7:24] something called uh a Kaa uh structure [7:27] so uh you uh uh so that means you always [7:31] append the the log so this uh this log [7:34] commit is for uh [7:36] Dural ability uh uh [7:40] consideration [7:42] uh yeah so this is when uh when uh the [7:46] memory uh then then the program crashed [7:48] you can recover from commit lock uh that [7:51] is the that is the only a uh place you [7:55] you read from the commed doog and and [7:58] the memory uh the a memory table uh live [8:02] in the in the memory and then when you [8:05] write the uh when you write the uh the [8:07] key valum PA then you just write uh so [8:11] first you write to the commit log and [8:13] then after that then you write to the uh [8:15] memory table uh when the memory table [8:18] reach to some uh threshold so uh then it [8:22] will uh D to the D to the SST uh s [8:29] string [8:31] Table and there uh so this this is [8:36] normally the code of storage and then [8:39] you you have uh you have you could have [8:41] many levels of SST and then you can do [8:44] then you can do uh compaction there say [8:48] say if you want to update table uh then [8:51] you delete uh yeah upserts then you you [8:54] can do [8:55] compaction uh compact the sess uh [9:00] table uh so by this way you can uh by [9:05] this way you can uh write very fast [9:09] because actually when you write to this [9:12] uh memory table actually you just write [9:14] to the uh curlo space buffer I think if [9:18] you disable the stand standard iio [9:20] buffer then you you can just write the [9:23] uh just right right right to the space [9:26] buffer uh you can direct R to c space [9:31] barer and then then very fast [9:34] uh and and then uh when when uh so this [9:39] is a big hash table actually uh and then [9:44] it go to the [9:46] uh code storage when it's reached to [9:49] some threshold so this design this [9:52] design has a very good performance uh on [9:55] right uh and a throughput latency on [9:58] right and and high through put and right [10:00] but but the problem is when you read it [10:03] uh when you read the data you you you Le [10:06] uh you Le a uh read different level of [10:10] uh uh SST table you need to do [10:15] merge so this this is called something [10:18] like a read merch on [10:22] read [10:24] yeah so as think [10:27] the lsmt key uh is the is the is the [10:32] solution uh for this kind of question [10:34] for the right uh optimized uh yeah [10:40] database yeah so can can we actually uh [10:43] lay out one record let's can we write [10:45] one record in the m m table and also [10:48] what's what's the going to record looks [10:50] like in SST table can we actually give a [10:52] one concrete yeah okay so let's say key [10:56] just uh let's say uh [11:00] just see [11:02] how the just the date [11:07] uh yeah we give give give today's date [11:12] can use date or August [11:15] 11 [11:17] uh or maybe something else [11:22] uh [11:25] uh yeah so so when I write this uh just [11:29] use this as a as a as a key the data as [11:31] a key and then then we have some s [11:34] satellite data Maybe we have some event [11:37] uh something uh some event or some yeah [11:41] some some event or location something [11:44] something like that sorry yes this this [11:47] is just as a schema and the data could [11:50] be the data could be yeah [11:52] so uh so for example today we have a [11:56] walk let's say location uh Zoom for [11:59] example yeah so so uh yeah we have a key [12:04] for example this this dat data is just a [12:07] key like in Uber strip data they use the [12:11] data St Str as the key in the live [12:16] table okay anyway anyway just then we [12:19] can use the the date and then first we [12:21] write this [12:24] uh we we write this this this uh this [12:28] data to uh commit lock uh for uh [12:31] durability uh purpose and then we write [12:34] it to uh memory table uh so inside the [12:37] memory table we have a lot of this this [12:39] kind of [12:40] item [12:43] so yeah maybe maybe we we we can we can [12:47] put a put a time time time stamp or a [12:51] time stamp or something time [12:54] stamp let's say uh L second for example [12:58] we get a lot of we get a lot of [13:01] uh yeah actually the time stamp is the [13:05] want is something like that yeah [13:08] something like this so we get a lot of [13:10] this kind of uh yeah event this is for [13:14] example event yeah Cassandra is very [13:16] good for event store yeah we we use [13:18] Cassandra to uh store event I mean in my [13:21] previous project so I think I think we [13:23] can use it uh here so we have a lot of [13:25] events store and we don't want to modify [13:28] the because the event is some just some [13:31] some history so we don't have to um yeah [13:34] normally we don't modify history so we [13:36] don't don't update event so yeah we we [13:39] we read a lot of event but we only read [13:43] it very infrequently for example for for [13:46] auditing purpose uh for some explanatory [13:50] analysis per purpose so yeah so I think [13:53] this event is a good example for this [13:56] case uh and then we we have this in the [14:00] in the uh memory table and when the [14:02] memory table let's say if it's reach [14:04] let's say uh a for example then we write [14:09] yeah we write we write it to uh [14:12] SST so we so this is the yes so this is [14:18] a memory uh mem [14:22] table [14:24] Yeah and then we we we just uh uh this [14:29] this SST uh [14:32] was was a was a was a word coed by [14:35] Google a big table I mean it me a solid [14:38] stream [14:39] table uh actually when we want to update [14:42] event it [14:46] will it will do compaction there uh yeah [14:50] update event or or we want [14:54] to yeah we if we want to update or [14:56] delete then we put a tombstone there uh [14:59] for example if you want to delete uh [15:03] then for example for example if we want [15:04] to delete this this one in the [15:06] middle uh [15:09] then actually uh Delete uh update delete [15:14] and everything is is is is is is right [15:18] in this uh [15:20] lsmt the the the the the Kaa uh uh [15:24] infrastru the ca uh structure uh let's [15:28] say we we put a tomb uh I see uh yeah [15:32] yeah [15:33] Tombstone yeah so here let's say uh yeah [15:37] so so we put a time stamp Tombstone uh [15:40] time stamp here uh then then there's [15:45] another backround uh uh process there a [15:48] demon to uh to do uh to do uh to do [15:54] compaction so [15:57] uh so it it it will do uh it would comp [16:02] compact This Ss St compact uh [16:08] SST [16:09] uh to to to refine the data they's say [16:15] uh yes if this [16:18] Tombstone yeah if we say Tombstone here [16:21] maybe let's say we have have H H uh [16:25] let's say [16:27] uh one item and and say we say a [16:31] tombstone [16:32] here then maybe we just we just we just [16:35] uh [16:37] uh yeah then then we uh when we merge [16:40] this this SST when we compact this SST [16:43] we just remove it we just remove it when [16:48] we yeah compile if we don't want want of [16:51] the version but here you mentioned uh [16:54] this multi object transaction maybe [16:57] maybe we need we need the [17:01] version MBC CD that but okay but here I [17:05] would like say we can just remove it to [17:08] to to compact to SST yeah just yes okay [17:13] so if uh okay I think I mention several [17:16] things so if I if I visualize and maybe [17:19] visualize it so basically uh what you'll [17:21] say is that you you have a record this a [17:23] record it's it's a pending so each time [17:26] you're going to to pending a record in [17:28] the Lo uh yes this is like a r head lock [17:31] something yeah yeah right okay so U so [17:35] the first step is you you pending on [17:38] record to R headlock and then you're [17:40] going to once it's once it's flashed [17:43] once it's flashed right you have a flash [17:45] point right yes you can see like record [17:49] three record four is Flash then once [17:51] it's flash then you're going to right [17:54] back to right back to um memory uh which [17:58] is a m [17:59] table you you're going to WR to M table [18:02] right okay yeah okay and [18:07] um okay um what going to be happen so [18:11] how my question sorry soorry I think I [18:14] think when you write it you okay so you [18:17] mean the uh the right hand log is a [18:19] commit log here right do do you mean the [18:21] same thing yeah right okay [18:25] okay it's a we [18:27] can okay [18:29] okay so once you once your let's say R4 [18:32] just write to the red commit lock so you [18:34] write to the m table and how you're [18:37] going to process this proceed process [18:39] this part uh what um let's say uh we can [18:43] have example here let's say record to is [18:46] as you mention above like one two three [18:49] four five as time stand then it's like [18:51] marking VI and then um and F4 is 1 2 3 4 [18:58] five again um it's a it's a key and but [19:03] here uh it's it's instead of Market [19:05] interv it's called cooking [19:10] class so how do you process it how do [19:13] you write to the m uh you mean uh we [19:15] have so okay so this is the updat [19:18] [Music] [19:20] right uh so okay then we just append [19:23] appended the uh so the memory table uh [19:29] uh okay so the update in memory table so [19:34] you can uh just overwrite it I mean I [19:38] think the memory table is just a big [19:40] hash table so then you [19:42] [Music] [19:45] can yeah I think you can just you can [19:49] override it I think maybe maybe it's [19:50] tunable you can use some configuration [19:53] uh to to to to define the behavior let's [19:57] say uh for example if you just want to [19:59] overwrite it for example if I just uh I [20:02] config to overwrite the old Vue I don't [20:05] uh I just I always get the latest latest [20:08] version uh of the vual then in memory [20:11] table we just [20:14] updated we can update [20:17] it because because uh you see uh here I [20:21] I use time stamp Lan second so which I [20:24] mean the event [20:27] shouldn't I mean [20:29] I have an assumption the events [20:31] shouldn't uh have the same key uh [20:35] different record should have the same [20:36] should shouldn't have the same key yeah [20:38] but here uh you are designing a database [20:41] right so the database so application [20:43] developer wish will work on your design [20:46] may not design the primary KY as time [20:48] stamp right the time stamp Nan is just [20:52] one example you're given here because [20:54] you design a database or do you want to [20:56] say uh you know whoever use database you [20:59] have to design the ks time stem oh no no [21:02] no no no [21:05] uh okay then we can uh then we can just [21:08] uh just uh use this memory table and the [21:12] and the and the huge array then we just [21:15] append it always a [21:16] pend and we use compaction uh program [21:20] the demon compaction demon to process [21:22] the duplicate [21:25] key we just always append it [21:29] okay so yeah this is one thing and also [21:33] additionally uh when you see M table uh [21:35] it's actually in memory data structure [21:38] right yes so what in memory data [21:41] structure you thinking [21:42] of uh great question I I think initially [21:45] I thought it would be a a hash table um [21:48] but now I think if we don't want to uh [21:52] override happened in in memory table [21:56] then we can just use use it and a big uh [22:00] vector or a big array then we can always [22:03] theend then we can allocate we we can [22:05] allocate a [22:07] huge uh space a huge memory space and a [22:11] vector or and AR R just we just to have [22:15] a yeah we just have a a counter and when [22:18] the counter Reach the the capacity then [22:20] we just uh Dum the mer table to uh SST [22:26] table okay so if it's array and you [22:30] mention that it could potentially have [22:32] eight gigabytes of data so let's assume [22:35] that what's so first what what do you [22:38] think about limitation on single [22:41] record um you know uh what what do you [22:44] want to put limitation on single record [22:46] here limitation single record uh like K [22:50] size value size something like [22:54] that uh I don't think we need to put [22:57] that one because the standard like data [22:59] uh the user can put any standard data [23:02] maybe uh okay then we can have uh we can [23:06] have a uh we can have a thread to detect [23:09] the memory usage of the data uh of of [23:13] the [23:14] process so we can check the process uh [23:17] process state in Linux we can check the [23:20] uh Pro State uh memory and to get the [23:25] memory usage of of this table of of this [23:28] process is so when it reach the [23:33] threshold yeah we allocate 8 G 8 G BTE [23:37] but we uh [23:39] we we don't we don't specify the the the [23:44] r number [23:46] threshold yeah okay so what here so if [23:50] you don't specify threshold I'm [23:51] wondering how do you going to no I I [23:53] mean we we spef we specify the memory [23:56] threshold instead of a R num threshold [23:59] and we have a we have a [24:02] uh yeah we have a uh we have a process [24:05] to check [24:07] the proc state memory uh file then we [24:11] can get the the memory usage of the of [24:15] the program yeah so what so if you don't [24:18] specify anything customer can do [24:20] something crazy right your your platform [24:23] developer so they can have k equal to [24:25] 200 gabt and value is something right [24:30] okay then we can specify some to avoid [24:32] this crazy uh [24:34] scenario yeah we can [24:36] specify this the this the 64 [24:45] megabyte okay yeah so let's see we have [24:48] some stret cold here uh let's actually [24:50] let's actually go back this later Let's [24:52] see we have the X um K bite here for key [24:57] and value we can see uh y uh y byes for [25:02] Value we can go back to the the case [25:04] later [25:06] um okay so uh you mention uh you [25:09] potentially consider array but how you [25:12] going to search from this 8 gab data for [25:14] a single [25:21] record 8 G 8 gigabyte single record uh [25:27] because uh you only flash data from M [25:29] table to string table it's threshold [25:32] which is 8 gab right so you may have 8 [25:35] gab of data in memory in Array format [25:38] and uh how you're going to search a [25:40] single record out of this 8 [25:43] gigabytes okay uh yeah so the area you [25:47] cannot you cannot do search yeah [25:51] so um let me [25:54] think so then I I think let's go back to [25:58] the hash table let's go back to the hash [26:01] table uh data structure I think I [26:06] really yeah the Merit table I I think is [26:09] should [26:11] be should should be hold on hold [26:17] uh uh yeah so we basically we need the [26:21] basic functionality is is [26:25] [Music] [26:26] search yeah we we need have a hash table [26:30] for that purpose [26:32] yeah yeah so I think we probably want to [26:35] use a hash table right we don't want to [26:37] use yeah the basic structure should be a [26:39] hash table yeah okay so this is one [26:42] thing additionally uh I do have a [26:44] question let's say uh you want to search [26:47] a record so I think you mention [26:49] something like you have a leveled table [26:53] the top table is a memory table then [26:56] you're going to go below [26:58] and so you're going to have some like [27:02] level one sorted string level one sorted [27:05] string table s the string table you will [27:07] have like level two s string table right [27:11] and so let's assume that let's let's do [27:14] few things here there are some some very [27:16] interesting question um first question [27:19] is that if you're searching a single [27:21] record let's say search a record are are [27:25] 100 or something um if it's in table [27:28] because you use hash table so you can [27:30] read a hash table it's hash table so you [27:33] can get data in log [27:38] n n is proportional to the total records [27:41] in the hash table right if it's [27:43] there right but what if it's isn't there [27:47] what you're going to do and also uh if I [27:51] understand that M table is in memory all [27:53] the rest of table are in disk right so [27:56] this going to be in disk and this going [27:58] to be in dis uh at least you save into [28:01] the dis right yes so how you're going to [28:04] process this I think you need some index [28:07] for This Ss table and then you can do [28:09] the [28:11] uh you still need some some index and [28:14] then you load the index in the memory [28:16] and then you do search you cannot scan [28:18] the full uh disk for this SST [28:23] table and also why the hash table use a [28:26] login oh hash table is a oh hash table [28:30] it could be uh it could be log one yeah [28:32] it could be log one depends on how if [28:34] you use three hash table then it's l [28:36] okay it depends on how you how yeah log [28:39] One login yeah it's really depends on if [28:42] you use hash code or something [28:45] okay anyway I think I think uh we we [28:48] should do the we should do we should [28:50] have some index in the yeah I yeah I [28:56] think can you describe the index here uh [29:01] let's say the index [29:04] uh this say the index could be [29:07] [Music] [29:08] the for example here the the index could [29:12] could just be the uh could just be the [29:14] key to the to the to the for example the [29:17] r number uh yeah the r number the index [29:22] but but you need to have at least the [29:24] index for this um [29:29] yeah [29:30] then [29:32] index just the index to the to the [29:35] number and then you just can uh then [29:38] when you get this record then you can [29:40] search uh this this R 100 100 in level [29:45] one to three and Etc like uh [29:50] SST and to get the to pinpoint the exact [29:54] uh Records for for that for the R1 100 [29:58] and then you do a [30:03] merch uh yeah so merge and read so so so [30:09] yeah so when you read then you do the [30:11] merge but you use a uh you use some [30:14] index structure to to do it you yeah [30:19] yeah so I'm little bit confused about [30:21] merge part uh let's assume that uh let's [30:24] assume that uh we have run record here [30:27] mhm um at time stamp four maybe and then [30:31] we have record 100 here at time stamp [30:34] three yeah and and we have U r00 here at [30:39] time stamp six uh how you going to do [30:41] the merge okay so you will uh just apply [30:45] the change over the stank of uh just [30:48] over stank of the the different version [30:50] of that record uh according to the [30:54] time uh I think this is pretty much [30:57] what's they did uh in hoodi in hoodi [31:01] they also did the same thing so [31:04] uh so they have different version of of [31:06] the same record yeah yeah and then apply [31:10] they just uh they just uh uh apply the [31:13] change each version has a has a [31:16] different uh has a difference between [31:19] the the old version and it's just [31:21] starting from old version and then apply [31:22] the [31:24] changes [31:25] uh they say uh [31:29] for example if if there Tombstone if [31:31] there's a [31:33] tombstone on version four they just [31:36] deleted and and then in version six it [31:39] just recreated again and then it just [31:42] you just uh yeah you just uh you create [31:45] again and then maybe in the latest [31:48] version which one is in the which is in [31:50] the in the memory table maybe there's [31:53] some update then you just apply that [31:55] change okay so so if I understand right [31:59] so basically what you'll see is that if [32:01] I'm reading record 100 so I need to go [32:04] through all the levels table and get all [32:07] the records and do a read consolidation [32:09] and read [32:12] repair maybe there maybe there's a [32:15] different scenario let's say for example [32:16] if you found if you found the if you [32:18] already uh found the record in the [32:20] memory table that is the native version [32:22] uh then you can return it if you if you [32:25] if you couldn't find it in the table [32:29] then you have to go to yeah then you [32:32] have to go [32:35] to go to the the different level of [32:39] SST oh you should you should maybe you [32:41] should just need to find the latest [32:43] version you don't have to find other [32:46] version uh because here we we we we [32:50] didn't we we we are not uh we are not [32:53] recording the change we record the full [32:56] record so that means you can only you [32:59] can you can just get the latest version [33:01] yeah I think if it's just actional [33:03] database you want to return fast maybe [33:05] just only latest version you can you can [33:08] give the to compact compaction um [33:11] process and compact it later we still [33:14] have some question here so let's let's [33:16] yeah let's let's uh let's actually uh go [33:19] to next question assume that I think one [33:22] of the very good use case for this [33:23] database is that you want to count how [33:25] many of the YouTube video field so [33:28] you're going to have some YouTube url [33:31] could be very long uh it could be any [33:33] URL right then the key is YouTube url [33:37] okay and the value is a a [33:41] number just like a a number just a [33:44] number like a view [33:47] count okay so in this scenario the key [33:51] will be much much larger than the video [33:53] account uh assume that you have 8 [33:55] gigabytes of data [33:57] and you probably have more than seven [33:59] gigabytes is a [34:01] key so right is a key more than seven [34:05] gigabytes is key and you uh in that case [34:08] um you're going to have so what's the [34:11] issue here like what's the issue you can [34:13] see here [34:15] uh since uh you need to uh keep updating [34:19] the view count because the you change [34:22] very fast it's a heavy heater issue [34:29] uh so this is a lot of update right the [34:32] because the view count keeps changing [34:34] right yeah but update is actually update [34:37] it happens any time right it's just an [34:39] update it's uh it's not actually adding [34:42] extra uh not ex adding extra threshold [34:45] it can be update the same YouTube video [34:48] it could be insert another YouTube url [34:50] but from database perspective it [34:52] shouldn't be an isue here right I think [34:55] there is a fundamentally one isue here [34:57] um is actually [34:59] um going to be cause the system to crash [35:03] I think in my [35:05] opinion you mean uh sorry I I didn't get [35:09] it you mean the key when the key is uh [35:11] to to now or when the key is very big [35:15] like in this case like more than seven [35:17] gigabytes is a key and I think there is [35:19] a fundamentally one issue with current [35:21] design and we probably want to think [35:23] carefully then in this case we shouldn't [35:26] I mean we shouldn't use this [35:28] uh URL and the [35:33] [Music] [35:37] key so you mean the database uh this [35:40] design have a have a issue with this L [35:42] key uh scenario yeah so I I think [35:46] currently the the the design you [35:48] describe has a issue with this [35:50] one uh you mean the system will crash [35:53] how so the system will will be [35:55] performing very badly with exting [35:59] design and [36:08] um okay [36:11] so so this will [36:15] keep [36:22] updating okay so let's save some time [36:25] and so I I have so many questions let's [36:28] actually give you something here so like [36:30] I think mod most of the uh server we [36:33] currently have is probably 250 gigabytes [36:36] of memory and to like 20 32 gigabytes of [36:41] memory and uh in this case because you [36:45] you need to keep index in memory right [36:48] yeah yeah so if you want to keep index [36:50] in memory so you probably only can take [36:52] in this case you can only take like four [36:55] pages four level or four level or [36:59] sst3 and U if it's more than four you're [37:02] going to have a memory [37:04] soing paging page default you're going [37:06] to have page default and you're going to [37:08] have this memory uh me called memory [37:13] Soo uh so something it's basically just [37:16] page swap page swap always so it's going [37:19] to be flash it's basically the this your [37:23] your database not going to be responding [37:25] [Music] [37:29] oh because you you uh considering this [37:32] four SST tree uh because each SS tree [37:39] the index part index you you have the [37:41] key right because the key is like Oh you [37:44] mean you you mean how I do the indexing [37:47] okay [37:49] um yeah I I think [37:52] this we we should okay [37:55] so we should use use this uh full key to [37:59] to to be the to be the to be the key [38:02] here we shouldn't use this uh YouTube [38:04] URL and the index key here we should use [38:07] some short form of it like [38:11] uh like some hash key or something or [38:14] maybe maybe uh yeah maybe has key [38:19] uh but we we use hash Q we might got uh [38:23] hash [38:25] cation but but in this case I think we [38:28] should [38:29] use a hash key here I mean this key is [38:33] just a very uh very live design here and [38:36] we can of course we we can polish this [38:39] design um so uh it so the key here can [38:43] change um but I think the my point here [38:46] is the K to the value ratio could be [38:48] very small so the K to the value ratio [38:51] may be one 2 10 and you have multiple [38:54] case that it could be 1 to 10 so in this [38:56] case sorry 10 to what so in this case [38:58] that majority of the data majority of [39:01] your memory going to be St the key just [39:04] as a key yeah just as a key yeah so you [39:06] you can have multiple cases that the K [39:09] is a major data part so going to be 10 [39:12] part the bite going to take is 10 to one [39:14] yeah but all these keys are different so [39:16] you still have to anyway you have to [39:18] store the key [39:19] somewhere then you can you can create [39:23] it okay so yeah I I think my point here [39:26] just save some I think my point here is [39:28] 8 gabes is probably too [39:31] big yeah probably I think most of them [39:34] just use like a few hundred megabytes [39:37] maybe even smaller than [39:40] that but we probably can check um but I [39:43] think maor is probably is just use a few [39:46] hundred [39:49] megabytes yeah so it's I think it's a [39:52] few 100 megabytes I think Rock DB is uh [39:55] Rock DB is like uh [39:58] 100 megabytes less than 100 like 10 [40:00] megabytes or something it's pretty small [40:05] um if this is long [40:12] URL yeah so yeah so some maybe you can [40:15] maybe you can use a hash as a [40:18] key oh oh oh yeah so but you you're [40:21] designing a database you don't you don't [40:23] really actually tell what application [40:25] developer do so application developer [40:27] you should assume that application [40:29] developer can do whatever they [40:31] like okay yeah that that is good [40:34] question if the key is huge and then [40:36] this database uh just become a a storage [40:40] of the [40:43] key [40:45] yeah yeah so that's why I probably want [40:47] to limit the key so for example here you [40:50] may see the key than or something yeah [40:53] the key size cannot be too long the [40:56] because normally when we [40:58] Define primary key we never use a very [41:01] big key normally use very a small a [41:04] string yeah okay I think I think you you [41:07] you you are conceiving the [41:10] you contri uh you are making up a [41:15] deliberately make up the the the [41:17] question hard because normally we [41:20] normally we don't have the a huge [41:23] key oh oh yeah yeah it's actually it's [41:27] actually not uh I think it's actually a [41:30] real use case in in Google they actually [41:32] start yeah they actually start YouTube [41:36] as a key I think it's use it yeah and if [41:39] you look at uh uh Google uh if you're [41:44] looking at the Google um the how they [41:46] design the big table table Yeah so they [41:50] actually use URLs they reverse URL use [41:53] URL I think it's a real use case um but [41:56] here Point yeah here it could be any use [41:59] case if the KY length is 10 times or [42:01] even larger than the value yeah but how [42:04] about if uh if our our YouTube url is [42:08] greater than one kilobyte that means we [42:10] cannot use this database interest yeah [42:14] so probably want to process that part [42:17] but here 1K just like some number came [42:20] up face I'm seeing you need to limit the [42:22] key set right otherwise okay major data [42:24] is key u Okay so let's assume that [42:28] something let's assume that you want [42:29] let's give another example here you want [42:33] to search for record 501 and but there's [42:36] no F all the [42:41] tables [42:44] uh okay so if it is not in this table [42:47] then we need to [42:50] go [42:53] uh so we uh actually um [42:57] we need to go go down to [43:02] the yeah then uh so this is when we [43:06] write the data so it will store the [43:09] exent but when we read the data actually [43:12] the request will be sent to uh sent to [43:14] each load uh by the uh coordinator and [43:17] then uh each workload have have maintain [43:21] uh a local uh range of the [43:29] the key the key and then we can we can [43:32] send a request to each load and say if [43:35] you have this uh record uh in your [43:39] storage and then each load will return [43:42] will [43:43] return response say I have I have if I [43:47] don't have then you just I don't have [43:49] then if it has then you just return the [43:51] record to the coordinator and then the [43:53] coordinator just the uh the merge the [43:57] responses from different different [44:00] worker actually there's some uh cons uh [44:02] consensus uh a quum uh yes [44:07] [Music] [44:08] so and then coordinator will merge it [44:12] and then return to the client yeah I [44:15] think we are talking about different [44:17] issue here I think what you're talking [44:19] about is that you you you basically [44:21] talking about record uh Discovery okay [44:25] Discovery right you're talking about [44:26] given record like [44:28] 501 yeah and you have thousands of notes [44:32] Here thousands of notes here and which [44:36] data record is here I'm talking about [44:38] something very simple you just give a [44:41] record file over you're looking for this [44:43] single node and yeah we can talk go back [44:46] to record Discovery later okay so okay [44:49] so just a single node [44:52] uh if for single Lo if we couldn't find [44:55] it that means we don't have it right we [44:57] don't we don't have it yeah but what's [45:00] the issue here can you see a [45:03] issue that means we have to check uh we [45:07] have to check this the memory table and [45:09] the the three levels of uh [45:13] SST [45:15] yeah it's kind of [45:21] slow yeah so maybe we can maintain a [45:24] global uh it a global range of this [45:33] um the global index to improve it uh [45:38] Global index may not be doable because [45:40] your index may be larger than your data [45:42] yeah that's F then then we have to check [45:46] it one by [45:48] one okay um can you think of some other [45:51] potential uh optimization for this [45:54] part um [45:58] okay the record [46:04] um so we can then we cannot do index [46:07] maybe oh okay because it is a [46:10] solid it is a solid string so we can [46:13] just do barer [46:17] search right but uh I think the majority [46:19] here the majority difficulty here like [46:22] majority lency here is loading from disk [46:26] to memory and loading from disk to [46:30] memory is proportional to the index size [46:33] which means that it could be [46:34] proportional to the S table size because [46:37] index could be the key could be same [46:40] size as the S string typ table no no I [46:43] think we just need to read the first [46:45] record of the of the for example level [46:47] one we just read the first record and [46:49] then we read the last one I think that [46:52] that should be very uh trivial uh cost [46:55] so we don't have to load [46:57] from dis to memory I think oh no I don't [47:00] think so I don't think that's actually [47:02] the [47:04] case you mean we need to load the the [47:07] whole SST uh we need yeah we need to [47:10] probably load from L1 to L3 all all them [47:14] because depends you know you're not [47:16] writing so you're not going to say like [47:18] level one is uh A2 C and level level two [47:23] is uh like a D2 no that's not not even [47:27] that I mean even for for the just for [47:29] level one SST right so uh we know uh we [47:32] know the key SED so then we just read [47:34] the first record uh of the file actually [47:37] we don't have to load all the memory no [47:40] not all of them into the memory right we [47:42] but assume that it's big enough then [47:44] assume that the dictionary then all them [47:46] going to look like something like this [47:48] right yeah yeah yeah yeah yeah yeah then [47:50] we just need to read it first and then [47:52] we we know the size of we know the r [47:55] number then we just uh we just to or [47:57] maybe we know the size of the the file [47:59] then we just read [48:01] the the next one uh we just read the [48:04] last one and then [48:07] window uh but assume that it's big [48:10] enough then it's all going to be look at [48:13] the first record is a the last record is [48:15] z something like [48:16] that just like that we we can do some we [48:19] can St we can store some metadata uh in [48:21] the head of the of the SST and then we [48:25] use that metadata to do [48:29] sear okay so yeah what kind of metadata [48:33] we are talking about here uh like just [48:36] uh uh just how for example the [48:40] the the the key for example we can just [48:44] some just like [48:45] the uh so just as they say uh uh how [48:50] long is the first record and and what is [48:53] the next say for example what if the [48:56] first record St with a that the second [48:58] second record starting with b and how [49:01] long it would how long it is then we [49:03] weuse some then with with this metadata [49:06] information we can pinpoint to the [49:08] location of the record and we know the [49:12] we know the the the how to part this is [49:17] something like a partition path and then [49:19] we know we we can pinpoint the record [49:22] and we know this record belongs to which [49:25] partition so it's U it's not about [49:28] partition right I think the difference [49:30] between it is not partition but but [49:32] something like that then we just we just [49:34] use use a way to to know uh uh which [49:37] part of this record belongs to then we [49:40] can use this R500 and zero [49:45] to yeah to find to find this five R 500 [49:49] Z 5001 [49:52] sorry because I always think we don't [49:55] have to load all the SST from dis to [49:58] memory I think Lo loading all from dis [50:01] to memory that is a huge uh [50:04] cost I have that kind of a feeling yeah [50:07] I feel I have some way to to to to do it [50:11] in a faster [50:14] way okay so here uh I think the okay [50:18] let's we can actually skip this part I'm [50:20] thinking something you can use a bloom [50:22] filter here Blom filter oh Bloom filter [50:25] to check the existence of This Record [50:28] yeah but you want to search it right but [50:30] you want to search get the whole record [50:32] you don't only need to you don't you you [50:35] not only want to know if it exist you [50:37] only want to know the you only want to [50:40] get it uh read so if it don't exist then [50:44] you just you know you know it's not [50:46] exist so you don't even need to search a [50:47] m table oh okay then then in that case [50:50] then you can use a bloom filter right in [50:53] that case you can use the bloom filter [50:55] yeah okay okay yeah yeah yeah okay [50:58] that's fine um that that's a great point [51:00] but I didn't think you just want to load [51:02] the existence but if you yeah if you [51:06] just want to look that a broom F filter [51:08] is is the best solution I think okay [51:10] okay sounds good um can we go up uh I [51:12] think the we have discussed extensively [51:15] for SST and then let's look at the [51:18] result um so we basically can support [51:21] write read and delete uh no problem and [51:24] we can we can support compos a primary [51:27] key actually we need to have little [51:29] discussion here let's let's say uh let's [51:31] go go below uh let's give example here [51:35] let's say uh in the second page uh let's [51:38] say uh we have some K so someone Define [51:40] K as um uh ZIP code U somehow let's say [51:45] uh we want to do some um yep yep right [51:49] so we want to do some yep so the ZIP [51:52] code okay zip code user is partition key [51:55] and then uh then you have [51:58] activity and you may have something else [52:01] like activity time them maybe uh [52:08] um activity anyway so [52:12] location you already have maybe time [52:15] maybe time maybe maybe time yeah maybe [52:17] time time St oh yeah okay so and maybe [52:23] Additionally you want to have um [52:27] yeah I think this is good enough how [52:28] many people long okay that's good enough [52:32] yeah yeah so let's assume that uh this [52:36] ZIP code is a string and user ID is a [52:39] your ID activity is your ID time stem is [52:45] uh time stem okay okay so how you going [52:49] to convert this to a internally how you [52:52] going to convert this you mean this is a [52:54] key this is just a key right that's a [52:56] compos key yeah this a composite key um [52:59] composite key great question so [53:04] the so we uh we need partition key we [53:10] can use the zip code and the partition [53:11] key maybe in this case but this is [53:14] actually this the first is the first [53:16] part is is also a composite key because [53:20] it's all composite key it's it's a very [53:22] complex key yeah yeah this itself is a [53:24] composite key um then we [53:29] can okay so so so so we we need to uh we [53:32] need to uh uh so first we need to use [53:35] this and a we can use this as a [53:37] partition uh [53:40] key and inside this is partition then [53:44] then then we decide which this uh which [53:47] uh which machine which load this record [53:50] will be stored in [53:54] um yeah so the so that means we [53:58] can this ZIP code yeah we can use this [54:01] ZIP code and and you user ID because zip [54:05] code is limited we we only have that [54:07] number of zip code but this U ID maybe [54:11] we can give the range or maybe we can [54:14] just let's say we can use the first [54:16] letter of the U ID uh of the user U ID [54:22] uh yeah [54:24] as to to to find to find the machine [54:28] let's say we have we have 24 machine [54:30] let's say uh then we can map this 26 [54:33] machine we we can map the later from [54:36] user U ID to then machine [54:39] ID yeah so so so we can use this and the [54:43] partition key or maybe shot key and in [54:45] in one machine uh then we can use this [54:49] uh activity U ID as another level of of [54:53] sharting inside the machine [54:57] and it's time St yeah it's already Bing [54:59] the machine why you need another level [55:01] of charting [55:04] here let's say uh let's say this one is [55:07] for the for for for the data center [55:09] right this one is for the data center [55:11] this activity is for the for the for the [55:13] for the rank and this one is for the [55:16] machine for example so sorry yeah not [55:18] notate data center level and this rank [55:21] level and this machine level oh but um [55:25] in in in currently uh in Internet U [55:29] wouldent you actually don't know which [55:31] server are in which data you know which [55:34] server in which data center but uh isn't [55:36] that too much uh too much information [55:39] for Server know which rec or which uh [55:43] yeah V track the [55:45] serviceing uh so okay so we know the [55:48] data center but okay so then we can use [55:50] this as the rank to to find the rank and [55:53] this to find the [55:54] machine uh this one I think uh inside [55:57] that [55:58] machine uh we use this as the as the the [56:03] real hash [56:04] key uh I think we are talking about [56:07] different level abstraction here okay so [56:10] I think in in currently we over has [56:14] inside of data center we have this names [56:16] um DN right domain names uh sorry domain [56:19] name server so you're going to have [56:22] something like ad hoc server like ad hoc [56:24] one like maybe say uh San Francisco then [56:29] then the DNS mapping is AD hog by San [56:31] Francisco to IP address like something [56:35] like something right so you don't really [56:37] know you have no idea which you you [56:40] probably have some idea which data [56:42] center it is see um because you can have [56:44] some knowledge information from ASAP but [56:47] is it too isn't it too much to say um [56:50] which rack it is in and also [56:52] additionally additionally uh this [56:56] machine made that right but the name may [56:58] be changed to something else assume that [57:00] this this machine that you may change it [57:02] to something [57:05] like uh [57:07] yeah but you talking about the but here [57:10] I mean uh so we have a record and we we [57:13] just write to the uh coordinator right [57:16] and then coordinator we decide which [57:18] machine we This Record should be stored [57:20] right so there's no DNS there right we [57:23] we only have the DNS of the coordinator [57:25] right [57:26] but as a cluster we don't know which [57:29] real server the virtual sorry the the [57:32] coordinator is just like a just like a [57:34] Gateway just like a virtual server just [57:36] like a some Gateway there but when we [57:39] write to the cassendra database we don't [57:42] know which machine it will stored which [57:45] we even don't know which data center it [57:46] will be stored in right yeah that makes [57:49] sense you you don't really care you just [57:51] want to know the IP address yeah we just [57:53] need to know the Gateway machines IP [57:55] address and then we write to there and [57:57] then the gway uh the the coordinator or [58:02] maybe the gway we call it so we we [58:05] decide which uh data center which rank [58:08] or which machine it goes and and there [58:12] even a program called a snitcher to to [58:14] to to to detect to detect the network [58:18] the network situation uh and decide [58:21] which which is the fastest way to go or [58:24] or yeah anyway I mean I think this we [58:27] can use this partition key to decide the [58:30] uh to decide [58:32] the which uh which file in which machine [58:36] in which in which file in which [58:38] directory in which machine in which rank [58:40] in which data center uh the the record [58:43] will be stored oh okay so I think my [58:46] point here is um actually my my question [58:51] here is relatively simple uh it's just [58:53] how you how you convert [58:56] this uh composite [58:58] key composite key to to uh because [59:01] you're going to to use hmap right how [59:03] you convert this component key to a key [59:05] in hashmap let's see [59:07] this uh oh okay so [59:12] uh I say you you mean the the the the [59:16] schema or maybe the data model of of the [59:20] of this uh of this [59:22] database okay so uh actually uh [59:26] okay I see uh I'm not sure you okay so [59:29] so so [59:31] uh so actually uh the data will be [59:34] stored in raw oriented database or this [59:37] is [59:38] or oriented oriented and and inside this [59:43] uh inside this RW uh there will be uh [59:45] there will be [59:47] a this the first key is this the Z code [59:51] and the and the [59:53] user uh and under this uh there will be [59:56] uh a lot of [59:58] activities uh the the next level is [60:02] activity this is called uh column wise [60:05] Row the white wide column something okay [60:08] so any so this is [60:12] activity [60:14] uh and and this is [60:17] the level of the and then activity and [60:21] and and the time stamp time stamp um [60:26] yeah so for for example for the same uh [60:29] for the same uh uh key of uh key of Z [60:34] and user actually you you can you could [60:36] have U multiple uh compilation of [60:39] activity uh and time stamp you can you [60:42] can you can also St it [60:45] here [60:47] um yeah so so you can you can you can [60:50] start them here [60:53] um uh I I think talking about the column [60:57] family column colum column family yeah [60:59] column family that's actually the value [61:01] part right in value you have this column [61:03] family yeah in val have that [61:06] one I think I got confused here some [61:10] concept get confused yeah yeah okay uh [61:14] yeah let's actually um because we have [61:16] only 15 minutes now let's actually look [61:18] at the isolation level and the system [61:20] requirement and see what we can optimize [61:23] to meet the requirement here [61:26] okay so R don't block right right don't [61:30] block R so that means we have different [61:33] uh uh isolation level yes uh this one we [61:39] can I think uh single object transaction [61:42] the mul transaction support [61:45] dump we can use something called mvcc [61:48] the multiv version concurrency [61:51] control [61:53] uh we don't block right yeah to make [61:57] sure there's [61:58] no no little dirty read and right [62:05] uh multi object transaction yeah can you [62:09] give actually one example [62:11] here uh let's say R don't block right [62:17] uh so when you uh okay when you when you [62:21] write the data uh then you get a [62:24] snapshot of [62:27] uh of that record [62:30] uh and then [62:33] uh and then you just write to to uh to [62:38] to the slapshot but uh when another [62:41] thread uh uh comes in and read the data [62:44] is just the read from the original [62:50] version okay yeah yeah I see how you [62:53] manage a snapshot and original version [62:57] how manage is a snapshot original [62:59] version uh can you give like example [63:02] here you can you can use time uh you can [63:05] use time stamp yeah you you could have [63:08] multiple version and and different [63:10] version have different time [63:12] stamp or maybe some U ID plus time stamp [63:17] so you can get a you leak a [63:20] snapshot for the current thread [63:26] um what's the time stamp this is is this [63:28] commit time uh you know what time it [63:31] is is a WR written time commit time uh [63:36] it it's com uh it's commit time for the [63:38] original one it's just is a commit time [63:41] yeah it's commit time I think it's [63:43] commit [63:46] time okay uh say so basically say you're [63:49] saying when you read a key you get a [63:51] list of list of record and each record [63:54] will have a commit time and depends on [63:57] when you read it you make sure some [63:58] record are visible some record not [64:02] visible uh yeah when you for for [64:07] the for the right for the right slam for [64:09] the slam shot is not readable is not [64:12] visible to the read uh for to the read [64:17] thread but the read thread should should [64:19] have the view of the current the [64:22] whole the whole table [64:27] okay so [64:30] um so how do you tell if a record is [64:34] visible for example uh you have read and [64:36] write in parallel you know it's [64:39] concurrently you have read and write [64:40] concurrently so how do you know which [64:43] data is visible to the r [64:46] SL okay so so so all the next all the [64:49] commit uh all the commit string the all [64:53] the commit time uh [64:56] it's just with if if this if there a [64:59] snapshot then it the the it have some [65:03] some uh let the commit time plus [65:06] uid the tank with it if if if just know [65:09] that kind of tank then then then it is [65:13] visible so the commit time is before [65:16] like if commit time is before your [65:18] transaction is visible like after a [65:20] transaction is invisible right something [65:22] like that yeah after the transaction if [65:25] it mitted then then yeah then there [65:29] won't be that special tank then that [65:31] means that it is materialized it it's [65:35] committed then you can read it it is [65:37] visible yeah [65:40] okay okay makes sense um yeah I think he [65:44] solves the r don't block rate red don't [65:46] block right and um how in that case how [65:49] would you like to handle like single [65:51] object or multi object transaction and [65:54] yeah let's let's look at this problem [65:56] first a single object [65:59] transaction this I still haven't read [66:02] about this part single object multi [66:04] object trans oh okay so yeah okay [66:08] familiar not familiar yeah yeah I I [66:10] still haven't read about this [66:12] part yeah so [66:36] passive transaction [66:51] control optim optimistic [67:14] B [67:33] [Music] [67:44] broken [67:55] the [68:09] optim okay a [68:24] single optim [68:37] object [69:04] data center MTI replication m center [69:08] production Center M replication [69:46] app develop [69:59] link l [70:38] [Music] [70:51] optim [70:52] transaction recover [71:00] transaction [71:14] recover okay so let's actually F we only [71:18] have 30 minutes let's actually uh finish [71:21] try to finish the interview in five [71:22] minutes uh we still I want to finish [71:24] little bit rest part uh how do you [71:26] handle the snapshot part how you want to [71:29] dump the [71:30] snapshot dump a snapshot [71:34] uh yes [71:38] so yeah then we have we have different [71:41] version of this uh uh okay so that that [71:46] is a snapshot for re okay so the down [71:49] dump the database [71:51] snapshot uh support d [71:57] yeah I still haven't checked [72:00] it no idea no idea that's that's fine [72:04] that's fine let's look at the last few [72:06] part last few requirement here I think [72:08] the database because you write on the [72:10] sequential right so it's going to be uh [72:13] naturally optimized on the rest through [72:15] put and uh and also we talk about [72:18] several ways to uh um um focus on how to [72:22] make it low lency and uh here so let's [72:26] actually focus on two part uh can you [72:28] actually uh comparing this database to B [72:31] Tre what do you think is a what do you [72:33] think which kind of access pattern is [72:35] faster which kind of access pattern is [72:38] slower so the B tree I think the rate [72:42] axis pattern okay [72:44] so [72:47] uh so uh [72:50] the so if you have a lot of uh [72:55] access panel you mean the read [72:58] or so the p is okay you say yeah sorry [73:03] uh it could be a combination of read [73:05] right it's really you know it the [73:06] combination of read right which part is [73:08] faster for B3 which part is faster for [73:11] this this you the you design the B the [73:14] read for the B3 will be definitely [73:16] faster but the right of the B3 will be [73:19] uh much slower than than this design [73:25] uh is is this uh I I think for certain [73:29] yeah I think for certain rate this might [73:32] be faster for certain rate this might be [73:37] faster okay so uh if there's no uh [73:41] duplicate [73:44] key if there no duplicate key no uh [73:48] let's see L if there's no update no [73:52] upsert maybe the read will be very fast [73:56] for this one because you don't have to [73:59] go you don't have to dive into the SST [74:02] and to to check you just need [74:05] to you you don't have to do the do the [74:08] merge thing or or or or [74:11] compaction if if there's no compaction [74:14] required then the system performance [74:16] will be much [74:17] better [74:20] uh yeah [74:22] so the drawback of this design is uh I [74:25] mean the [74:27] delete the delete is upsurt that will [74:30] cost that will cost a lot of [74:35] time yeah but but but the right will be [74:39] definitely the right will be definitely [74:41] fast faster and and uh higher available [74:46] than than b [74:47] Tre because B3 you have to adjust the [74:50] the the the the height of the [74:53] tree uh [74:55] yeah so I think for this one if you read [74:58] the recently data recently data it's [75:00] going to be faster than b right because [75:03] most of recent data is in memory M table [75:07] uh yes yeah correct yeah okay uh the [75:10] last part is horizontal scalable how do [75:12] you want to horizontally scalable this [75:14] service uh this uh this one's uh so you [75:19] can use consistent hash to do the uh to [75:24] do the SK to to scale uh to scale the [75:27] whole [75:27] cluster uh so then you just can and and [75:31] and and a machine and a new Lo into this [75:34] the cluster and it will be so so it is [75:39] linear the performance [75:41] uh so the [75:43] linearity is is much better than the [75:46] orig the traditional uh old school uh [75:50] like [75:51] post the relational database so this [75:55] database is very uh good for uh scale uh [76:00] for scaling uh especially horizontal [76:05] scale it just append the new data [76:10] and [76:12] uh yeah you do consistent hash and the [76:16] the the data migration will be very [76:19] minimum uh and then you add the capacity [76:22] for the system [76:27] yeah when you do yeah yeah I think [76:30] consistent Hing is [76:34] fine I'm I'm thinking of the I'm [76:37] thinking of possible Corner case maybe [76:40] forance Corner case of consistent hation [76:50] uh okay uh I think it's fine I think the [76:53] hasing is fine but the difference [76:55] you don't have node like come and go [76:57] very frequently it's more like [76:58] infrequent because it's all no in data [77:00] center yeah should [77:03] be in that case maybe uh you can we can [77:07] use some uh some something like cord [77:11] like I remember uh uh we have we have a [77:15] a b torent client actually in that case [77:18] the load come down go very fast the Cod [77:20] right the code and the ner yeah yeah [77:23] yeah so yeah that's [77:26] yeah then then in that case the the node [77:28] come that go very fast it's it's a very [77:31] Dynamic uh network but we still have can [77:35] get a get a good [77:37] performance yeah yeah U so I think yeah [77:40] it's I I think it's working I don't see [77:42] a issue here uh I don't see a issue [77:48] here give me yeah give me 10 second let [77:51] me see [77:59] yeah I don't think there [78:10] um proportional to proportional to node [78:44] cons migration [78:55] proportional to the node number [78:58] [Music] [79:26] [Music] [79:33] data [79:35] Discovery record discovery [79:40] [Music] [80:14] proportional to [80:26] consider migration [81:22] transaction [81:52] hard [82:09] Focus isolation [82:12] level system [82:23] requirements of system [82:27] requirements [82:43] simar on [82:47] envelope is a good point [82:53] [Music] [83:09] transaction [83:52] distri [83:58] replication [84:10] parac transaction [84:43] cross topic [84:45] transaction committed committed [85:19] thank you yeah thank you Scott yeah [85:21] thanks h [85:35] single multiple [85:37] trans [85:42] fa single object multiple [85:48] object single object mple object [86:08] sorry multiple object [86:28] object associate impact [86:31] object [86:49] relation cross [86:52] transaction two commit [86:55] mple object [87:35] trans [88:21] yeah thank you Scott thank thank you sh [88:23] and [88:30] everybody thanks [88:31] everybody byebye