工业界资深数据科学家教你破解各大公司面试
FLAG等各大公司数科面试真题讲解

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 761|回复: 17
收起左侧

[系统设计/OOD] 分布式系统设计自学整理

[复制链接] |试试Instant~
我的人缘0
amcw7777 发表于 6 天前 | 显示全部楼层 |阅读模式
该内容以做模糊处理,您需要登录后才可查看. 登录 | Sign Up 注册获取更多干货
本楼: 【顶】   100% (4)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
下周面试,希望能用一周时间按照自己的逻辑整理一下之前所学的分布式系统知识!


补充内容 (2018-11-9 09:57):
计划目录:
1. GFS
2. BigTable(SSTable)
3. Cassandra
4. MapReduce
5. Spark
6. Zookeeper
7. Kafka

评分

参与人数 12大米 +73 收起 理由
kdzhang + 5 很有用的信息!
heymine_ + 5 给你点个赞!
我爱我老婆 + 1 赞一个
零度好冷啊 + 3 给你点个赞!
Octave Dijk + 3 很有用的信息!
zzwcsong + 30
Georgeapex + 1 赞一个
zhuang1992 + 5 很有用的信息!
kevinnote620 + 5 给你点个赞!
Pro MacBook + 5 给你点个赞!
vividlau + 5 给你点个赞!
熊猫杀很大缺积分 + 5 很有用的信息!

查看全部评分


上一篇:大神们帮忙分析下代码哪里有问题Leetcode 46 题 Javascript
下一篇:刷题题打卡日志

本帖被以下淘专辑推荐:

  • · CS|主题: 229, 订阅: 14
我的人缘0
 楼主| amcw7777 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
1. GFS,先从最底层数据库结构开始了解,很多内容没有完全消化,这是我一次读paper的总结,希望以后慢慢了解更多,错误的地方希望大家指正!
GFS(Google file system): a distributed file system, 用来存储数据,作为BigTableSortedString Table的底层), 也是HDFS的真身。把文件放在很多个disks上,能够满足大量读写需求。
GFS的目的:
1. Fault-tolerance: 假设有1000个机器,每个机器每年会坏一次,那么每天就有大概3个机器会挂。如何确保数据安全?
2. Performance 大量的同时读写,如何处理I/O
3. Consistency:如果有多个人同时读写,如何确保最后读到的是最新的数据
4. Efficiency:如何最优使用网络bandwidth来传输数据
GFS之前的文件系统:
1. 每个文件分成blocks 4096byte),每个文件有自己的Metadata,记录文件名/时间/size/blocksdiskoffset
2. Master-slave 系统:数据都存放在master上,slave是备份,master挂了,找一个slave顶上去
3. 缺点:随机访问速度慢,多进程读写需要锁进程,数据存放在一个master严重依赖badnwidth
GFS的结构:
1. client,比如SSTableread/writefile to GFS
2. Master,这里的master跟一般文件系统的不一样,不存放数据,memory中存放
3. Chunk servers,存放数据的metadata和一个hashtable[filename][chunk_index] = chunk_server
4. chunks,和一般的4096 block不同, GFS的数据每一块比较大,default用的是64M,这样metadata就比较小了。建立在小数据碎片很小的基础上。
5. Megadata, 64Byte 每个chunk
6. Replica 每个数据存3次,在不同的chunkserver上,以防止chunk server 挂了
Read:读数据:
1. Client 发送 filename master
2. master 找到这个filemetadata 然后找到相应的chunk list,最后在hashmap里找相应的chunk serverlist,返回给client,这些数据会在clientcache
3. Clientchunk server list 对于每个chunk,对应最多3server,根据IP地址选择最近的server来读取数据
*4. 实际上会有一个 version的信息,在每个数据里和chunk server list,如果在server数据里的versionchunk server 不同就重新连接master
*5. Client 会吧server list 放进cache里,这样就不需要每次都问master
gfs-read.png

