第五周作业

发布于: 2020 年 07 月 08 日

作业一:

  • 用你熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

package Cache;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.UUID;
public class TestHashCircle {
// 机器节点IP前缀
private static final String IP_PREFIX = "192.168.0.";
private static final int SERVER_NUMS = 10;
private static final int VIRTUAL_NUMS = 200;
private static final int RECORDS = 1000000;
public static void main(String[] args) {
// 每台真实机器节点上保存的记录条数
Map<Node, Integer> map = new HashMap<>();
// 真实机器节点, 模拟10台
List<Node> nodes = new ArrayList<>();
for (int i = 0; i < SERVER_NUMS; i++) {
Node node = new Node(IP_PREFIX + i, 8070);
nodes.add(node);
}
IHashService iHashService = new HashService();
// 每台真实机器引入100个虚拟节点
ConsistentHash<Node> consistentHash = new ConsistentHash<>(iHashService, VIRTUAL_NUMS, nodes);
// 将5000条记录尽可能均匀的存储到10台机器节点上
String[] keys = new String[RECORDS];
for (int i = 0; i < keys.length; i++) {
// 产生随机一个字符串当做一条记录,可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
keys[i] = UUID.randomUUID().toString() + i;
// String data = "key" + (i * 17) + "ss" + i * 19;
}
for (String key: keys) {
// 通过记录找到真实机器节点
Node node = consistentHash.getServer(key);
if (!map.containsKey(node)) {
map.put(node, 0);
}
// 再这里可以能过其它工具将记录存储真实机器节点上,比如MemoryCache等
// ...
// 每台真实机器节点上保存的记录条数加1
map.put(node, map.get(node) + 1);
}
double[] numbers = new double[SERVER_NUMS];
// 打印每台真实机器节点保存的记录条数
for (int i = 0; i < SERVER_NUMS; i++) {
Node key = nodes.get(i);
System.out.println(key.toString() + "节点记录条数:" + map.get(key));
numbers[i] = map.get(key);
}
System.out.println("标准差: " + variance(numbers));
}
//标准差σ=sqrt(s^2)
public static double StandardDiviation(double[] x) {
double sum=0;
for(int i = 0; i < x.length; i++){//求和
sum += x[i];
}
double dAve = sum / x.length;//求平均值
double dVar=0;
for(int i = 0; i < x.length; i++){//求方差
dVar = dVar + (Math.pow((x[i] - dAve), 2));
}
return Math.sqrt(dVar / x.length);
}
//标准差
public static double variance(double[] data) {
double variance = 0;
double expect = sum(data) / data.length;
for (int i = 0; i < data.length; i++) {
variance = variance + (Math.pow((data[i] - expect), 2));
}
variance = variance / data.length;
return Math.sqrt(variance);
}
private static double sum(double[] data) {
double sum = 0;
for (int i = 0; i < data.length; i++)
sum = sum + data[i];
return sum;
}
}

