现代数据管理

现代数据管理

大题

1. DynamoDB 时钟向量更新

Vector Colock---逻辑时钟分布式系统无全局时钟，很难给所有事件定义全局顺序，为此Lamport定义了逻辑时钟（Logical Clock），算法要知道

Vector Clock---每个机器节点维护一个逻辑时钟的向量VC向量VC的属性要知道

Vector Clock的更新算法     重点

节点 i 本地发生一个事件时 VCi[i] + 1；

节点 i 给节点 j 发送消息m时，将整个 VCi 存在消息里；

2. DynamoDB对于Memcached存在的缺点进行的一致性hash的改进策略

Memcached存在的缺点

虚拟节点的位置和大小随机，如果有新的节点加入，可能导致扫描所有节点上的所有数据对象，判断是否需要迁移，这种全局的扫描开销很大

DynamoDB对memcache一致性hash的改进措施

1. 固定所有虚拟节点的位置和大小，只改变虚拟节点和节点的对应关系；

2. 将整个地址空间平均分成Q个虚拟节点，每个物理节点（假设有S个）分配Q/S个虚拟节点；

3. 当有新的节点加入时，现有的每个节点拿出等量的虚拟节点分给新节点；

4. 当有节点离开时，该节点的所有虚拟节点平均分配给所有的其他节点，确保系统中每个的节点的虚拟节点依然是Q/S个。

3. NAS如何读写数据，以及它的优缺点

NAS读写事务的原理

1. NAS用户的I/O请求封装到TCP/IP协议中，通过IP网络传输；

2. 远程NAS文件系统将该请求转换成块I/O来实现对NAS磁盘存储的读写；

3. 如果要将数据传回客户端，NAS重新将数据封装到TCP/IP协议中，通过网络回传。

NAS全称Network Attached Storage，它的典型组成是使用TCP/IP协议的以太网文件服务器，数据处理是“文件级”，可以把NAS存储设备附加在已经存在的以太网上

优点：1. 部署简单，只需与传统的交换机连接即可          2. 成本较低，投资仅限于一台NAS服务器          3. NAS服务器一般支持web客户端管理，对熟悉操作系统的网络管理人员来说使用方便

缺点：1. 由于与应用使用同一网络，会增加网络拥塞，NAS性能也受制于网络传输能力          2. 数据安全性方面一般只提供两级用户安全机制，还需适当额外增加适当级别的文件安全手段

4. 淘宝的OceanBase读写事务的原理

查询事务

由MergerServer把基线数据（ChunkServer）和增量数据（UpdateServer）融合后返回调用者，分散在多台服务器上；

写事务

集中于UpdateServer上进行，避免了复杂的分布式写事务，可实现跨行跨表写事务，又有较好的扩展性

OceanBase和BigTable读写事务的原理的区别

基于Oceanbase和Bigtable的应用场景不同，使得Oceanbase对Bigtable的读写事务进行了个性化的优化操作。在淘宝的应用场景中，经过分析虽然在线业务的数据量十分庞大，但最近一段时间内的修改量往往并不多。因此，OceanBase决定采用单台更新服务器来记录最近一段时间的修改增量，而以前的数据保持不变，以前的数据称为基线数据。基线数据以类似分布式文件系统的方式存储于多台基线数据服务器中，每次查询都需要把基线数据和增量数据融合后返回给客户端。这样，写事务都集中在单台更新服务器上，避免了复杂的分布式事务，高效地实现了跨行跨表事务;另外，更新服务器上的修改增量能够定期分发到多台基线数据服务器中，避免成为瓶颈，实现了良好的扩展性。而在Bigtable中没有这样的特定需求，读写事务的量级和相互关系是不确定的。其通过日志文件和memtable来进行写操作，通过memtable和sstable合并视图进行读操作，来满足各种情况下的要求。

5. 多副本下的Chunk写数据的流程，用图描述

七个流程

书上的原流程

图

6. Bigtable基于日志的读写原理，用图描述出来

Tablet的更新操作提交到REDO日志中，持久化信息保存在GFS上。在这些更新操作中，最近提交的日志存放在一个排序的缓存中（称为memtable），较早的更新存放在一系列的SSTable中

7. Paxos算法

Paxos算法的目的：解决分布式环境下一致性的问题算法分为prepare和accept两个阶段

prepare阶段

1. proposer选择一个编号n的提案，并将prepare请求发送给acceptors中的一个多数派（法定集合）

2. acceptor收到prepare消息后，如果提案编号小于它已经回复的编号，则拒绝该消息；若编号大于它已经回复的所有prepare消息，则acceptor将自己上次接收的消息的提案编号回复给proposer，并承诺不在回复小于编号n的提案

accept阶段

1. 当一个proposer收到了多数acceptors对prepare提案的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和根据prepare阶段决定的值value；

2. 如果acceptor收到一个编号为n的提案的accept请求，只要该acceptor没有对编号大于n的prepare请求做出过响应，它就接受该提案。如果n小于acceptor已响应过的prepare请求，则拒绝，不回应或者回复error。（当proposer没有收到过半回复时，它会重新进入第一阶段---递增提案编号，重新提出prepare请求）

8. MapReduce

是一种线性可伸缩的编程模型，处理和生成超大数据集的算法模型

着重关注伪码举例

9. 什么是storm的拓扑逻辑编程模型，这个模型的特点和思想

storm实时流处理，用于实时计算

storm的特性

支持水平扩展

具有高容错性，可确保每个消息都被处理到

具有很高的处理速度

处理的数据保存在内存中

storm的编程模型

流水线并行

多任务并行

小题

1. 数据的三种形式

结构化数据

可用关系型数据库表示和存储，表现为二位形式的数据

半结构化数据

