kuan525's notes

发表于 分类于 ， 
1
2
3
4
5
6
7
8
9
10
11
pair<int, int> calculateIntersection(pair<pair<int, int>, pair<int, int>> rect1, pair<pair<int, int>, pair<int, int>> rect2) {
    int x1 = max(rect1.first.first, rect2.first.first);
    int y1 = max(rect1.first.second, rect2.first.second);
    int x2 = min(rect1.second.first, rect2.second.first);
    int y2 = min(rect1.second.second, rect2.second.second);

    int width = max(0, x2 - x1);
    int height = max(0, y2 - y1);

    return make_pair(width, height);
}

发表于 分类于 ， 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int L = 1e6 + 5;//长度上限，这里一般够用
const int HASH_CNT = 2;//双哈希
struct StringHash_interval {
    int hashBase[HASH_CNT] = {29, 31};//哈希种子，可以用131, 13331
    int hashMod[HASH_CNT] = {int(1e9 + 9), 998244353};//任意选择一个较大的质数来约束大小
    char s[L];
    int ls;
    int hsh[HASH_CNT][L];
    int pwMod[HASH_CNT][L];

    void init() {  // 初始化
        ls = 0;
        for (int i = 0; i < HASH_CNT; ++i) {
            hsh[i][0] = 0;
            pwMod[i][0] = 1;
        }
    }

    StringHash_interval() { init(); }

    //这里使用的版本时串的前面的幂次大大大大,并且时从1开始的
    void extend(char c) {//后面添加
        s[++ls] = c;                          // 记录字符数和每一个字符
        for (int i = 0; i < HASH_CNT; ++i) {  // 双哈希的预处理
            pwMod[i][ls] = 1ll * pwMod[i][ls - 1] * hashBase[i] % hashMod[i];  // 得到b^ls
            hsh[i][ls] = (1ll * hsh[i][ls - 1] * hashBase[i] + c) % hashMod[i];
        }
    }

    vector<int> getHash(int l, int r) {  // 得到哈希值
        vector<int> res(HASH_CNT, 0);
        for (int i = 0; i < HASH_CNT; ++i) {
            int t = (hsh[i][r] - 1ll * hsh[i][l - 1] * pwMod[i][r - l + 1]) % hashMod[i];
            t = (t + hashMod[i]) % hashMod[i];//负数变为正数
            res[i] = t;
        }
        return res;
    }
};

发表于 分类于 ， 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Hash{
    string s;

    Hash(){s="";}
    Hash(string s):s(s);

    //单hash，使用双哈希可以参考区间hash模板
    long long getHash(){
        long long tt = 1;
        for(int i = 0; i < s.size(); i ++)
            tt = (tt * 131 + (s[i]-'0')) % 100000007; 
        return tt;
    }
};

发表于 分类于 ， 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct ss{
    unsigned long long a, b, c, d, e, f;
    
    int randval[100010];
    ss(){
        a=b=c=d=e=f=0;
        for(int i = 0; i <= 100010; i ++)
            randval[i] = random(1, (int)1e9);    
    }
    ss(int a, int b, int c, int d, int e, int f):a(a), b(b), c(c), d(d), e(e), f(f){
        for(int i = 0; i <= 100010; i ++)
            randval[i] = random(1, (int)1e9);
    }
    ss(ll x){
        a=x;
        b=x*23;
        c=x*x*x;
        d=randval[x];
        e=x*x;
        f=(ll)sqrt(x);
    }

    ss operator -=(ss t1){
        a-=t1.a;
        b-=t1.b;
        c-=t1.c;
        d-=t1.d;
        e-=t1.e;
        f-=t1.f;
        return *this;
    }

    ss operator +=(ss t1){
        a+=t1.a;
        b+=t1.b;
        c+=t1.c;
        d+=t1.d;
        e+=t1.e;
        f+=t1.f;
        return *this;
    }
    
    bool operator ==(ss t1){
        return a==t1.a&&b==t1.b&&c==t1.c&&d==t1.d&&e==t1.e&&f==t1.f;
    }
};
ss operator + (ss t1, ss t2){
    return ss(t1.a+t2.a,t1.b+t2.b,t1.c+t2.c,t1.d+t2.d,t1.e+t2.e,t1.f+t2.f);
}