Write: 写数据:(这里的写指的是modify
1. Client filenamemaster
2. master恢复chunk server list,这里跟读一样,但是chunkservers分成两种,一个叫primaryreplica,一种叫secondary replica
3. 把数据写到三个replicacache里(!!不是硬盘,是LRU cache
4. Client 发写请求给primary replicaprimary把最新的文件写到硬盘
5. Primary 把写请求 forward给两个secondary secondary  data
6. 写完之后secondary告诉primary写好了
7. primary 回复client 如果出错就重复3-7
*和传统方法不一样的是,GFS写数据提供recordappend方法,用来保证多client同时写
gfs-write.png
系统优化:
1. 一般不需要第二个master 如果挂了去重启就行,但是master会存一个log到硬盘,重启之后从log恢复state
2. 如何判断chunk server是不是挂了:heartbeat message
3. 如何判断一个chunk server上某个block挂了: Achunk is broken up into 64 KB blocks. Each has a corresponding 32 bit checksum.

评分

参与人数 8大米 +89 收起 理由
Killua1222 + 5 给你点个赞!
Warald + 60 很有用的信息!
Pro MacBook + 5 很有用的信息!
chiyu + 1 赞一个
熊猫杀很大缺积分 + 5 很有用的信息!
mayingjie116 + 5 谢谢分享!
monkey_cc + 3 好资料啊!
玥儿账号又丢了 + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
rsy56640 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
amcw7777 发表于 2018-11-9 09:43
1. GFS,先从最底层数据库结构开始了解,很多内容没有完全消化,这是我一次读paper的总结,希望以后慢慢了 ...

分享一个 levelDB (SSTable) 资料:leveldb-handbook.readthedocs.io/zh/latest/

评分

参与人数 1大米 +3 收起 理由
amcw7777 + 3 谢谢~我最多就能给3米哈哈

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| amcw7777 发表于 5 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
BigTable: a NoSQL database (Column based) based on GFS
补充:大数据中常见的两种NoSQL:1)key/ value based like Redis or MemcacheDB 和 2)column based, BigTable
SSTable的数据结构:
1. Rows (key) : 最大64KB 的字符串,在SSTable中,是按照Row key 排序好的,顾名思义,sorted string table
2. Columnkeys: 一个set,可以支持range query
3. value:包括两部分,第一部分是value, 第二部分是时间timestamp,是一个64bit的整

SSTable的文件格式:原则是不能修改,只能append,根据timestamp来决定哪个是最新的value
1. 分成datablock, 每个block 64
2. 在SSTable最后有一个 block inde
3.查询SSTable先 load index然后二分查询 (不能放进内存用hashtable查询!)
Bigtable 系统:
1.Master server: 负责测试tablet server是不是在工作, 处理GFS的sharding等,在Bigtable中,Client是不会和master交流的,要和Lock交流
2. Lock server: 用Chubby或者zookepper实现,完成多进程的锁,用metadata查找key所在的server
bigtable-lock.png
3. Tablet server: 处理读写操作
写操作:
1.Client ask lock
2.Lock return a tablet server and lock it
3.Go to tablet server, 1) write to 1) commit log (write ahead log) in disk and 2)memTable in memory. If memory down, recovery from log
4. Minorcompaction: when memory hit the threshold, frozen this one and write to GFS asa SSTable
5.Major compaction: Merge SSTable, with same row key, use the most recent record.
6.After all, client ask lock to unlock the tablet server and update the metadata
读操作:
1. Clientask lock
2.Check metadata, return the tablet server and lock it
3.Go to tablet server, first check memTable
4.If not in memTable , check tablets one-by-one
5.For each tablet, check the index firstly. So the worst time is O(mlogk), m isthe number of tablets, k is the length of each tablets.
6.Retern value and unlock the server
其他重要的scale化:
1. readcache: tabletserver上,1)scan cache 保存已read的key/value,化重复read; 2)block cache,存GFS上SSTBlock,优化读取附近的key(不是很懂)
2.Bloom filter对每SSTable加入一个bloom filter (多个hash函数来确定的一个bit filter),如果key没有通SSTable的bloom filter,就不用read SSTable的index了,省去了二分的时间

回复

使用道具 举报

我的人缘0
Euler57721 发表于 5 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (497)
 
 
20% (132)  踩
一般不需要第二个master, 如果挂了去重启就行,但是master会存一个log到硬盘,重启之后从log恢复state

这样不是就有downtime了么?另外,NameNode在现实中承受的大量QPS,很容易挂掉。现在大一点的文件系统Metadata都是分布式存储的。
回复

