Chinaunix首页 | 论坛 | 博客
  • 博客访问: 6796671
  • 博文数量: 578
  • 博客积分: 13065
  • 博客等级: 上将
  • 技术积分: 10103
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-26 16:44
个人简介

推荐: blog.csdn.net/aquester https://github.com/eyjian https://www.cnblogs.com/aquester http://blog.chinaunix.net/uid/20682147.html

文章分类

全部博文(578)

分类: 架构设计与优化

2015-04-15 18:34:16

UniqGenerator.pdf

1. 前言

1.1. 目的

UniqGenerator提供一个简单、可靠、高效的、可支撑大容量和大并发的取绝对唯一ID(可以是数字型的,也可以是字符串型的)的通用机制,这里讲的“绝对”是指在同一系统内部的绝对唯一,有别于UUID(通用唯一识别码,Universally Unique Identifier)。

1.2. 背景

在很多应用场景中有着取唯一ID的需求,比如淘宝交易单号、中国人保保单号等,它们的特点是一长串数字或字母和数字混合的长字符串,而最关键的一点是必须绝对唯一,1000万中存在1个重复也不允许。

要满足这样的一个需求,最简单的方法是由单独的一台机器分配ID,然后供应其它机器使用,但是这种方法有两个问题:一是整个系统对这台机器产生了强依赖;二是这台机器可能会成为瓶颈。

2. 分析思路

分析思路可归纳为两点:一是对需求分类;二是针对需求以类举的方式提出解决方法。

3. 协议结构

3.1. 令牌和租约

参与分配唯一ID的机器都需要取得一个令牌,这是它能分配唯一ID的先决条件。令牌是一种有限的资源,获取令牌的方式是租约。

租期以天为单位,在一个令牌的租期未满之前,租用它的机器独占它,直到租期满1天后,即假设租期为7天,则8天后其它机器都可以租用该令牌。在租期的基础上延后1天是为保证令牌的绝对安全,防止同一个令牌在超过1台的机器上存活。

1台机器租用一个令牌后,可以对这个令牌不断续约,续约间隔时间以小时为单位。

3.2. 唯一性

怎么做到ID的唯一性?协议将根本下图所示的这样一个思路进行设计。

3.3. 结构

通过下图所示的结构,即可保证产生的ID在系统内部具有绝对的唯一性(本设计方案不能保证不同系统间的ID也能绝对唯一):

 

针对不同需要,将结构划分成3种类型(但可以根据需求继续扩充):

3.3.1. 固定长度的字符串

固定长度的字符串经常被用于定义各种订单号、交易流水号等,如中国人保(PICC)的保单号,微信的交易单号。

 

为满足不同的需求,令牌和序列号两者的字符个数是可以配置的。而日期、业务识别码和业务自定义部分需要应用自己以参数方式传入。

 

为了保证序列号的唯一性,须对序列号进行持久化记录,以便在时间范围内UniqGenerator进程重启或机器重启后,仍不会产生重复的序列号。

但如果仅这样,当这个序列号的记录文件被删除时,则会产生问题。为降低这个风险,UniqGenerator进程在启动时主动检查这个文件是否存在,如果不存在则直接启动失败。通过UniqGeneratorformat参数可以生成这个文件,在首次启动时需要做一下这项工作,UniqGenerator不自动做的原因是为一定程序上保证安全性。

3.3.2. 有状态数字型

当需要为第一条留言或评论分配一个唯一的ID时,则可以使用有状态的数字型ID,一个8字节的无符号整数,程序处理起来也非常便利。调用程序可不关心Uniq64的内部结构,而直接将它当作整数使用。

由于只使用了8字节,时间部分无法精确到秒,所以序列号也需要持久化。

3.3.3. 无状态数字型

无状态数字型和有状态数字型的区别在于,无状态的不需要持久化记录序列号,因为它的时候精确到了秒,UniqGenerator进程每次启动时会延迟1秒钟,以错过时间来保证唯一性。也因此,它比有状态的多了4字节,程序中不能直接当作整数使用。