发表于 分类于 ， 
1
2
3
4
5
6
7
8
9
int qmod(int a, int b, int mod) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = (ll)ans * a % mod;
        a = (ll)a * a % mod;
        b >>= 1;
    }
    return ans;
}

发表于 分类于 ， 
1
2
3
4
5
6
7
8
9
#define debug(a) cout << #a << " = " << a << endl;
#define debug2(a,b) cout<<#a<<" = "<<a<<' '<<#b<<" = "<<b<<endl;
#define debug3(a,b,c) cout<<#a<<" = "<<a<<' '<<#b<<" = "<<b<<' '<<#c<<" = "<<c<<endl;
#define debug4(a,b,c,d) cout<<#a<<" = "<<a<<' '<<#b<<" = "<<b<<' '<<#c<<" = "<<c<<' '<<#d<<" = "<<d<<endl;
#define debug5(a,b,c,d,e) cout<<#a<<" = "<<a<<' '<<#b<<" = "<<b<<' '<<#c<<" = "<<c<<' '<<#d<<" = "<<d<<' '<<#e<<" = "<<e<<endl;
#define debugx(a, idx) cout << #a << "[" << idx << "] = " << a[idx] << endl;
#define debugarr(a, x) for(int i = 0; i < x; i++) cout << a[i] << ' '; cout << endl;
#define debugvec(a) for(int i = 0; i < a.size(); i++) cout << a[i] << ' '; cout << endl;
#define debugarr2(a, n, m) cout<<#a<<": \n";for(int i=0;i<n;i++){for(int j=0;j<m;j++)cout<<a[i][j]<<' ';cout<<'\n';}

发表于 分类于 ，

KMP计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int KMP(vector<int> a, vector<int> b) {
    a.insert(a.begin(), 0); b.insert(b.begin(), 0);
    vector<int> next(b.size());
    for(int l = 0, r = 2; r < b.size(); r ++) {
        while(l != 0 && b[r] != b[l+1]) l = next[l];
        if(b[r] == b[l+1]) l ++;
        next[r] = l; // 位置
    }
    int ans = 0;
    for(int i = 1, j = 0; i < a.size(); i ++) {
        while(j && a[i] != b[j+1]) j = next[j];
        if(a[i] == b[j+1]) j ++;
        if(j == b.size()-1) {
            ans ++; j = next[j];
        }
    }
    return ans;
}

发表于 分类于 ，

1. 为什么需要ipconf

2. ipconf具体是什么

3. ipconf有什么好处

4. ipconf是什么架构

5. ipconf的负载均衡用的什么策略

6. ipconf怎么容灾

7. ipconf怎么限流/熔断

8. 为什么自己封装服务发现

9. 服务发现怎么写的

10. ipconf的亮点

11. ipconf的难点

12. ipconf的缺点

13. ipconf可优化的点

14. 有没有对ipconf做压测，效果怎么样

15. etcd是什么

16. 为什么使用etcd

17. etcd怎么使用

18. etcd起了什么作用

19. 监听前缀是怎么做到的

20. 怎么捕获etcd中内容的改变

发表于 分类于 ，

背景介绍

目前state server中的状态，都存储在本地内存中，这就导致如果state server进程退出之后状态将完全丢失，这样就违背了设计的初衷，将gateway server与state server进行拆分，就是未来将state server设计成无状态服务，可以满足迭代的效率需求不断重启升级，gateway server只有长连接轻易不重启，提供最大程度的稳定性。

无状态带来的好处是显而易见的，第一是可伸缩性，可以通过增加机器进行水平扩展应对长连接的增长。第二是高可用性，可用性体现在state server可以重启，重启时将进行故障恢复，只需要长连接被持有服务就可以正常运行用户无感知。

显示我们服务可靠性的终极目标：客户端/gateway server/ipconfig server/state server系统内任意组件的异常都不会影响用户的使用体验。

目标及约束

  1. 【无状态】：服务可随时重启，不会因为长期造成系统功能不可用，对用户无感知，同时尽可能的支持水平扩展。
  2. 【低延迟】：无状态化必然是以中心存储为代价的，则必然存在跨机通信，这将增加延迟。

技术方案

如何标记一个唯一的连接

connID是gateway在本地生成的，分布式化面对的第一个问题就是需要将连接状态能够跨时空的唯一标识。

