架构师课程第五周 作业

用户头像
杉松壁
关注
发布于: 2020 年 07 月 06 日
一、用你熟悉的语言实现一致性hash算法

一致性hash算法将key映射在0~2^32环之间,根据相同的CRC32算法,将node映射到环上,由key顺时针找到最近的node的环上的对应位置即可。

package consistenthash
//https://github.com/golang/groupcache/blob/master/consistenthash/consistenthash.go
import (
"hash/crc32"
"sort"
"strconv"
)
// Hash comment
type Hash func(data []byte) uint32
// Map struct
type Map struct {
hash Hash
replicas int
keys []int // Sorted
hashMap map[int]string
}
// New for create Map struct
func New(replicas int) *Map {
m := &Map{
replicas: replicas,
hash: crc32.ChecksumIEEE,
hashMap: make(map[int]string),
}
return m
}
// Add some keys to the hash.
func (m *Map) Add(keys ...string) {
for _, key := range keys {
for i := 0; i < m.replicas; i++ {
hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
m.keys = append(m.keys, hash)
m.hashMap[hash] = key
}
}
sort.Ints(m.keys)
}
// Remove keys from the hash
func (m *Map) Remove(keys ...string) {
for _, key := range keys {
for i := 0; i < m.replicas; i++ {
hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
if _, ok := m.hashMap[hash]; ok {
delete(m.hashMap, hash)
}
for k, v := range m.keys {
if v == hash {
m.keys = append(m.keys[:k], m.keys[k+1:]...)
}
}
}
}
}
// Get gets the closest item in the hash to the provided key.
func (m *Map) Get(key string) string {
hash := int(m.hash([]byte(key)))
// Binary search for appropriate replica.
idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash })
// Means we have cycled back to the first replica.
if idx == len(m.keys) {
idx = 0
}
return m.hashMap[m.keys[idx]]
}

使用redis进行了测试,可以实现一致性hash的功能,将key分布到不同的node上去。

package main
import (
"fmt"
redis "github.com/go-redis/redis/v7"
"os"
"test5/consistenthash"
"time"
)
const VNUM int = 160
func Get(k string, node string) string {
rdb := redis.NewClient(&redis.Options{
Addr: node,
})
defer rdb.Close()
rsp := rdb.Get(k)
return rsp.Val()
}
func Set(v map[string]string, node string) string {
rdb := redis.NewClient(&redis.Options{
Addr: node,
})
defer rdb.Close()
rsp := rdb.Set(v["key"], v["value"], time.Duration(3600)*time.Second)
return rsp.Val()
}
func main() {
var rsp string
NODE := []string{
"127.0.0.1:7000",
"127.0.0.1:7001",
"127.0.0.1:7002",
"127.0.0.1:7003",
"127.0.0.1:7004",
"127.0.0.1:7005",
"127.0.0.1:7006",
"127.0.0.1:7007",
"127.0.0.1:7008",
"127.0.0.1:7009",
}
h := consistenthash.New(VNUM)
h.Add(NODE...)
lag := os.Args
method := lag[1]
key := lag[2]
node := h.Get(key)
if method == "set" {
v := make(map[string]string)
v["key"] = lag[2]
v["value"] = lag[3]
rsp = Set(v, node)
}
if method == "get" {
rsp = Get(lag[2], node)
}
fmt.Println(rsp)
}
二、编写测试用例,测试100万KV数据,10个服务器节点的情况下,计算这些KV数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
package consistenthash
import (
"crypto/rand"
"fmt"
"github.com/grd/statistics"
"math/big"
"strconv"
"testing"
)
func TestStandardDeviation(t *testing.T) {
var data statistics.Int64
m := make(map[int]int64)
hash := New(160)
hash.Add("121", "35677", "212", "7019", "2245", "156", "21", "6", "111", "10345")
for i := 0; i < 1000000; i++ {
j, _ := rand.Int(rand.Reader, big.NewInt(100000))
k, _ := strconv.Atoi(hash.Get(string(j.Int64())))
m[k]++
}
for _, v := range m {
data = append(data, v)
}
sd := statistics.Sd(&data)
fmt.Printf("Sd: %v\n", sd)
fmt.Println("Distribution", data)
}

运行结果:

Sd: 10768.69476254615
Distribution [104362 91171 98839 81994 117707 86753 104651 100618 109544 104361]
PASS
ok test5/consistenthash 1.738s
三、总结

本周主要内容有Cache、消息队列、负载均衡和mysql高可用方案。

Cache在计算机系统中可以说是无处不在,从硬件架构中的CPU的高速缓存、内存的cache/buffer、磁盘缓冲到软件系统中的各种缓冲方案:本机的缓存、分布式系统中的缓存服务(Memcached、Redis)。缓存之所以会出现,是因为计算机各系统间的访问速度差别太大,严重影响了高速设备发挥出足够的性能,所以人们设计了Cache这种东西缓解设备间的访问,提高系统性能。那为什么这些系统中的各组件访问速度差别很大呢,主要是考虑到性价比的关系。越是高速的存储造价越贵,所以如果用CPU cache的材料来生产磁盘,价格肯定会成为问题。不过,我们可以期待或许有一天新的材料可以将这种设备间的访问速度统一,Cache可能就失去了它最大的作用。

消息队列是为了实现请求的异步调用。消息队列的好处:实现异步、削峰填谷、失败隔离和自我修复、解耦。在同步调用架构中,一个请求的在处理完成之前是处于阻塞状态,我们只能等待返回,如果处理的过程比较耗时,对用户的体验肯定是差的,而且系统的效率也不高。异步调用将各组件之间的处理解耦,可以同时接受前端的大量请求,不必等待后端将请求完全处理完成即可返回,通过回调等方式告知用户处理结果,从而大大提升了系统效率。常见的消息队列有ActiveMQ、RabbitMQ、RocketMQ、Kafka等。其中Kafka对分布式系统的支持最好。至于选择哪一种消息队列使用,可以看软件的成熟度、社区活跃度、代码更新间隔、使用的语言等维护考量。

负载均衡是一个中高型架构中必然会使用的东西。随着业务发展,请求数量增加,单台的服务器总有承受不住压力的时候,而且单台单点也是故障点。这个时候就要用到负载均衡了。它可以将请求按照规则转发到后端大量的服务器中。不仅解决了单点故障,更是极大的扩充了系统的性能,而且部署相对简单,成本可控。负载均衡有重定向负载均衡、dns负载均衡、方向代理负载均衡、4层负载均衡、数据链路层负载均衡,这些负载均衡可以配合使用,从而满足自己的需要。负载均衡算法有轮询、加权轮询、随机、最小连接、原地址散列、cookie保持等方式。在使用负载均衡的时候,需要考虑session回话的问题,主要有session复制、session绑定、利用cookie记录session、session服务等方式。

Mysql高可用方案有主从复制、主主复制。但是只能解决读并发性能的提升,不能解决主并发的问题。当涉及到主并发瓶颈的时候,就要考虑使用分布式数据库。



用户头像

杉松壁

关注

还未添加个人签名 2018.03.30 加入

还未添加个人简介

评论

发布
暂无评论
架构师课程第五周 作业