分布式系统

什么是分布式系统

用多台机器解决一台机器解决不了的问题。
两派：

1. 多台便宜的机器。 Google
2. 高性能的机器。 Sun 太贵了

谷歌三剑客

GFS Google Distributed File System 怎么存 高富帅 (C++实现)
MapReduce 怎么处理
BigTable 就是NoSql数据库

HDFS 很多分手 (Java) 一帮在狗家没有实现升职加薪迎娶白富美的工程师去yahoo做的开源file system。
文件系统 (Database Server和webserver 都是存在GFS上的）

需要什么功能：

写文件，读文件， 支持多大的文件： 越大越好 > 1000T （100+ PB）， 文件总数也就·1个billion
多台机器存储 10万台 百万台机器
重点是用的是便宜的机器，可以实现成本控制，但机器可能随时会坏， 网络可能有问题，所以设计的时候要考虑进去。

Service:

Client + Server
我们的client是webserver + database serve

多台机器的沟通模式

Peer to peer： 谁也看不惯谁。优点是一条机器倒掉其他还可以干活。 缺点是数据同步问题比较麻烦。
例子Peer 2 Peer: BitComet, Canssandra,
Master slave：缺点单Master一倒，别的不好干活。 设计简单, 容易保持一致。
比较：DB里的Master存数据，Slave 备份数据
GFS（HDFS）的master是管理者不存储数据。 Slave是被管理者（存储数据）
GFS里面用了Master Slave， 大多数系统是用了Master Slave。
HDFS里面的master叫Name Node, Slave叫DataNode

NameNode

Name Node的数据结构是什么样的？在memory里hold 一份 Tree， 同时也有持久化。

Meta data是一个Tree的形式？Meta data能只hold在Name Node的memory上吗？ 一定要持久化。

Name node里的TreeNode具体存什么信息？

可以存路径，权限，timestamp, Block ID
同时Name Node 可以保存一个Hash表来保存block Id to Data node 的mapping

能只有一个Name Node吗 ？ 万一 Name node crash了 ？

需要再找个机器也存一份，互为备件。
然后另一个问题就出现了： 两个Name Node如何同步？ Shared Log : operations(写操作)
看LinkedIn log blog : The Log: What every Software engineer.....
Log可能会太长， 所以还得经常定时的snap shot
Name Node通过heartbeat来跟踪data Node 的健康信息， Name Node也用来追踪new block在哪。

文件存在哪

文件系统 （内存不够，数据库比较适合结构化的东西）
对于一个文件除了内容之外还要存什么 ？ meta data
meta data和文件内容最好分开存。

文件内容是分开存储还是连续存储呢 ？
windows是连续 ，碎片比较多
linux是分开存，分成小块block，缺点是需要去维护。每一块可能只有1k字节。
metadata里存index, block id, diskOffset， 硬盘地址

对于大文件的话1k的block就太小了
Google改成了64M的chunk,
把chunk info放在master上，把chunk的offset放在chunk server上。master不需要记录offset。
HDFS里面还是叫Block的

经验之谈：存10P大小的文件的metadata需要多大。
一个chunk需要64b的metadata, 10P文件的metadata放到1台机器上就可以了

写文件

写文件的时候可以先只创建一个TreeNode，并不一定真的allocate block. （Lazy)
然后再request block（可能是三个block). 因为可能有时只建空文件并不真的写。
然后再像串糖葫芦一下写，并跟client ack， 并跟Name Node确认。

分成很多chunk每次只写一个，传输单位也是一个chunk或者一个block。
分割文件的过程是master做还是client做 ？ Client

写的时候先联系master， master给分配一个chunk server, 然后chunk server找一个去写
1。通知master
2。Assign chunk location (master维护一个chunk to server的map)
3。 Transfer data
4.。通知写好了

写多台机器

写三个机器，谁来写 ？三个机器组成一个队列， 先写给队长，队长再传给别人

怎么选队长： 近的，现在写入比较少的。磁盘用的比较少的
队长挂了怎么办？
每次选的队长是不是一样的？不一样。

写的时候chuckServer挂了怎么办 ？

传的时候可以采用pipeline的方法。并不需要等每一个packet都传完再传下一次，可以一次发好几个（但要有upper limit).

传输失败的情况 或者chunk坏了怎么办。

可以用Ack来发现传输失败的情况。也可以用Check Sum做 。
Client每512个字节做一个CRC32的checksum，把它加到512字节上。
DataNode重新计算checksum然后比较。

chunk坏了怎么办 ？？

add checkSum to chunk 大概一个integer那么大 ，读取的时候
checkSum, md5, sha1, sha256, sha512

什么时候检查check sum ? 读的时候检查？ 周期性的检查。都可以

通过Version number确定谁是好的？？
https://blog.cloudera.com/blog/2015/02/understanding-hdfs-recovery-processes-part-1/

修改，

直接别处写份新的。 在别的地方

读取

先从Name Node去要block location, 这样就知道在哪台机器上。对同一个block可以返回好几个data node并给出相应的data node的信息并推荐排序，然后client自己选哪个去读。

Work Solution

Master的task: 存各个文件的meta data;
存各个文件的map: 读取时找到对应的，写入时分配空闲的 。

单master 够不够 ？

双master, multi master

修复chuck

存三份。
三份存哪儿：
两份存的很近，一份存的远。 存的近的可以方便修复 (Can tolerate 2 failures, Has good data locality, fast block recovery)
ask master for help

选chunk的策略

选最近写入比较少的
选硬盘比较空的

Chunk server down 怎么办

怎么发现
heartbeat

一个master可以管理多少台机器 ？一千台是没有问题的

Data Center :
-- Cluster
(-- Rack, 机柜)
--Node/Server(节点) container

什么时候用文件系统，什么时候用数据库，什么时候用SQL,什么时候用NoSQL
决定因素是 要考虑数据model，和以后对数据的操作类型，怎么用，怎么查询

Reading
GFS论文， http://static.googleusercontent.com/media/research.google.com/en//archive/gfs-sosp2003.pdf
Hdfs论文，http://pages.cs.wisc.edu/~akella/CS838/F15/838-CloudPapers/hdfs.pdf
https://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-hdfs/HdfsDesign.html
https://engineering.linkedin.com/distributed-systems/log-what-every-software-engineer-should-know-about-real-time-datas-unifying