一个连接目前从属与一个gateway进程，所以通过endpoint+connID可以跨机器唯一标记，但是如果gateway server重启后，connID将重新计数，则有可能导致两个连接拥有同一个标记，那么再加上一个运行时标记runID，即runID+endpoint+connID唯一标记一个连接，如果runID和endpoint都是字符串的话，那么gateway server处理connID的生成以及传输时的网络带宽都将会增加，应该通过一些简单的编码技巧对其进行改造。

connID是64位的，一个进程生成的连接数实际上远远用不了64位的证书去存储，事实上单机100w一个是一个极限，生产环境中不会有人把100w的用户寄托在一台机器上，继续优化毫无意义。

所以本质上，就是要分布式的场景下能够生成一个单机的唯一的int64类型的ID即可，这就是典型的“雪花算法”。

直接使用雪花算法，来生成一个唯一ID即可，他只要在单机上可保持全局高并发且全局唯一即可。

最高位是无效位，用来后面的灰度升级，41位是精确毫秒的时间戳，剩下的10位表示当前的节点编号，通常前5位表示数据中心，后5位表示数据中心机器的编号，10位可以表示1024台机器，如果每台机器可以容纳50w长连接，可以同时在线5亿条长连接，最后12位表示在这1毫秒之内的一个并发序号（是连续递增的），事实上如果今后接入层真的有超过5亿长连接的场景，可以降低后面的12位序号，因为连接的创建单机通常不用保持那么高的并发，需要的时候可以改造雪花算法（比如切换起始时间戳）。

我们其实只需要解决的事单实例重启后id会出现重复的情况，其实不需要给gateway server进行编号，因为跨机器id重复其实不会影响准确性，整体上的架构并不需要connID全局唯一，可以魔改雪花算法来适应需求。

state server如何改造成无状态服务

1
2
3
4
5
6
7
8
type connState struct {
    sync.RWMutex
    heartTimer  *timingwheel.Timer
    reConnTimer *timingwheel.Timer
    msgTimer    *timingwheel.Timer
    connID      uint64
    maxClientID uint64
}

首先要将连接的connID存储在redis中，在state server重启时进行batch的读取操作，因此较为适合使用redis的set数据结构，因为connID都是int64的整数可以在redis中较好的压缩，占用空间较小，通常分布式的redis场景下，一个set数据集合中元素的个数不要超过5k否则称之为大KEY，所以必须对set即可进行分片，否则存储不下这么多的connID，因此我们使用connID进行shard，hash(connID % 1024)将得到一个slot，使用slot作为set的key，确保同一个connID一定落到改slot中，这样我们才能可伸缩性的对其进行读取。

在state server重启进行读取的时候要去夹在set中的数据，在其配置中划分其所要读取事slot的range信息即可，初始化阶段遍历slot批量读取set集合中的connID，基于connID的信息回复一些信息。

但是这里要注意的事，如果state server写入slot事hash的，也就是说他可以任意的写入不同的slot上，但是当state server宕机重启后，仅取加载其配置的slot上的conn信息，这就倒置conn的状态发生来迁徙，不再原来的state server上，但是按照现在的架构，必须保证gateway server请求唯一的state server，否则将找不到对应的状态，比如说来conn信息的迁移将倒置conn状态的丢失，因此hash是可行的。

为此，我们只能是配置的slot，state server的connID只能写入配置的slot上，并重启时加载配置slot中的connID即可，如此才能实现state server的重启

这样的设计将使得state server难以扩缩容，这就是有状态服务相对于web server的及时挑战所在，对于状态我们只是将其分分分布式存储而已。

当connID我们读取到state server内存后，第一步就是要检查一下是不是在蹦阔之前存在没有push下去的消息，所以我们得把msgTimer以及msg存储下来，这设计复杂的状态转移，但是可以简化这个设计。

如果长连接的作用不是数据消息，仅仅是发送控制消息，也就是通知客户端这里有新的消息，你可以来拉取，也就是所谓的推拉结合的设计，这样即解决了轮训造成的网络风暴以及延时问题，也可以简化消息的存储。

state server仅需要存储当前连接的最后一次push的消息即可，称之lashMsg并且启动一个定时器，该定时器要加上一个lock来保证客户端ack时确实ack的事当前lashMsg否则会导致连续push消息时ack乱序将lastMsg确认，导致消息丢失问题。这个lock就是lastMsg的一些元信息即可，比如connID与msgID二者确认一定是当前ack的lastMsg，如果连接在state server崩溃期间也崩溃了，这并不要紧，因为客户端连接登陆后会主动的拉一次消息。