4. 序列号持久化

4.1. 文件结构

4.2. serial_file.h

#ifndef SERIAL_FILE_H

#define SERIAL_FILE_H

#include 

namespace uniq_generator

{

 

// 运行:uniq_generator --format,格式化生成序列号文件

// 如果uniq_generator启动时检测不到文件存在,则启动不成功。

 

#pragma pack(4)

 

// 序列号文件头结构

struct SerialFileHeader

{

    uint32_t version;    // 版本号

    uint32_t num_blocks; // 块数(默认100)

    uint64_t padding1;   // 预留

    uint64_t padding2;   // 预留

    uint64_t padding3;   // 预留

    uint64_t padding4;   // 预留

    uint64_t padding5;   // 预留

    uint64_t padding6;   // 预留

    uint64_t padding7;   // 预留

    uint64_t padding8;   // 预留

    struct SerialBlock blocks[0];

};

 

// 序列号块结构

// 对于Uniq96类型,它不需要持久化

struct SerialBlock

{

    char name[16];                      // 名称,如果一个块未被使用,则名称为空,要求最后一个字符为结尾符

    int64_t create_time;                // 创建时间

    int64_t modification_time;          // 最后更新时间

 

    union

    {

        uint32_t flags;                 // 标志字段

        struct

        {

            uint32_t everyday_reset: 1; // 每天是否重置

            uint32_t padding: 31;       // 预留

        };

    };

 

    uint32_t padding1;                  // 预留

    uint64_t padding2;                  // 预留

    uint64_t padding3;                  // 预留

    uint64_t serial;                    // 序列号

    uint32_t step;                      // 更新步大小

};

 

#pragma pack()

 

} // namespace uniq_generator

#endif // SERIAL_FILE_H

5. 系统架构

5.1. 分布式结构

UniqGenerator采用弱主从分布式架构。不同于一般的主从架构,这里的两个Master地位均等,可同时提供读和写。

两个Master间互发心跳,心跳间隔时间以秒为单位,两者间需要做数据同步。

Agent发也往Master发心跳,心跳间隔时间以小时为单位,通过心跳的方式续约Token

5.1.1. Master

Master负责对Token的租约管理,并以心跳方式对Agent进行弱监控。

为防止Master单点的数据安全和服务可用性,需要部署两个Master实例。为规避主从Master切换问题,这两个Master地位均等,同时提供租约和续租服务。

续租可认为是读事件,租约可认为是写事件。对于写事件必须得到两个Master的共同确认,对于读事件则只需其中一个确认即可。

 

租期满时,就需要解约,这也是一个写事件,需要两个Master共同确认,满期的租约不能被续租。

需要两个Master共同确认,是为防止数据的不一致。一个Master重启后,需要先从另一Master同步数据,同步完成之前不提供服务。如果两个Master刚好都重启了,则相互同步,任何一个同步完成,即可提供读服务。

5.1.2. Agent

唯一ID由Agent产生,并提供多种形式的获取接口(如HTTP唯一IDRPC唯一ID等)。Agent在产生唯一ID之前,需要先从Master成功租约到一个TokenMaster保证同一个Token只会被一个Agent租用。

租期最少1天,最多可达30天,系统默认配置为7天。Master保证在租期内其它Agent不会租用到这个Token,但租期后可租给其它机器,因此Agent需要不断的向Master续租。过租期后,则只能重新租用新的Token

5.2. Agent结构

Agent设计为单进程双线程结构:

1) SerialThread

响应取唯一ID请求,生成唯一ID,然后返回给请求者。

2) HeartbeatThread

专职向Master发送续约心跳,当不能正常与Master心跳时,则连接另一个Master,如果同任何一个Master都不能正常心跳,则轮询重试,直到心跳正常。

 

5.3. Master结构

在第一个版本中,AgentMaster的心跳基于Thrift RPC实现。但考虑到性能容量等因素,如果Thrift RPC不能胜任时,则可以引入基于UDP的实现。

 

Master是一个单进程多线程结构:

1) RPC Thread

Agent和另一个Master提供RPC服务,实际上基于Thrift的实现,面向Agent和另一MasterRPC将是互相独立的RPC线程。

2) Lease Thread

租约线程,负责管理租约,如对租约满期的处理等。

3) HeartbeatThread

专职向另一个Master发心跳的线程,心跳也用于同步两者间的数据。

 

 

Master提供白名单机制,限制只有在白名单中的AGENT才可以申请租约,并提供一个Web界面管理租约。允许人为的强制解除租约和人工续约。

5.3.1. 租约接口lease.thrift

namespace cpp uniq_generator.master

 

// Token类型定义

// 一台机器对于同一种类型的Token,只能租用一个

enum TokenType

{

    TOKEN_STRING2_INCLUDE_LETTER = 2, // 2个字符,可包含A-Z字母

    TOKEN_STRING3_INCLUDE_LETTER = 3, // 3个字符,可包含A-Z字母

 

    TOKEN_STRING2_ONLY_NUMBER = 12, // 2个字符,纯数字

    TOKEN_STRING3_ONLY_NUMBER = 13, // 3个字符,纯数字

    

    TOKEN_UINT1 = 21, // 1个字节的无符号整数

    TOKEN_UINT2 = 22  // 2个字节的无符号整数

}

 

// 租用结果

enum RentingResult

{

    RR_SUCCESS = 0,  // 租用成功

    RR_RENTED = 1,   // 已被其它租用

    RR_UNRENTED = 2  // 未被租用

}

 

// 令牌

struct Token

{

    1: TokenType token_type;  // Token类型

    2: string token;          // Token

}

 

// 租约结构

struct TokenInfo

{

    1: TokenType token_type;  // Token类型

    2: string token;          // Token

    3: i64 create_time;       // 租约创建时间

    4: i64 modification_time; // 最近续约时间

}

 

// 面向Agent的租约服务(心跳)

service LeaseService 

{

    // 申请一个Token租约

    // 成功租约到返回非空字符串

    // 租约过程中如果遇到错误,则抛出异常

    string request_token(1: TokenType token_type);

 

    // 续租

    // tokens 被续约的Token

    // 续租过程中如果遇到错误,则抛出异常

    RentingResult rent_token(1: Token token);

 

    // 获取已取得的所有Tokens

    // 获取过程中如果遇到错误,则抛出异常

    list list_tokens();

 

    // 解约一个Token

    // 解约过程中如果遇到错误,则抛出异常

    void terminate_token(1: TokenType token_type, 2: string token);

    

    // 心跳一下,啥都不做

    void heartbeat();

}

6. 实现结构

UniqGenerator的实现充分利用了开源,以期大幅度提升开发效率:

1) Thrift

AgentMaster间,以及两个Master间的网络通讯使用的都是Thrift,使用RPC的好处是分布式编程变得简单快捷,同时Thrift支持丰富的语言,使得前后台交互也变得简单。

2) Boost

UniqGenerator使用著名的准C++标准库Boost作为基础类库,以帮助提升开发效率。同时,Thrift也需要Boost

3) gflags

Google出品的命令行参数解析器,使用得基于命令行参数的处理变得非常简单好用。

4) glog

Google出品的写日志类库,流式的写日志,无类型安全问题。

 

7. 编程接口

7.1. uniq_generator.h

#ifndef UNIQ_GENERATOR_H

#define UNIQ_GENERATOR_H

#include 

#include 

#include 

namespace uniq_generator

{

 

// 64位的唯一数

// Uniq64的优点是可以直接做64位无符号整数使用

// 它的特点是时间精确到小时,无论是同一台机器还是不同台机器,不同小时产生的值均不会相同

struct Uniq64

{

    union

    {

        uint64_t value;

 

        struct

        {

            uint64_t year: 7;    // 当前年份减2000后的值,如2015为15,2115为115,最多支持到2127年

            uint64_t month: 4;   // 当前的月份

            uint64_t day: 5;     // 当前日期的月份天