package Cache;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
// 每个资源分割的节点数量
private int numberOfReplica;
// hash object
private IHashService hashService;
// 服务器节点list
private SortedMap<Long, T> circle = new TreeMap<>();
public ConsistentHash(IHashService hashService, int numberOfReplica, List<T> servers) {
this.numberOfReplica = numberOfReplica;
this.hashService = hashService;
for(int i=0; i<servers.size(); i++) {
this.addServer(servers.get(i));
}
}
public void addServer(T node) {
for (int i=0; i<numberOfReplica; i++) {
this.circle.put(this.hashService.hash(node.toString() + i), node);
}
}
public void removeServer(T node) {
for(int i=0; i<numberOfReplica; i++) {
this.circle.remove(this.hashService.hash(node.toString() + i), node);
}
}
/**
* 从环上hash最近的位置取node
*
* @param key
* @return
*/
public T getServer(String key) {
if (circle.isEmpty()) return null;
long hash = hashService.hash(key);
if (!circle.containsKey(hash)) {
// tailMap找到大于等于key的所有元素,使用红黑树原理
SortedMap<Long, T> tailMap = circle.tailMap(hash);
// 如果环大于hash的部分为空,证明hash值超过最后一个节点
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}

package Cache;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
/**
* hash算法实现
*/
public class HashService implements IHashService {
/**
* MurMurHash算法,性能高,碰撞率低
*
* @param key String
* @return Long
*/
public Long hash(String key) {
ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() >= 8) {
k = buf.getLong();
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
if (buf.remaining() > 0) {
ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
}

192.168.0.08070节点记录条数:100477
192.168.0.18070节点记录条数:103028
192.168.0.28070节点记录条数:95792
192.168.0.38070节点记录条数:104840
192.168.0.48070节点记录条数:93926
192.168.0.58070节点记录条数:98650
192.168.0.68070节点记录条数:104212
192.168.0.78070节点记录条数:103168
192.168.0.88070节点记录条数:93897
192.168.0.98070节点记录条数:102010
标准差: 3978.8067306668718

作业二:

根据当周学习情况,完成一篇学习总结

分布式缓存架构

什么是缓存Cache

  • 缓存

  • 存储在计算机上的一个原始数据复制表,以便于访问

  • 缓存是介于数据访问者和数据源之间的一种高速存储,当数据需要多次读取的时候,用于加快读取的速度。

  • 缓存Cache和缓冲Buffer的分别?

  • 缓存主要用于读多写少的场景

  • 缓冲读写场景下都可用,主要用于网络、磁盘读写的场景下

无处不在的缓存

  • CPU缓存

  • 操作系统缓存

  • 数据库缓存

  • JVM编译缓存

  • CDN缓存

  • 代理与反向代理缓存

  • 应用程序缓存

  • 分布式对象缓存

  • 缓存数据存储(Hash表)

缓存的关键指标

  • 缓存命中率

  • 缓存是否有效依赖于能多少次重用同一个缓存响应业务请求,这个度量指标被称作缓存命中率。

  • 如果查询一个缓存,十次查询九次能够得到正确结果,那么它的命中率是90%

影响缓存命中率的主要指标

缓存键集合大小
  • 缓存中每个对象使用缓存键进行识别,定位一个对象的唯一方式就是对缓存执行精确匹配

  • 键数量越少,缓存的效率越高

缓存可使用内存空间
  • 直接决定了缓存对象的平均大小和缓存对象数量

  • 因为缓存通常存储在内存中,缓存对象可用空间受到严格限制且相对昂贵。

  • 如果想缓存更多的对象,就需要先删除老的对象,再添加新的对象。老的对象被删除后,将来的请求无法命中它,这就会降低命中率

  • 物理上能缓存的对象越多,缓存命中率就越高。

缓存对象生存时间
  • 缓存对象生存时间称为TTL

  • 缓存天气预报数据15min没问题,则可设置TTL为15min

  • 根据应用场景灵活设置TTL

  • 对象的缓存时间越长,缓存对象被重用的可能性就越高

代理缓存

反向代理缓存

多层反向代理缓存

内容分发网络CDN

CDN同时配置静态文件和动态内容

  • 通读缓存read-through

  • 代理缓存,反向代理缓存,CDN缓存都是通读缓存

  • 通读缓存给客户端返回缓存资源,并在请求未命中时获取实际数据

  • 客户端连接的是通读缓存而不是生成响应的原始服务器

旁路缓存cache-aside
  • 对象缓存是一种旁路缓存,旁路缓存通常是一个独立的键值对存储

  • 应用代码通常会询问对象缓存需要的对象是否存在,如果存在,它会获取并使用缓存的对象,如果不存在或已过期,应用会连接主数据源来组装对象,并将其保存回对象缓存中以便将来使用

浏览器对象缓存
// 在WebStorage缓存对象的JavaScript代码
var preferences = {/* data object to be stored */};
localStorage.setItem('preferences', JSON.stringify(preferences));
// 访问缓存对象的JavaScript代码
var cachedData = localStorage.getItem('preferences');
var preferences = JSON.parse(cachedData);
本地对象缓存
  • 对象直接缓存在应用程序内存中

  • 对象存储在共享内存,同一台机器的多个进程可以访问它们

  • 缓存服务器作为独立应用和应用程序部署在同一台服务器上

  • 本地缓存对象构件分布式集群

远程分布式对象缓存

Memcached分布式对象缓存

//PHP客户端访问Memcached集群
$m = new Memcached();
//添加服务器集群
$cache->addServers(array(
array('cache1.example.com', 11211),
array('cache2.example.com', 11211),
array('cache3.example.com', 11211)
));
//写缓存,失效时间5分钟
$m->set('userCount', 123, 600);
  • Memcached分布式缓存访问模型

  • 分布式对象缓存的一致性hash算法

  • 基于虚拟节点的一致性hash算法

  • 各介质数据访问延迟

  • 技术栈各个层次的缓存

缓存为什么能显著提升性能?

  • 缓存数据通常来自内存,比磁盘上的数据有更快的访问速度

  • 缓存数据的最终结果形态,不需要中间计算,减少CPU资源消耗

  • 缓存降低数据库、磁盘、网络的负载压力,使这些I/O设备获得更好的响应特性

缓存是系统性能优化的大杀器

  • 技术简单

  • 性能显著提升

  • 应用场景多

  • 合理使用缓存

  • 过分依赖缓存、不合适的数据访问特性反而会拖慢系统。

  • 频繁修改的数据,这种数据如果缓存起来,由于频繁修改,应用还来不及读取就已经失效或更新,徒增系统负担。一般来说,数据的读写比在2:1以上,才具有缓存意义

  • 没有热点的访问

  • 缓存使用内存作为存储,内存资源宝贵而有限,不能将所有数据都缓存起来

  • 大部分数据访问不是集中在小部分数据上,那么缓存就没有意义

数据不一致与脏读

  • 一般会对缓存的数据设置失效时间,一旦超过失效时间,就要从数据库中重新加载

  • 数据更新时立即更新缓存

  • 会带来更多的系统开销和事务一致性的问题

  • 数据更新时通知缓存失效

  • 删除该缓存数据,是一种更加稳妥的做法

缓存雪崩
  • 随着业务的发展,缓存会承担大部分的数据访问压力,数据库已经习惯了有缓存的日子

  • 当缓存服务崩溃的时候,数据库会因为完全不能承受如此大的压力而宕机,进而导致整个网站不可用

  • 发生这种故障,甚至不能简单的重启缓存服务器和数据库服务器来恢复网站访问

缓存预热
  • 缓存中存放的是热点数据(遵循二八原则规律中的二占了八的访问量),热点数据又是缓存系统利用LRU(最近最久未用)算法对不断访问的数据筛选淘汰出来的,这个过程需要花费较长时间

  • 在这段时间,系统的性能和数据库负载都不太好,那么最好在缓存系统启动的时候就把热点数据加载好,这个缓存预加载手段就是缓存预热(warm up)

  • 例:对于一些元数据如城市地名列表、类目信息,可以启动时加载数据库中全部数据到缓存进行预热

缓存穿透
  • 如果不恰当的业务、或者恶意攻击持续高并发的请求某个不存在的数据,因为缓存没有保存该数据,所有的请求都会落到数据库上,会对数据库造成很大的压力,甚至崩溃

  • 一个简答的对策是将不存在的数据也缓存起来(其value值为null),并设定一个较短的失效时间

  • Redis VS Memcached

  • Redis支持复杂的数据结构

  • Redis支持多路复用异步I/O高性能

  • Redis支持主从复制高可用

  • Redis原生集群与share nothing集群模式

Redis集群

  • Redis集群预分好16384个桶,当需要再Redis集群中防止一个K-V时,根据CRC16(key)mod 16384的值,决定将一个key放到哪个桶中

  • Redis-cluster把所有的物理节点映射到【0-16383】slot上(不一定是平均分配),cluster负责维护slot与服务器的映射关系

  • 客户端与Redis节点直连,客户端不需要连接集群所有节点,连接集群中任何一个可用节点即可

  • 所有的Redis节点彼此互连

消息队列与异步架构

同步调用VS异步调用

  • 同步调用

  • 多次同步调用

  • 阻塞应用线程

  • 异步调用

  • 多次异步调用

  • 不阻塞应用线程

消息队列构件异步调用架构
  • 角色

  • 消息生产者

  • 消息队列

  • 消息消费者

  • 模型

  • 点对点模型

  • 发布订阅模型

  • 消息队列的好处

  • 实现异步处理,提升处理性能

  • 更好的伸缩性

  • 削峰填谷

  • 失败隔离和自我修复

  • 因为发布者不直接依赖消费者,所以消息系统可以将消费者系统错误与生产者系统组件隔离

  • 生产者和消费者互相不受对方失败影响

  • 这意味着任何时刻,我们可以对后端服务器执行维护和发布操作。我们可以重启、添加或删除服务而不影响生产者可用性,这样简化了部署和服务器管理的难度。

  • 解耦

  • 事件驱动架构EDA

  • 主要MQ产品比较

  • RabbitMQ主要特点是性能好,社区活跃,但是RabbitMQ用Erlang开发,对不熟悉Erlang的同学而言不便于二次开发和维护。(49M)

  • ActiveMQ影响比较广泛,可以跨平台,使用Java开发,对Java比较友好。(27M)

  • RocketMQ是阿里推出的一个开源产品,也是使用Java开发,性能比较友好,可靠性也比较高。(35M)

  • Kafka,LinkedIn出品,Scala开发,专门针对分布式场景进行了优化,因此分布式的伸缩性会比较好。(63M)

负载均衡架构

  • HTTP重定向负载均衡

  • DNS负载均衡

  • 反向代理负载均衡

  • IP负载均衡

  • 负载均衡服务器(网关服务器)

  • 数据链路层负载均衡

负载均衡算法
  • 轮询

  • 所有请求依次分发到每一台服务器上,适合所有硬件配置都相同的场景

  • 加权轮询

  • 在轮询基础上,按照配置权重分配请求

  • 例如高性能服务器设置权重大一些,分配更多请求

  • 随机

  • 最少连接

  • 新请求分发到最少连接请求的服务器上

  • 源地址散列

  • 将来源的IP地址进行Hash计算得到应用服务器

  • session会话粘滞使用

  • 应用服务器集群的Session管理

  • Session复制

  • Session绑定

  • 利用Cookie记录Session

  • Session服务器(集群)单独保存

分布式数据库

  • MySQL复制

  • 主从复制

  • 主多从复制

  • 优点

  • 分摊负载

  • 专机专用

  • 便于冷备

  • 高可用

  • 主主复制

  • 主主失效恢复

  • 主主失效的维护过程

  • MySQL复制注意事项

  • 主主复制的两个数据库不能并发写入

  • 复制只是增加了数据的读并发处理能力,没有增加写并发能力和存储能力

  • 更新表结构会导致巨大的同步延迟

  • 数据分片

  • 分片目标

  • 分片特点

  • 分片原理

  • 硬编码实现数据分片

  • 应用代码将分片key映射成服务器编号

  • 映射表外部存储

  • 数据分片的挑战

  • 需要大量的额外代码,处理逻辑因此变得更加复杂

  • 无法执行多分片的联合查询

  • 无法使用数据库的事务

  • 随着数据的增长,如何增加更多的服务器

  • 分布式数据库中间件

  • Amoeba/Cobar架构

  • Cobar系统组件模型

  • 路由配置实例

  • Cobar如何做集群的伸缩

  • 实践中Cobar扩容策略

  • 数据库部署方案

  • 单一服务与单一数据库

  • 主从复制实现伸缩

  • 两个Web服务及两个数据库

  • 功能分割

  • 以上方案综合部署

NoSQL

  • CAP原理

  • C一致性

  • 每次读取的数据都应该是最近写入的数据或者返回一个错误,而不是过期数据

  • A可用性

  • 每次请求都应该得到一个响应,而不是返回一个错误或者失去响应

  • 不过这个响应不需要保证数据是最近写入的

  • 要求系统一直是可以正常运行的,不保证响应的数据是最新的

  • P分区耐受性

  • 因为网络原因,部分服务器节点之间消息丢失或延迟了,系统依然应该是可以操作的

  • 对于一个分布式系统而言,网络失效一定会发生,也就是说,分区耐受性是必须要保证的,那么在可用性和一致性上就必须二选一

  • 若选择一致性,系统可能返回一个错误码或者干脆超时,即系统不可用

  • 若选择可用性,系统总是返回一个数据,但是并不能保证这个数据是最新的

  • 在分布式系统必须要满足分区耐受性的前提下,可用性和一致性无法同时满足

  • CAP原理与数据存储冲突

  • 最终一致性

  • 最终一致写冲突

  • 简单冲突处理策略

  • 根据时间戳,最后写入覆盖

  • 客户端冲突解决

  • 合并各个响应结果

  • 投票解决冲突Cassandra

  • 尝试写入三个节点,至少2个节点响应才更新成功

  • 尝试从三个节点读取,至少2个节点返回,取最新版本

  • Cassandra分布式解决方案

  • HBase架构

  • Log Structed Merge Tree

ZooKeeper

  • 分布式系统脑裂

  • 在一个分布式系统中,不同服务器获得了互相冲突的数据信息或者执行指令,导致整个集群陷入混乱,数据损坏,本称作分布式系统脑裂

  • 数据库主主备份

  • 分布式一致性算法

  • Proposer

  • Acceptor

  • Leaner

  • 第一阶段:Prepare阶段

  • Proposer向Acceptors发出Prepare请求,Acceptors针对收到的Prepare请求进行Promise承诺

  • 第二阶段:Accept阶段

  • Proposer收到多数Acceptors承诺的Promise后,向Acceptors发出Propose请求,Acceptors针对收到的Propose请求进行Accept处理

  • 第三阶段:Learn阶段

  • Proposer在收到多数Acceptors的Accept之后,标志着本次Accept成功,决议形成,将形成的决议发送给所有Learners

  • Proposer生成全局唯一且递增的Proposal ID(可使用时间戳加Server ID),向所有Acceptors发送Prepare请求,这里无需携带提案内容,只需携带Proposal ID即可。

  • Acceptors收到Prepare和Propose请求后

  • 不再接受Proposal ID 小于等于 当前请求的Prepare请求

  • 不再接受Proposal ID 小于 当前请求的Propose请求

  • Zookeeper架构

  • Zab协议

  • Zookeeper的树状记录结构

  • /

  • services

  • YaView

  • servers

  • stupidname

  • morestupidity

  • Locks

  • read-1

  • apps

  • users

  • Zookeeper API

String create(path, data, acl, flags)
void delete(path, expectedVersion)
Stat setData(path, data, expectedVersion)
(data, Stat) getData(path, watch)
Stat exists(path, watch)
String[] getChildren(path, watch)
void sync(path)
List multi(ops)
  • 配置管理

  • Administrator

  • setData(“/config/param1”, "value”,-1)

  • Consumer

  • getData("/config/param1", true)

  • 选master

  • getdata(“/servers/leader”, true)

  • if successful follow the leader described in the data and exit

  • create(“/servers/leader”, hostname, EPHEMERAL)

  • if successful lead and exit

  • goto step 1

搜索引擎

  • 互联网搜索引擎整体架构

  • 爬虫系统架构

  • 爬虫禁爬协议

  • User-agent: GoogleBot

  • Disallow: /tmp/

  • Disallow: /cgi-bin/

  • Disallow: /users/paranoid/

  • 文档矩阵与倒排索引

  • 文档与倒排索引

  • 带词频的倒排索引

  • 带词频与位置的倒排索引

  • Lucene架构

  • Lucene倒排索引

  • Lucene索引文件准实时更新

  • 索引有更新,需重新全量创建一个索引来替换原来的索引,这种方式在数据量大时效率很低,并且由于创建一次索引的成本很高,性能也很差

  • Lucene中引入了段的概念,将一个索引文件拆分为多个子文件,每个子文件叫做段,每个段都是一个独立的可被搜索的数据集,索引的修改针对段进行操作

  • 新增:新数据需要创建索引,选择新建一个段来存储新增的数据

  • 删除:当需要删除数据时,在索引文件新增一个.del的文件,用来专门存储被删除的数据ID

  • 更新:是删除与新增的组合

  • 为了控制索引里段的数量,必须定期进行段合并操作

  • ElasticSearch架构

  • 索引分片,实现分布式

  • 索引备份,实现高可用

  • API更简单、更高级

Doris——海量KV Engine

  • 当前现状

  • 网站关键业务有许多海量KV数据存储和访问需求

  • **站UDAS使用

  • 存在问题:

  • 扩容困难

  • 写性能较低

  • 实时性低

  • 网站有多套KV方案,接口不统一,运维成本高

  • 飞天KV Engine(Aspara)问题

  • 使用复杂

  • 性能较低

  • 产品需求

  • 定位

  • 海量分布式透明化KV存储引擎

  • 解决问题

  • 替换UDAS

用户头像

zyong

关注

还未添加个人签名 2018.09.26 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业