不符合关系型数据库或其他数据表的形式关联起来的数据模型结构，但含相关标记，用来分隔语义元素以及对记录和字段进行分层，eg：Json和XML

非结构化数据

没有固定结构的数据，eg：文档、图片、视频、音频等

2. 大数据 4V

Volume：数据体量大

Variety：数据类型繁多

Velocity：处理速度快

Value：价值密度低

3. 为什么Google要提出知识图谱？

知识图谱和传统搜索结果对比，有3方面的显著提升

结果的正确与全面

最好的总结

更深、更广的知识体系

4. memcached的背景及业务特征

memcached是一个高性能的分布式内存对象缓存系统，用于动态Web应用以减轻数据库的负载，且开源、协议简单

业务特征

在内存中缓存数据和对象，为动态、数据库驱动网站提供更快的运行速度

采用LRU替换策略

分布式缓存，不同主机上的多个用户可同时访问

使用自己的页块分配器

使用基于存储“键-值”对的hashmap

虚拟内存不会产生碎片，虚拟内存分配的时间复杂度可保证为O(1)

5. 精简时钟向量

服务器向量：server的数量是可控的，可以不用client来表示向量空间，                    而是用server来标识向量空间----向量空间由client变为了server标识

向量时钟的剪枝：Riak剪枝系统由四个参数来避免向量空间的无线增长：                           small_vclock | big_vclock | young_vclock | old_vclock

6. DynamoDB对一致hash的改进中虚拟节点的两个动作

当有节点加入时，从现有节点每个拿出等量的虚拟节点分给新节点；

当有节点离开时，将此节点的所有虚拟节点平均分配给余下的节点，保证系统中每个节点始终有Q/S个虚拟节点。

7. SQLRelay优化，引进来干什么？

Oracle中的PHP pearDB是放在Apache上的，没有连接池的功能，SQLRelay是一个开源的连接池代理服务，用来提供连接池服务

8. 为什么BigTable参考了OceanBase

高扩展性

低成本

高可靠性

数据准确性

高性能

9. 分布式B+树的实现难点？

状态数据的持久化和迁移

子表的分裂与合并

10. Google为什么要设计GFS？

用大规模的集群去承载大数据，降低成本

文件可能非常巨大，普通的文件系统无法管理

系统需要经常处理由数亿个对象构成且快速增长的、数以TB的数据集

GFS是一个可扩展的分布式的文件系统，用于对大数据的访问

GFS可运行在廉价的普通硬件上，还提供容错机制

11. GFS的设计理念

组件失效应被视为常态而非意外事件

文件的大小通常比较大

写文件的方式通常以追加为主，很少会覆盖

客户端的使用和文件系统是一起设置的，比较灵活

12. 文件块chunk的设计思想

chunk：文件被分割为固定大小的文件块

每一个chunk创建时，Master服务器会给它分配一个64位全球唯一且不变的chunk标识

ChunkServer：chunk服务器把chunk以linux文件的形式保存在本地硬盘上，                        根据指定的chunk标识和字节范围来读写数据

13. Bigtable在大数据的基础上与GFS有什么不一样的之处？

GFS是把数据作为文件（块）---chunk来处理

Bigtable用数据库的方式管理大数据

14. Bigtable数据模型具备什么特点？

Bigtable数据特征：是一个稀疏的、分布式的、持久化存储的多维排序Map(由key/value)

15. Bigtable底层存储机制Tablet/SSTable

Tablet：用户可通过选择合适的行关键字在数据访问时有效利用数据位置的相关性

Tablet服务器：每个Tablet服务器都管理一个Tablet的集合

处理它加载的Tablet的读写操作

在Tablet过大时对其分割

SSTable：列族---列关键字组成的集合，是访问控制的基本单位                访问控制、磁盘和内存的使用统计都是在列族层面进行的

SSTable是一个持久化、可排序的、不可更改的Map结构（key/value映射）

16. 三层寻址（寻找Tablet的位置信息）

使用一个三层的、类似B+数的结构存储。

一个存储在chubby中的文件，包含Root Tablet的位置信息

第一层：Root Tablet，包含一个特殊的METADATA表，记录METADATA里所有的Tablet位置信息

实际上，Root Tablet是METADATA表的第一个Tablet

它永远不会被分割，从而保证Tablet的位置信息存储结构不超过三层

第二层：MATADATA表，其中的每个Tablet包含了一个用户Tablet的集合

第三层：用户Tablet

17. Paxos算法的活锁问题---编号、特点

编号“冲突--自增”的过程

当某proposer提交的proposal编号被拒绝时，可能是因为acceptor承诺返回了更大编号的proposal，这会导致proposer提高编号继续提交，该过程可能会产生活锁现象

活锁

如果2个proposer都发现自己的proposal编号过低而提出更高编号的proposal，会导致死循环，这种情况称为活锁

18. MapReduce基本思想

创建一个Map函数处理一个基于key/value对的数据集合，输出中间数据集合（该集合再次以key2/value2对的形似呈现）

创建一个Reduce函数来合并处理中间数据内具有相同key2值的value

19. Map产生的是一个中间结果，Reduce输出的是一个全局的最终结果。

Map输出的中间结果传输到Reduce的数据管道走的是RPC，在分布式环境中是一种很大的占用

20. 对MapReduce的数据传输策略进行优化---Combiner函数

Combiner函数作用---去重、汇总、进行本地化处理

Map函数产生的中间key值可能有很多重复，而这些重复记录将通过网络被发送到一个单独的Reduce任务进行计算，因此用户可指定一个Combiner函数，该函数在本地将这些记录进行合并后再将结果通过网络发出。

Combiner函数在每台执行Map任务的机器上都会被执行一次。