            uint64_t hour: 5;    // 当前时间的小时

 

            uint64_t token: 12;  // 每台机器独占的,用来做机器间的区分

            uint64_t serial: 31; // 递增的序列号,一天内不重复,单台机器一天最大到2147483648

        };

    };

 

    std::string str() const

    {

        std::stringstream result;

        result << value;

        return result.str();

    }

 

    std::string uri() const

    {

        std::stringstream result;

        result << "uniq64://"

               << year << "-" << month << "-" << day << "_" << hour << "/"

               << token << "/" << serial;

        return result.str();

    }

};

 

// 96位的唯一数

// Uniq96相比Uinq64,不能直接做整数值使用

// 它的特点是时间精确到秒,无论是同一台机器还是不同台机器,不同秒产生的值均不会相同

// 使用它时,建议进程启动时延迟一秒,以保证可以总是产生不同的值

struct Uniq96

{

    union

    {

        uint64_t value;

 

        struct

        {

            uint64_t year: 12;        // 当前年份减2000后的值,如2015为15,6096为4096,最多支持到6096年

            uint64_t month: 4;        // 当前日期的月份

            uint64_t day: 5;          // 当前日期的月份天

            uint64_t hour: 5;         // 当前时间的小时

            uint64_t minute: 6;       // 当前时间的分

            uint64_t second: 6;       // 当前时间的秒

            uint64_t microsecond: 10; // 与当前时间的微秒数相关的值

            uint64_t token: 16;       // 每台机器独占的,用来做机器间的区分

        };

    };

 

    uint32_t serial;                  // 递增的序列号

 

    std::string str() const

    {

        std::stringstream result;

        result << value << serial;

        return result.str();

    }

 

    std::string uri() const

    {

        std::stringstream result;

        result << "uniq96://"

               << year << "-" << month << "-" << day << "_"

               << hour << ":" << minute << ":" << second << "_" << microsecond << "/"

               << token << "/" << serial;

        return result.str();

    }

};

 

class CUniqException: public std::exception

{

public:

    explicit CUniqException(int errcode, const char* errmsg, const char* file, int line) throw ()

    {

        init(errcode, errmsg, file, line);

    }

 

    explicit CUniqException(int errcode, const std::string& errmsg, const std::string& file, int line) throw()

    {

        init(errcode, errmsg.c_str(), file.c_str(), line);

    }

 

    virtual const char* what() const throw()

    {

        return _errmsg.c_str();

    }

 

    int errcode() const throw()

    {

        return _errcode;

    }

 

    const char* file() const throw()

    {

        return _file.c_str();

    }

 

    int line() const throw()

    {

        return _line;

    }

 

private:

    void init(int errcode, const char* errmsg, const char* file, int line) throw ()

    {

        _errcode = errcode;

        if (errmsg != NULL)

            _errmsg = errmsg;

 

        if (file != NULL)

            _file = file;

        _line = line;

    }

 

private:

    int _errcode;

    std::string _errmsg;

    std::string _file;

    int _line;

};

 

//

// 工厂方法

//

 

// 取得内置的UniqGenerator

// 如果获取过程中遇到错误,则抛出CUniqException

extern IUniqGenerator* get_uniq_generator() throw (CUniqException);

 

// 根据指定的名称创建一个UniqGenerator

// 如果名字已存在则返回NULL

// 如果创建过程中遇到错误,则抛出CUniqException

extern IUniqGenerator* create_uniq_generator(const std::string& uniq_generator_name) throw (CUniqException);

 

// 取唯一数接口

class IUniqGenerator

{

public:

    virtual ~IUniqGenerator() throw () {}

 

    virtual std::string get_uniq(size_t token_size) throw (CUniqException) = 0;

    virtual void get_uniq(Uniq64* uniq) throw (CUniqException) = 0;

    virtual void get_uniq(Uniq96* uniq) throw (CUniqException) = 0;

};

 

} // namespace uniq_generator

#endif // UNIQ_GENERATOR_H

 

 

阅读(4530) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册