相关协议

应用层协议结构

洋葱式结构，一层包一层。

 

相关协议

IP (Internet Protocol)

实现方式：使用IPv4地址，唯一标识一台联网的机器，基于路由转发。

IP包结构：头，数据

特点：无连接，无序，不保证可靠

 

TCP (Transmission Control Protocol)

实现方式：在IP基础上实现

增加的端口号Port：不同的进程通信。

特点：有连接，有序，可靠，建立连接成本高

 

 UDP (User Datagram Protocol) 

实现方式：在IP基础上实现

增加的端口号Port：不同的进程通信。

特点：进行数据校验，其他与IP相同，不需要建立连接，速度快。应用程序自己检查是否收到，是否按照顺序。

 

DNS (Domain Name Service)

TCP端口：53

作用：进行域名解析

全球有根域名服务，各国各自管理自己的域名分配

 

 HTTP (Hyper Text Transfer Protocol)

TCP端口：80

 

进程和线程

进程

创建：通过fork创建

特点：虚拟内存私有，打开文件私有

线程

创建：pthread

特点：虚拟内存共享，打开文件共享，一个进程可以由很多线程

协程

比线程更小，从操作系统的角度看不见，操作系统仍然认为其是一个线程

 

进程间通信方式

共享内存

在单机，要并发控制，一方修改另一方立马可以看到。

消息传递

可单机也可多机，多台机器间传递如socket通信，pipe等。

消息传递基本格式

请求：功能+参数

功能：功能的ID或者功能名，如HTTP GET, HTTP PUT

参数：输入数据，如编码(Encoding)，序列化(Serialization)

回答：结果+结果数据

结果：结果ID或者结果名

结果数据：也需要编码和串行化

分布式系统

分布式系统类型

客户端/服务器模型

客户端发送请求，服务器完成操作，发回响应。

P2P模型

没有中心控制节点，节点之间对等。

主从模型

有一个/一组节点为主，进行中心控制协调。其它多个节点为workers，完成具体工作

故障类型

Fail stop

出现故障，进程崩溃

Fail slow

出现故障，运行速度变得很慢，如挖矿病毒

Byzantine failure

恶意攻击

CAP定理

数据一致性（Consistency），可用性（Availability），分区容错（Partition tolerance），三者不可兼得。

系统设计理念

简单往往是最好的，怎么简单怎么来。

分布式文件系统

NFS（Sun’s Network File System）

起源

Sun公司1985发布了NFSv2，定义了开放的client/server之间的通信协议标准。

系统架构

特点

1. 1. 1. 从不同的终端都可以访问同一个目录
      2. 多用户共享数据
      3. 集中管理

设计目标

1. 1. 1. 简单快速的恢复
      2. 远程文件操作性能高

保存状态的问题

客户端打开文件时，若文件内部的位置信息保存在NFS服务器中，在发生中断时，读或写的指针位置没有恢复，启动后再写可能面临灾难性后果。

解决方案——无状态

NFS服务器中不保存任何状态。客户端负责主要控制信息，服务器只负责读和写，不保存任何状态。

打开文件

客户端发送一个请求文件命令，服务器返回一个文件标识符，客户端使用此文件标识符对文件进行操作。

读取文件

客户端发送文件标识符，缓冲区，长度，服务器端读取文件后返回数据和文件属性。客户端更新文件记录

写入文件

客户端发送文件标识符，缓冲区，长度，服务器端写入文件后返回文件属性。客户端更新文件记录。

好处：只用重启，什么额外操作都不用

解决方案——Idempotent（幂等性）

在没有其他操作前提下，重复多次结果不变

好处：如果一个请求没有响应，那么就不断重试。

缓存一致性问题

A读取了文件File（version_0.1）放入缓存，B读了文件File（version_0.1）然后在缓存中写，文件变成了File（version_0.2），但是文件并没有更新到文件系统。就会产生问题：