而msgTimer其实可以忽略，因为只要通过connID拿到lastMsg，再启动一次定时器即可，最坏的情况也是等待两个定时周期后将其再次rePush，用户几乎无感知，并且这样设计可以大大简化state server的状态机，让给重启后连接也崩溃了，重启的msgTimer会正常运行在两个定时周期清除redis中的lastMsg

第二步，让给需要回复连接的心跳功能，如果state server启动后，connID对应的连接也失效了，重启后的连接如果没有是小那也需要恢复其心跳定时器，这样才能继续实现连接可靠性，所以我们只需要回复connID对应的心跳定时器即可，同样最快情况事这个连接已经失效，那么在心跳周期后进入重连，重连也超时后就会直接清理掉该连接的状态，实现整个连接状态生命周期的闭环。

第三部，就是对上行消息中max_client_id的恢复，为保证上行消息的强可靠性，需要将其存储在redis中，但是他的生命周期是什么呢？一个在login connID的时候由客户端自行初始化其值，在每次上行消息中进行比较并自增操作，其生命周期跨越一个连接，应该是再一次会话內保持自增，属于业务范畴，为保证redis中内存的最终回收，在连接断开时由重连定时器过期时出发redis中key的删除，以此实现上行消息的完整可靠性保证。

分布式场景下gateway与state server如何交互

针对以上的设计，state server本质上还是维护了一些定时状态，如果同一个连接的处理过程不再一个state server上进行，则会导致错误发生，例如在stateA上进行了连接，然后重连请求却发送给了stateB，这将导致stateB认为这是一个过期请求而忽略，stateA在重连定时器超时后将连接状态断开，用户就会感到莫名其表的随机断线。

再例如，gateway持有长连接socket，那么state server必须在push消息时正确的找到socket所在的gateway机器本身，才能发送push rpc，否则下行消息将发送失败。

因此在分布式场景下需要一个router sdk，来作为gateway和state交互时的路由表，为什么时sdk而不是一个server，这就为了减少不必要的网络消耗，本地化可以减少多次网络调用。

这个router sdk对于点对点通信提供两个接口，一个时add，一个时query，在state server注册连接时介入路由信息，key是did，value是endpoint+connID，直接通过rpc进行调用，这里还要实现一个del操作，在连接登出时调用，那就得在connState中存储did信息，这样在clost连接状态时才能删除原称得路由记录。

对于群组通信，让给push量过大可以使用消息队列削峰填谷，但是未来防止重复消费造成网络带宽浪费，可以使每个state server消费，确定的几个分区数据，通常是一个。

因此整个接入层网关就实现了，水平扩展的能力，但目前还无法做到动态的扩缩容。

为了减缓业务层的操作，router sdk可以维护sessionID到did到倒排列表，在发送消息时，通过mget did操作获得分区号和endpoint以及connID信息，通过分区号将消息发送个对应的state server然后其内部通过connID进行内部路由找到，长链socket完成push通信，这一步骤的开发将在业务层中实现。

这里还要说明一点，未来保证同一个gateway持有的长连接状态都能呗同一个state server处理，最简单的方式就是确保gateway server仅与一个state server进行通信，这种方式降低了下游state server的可用性（一个state server垮掉后该gateway上的连接将不再可用），单实现简单易于扩展，为此state server的可靠性将依赖其快速启动的能力，由于上虞的数据都存储在分布式的缓存中，可以在秒级完成重启，对外继续提供长连接服务。

基于当前的架构，整体上就是一个分片策略，关于连接的状态都是完全隔离的，因此其实在设计connID时不需要考虑节点编号，只需要在最高位作为灰度发布位空闲下来，接下来的47位用来存储时间戳，这已经完全够用了，剩下的16位用来表示当前时间戳下的自增计数位。

任务分解

  1. ConnID全局改造
  2. Gateway 绑定 state server改造
  3. state server 绑定 gateway 改造
  4. state server 根据slot操作redis的shard
  5. 完成 router sdk 的借口开发，add和query（MQ逻辑和RPC逻辑在IM server中开发）
  6. state server 重启故障恢复
  7. 保证up msg中 max_client_msg 的连续性
0%