使用道具 举报

我的人缘0
 楼主| amcw7777 发表于 5 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
Euler57721 发表于 2018-11-10 01:21
这样不是就有downtime了么?另外,NameNode在现实中承受的大量QPS,很容易挂掉。现在大一点的文件系统Met ...

谢谢大大的回复!我想了一下你的问题:
1. Master建立自己的replica,同时setup shadow master。Shadow master平时设置成read-only,可以在master当机的时间load replica,并且代替master工作。
2. 如果64M的data,有64B的megadata,那么1PB的data,megadata也就1G,大小足够放在内存了,假设放在了memcached里,100k的QPS,应该足够多的hadoop来map了?是不是真正工业界的service scale比我想象的大很多啊。。
3. 请教一下大大,我过几天要去databricks面试,因为我是new grad不大了解工业届,你觉得我应该跟面试官聊啥?谢谢!
回复

使用道具 举报

我的人缘0
Euler57721 发表于 5 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (497)
 
 
20% (132)  踩
amcw7777 发表于 2018-11-10 01:46
谢谢大大的回复!我想了一下你的问题:
1. Master建立自己的replica,同时setup shadow master。Shadow  ...

回答你的问题。
2. 现实生活中data不总是占满64M,会有大量几k几十k的文件碎片,1PB的metadata至少在几十G。大一点公司的storage QPS都是用million计的。
3. 面Databricks你应该研究Spark和Flink,他们又不做Storage

补充内容 (2018-11-10 02:19):
另外,作为面试官我肯定会考的问题:
1. 怎么保证Master和Shadow master一致性?写一半挂了怎么半?

评分

参与人数 1大米 +3 收起 理由
amcw7777 + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| amcw7777 发表于 5 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
谢谢~
加入QPS是10M, 每个内存的QPS是100k,所以需要100个server来负责matadata的处理?那样的话一致性就很难确保了呀,是有什么特别的方法吗?
我的计划是一会把p2p的NoSQL整理一下,然后就走一下MapReduce -> Spark,我觉得对数据库理解深刻一点对后面系统的bottleneck可能理解更深刻,加上这几篇paper确实写的挺精彩的!
回复

使用道具 举报

我的人缘0
 楼主| amcw7777 发表于 5 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
Euler57721 发表于 2018-11-10 02:15
回答你的问题。
2. 现实生活中data不总是占满64M,会有大量几k几十k的文件碎片,1PB的metadata至少在几 ...

我觉得,可以为master 建立一个private database来写入 log,如果shadow有lag的话,可以从log中读取。
问题:如果有大量的写操作,那么master写入log的I/O会成为一个bottleneck
我记得Raft可以解决这个问题,但是具体原理我不是很清楚。
刚才我回复了自己,粘贴一下:
加入QPS是10M, 每个内存的QPS是100k,所以需要100个server来负责matadata的处理?那样的话一致性就很难确保了呀,是有什么特别的方法吗?
我的计划是一会把p2p的NoSQL整理一下,然后就走一下MapReduce -> Spark,我觉得对数据库理解深刻一点对后面系统的bottleneck可能理解更深刻,加上这几篇paper确实写的挺精彩的!

真的很谢谢你! 希望能指出更多我理解不到位的问题!
回复

使用道具 举报

我的人缘0
 楼主| amcw7777 发表于 5 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
Cassandra简单看一下,主要总结一下consistanthashing,今天重点是MapReduce,如果以后有需求再revisit

特点:NoSQL,peer-to-peer,column key
主要技consistant hashing
特点:容易展(consistant hashing),单值读写快,一致性高

Consistent hashing:
1. 加入有一个,等分成2^64份
2. 在加入一个机器A,在上随机3个位置置成A的三个virtual nodes
3. 来一个key,hash成0-2^64的一个,从值顺时针找到第一个virtual node,就把这组key,value)存放在node上
4. 加入新机器,比如已A,B加入C,是随机生成3个C的virtual nodes。然后把C到A之前的data从Btransfer到C
5. Repica: 不仅仅存在key后面第一个virtual node上,而是存在三个node上
consistent-hashing.png


回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-11-15 08:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表