1. 1. 1. 1. A并不知道B更新了文件，A的缓存的文件是过时的。
         2. C无法读取到B的本地缓存文件，无法读取到最新文件。

解决方案——Flush_on_close_consistency（关闭时更新）

在文件关闭时，自动把缓存中的已经修改的文件数据，写会NFS服务器。

此方法只能解决问题2，可以保证C读取到最新的文件。但是问题1依然无法解决。

（用前检查）为了解决此弊端，规定在每次使用缓存之前，必须检查是否过时，可以解决问题1，但是会带额外的性能开销（即使只有一个用户的时候，都会带来大量的确认更新请求开销）。

AFS (Andrew File System)

设计目标

可伸缩性，使得一个服务器尽可能多的支持客户端。

解决polling状态问题——Invalidation

客户获得一个文件就要在服务器上登记（登记制度）

当服务器发现文件被修改，就向登记了的客户发送一个消息，客户就会删除缓存文件并更新。

AFS VS NFS

缓存单位

NFS以数据页为单位缓存，AFS以整个文件为单位缓存。

缓存位置

AFS缓存放在硬盘（所以AFS通常可以缓存大文件。），NFS缓存在内存中。

权限

AFS管理权限比NFS更加详细。

GFS/HDFS

GFS(Google File System)是Google MapReduce系统的基础。

HDFS(Hadoop Distributed File System)是GFS的开源实现，基于Java，是应用层文件系统，与Hadoop捆绑在一起。

应为属于应用层，必须链接到HDFS client库才能使用。

GFS设计目标

大块数据顺序读。

并行追加。

不支持对已有文件的修改操作。（只追加）

HDFS/GFS系统架构

Name Node：存储文件的元数据。

Data Node：存储数据块。

文件切分成定长数据块

每个数据块独立分布在Data Node上

默认每个数据块存储3份，在3个不同的Data Node上。

支持并发读，不支持并发写。

HDFS/GFS打开文件操作

“打开文件请求”发送给Name Node。

Name Node 返回元数据。

需要与Name Node通信一次。

 

HDFS/GFS读文件操作

得到了元数据，之后的读操作直接绕过Name Data，直接访问Data Node。

可以从多个副本中选择最佳的Data Node读取数据。

支持很多并发的读请求。

 

HDFS/GFS写文件操作

写文件是写新创建的文件，不是修改已有的文件。

Name Node决定写在哪个Data Node上。

形成一个数据传递通道，流水线传递方式，最大限度利用网络带宽。

数据传递过程：Primary -> Secondary -> Data Node。

但是此时还没有写进HDFS。此时只是在内存中缓存数据。

Primary给各个节点发送写指令，各个节点返回结果。此时才真正把数据从内存写到HDFS中。

不支持并发写的原因

因为一个写的操作要写3个Data Node。若两个写同时进行，A写Node1，Node2，Node3，选的是Node1为primary，但如果B选了Node2为primary，那么A先写或者B先写，都会有一个的数据的备份被破坏。

并发Append

文件最后一个数据块在同一个primary data node。

相当于单机事务，可以在单机上完成并发控制。

保证append成功，但不保证append顺序。

 

NoSQL

什么是NoSQL

简化了RDBMS的功能，不支持（完全的）SQL，不支持（完全的）ACID，支持非关系的数据模型。

 

应用场景

支持公司某类重要应用，是专门开发的系统。

 

NoSQL和SQL比较

各有所长，不能一概而论

 

 

Key-Value存储

是一种分布式存储系统，数据形式为<key,value>对，支持Get/Put操作。

主要系统

Dynamo

Bigtable

Cassandra

RocksDB

Dynamo

来源：来源于亚马逊公司电子商平台。

数据模型:<key,value>

操作：Put(key,value),Get(key)

仅支持单个<key,value>操作，不支持ACID

 

系统结构

多个nodes组成分布式系统，组成一个环。

每个nodes由dynamo和local storage engine组成

local storage engine：是本地存储系统，使用MySQL或Berkeley DB，存储<key,value>对。

 

节点划分方式-Consistent Hashing

将每个节点划分为固定长度的存储区间，每个node设置一个token。

每个key映射为一个token，token = hash(key)，token∈(min,max)

“向上取整”。

 

故障处理方式

假设某个节点挂掉了，则将其区间合并到后一个节点。如u3挂掉了，那么u3负责的区间由u4管理。

 

备份（3个副本为例）

将当前节点的数据备份到后两个节点。如u3数据，备份放在u4和u5。

 

减少一个节点

改变删除节点的后一个节点区间，备份的往前推一位。如节点u4删除了，那么u5

负责原u4的区间和u5区间。原本节点u5备份u2,u3,u4，变成了备份u1,u2,u3。

 

增加一个节点

区间划分更细，拷贝数据，备份往后推一个。如节点u4和u5之间增加一个节点u4_1，那么将u4负责的区间划分为两半，前半部分u4负责，后半部分u4_1负责。这需要将原本u4后半部分区间拷贝到u4_1。

同时节点u5原本负责u4,u3,u2，现在备份u4_1,u4,u3

 

多副本读写

最简单方法：同时向所有备份发送读请求，等待所有节点答复然后完成响应。缺点是比较慢，需要等待所有节点确认，因为要保证数据是最新的。

 

Quorum机制多副本读

采用交集思想

Quorum(N,W,R)

N：副本个数

W：写完成的回答个数

R：读完成的回答个数。

只要满足R+W>N，就能一定读到最新的数据。

假设3个副本，两个写请求完成，也就是3个副本中有2个是最新的，1个是旧的，若读请求完成个数为2，那么一定能读到最新的，最差的情况是读到1个旧的。

Quorum机制多副本写

向所有副本发送Put，至少等待W个节点响应，就认为写成功，W取决于Quorum机制。

 

最终一致性Eventual Consistency

不能保证短时间内副本一致，但是保证可能长时间后副本会一致。

如Put操作并没有等待所有节点写完成，只等W个节点写完成就默认完成了。最终系统中副本都会变得一致。

优点

提高写效率

避免了访问挂掉的一直等待，提高系统可用性。

 

 

持久性和可用性

持久性Durability：数据不会应为关机而丢失

可用性Availability：即使出现了关机的情况，数据任然可以被访问。（直接关系到用户体验）

 

 

Key-Value存储系统——Bigtable/HBase系统

来源

由谷歌提出

数据模型（以存储网页为例）

<row key,column family:column key,version,value>

row key：唯一标识符，按顺序存储

column family：网页内容，需要事先声明，种类有限

column key：网页的源地址和标签信息

version：版本信息

value：存储的值

row key,column family:column key,可作为key。

具体存储是column family分开存储

<row key,column family:column key,version,value>

忽略version情况下，因为column family是分开存储的，所以一条数据需要多个表存储。

每个表可对应为一个3列的table，列分别为 | Row key | Column Family1:Column Key1|Value |。

第二个表则是 | Row key | Column Family2:Column Key2 | Value| 。

 

BIgtable的操作

GET：给定row key, column family, column key，读取key。

PUT：给定row key, column family, column key，创建或更新value。PUT合并了创建和更新功能。

SCAN：读取某个范围内的所有row key的value。

DELETE：删除一个指定的value。

创建表

格式

create ‘表名’,’column family’

案列

create ‘mytable’, ‘mycf’

 

插入数据

格式

put ‘表名’ , ’Row Key’ , ’column family:column key’,’value’

案例

put ‘mytable’, ‘abc’, ‘mycf:a’, ‘123’

0 row(s) in 0.0580 seconds

put ‘mytable’, ‘def’, ‘mycf:b’, ‘456’

0 row(s) in 0.0060 seconds

 

SCAN

scan ‘表名’

scan ‘mytable’

Bigtable，HBase系统结构

  

master – tablet server类型

master负责分配tablet到tablet 服务器。只负责分配，不负责存储。

HBase将数据存储到分布式文件系统，所有数据冗余由分布式文件系统提供，HBase不提供。在Bigtable中，每个tablet仅存一份。

 

如何在Bigtable中找到tablet

Bigtable里面，采用三层B+Tree实现

每个叶子是一个Tablet

第一层是根tablet，第二层是MetaDataTablet。MetaDataTablet包含了所有tablet位置信息。第三层是tablet

tablet内部结构

基于LSM-Tree(Log Structured Merge Tree)存储，这不是一种数据结构，这是多种数据结构组成的

由多层树组成，分为内存层memory和外存层storage，c0树存储在内存层，c1 c2 … ch树存储在外存层，且大小是个等比数列。

每层都有一个索引

插入

首先操作追加到写前日志中，然后再写入内存C0中。当C0层数据达到一定大小，就相邻层之间进行合并，如C0和C1合并成一个新的C1。

这样新插入的值逐渐传递到最高Ch层。

更新和删除

不能直接更新或删除。

采用插入来解决更新和删除，更新就插入一个带有更高版本戳的数据，删除就插入一个标记，将数据标记为删除。在合并的时候会清理这些旧版本的和被删除的。

查找

一次查找C0,C1,C2…,Ch，直到找到一个最新的数据。读取比B+树性能差。越新的数据越靠近C0层，越老的数据越靠Ch。

SCAN

所有层C0,C1,C2,…,Ch同时进行SCAN，然后逐渐归并，性能比B+树差。

外存层次的组织

Leveling

每层只有一个大的排序文件，但是实际可以划分成多段。每段一个区间。

Tiering

每层多个排序文件，之间有重叠。读的性能下降，但是合并的总IO少。

 

与B+Tree的区别

B+Tree随机写，查找性能好，Scan访问一组节点，性能优

LSM-Tree顺序读写，查找性能差，Scan需要归并多个层次

 

Tablet Server结构

每个ColumnFamily分别存储在不用的Server

先写内存的MemTable，内存的MemTable写满了就送入到文件系统作为一个SSTable，然后MemTable继续保存新的写入内容。

每个Server内存有一个MemTable（C0）

每个Server文件系统存储多个SSTable，采用Tiering。SSTable只创建写一次，不会修改，最后删除。

 

Tablet Server Put操作

先写内存中的MemTable，内存写满了就送入文件系统作为一个SSTable。

先在log中追加写操作，再写入内存MemTable。

MemTable满了就对MemTable排序，然后将MemTable写入文系统作为一个新的SSTable。

 

Tablet Server GET操作

现在内存找，内存找不到就在文件系统找。

可能需要读取MemTable和多个SSTable。SSTable都建立了索引等辅助结构以提高效率。

Cassandra

Cassandra可以看成Dynamo和Bigtable的结合体，基于Java实现。

RocksDB也类似于Bigtable，基于C/C++实现。

 

ZooKeeper

ZooKeeper结构

多个ZooKeeper节点，多个客户机。

节点个数与故障关系

2f+1个ZooKeeper节点可以容忍f个节点故障。

 

ZooKeeper数据模型

ZooKeeper节点之间以树形组织在一起。一个ZooKeeper节点称为Znode。所有节点共同维护这棵树。

一个Leader，多个Follower

每个Clinet只连接到一台ZooKeeper服务器。

Znode属性

Name：从根节点到该节点唯一确定的路径

Data：存储的数据，不超过1MB

Version：版本号

Regular/Ephemeral：正常的节点or临时的节点。临时的节点会在系统与客户端断开后自动删除。

 

会话过程

Client主动与ZooKeeper连接开始会话

Client主动放弃或与ZooKeeper一段时间没有任何通讯，则关闭会话。

 

客户端API

创建，删除，判断节点是否存在。

读取节点数据getData，修改节点数据setData。

寻找子节点getChildren

同步操作sync()

 

Watch机制

判断Znode是否存在exists(path,watch)，设置一个Watch，当节点被删除或创建时收到通知，只监听一次。

API都提供同步或异步方式。

写的过程

写请求统一发送给Leader处理

Leader将写请求包装成一个幂等事务，广播给Follower，使用ZAB方式。

在广播之后，每个节点开始修改本地的数据。

读的过程

任意ZooKeeper节点都可以处理读请求。

因为写的全局顺序是Leader决定的，但读时分布式的，可能导致还没来得及更新就读到旧的数据。

 

ZooKeeper优点

串行化写：因为是Leader带领Follower按照相同顺序写的。

FIFO Client Order：每个Client自己的读写操作是FIFO顺序的，但是不同Client之间读写顺序不保证。

 

ZAB工作模式

ZAB广播

使用追加写，然后再更新数据，为了方便数据恢复。

propose阶段（广播txn）

Leader处理完写请求后，把新的txn写入本地log，广播Propose这个txn，每个txn都有唯一ID，且是单调递增的（保证了串行写）。

每个Follower收到Propose后，写入本地log，向Leader发回ACK

commit阶段（广播commit）

Leader收到f个ACK后，写Commit到log，广播Commit，开始修改ZooKeeper树。（永远是先写日志，再更新数据）

Follower收到Commit后，写Commit到log，修改ZooKeeper树。

如果Leader未收到f个ACK，或Follower长时间未Leader的消息，那么就出现了故障，开始恢复。

 

ZAB恢复

TxnID结构

高32位代表epoch，代表周期，第几任Leader，低32位为in-epoch id，代表周期内的ID。

每次选Leader，新的Leader上任，周期epoch增加1。每次恢复后，一定使用了更大的TxnID。

 

竞选Leader

每个节点查看自己看到的最大Txn，最大的Txn作为Leader。

新的Leader将确保所有的txn都正确执行，因为幂等性，不成功可以重复广播。

已经提交的但没执行的Client操作丢弃，因为Client会重试。

 

文件存储系统

树状结构数据模型

JSON（JavaScript Object Notation）

特点

是一个低成本的数据交换格式。
是Javascript程序语言标准(1999年)的子集。

JSON的数据类型定义是完全动态的，一个JSON记录本身自定义了自己的类型，不需要事先声明schema。

JSON格式定义

基本数据类型：string, number, true/false, null

Object：{“Key1″:”Value1″,…,”Keyn”:”Valuen”}

Array：[value1,…,valuen]

Object中可以嵌套Array，Array中也可以嵌套Object：

Google Protocal Buffers

特点

最初用于实现网络协议，所以叫Protocol。

可以用于表达程序设计语言中的结构和数组。

要求先定义类型，才可以表达数据。

数据格式定义

类似于关系数据库的定义

requeired：必需的数据类型。

optional：可选的数据类型，在树中表达为“?”

repeated：可重复的数据类型，可以为0次。在树中表达为“*”。

group：指明数据类型是一个组

JSON与Google Protocal Buffers相同点

都可以表达程序设计语言中的结构和数组

JSON嵌套为Object，PB为message和group。注意：PB系统中有两种嵌套方式！！！！！！！！！。

JSON数组为Array，PB为repeated。

JSON缺省值没有特别规定，PB为optional。

JSON与Google Protocal Buffers不同点

PB数据类型需要事先声明，JSON不需要

PB设计初衷是为了编码协议，是二进制编码的，JSON数据设计初衷是文本。

JSON与XML

相同点：都是半结构化表示。

区别：XML非常heavy-weight，XML文件需要格式定义。

其他关系数据格式/系统

Apache Avro：树状数据格式。

Apache Thrift：基于类似的理念，实现多语言的互相RPC调用。

Apache Parquet：PB的开源实现，HDFS上的一种列式树状数据存储文件格式。

MongoDB

特点

• • • 基本数据类型是JSON，存储为BSON二进制表示
    • MongoDB因为基本数据类型是JSON个数，所以不用创建表，直接插入即可。
    • 基本不支持Join

相关名词

• • • Database：关系型中的数据库概念
    • Collection：关系型中的table概念
    • Document：关系型中的记录概念

语法

插入数据，类似于SQL创建表格，若表格不存在则自动创建一个

  

统计计算机专业每一届人数

单机MongoDB架构

与MySQL类型，采用Operation Tree进行执行

 

分布式MongoDB架构（水平划分）

路由，Shard，配置服务器组成

Shar负责存储文件，路由负责路由到指定的Shard

ACID

多document（记录）的Transaction

4.0版本之前只支持单个记录修改的一致性

4.0版本之后增加了多document的transaction支持

并发控制

不同的存储引擎，支持不同级别的并发控制

WiredTiger支持文档级别的并发控制

Write Concer级别

• • • • • Unacknowledged（非应答）: 写请求发送了，就认为完成
        • Acknowledged（应答）：MongoDB应答了收到写请求，就认为完成
        • Journaled（日志级别）：MongoDB把写请求记录在硬盘上的日志中，认为完成

可用性

每个Shard可以有多个副本提供了可用性。

在RDBMS中支持JSON的方法是：把一个JSON记录存储为一个字符串

 

图存储系统-Neo4j

特点

自定义的结构，在本地硬盘存储图，而不是存储在表中。

开源Java实现

顶点称为Node

边称为relationship

顶点和边上存储多个key-value值，称为属性。

 

文件存储结构

顶点信息保存在Node store文件中

边信息保存在Relationship store文件中

属性保存在Propety store文件中

每个node，relationship，property都有unique id

 

Relationship双向链表

一个node的relationship形成双向链表

链接指针为relationship id

相应的node记录链表第一个relation id

 

Property单向链表

同一个node/relationship的property形成一个单向链表

链接指针为next property id

表的第一个property id存在对应的node/relationship中。

 

Relationship和Property之间的关系

每个边可以有多个property，同一个relationship的所有property形成一个单向列表。指针为next property id。

内存缓冲区

主要是对Node，Relationship，Property缓冲。

图数据操作

Traversal：遍历操作，可以在java中调用

Cypher：子图匹配。

Core API：增删改

 

Cypher子图匹配

节点

写在圆括号中

(节点名:类型,{属性})

边

写在方括号中

-[边名字:类型,{属性}]->

创建节点和创建边

子图匹配

格式：MATCH 节点/边 WHERE 条件 RETURN 通配符

 

找到具有 name:”张飞”属性的顶点

找到所有选修了体系结构的学生顶点。

找到所有选修了数据库和体系结构的学生顶点

找到所有2013年入学的选了体系结构的学生顶点

找到所有选了体系结构但是没有选操作系统的学生顶点。

从a到b有路径

(a) – [*] -> (b)

从a到b有路径，最短为3步，最长为5步

(a) – [*3..5] ->(b)

ACID

transaction：在java中显示使用，在cypher中隐式使用。

采用类似隔离快照的机制

一个transaction的写先保存起来，直到transaction,finish()才真正尝试修改数据。因为在finish之前可能有commit和rollback。

HA(High Availability)：主副本把transaction log发送给副本，从副本replay log执行同样的操作。

Gremlin查询语言

.out(‘name’)：表示指定出边

.values(‘name’)：表示取指定节点的指定属性对应的值

g.V().has(property)：查询具有指定property的节点

repeat().emit()

repeat表示不断重复括号中的，不断返回查询过程中遇到的符合要求的节点属性name对应的值。

 

获取label，也就是type

不同的图表示

属性图

顶点，边，属性，如Neo4j，JanusGraph/Gremlin支持的图

RDF图

属性都表示为顶点。

每个RDF记录都是三元组((subject 主, predicate 谓, object 宾)

RDF查询语言SPARQL

?前缀代表变量，注意”.”