精华内容
下载资源
问答
  • const浅析

    2018-12-13 13:59:57
    c++中使用到const的地方有很多, 而且const 本身也针对不同的类型可能有不同的含义, 比如对指针就有顶层和底层. 本节就是探讨关于C++中const的在不同的地方不同表现或含义. const 关于const : const修饰的对象一旦...

    前言

    c++中使用到const的地方有很多, 而且const 本身也针对不同的类型可能有不同的含义, 比如对指针就有顶层和底层. 本节就是探讨关于C++中const的在不同的地方不同表现或含义.

    const

    const修饰的对象必须在定义的时候初始化

    1. 关于const :

    • const修饰的对象一旦创建一般就不能改变, 所以对于const对象必须进行初始化.

      int i = 0;
      const int j; 	// error. 必须进行初始化
      const int j = 0;
      
    • 初始化时并不关心初始化对象的是const还是非const

      int i = 0;
      const int j = i;	// i 是非const也可以
      
    • const不能改变

      const int i = 0;
      i = 1; 	// error const的对象一般不能进行修改
      
    • 引用对象的类型必须与其所引用对象的类型一致

      int i = 0;
      int &j = i;
      double &size = j; // error. size与j的类型不一致
      
      • 因为以上引用的规则, 所以const类型的引用只能被const的对象引用
      int i = 0;
      const int &size = i;
      int &j = size; // error. size的类型为const int, j的类型为 int. 两者并不匹配
      
      • 引用类型对应的例外

        int size = 0;
        const double &i = size; // size与i的类型虽然不一致, 但是因为const的原因使得等式成立
        

        原因 : 虽然i与size两者的类型并不一致, 但是初始化i时, 编译器会为size生成一个临时量(double j = size;), 然后i最终绑定在这个临时量上(const double &i = j ). i 之所以能绑定在一个临时量上, 还是因为const的对象不能被修改, 则i 无法被修改, 保障了临时量不会被改变.

        注意 i实际绑定在临时量上, 并没有绑定在size上

        int size = 0;
        const double &i = size;
        size = 1;	// i 实际值并没有改变, 它绑定的是临时量不是size
        
    • 修改const对象的值

      int i = 0;
      const int size = i;
      const int &j = i;
      const_cast<int&>(size) = 1;	// 将size的值修改为1
      i = 2;	// 因为j绑定i, i被修改则j也被修改
      

      因为const只是对修饰的对象限制其不能修改, 不能保证对象一定是常量, 所以能保证是常量的对象最好都定义成constexpr . 对constexpr不清楚的可以看一下constexpr浅析

    2. const对象初始化

    使用const对象像非const对象进行初始化时需要注意, 像引用和指针会对初始化对象的类型有要求.

    • 非引用指针

      普通类型是可以直接进行赋值操作

      const int i = 0;
      int j = i;
      
    • 引用和指针

      引用和指针只能初始化同类型的对象

      const int ci = 0;
      const int *pi = &ci;
      
      int &r = ci;	// error
      int *p = pi;	// error
      

    3. 顶层与底层const概念

    顶层const : 指针本身是一个常量(即地址不允许改变).

    其实我们一直都有在用顶层const, 比如int i = 0;, 这就是一个顶层const, 因为 i 的地址不会改变, 只有值会被改变.

    int size = 0, i = 0;	// 其实是顶层const
    int *const p = &size; // const直接修饰指针本身, 顶层const
    p = &i;		// error. p是顶层const
    *p = 1;		// 顶层const可以直接修改值
    

    记住 : const int i = 0, 这里的 i 也是顶层const*

    底层const : 指针所指的对象是一个常量(指针本身是可以修改的, 只是指向的值不能进行修改).

    int size = 0, i = 0;
    const int * p = &size; // const直接修饰指针指向的对象, 底层const
    ptr = &i;	// ptr可以重新指向其他地址, 因为是底层const
    *ptr = 1;	// error. 底层const不能直接修改指向的值
    

    当然我们可以将一个对象修饰为既是顶层又是底层

    int size = 0;
    const int * const p = &size;	// 既是顶层又是底层
    const int i = 0;	// 既是顶层又是底层
    

    有一点一定要注意 : 顶层const被拷贝时会忽略掉顶层const

    const int i = 0;
    int size = i; 	// 这里的顶层const被忽略掉了
    auto j = i; 	// 此时 auto 推断出 j的类型为 int , i 的顶层const被忽略了
    

    4. const与重载函数

    在重载函数时, const类型的参数可能会在处理顶层const与底层const的时候出现问题. 具体什么问题分析之后再来总结.

    void Ccount(int ccount) {}			// ccount为顶层const
    void Ccount(const int ccount) {}	// error. ccount也是为顶层const, 赋值时会忽略掉顶层const, 就与上面的函数一样了
    
    void Ccount_pointer(int *ccount) {}	// ccount为顶层const
    void Ccount_pointer(int *const ccount) {}	// error. ccount也是为顶层const, 赋值时会忽略掉顶层const, 就与上面的函数一样了
    

    上面可以看出来, 因为顶层const会被忽略, 所以顶层const与另外顶层const不能被区分出来.

    // error. 在函数调用的时候有二义性, 并不能区分调用哪一个函数, 在编译期间报错. 
    void const_reference(int i) {}	// i 是顶层const. 参数类型为 int
    void const_reference(int &i) {}	// i 是顶层const. 参数类型为 int
    
    // 下面都没有问题
    void const_reference(int &i) {}	// i 是顶层const. 参数类型为 int
    void const_reference(const int &i) {}	// i 是底层const. 参数类型为const int
    
    void const_pointer(int *i) {}		// 顶层const
    void const_pointer(const int *i) {}	// 底层const
    

    因为引用对象的类型必须相同, 所以int &iconst int &i有区别, 前者类型为int , 后者类型为const int, 所以后者是底层const.

    上面可以看出来, 因为底层const不会被忽略, 底层与底层有区分, 所以可以底层const可以用来重载.

    5. const与类的常量成员函数

    如果const放在函数名的前面其意义只是告诉编译器返回类型是const类型的常量而已, 但是如果把const放在函数名后那就又是另一种情况了, 我们这里主要分析的就种情况.

    const int const_func(int i) {return i;}	// 这里函数返回的是const类型的, 即常量
    int const_func(int i) const {return i;}	// error. const不能直接放在普通函数名的后面, 只能放在成员函数(类函数)名的后面,原因之后分析.
    

    定义一个简单的类

    class A {
        private: int nun;
        public: int const_func() const {return 0;}	// success
    };
    // 如果将函数改为
    int const_func() const { ++num; return 0;}	// error
    

    int const_func() const函数中const是告诉编译器, 类中定义的非静态变量都不能进行修改. 原因在于类的所有成员函数都会隐式的传入this 指针, 即上面的成员函数被修改为

    int const_func(const A * const this)  { ++num; return 0;}
    

    this指针本身就是顶层const, 而放在函数名后面的const是为了修饰this指针的, 但是因为this指针不能显示的被传入, 所以const只能放在函数名后.

    知道了这里const修饰的是this 指针, 所以this->i就不能被修改了, 而静态成员不是属于实例化类本身, 也就没有this指向静态变量, 所以可以在以上类型的函数中修改静态变量.

    const放在成员函数名后面的函数我们称为常量成员函数

    但是有的时候非要在以上函数中改变某个变量的值怎么办? c++中有mutable关键字, 就是允许这样的特例发生. mutable就是告诉编译器, num可以在任何函数中进行修改.

    class A {
        private: mutable int nun;
        public: void const_func() const {++num;}	// success
    };
    

    6. const与类

    我们在定义类的实例化时, 可能会将类实例化定义为const, 即

    class A {
        private: int nun;
        public: int const_func()  {return 0;}	
    };
    A a;
    const A ca;
    a.const_func(); // success
    ca.const_func(); // error
    

    上面出错的原因在于ca的类型为const, 所以与之对应的函数应该是常量成员函数, 所以最好在定义类函数实现时, 重载一个常量成员函数.

    7. const与类静态成员

    同样上面的类为例子

    class A {
        private: static int nun = 0; // error
        public: int const_func() const {++num; return 0;}	// success. 原因上面分析了
    };
    

    在类中定义的静态变量不能在类中初始化, 必须在类外进行初始化, 不然报错. 所以上面应该在类外改为int A::num = 0; .

    但是有一个例外 :

    class A {
        private: const static int nun = 0; // success
    };
    

    因为const要求必须在创建的时候就需要对其初始化, 所以上式的例子才成立.

    8. const与typedef

    当我们不愿意每次都定义指针的时候, 就想到用typedef来定义指针类型. 即:

    typedef char * Str;
    char *str1 = "hello";
    const char *str2 = "hello";
    const Str str3 = "hello"; // 在gcc, g++中没有问题, 在vs17中测试, 这样无法通过编译, 需要修改, 但是在vs终端使用cl命令是可以使用
    

    对其进行相同的操作

    str1[0] = 'a';
    str2[0] = 'a';	// error
    str3[0] = 'a';	// success
    
    str1++;
    str2++;	// success
    str3++;	// error
    

    以上面的执行的操作可以看出来typedef不仅仅只是一个替换, 它将const Str str3转换为了char *const str3而不是跟str2一样.

    原因是 : char *重写声明之后, 真实的数据类型变成了char 而不是char *, 反而*成了声明符的一部分了, 导致const Str的数据类型为const char, 而*修饰const char, 也就成了常量指针.

    上面所有的typedef定义的别名都可以用using Type = 替换, 如 : using Type = char *. 而且建议使用using来代替typedef, typedef 的功能using都有, 还有typedef不支持模板化功能. 后面我们在分析为什么推荐使用using.

    总结

    本节汇总了部分关于const用法的注意点, 可能看起来会很晕, 也不是一次性就容易记住, 希望在看的时候最好也进行验证是最好的. 最主要记住底层const和顶层const, 怎样重载, 基本很多的问题都是衍生.

    展开全文
  • 当后端是缓存服务器时,经常使用一致性哈希算法来进行负载均衡。 使用一致性哈希的好处在于,增减集群的缓存服务器时,只有少量的缓存会失效,回源量较小。 在nginx+ats / haproxy+squid等CDN架构中,nginx/haproxy...

    Nginx版本:1.9.1

    我的博客:http://blog.csdn.net/zhangskd

     

    算法介绍

     

    当后端是缓存服务器时,经常使用一致性哈希算法来进行负载均衡。

    使用一致性哈希的好处在于,增减集群的缓存服务器时,只有少量的缓存会失效,回源量较小。

    在nginx+ats / haproxy+squid等CDN架构中,nginx/haproxy所使用的负载均衡算法便是一致性哈希。

     

    我们举个例子来说明一致性哈希的好处。

    假设后端集群包含三台缓存服务器,A、B、C。

    请求r1、r2落在A上。

    请求r3、r4落在B上。

    请求r5、r6落在C上。

    使用一致性哈希时,当缓存服务器B宕机时,r1/r2会仍然落在A上,r5/r6会仍然落在C上,

    也就是说这两台服务器上的缓存都不会失效。r3/r4会被重新分配给A或者C,并产生回源。

    使用其它算法,当缓存服务器B宕机时,r1/r2不再落在A上,r5/r6不再落在C上了。

    也就是说A、B、C上的缓存都失效了,所有的请求都要回源。

     

    这里不介绍一致性哈希算法的基本原理,如果不了解,先花个10分钟看下这篇文章:

    http://www.codeproject.com/Articles/56138/Consistent-hashing

     

    在分析模块代码之前,先来看下nginx所实现的一致性哈希算法。

     

    1. 初始化upstream块

    主要工作是创建和初始化真实节点、创建和初始化虚拟节点。

    其中真实节点是使用round robin的方法创建的。

     

    Q:总共有多少个虚拟节点,一个真实节点对应多少个虚拟节点?

    累加真实节点的权重,算出总的权重值total_weight,虚拟节点的个数一般为total_weight * 160。

    一个权重为weight的真实节点,对应的虚拟节点数为weight * 160。

     

    Q:对于每一个真实节点,是如何创建其对应的虚拟节点的?

    1. 真实节点的server成员是其server指令的第一个参数,首先把它解析为HOST和PORT。

        base_hash = crc32(HOST 0 PORT)

        一个真实节点对应weight * 160个虚拟节点,对于每个虚拟节点来说,base_hash都是一样的。

    2. 为了使每个虚拟节点的hash值都不同,又引入了PREV_HASH,它是上一个虚拟节点的hash值。

        hash = crc32(base_hash PREV_HASH)

    3. 虚拟节点的server成员,指向真实节点的server成员。如此一来,通过比较虚拟节点和真实节点的

       server成员是否相同,可以判断它们是否是相对应的。

     

    创建和初始化好虚拟节点数组后,对其中的虚拟节点按照hash值进行排序,对于hash值相同的虚拟节点,只保留第一个。

    经过上述步骤,我们得到一个所有虚拟节点组成的数组,其元素的hash值有序而不重复。也就是说,ring建立起来了。

     

    2. 初始话请求的负载均衡数据

    根据hash指令第一个参数的实时值KEY,KEY一般是$host$uri之类的,计算出本次请求的哈希值。

    hash = crc32(KEY)

    根据请求的哈希值,在虚拟节点数组中,找到“顺时针方向”最近的一个虚拟节点,其索引为i。

    什么叫顺时针方向最近?就是point[i - 1].hash < hash <= point[i].hash。

    本次请求就落在该虚拟节点上了,之后交由其对应的真实节点来处理。

     

    3. 选取真实节点

    在peer.init中,已经知道请求落在哪个虚拟节点上了。

    在peer.get中,需要查找虚拟节点对应的真实节点。

    根据虚拟节点的server成员,在真实节点数组中查找server成员相同的、可用的真实节点。

    如果找不到,那么沿着顺时针方向,继续查找下一个虚拟节点对应的真实节点。

    如果找到了一个,那么就是它了。

    如果找到了多个,使用轮询的方法从中选取一个。

     

    4. 缺陷和改进

    一个虚拟节点和一个真实节点,是依据它们的server成员来关联的。

    这会出现一种情况,一个虚拟节点对应了多个真实节点,因为:

    如果server指令的第一个参数为域名,可能解析为多个真实节点,那么这些真实节点的server成员都是一样的。

    对于一个请求,计算其KEY的hash值,顺时针找到最近的虚拟节点后,发现该虚拟节点对应了多个真实节点。

    使用哪个真实节点呢?本模块就使用轮询的方法,来从多个真实节点中选一个。

    但我们知道使用一致性哈希的场景中,真实节点一般是缓存服务器。

    一个虚拟节点对应多个真实节点,会导致一个文件被缓存在多个缓存服务器上。

    这会增加磁盘的使用量,以及回源量,显然不是我们希望看到的。

     

    解决这个问题的方法其实很简单,就是虚拟节点和真实节点通过name成员来建立关联。

    因为就算对应同一条server配置,server的第一个参数为域名,各个真实节点的name成员也是唯一的。

    这样一来,找到了一个虚拟节点,就能找到一个唯一的真实节点,不会有上述问题了。

     

    数据结构

     

    1. 真实节点

    就是采用round robin算法所创建的后端服务器,类型为ngx_http_upstream_rr_peer_t。

    需要注意的是,如果server指令的第一个参数是IP和端口,那么一条server指令只对应一个真实节点。

    如果server指令的第一个参数是域名,一条server指令可能对应多个真实节点。

    它们的server成员是相同的,可以通过name成员区分。

    struct ngx_http_upstream_rr_peer_s {
        struct sockaddr *sockaddr; /* 后端服务器的地址 */
        socklen_t socklen; /* 地址的长度*/
        ngx_str_t name; /* 后端服务器地址的字符串,server.addrs[i].name */
        ngx_str_t server; /* server的名称,server.name */
         
        ngx_int_t current_weight; /* 当前的权重,动态调整,初始值为0 */
        ngx_int_t effective_weight; /* 有效的权重,会因为失败而降低 */
        ngx_int_t weight; /* 配置项指定的权重,固定值 */
    
        ngx_uint_t conns; /* 当前连接数 */
    
        ngx_uint_t fails; /* "一段时间内",已经失败的次数 */
        time_t accessed; /* 最近一次失败的时间点 */
        time_t checked; /* 用于检查是否超过了"一段时间" */
    
        ngx_uint_t max_fails; /* "一段时间内",最大的失败次数,固定值 */
        time_t fail_timeout; /* "一段时间"的值,固定值 */
        ngx_uint_t down; /* 服务器永久不可用的标志 */
        ...
        ngx_http_upstream_rr_peer_t *next; /* 指向下一个后端,用于构成链表 */
        ...
    } ngx_http_upstream_rr_peer_t;

    ngx_http_upstream_rr_peers_t表示一组后端服务器,比如一个后端集群。

    struct ngx_http_upstream_rr_peers_s {
        ngx_uint_t number; /* 后端服务器的数量 */
        ...
        ngx_uint_t total_weight; /* 所有后端服务器权重的累加值 */
    
        unsigned single:1; /* 是否只有一台后端服务器 */
        unsigned weighted:1; /* 是否使用权重 */
    
        ngx_str_t *name; /* upstream配置块的名称 */
    
        ngx_http_upstream_rr_peers_t *next; /* backup服务器集群 */
        ngx_http_upstream_rr_peer_t *peer; /* 后端服务器组成的链表 */
    };

     

    2. 虚拟节点

    一个真实节点,一般会对应weight * 160个虚拟节点。

    虚拟节点的server成员,指向它所归属的真实节点的server成员,如此一来找到了一个虚拟节点后,

    就能找到其归属的真实节点。

    但这里有一个问题,通过一个虚拟节点的server成员,可能会找到多个真实节点,而不是一个。

    因为如果server指令的第一个参数为域名,那么多个真实节点的server成员都是一样的。

    typedef struct {
        uint32_t hash; /* 虚拟节点的哈希值 */
        ngx_str_t *server; /* 虚拟节点归属的真实节点,对应真实节点的server成员 */
    } ngx_http_upstream_chash_point_t;
    
    typedef struct {
        ngx_uint_t number; /* 虚拟节点的个数 */
        ngx_http_upstream_chash_point_t point[1]; /* 虚拟节点的数组 */
    } ngx_http_upstream_chash_points_t;
    
    typedef struct {
        ngx_http_complex_value_t key; /* 关联hash指令的第一个参数,用于计算请求的hash值 */
        ngx_http_upstream_chash_points_t *points; /* 虚拟节点的数组 */
    } ngx_http_upstream_chash_points_t;

     

    3. 请求的一致性哈希数据

    typedef struct {
        /* the round robin data must be first */
        ngx_http_upstream_rr_peer_data_t rrp; /* round robin的per request负载均衡数据 */
        ngx_http_upstream_hash_srv_conf_t *conf; /* server配置块 */
        ngx_str_t key; /* 对于本次请求,hash指令的第一个参数的具体值,用于计算本次请求的哈希值 */
        ngx_uint_t tries; /* 已经尝试的虚拟节点数 */
        ngx_uint_t rehash; /* 本算法不使用此成员 */
        uint32_t hash; /* 根据请求的哈希值,找到顺时方向最近的一个虚拟节点,hash为该虚拟节点在数组中的索引 */
        ngx_event_get_peer_pt get_rr_peer; /* round robin算法的peer.get函数 */
    } ngx_http_upstream_hash_peer_data_t;
    

    round robin的per request负载均衡数据。

    typedef struct {
         ngx_http_upstream_rr_peers_t *peers; /* 后端集群 */
         ngx_http_upstream_rr_peer_t *current; /* 当前使用的后端服务器 */
         uintptr_t *tried; /* 指向后端服务器的位图 */
         uintptr_t data; /* 当后端服务器的数量较少时,用于存放其位图 */
    } ngx_http_upstream_rr_peer_data_t;

     

    指令的解析函数

     

    在一个upstream配置块中,如果有hash指令,且它只带一个参数,则使用的负载均衡算法为哈希算法,比如:

    hash $host$uri;

    在一个upstream配置块中,如果有hash指令,且它带了两个参数,且第二个参数为consistent,则使用的

    负载均衡算法为一致性哈希算法,比如:

    hash $host$uri consistent;

     

    这说明hash指令所属的模块ngx_http_upstream_hash_module同时实现了两种负载均衡算法,而实际上

    哈希算法、一致性哈希算法完全可以用两个独立的模块来实现,它们本身并没有多少关联。

    哈希算法的实现比较简单,类似之前分析过的ip_hash,接下来分析的是一致性哈希算法。

     

    hash指令的解析函数主要做了:

    把hash指令的第一个参数,关联到一个ngx_http_complex_value_t变量,之后可以通过该变量获取参数的实时值。

    指定此upstream块中server指令支持的属性。

    根据hash指令携带的参数来判断是使用哈希算法,还是一致性哈希算法。如果hash指令的第二个参数为"consistent",

    则表示使用一致性哈希算法,指定upstream块的初始化函数uscf->peer.init_upstream。

    static char *ngx_http_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
    {
        ngx_http_upstream_hash_srv_conf_t *hcf = conf;
        ngx_str_t *value;
        ngx_http_upstream_srv_conf_t *uscf;
        ngx_http_compile_complex_value_t ccv;
    
        value = cf->args->elts;
        ngx_memzero(&ccv, sizeof(ngx_http_compile_complex_value_t));
    
        /* 把hash指令的第一个参数,关联到一个ngx_http_complex_value_t变量,
         * 之后可以通过该变量获取参数的实时值。
         */
        ccv.cf = conf;
        ccv.value = &value[1];
        ccv.complex_value = &hcf->key;
    
        if (ngx_http_compile_complex_value(&ccv) != NGX_OK)
            return NGX_CONF_ERROR;
    
        /* 获取所在的upstream{}块 */
        uscf = ngx_http_conf_get_module_srv_conf(cf, ngx_http_upstream_module);
        if (uscf->peer.init_upstream)
            ngx_conf_log_error(NGX_LOG_WARN, cf, 0, "load balancing method redefined");
    
        /* 指定此upstream块中server指令支持的属性 */
        uscf->flags = NGX_HTTP_UPSTREAM_CREATE
            | NGX_HTTP_UPSTREAM_WEIGHT
            | NGX_HTTP_UPSTREAM_MAX_FAILS
            | NGX_HTTP_UPSTREAM_FAIL_TIMEOUT
            | NGX_HTTP_UPSTREAM_DOWN;
    
        /* 根据hash指令携带的参数来判断是使用哈希算法,还是一致性哈希算法。
         * 每种算法都有自己的upstream块初始化函数。
          */
        if (cf->args->nelts == 2)
            uscf->peer.init_upstream = ngx_http_upstream_init_hash;
        else if (ngx_strcmp(value[2].data, "consistent") == 0)
            uscf->peer.init_upstream = ngx_http_upstream_init_chash;
        else
            ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, "invalid parameter \"%V\"", &value[2]);
    
        return NGX_CONF_OK;
    }

     

    初始化upstream块

     

    执行完指令的解析函数后,紧接着会调用所有HTTP模块的init main conf函数。

    在执行ngx_http_upstream_module的init main conf函数时,会调用所有upstream块的初始化函数。

    对于使用一致性哈希的upstream块,其初始化函数(peer.init_upstream)就是上一步中指定

    ngx_http_upstream_init_chash,它主要做了:

    调用round robin的upstream块初始化函数来创建和初始化真实节点

    指定per request的负载均衡初始化函数peer.init

    创建和初始化虚拟节点数组,使该数组中的虚拟节点有序而不重复

    static ngx_int_t ngx_http_upstream_init_chash(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us)
    {
        u_char *host, *port, c;
        size_t host_len, port_len, size;
        uint32_t hash, base_hash;
        ngx_str_t *server;
        ngx_uint_t npoints, i, j;
        ngx_http_upstream_rr_peer_t *peer;
        ngx_http_upstream_rr_peers_t *peers;
        ngx_http_upstream_chash_points_t *points;
        ngx_http_upstream_hash_srv_conf_t *hcf;
        union {
            uint32_t value;
            u_char byte[4];
        } prev_hash;
    
        /* 使用round robin的upstream块初始化函数,创建和初始化真实节点 */
        if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK)
            return NGX_ERROR:
    
        /* 重新设置per request的负载均衡初始化函数 */
        us->peer.init = ngx_http_upstream_init_chash_peer;
    
        peers = us->peer.data; /* 真实节点的集群 */
        npoints = peers->total_weight * 160;
    
        /* 一共创建npoints个虚拟节点 */
        size = sizeof(ngx_http_upstream_chash_points_t) + 
            sizeof(ngx_http_upstream_chash_point_t) * (npoints - 1);
    
        points = ngx_palloc(cf->pool, size);
        if (points == NULL)
            return NGX_ERROR;
    
        points->number = 0;
    
        /* 初始化所有的虚拟节点 */
        for (peer = peers->peer; peer; peer = peer->next) {
            server = &peer->server; /* server指令的第一个参数, server.name */
            
            /* Hash expression is compatible with Cache::Memcached::Fast:
             * crc32(HOST 0 PORT PREV_HASH).
             */
            if (server->len >= 5 && ngx_strncasecmp(server->data, (u_char *) "unix:", 5) == 0)
            {
                host = server->data + 5;
                host_len = server->len - 5;
                port = NULL;
                port_len = 0;
                goto done;
            }
    
            /* 把每个peer的server成员,解析为HOST和PORT */
            for (j = 0; j < server->len; j++) {
                c = server->data[server->len - j - 1];
    
                if (c == ":") {
                    host = server->data;
                    host_len = server->len - j - 1;
                    port = server->data + server->len - j;
                    port_len = j;
                    goto done;
                }
    
                if (c < '0' || c > '9') /* 表示没有指定端口 */
                    break;
            }
    
            host = server->data;
            host_len = server->len;
            port = NULL;
            port_len = 0;
    
       done:
            /* 根据解析peer的server成员所得的HOST和PORT,计算虚拟节点的base_hash值 */
            ngx_crc32_init(base_hash);
            ngx_crc32_update(&base_hash, host, host_len);
            ngx_crc32_update(&base_hash, (u_char *) "", 1); /* 空字符串包含字符\0 */
            ngx_crc32_update(&base_hash, port, port_len);
            
            /* 对于归属同一个真实节点的虚拟节点,它们的base_hash值相同,而prev_hash不同 */
            prev_hash.value = 0;
            npoints = peer->weight * 160;
    
            for (j = 0; j < npoints; j++) {
                hash = base_hash;
                ngx_crc32_update(&hash, prev_hash.byte, 4);
                ngx_crc32_final(hash);
    
                points->point[points->number].hash = hash; /* 虚拟节点的哈希值 */
                points->point[points->number].server = server; /* 虚拟节点所归属的真实节点,对应真实节点的server成员 */
                points->number++;
    
    #if (NGX_HAVE_LITTLE_ENDIAN)
               prev_hash.value = hash;
    #else
               prev_hash.byte[0] = (u_char) (hash & 0xff);
               prev_hash.byte[1] = (u_char) ((hash >> 8) & 0xff);
               prev_hash.byte[2] = (u_char) ((hash >> 16) & 0xff);
               prev_hash.byte[3] = (u_char) ((hash >> 24) & 0xff);
    #endif
            }   
        }
    
        /* 使用快速排序,使虚拟节点数组的元素,按照其hash值从小到大有序 */
        ngx_qsort(points->point, points->number, sizeof(ngx_http_upstream_chash_point_t),
            ngx_http_upstream_chash_cmp_points);
    
        /* 如果虚拟节点数组中,有多个元素的hash值相同,只保留第一个 */
        for (i = 0, j = 1; j < points->number; j++)
            if (points->point[i].hash != points->point[j].hash)
                points->point[++i] = points->point[j];
    
        /* 经过上述步骤后,虚拟节点数组中的元素,有序而不重复 */
        points->number = i + 1;
       
        hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
        hcf->points = points; /* 保存虚拟节点数组 */
    
        return NGX_OK;
    }
    static int ngx_libc_cdel ngx_http_upstream_chash_cmp_points(const void *one, const void *two)
    {
        ngx_http_upstream_chash_point_t *first = (ngx_http_upstream_chash_point_t *) one;
        ngx_http_upstream_chash_point_t *second = (ngx_http_upstream_chash_point_t *) two;
    
        if (first->hash < second->hash)
            return -1;
        else if (first->hash > second->hash)
            return 1;
        else
            return 0;
    }

     

    初始化请求的负载均衡数据 

     

    收到一个请求后,一般使用的反向代理模块(upstream模块)为ngx_http_proxy_module,

    其NGX_HTTP_CONTENT_PHASE阶段的处理函数为ngx_http_proxy_handler,在初始化upstream机制的

    ngx_http_upstream_init_request函数中,调用在第二步中指定的peer.init,主要用于初始化请求的负载均衡数据。

    对于一致性哈希,peer.init实例为ngx_http_upstream_init_chash_peer,主要做了:

    首先调用hash算法的per request负载均衡初始化函数,创建和初始化请求的负载均衡数据。

    重新指定peer.get,用于选取一个真实节点来处理本次请求。

    获取的本请求对应的hash指令的第一个参数值,计算请求的hash值。

    寻找第一个hash值大于等于请求的哈希值的虚拟节点,即寻找“顺时针方向最近”的一个虚拟节点。

    static ngx_int_t ngx_http_upstream_init_chash_peer(ngx_http_request_t *r, ngx_http_upstream_srv_conf_t *us)
    {
        uint32_t hash;
        ngx_http_upstream_hash_srv_conf_t *hcf;
        ngx_http_upstream_hash_peer_data_t *hp;
    
        /* 调用hash算法的per request负载均衡初始化函数,创建和初始化请求的负载均衡数据 */
        if (ngx_http_upstream_init_hash_peer(r, us) != NGX_OK)
            return NGX_ERROR;
    
        /* 重新指定peer.get,用于选取一个真实节点 */
        r->upstream->peer.get = ngx_http_upstream_get_chash_peer;
    
        hp = r->upstream->peer.data;
        hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
    
        /* 根据获取的本请求对应的hash指令的第一个参数值,计算请求的hash值 */
        hash = ngx_crc32_long(hp->key.data, hp->key.len);
    
        /* 根据请求的hash值,找到顺时针方向最近的一个虚拟节点,hp->hash记录此虚拟节点
         * 在数组中的索引。
         */
        hp->hash = ngx_http_upstream_find_chash_point(hcf->points, hash);
    
        return NGX_OK:
    }

    hash算法的per request负载均衡初始化函数。

    static ngx_int_t ngx_http_upstream_init_hash_peer(ngx_http_request_t *r, ngx_http_upstream_srv_conf_t *us)
    {
        ngx_http_upstream_hash_srv_conf_t *hcf;
        ngx_http_upstream_hash_peer_data_t *hp;
    
        hp = ngx_palloc(r->pool, sizeof(ngx_http_upstream_hash_peer_data_t));
        if (hp == NULL)
            return NGX_ERROR:
    
        /* 调用round robin的per request负载均衡初始化函数 */
        r->upstream->peer.data = &hp->rrp;
        if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK)
            return NGX_ERROR;
    
        r->upstream->peer.get = ngx_http_upstream_get_hash_peer;
        hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
    
       /* 获取本请求对应的hash指令的第一个参数值,用于计算请求的hash值 */
        if (ngx_http_complex_value(r, &hcf->key, &hp->key) != NGX_OK)
            return NGX_ERROR;
        ...
        hp->conf = hcf;
        hp->tries = 0;
        hp->rehash = 0;
        hp->hash = 0;
        hp->get_rr_peer = ngx_http_upstream_get_round_robin_peer; /* round robin的peer.get函数 */
    
        return NGX_OK;
    }

    我们知道虚拟节点数组是有序的,事先已按照虚拟节点的hash值从小到大排序好了。

    现在使用二分查找,寻找第一个hash值大于等于请求的哈希值的虚拟节点,即“顺时针方向最近”的一个虚拟节点。

    static ngx_uint_t ngx_http_upstream_find_chash_point(ngx_http_upstream_chash_points_t *points, uint32_t hash)
    {
        ngx_uint_t i, j, k;
        ngx_http_upstream_chash_point_t *point;
        
        /* find first point >= hash */
    
        point = &points->point[0];
        i = 0;
        j = points->number;'
    
        while(i < j) {
            k = (i + j) / 2;
    
            if (hash > point[k].hash)
                i = k + 1;
            else if (hash < point[k].hash)
                j = k;
             else
                return k;
        }
    
        return i;
    }

     

    选取一个真实节点

     

    一般upstream块中会有多个真实节点,那么对于本次请求,要选定哪一个真实节点呢?

    对于一致性哈希算法,选取真实节点的peer.get函数为ngx_http_upstream_get_chash_peer。

     

    其实在peer.init中,已经找到了该请求对应的虚拟节点了:

    根据请求对应的hash指令的第一个参数值,计算请求的hash值。

    寻找第一个哈希值大于等于请求的hash值的虚拟节点,即“顺时针方向最近”的一个虚拟节点。

     

    在peer.get中,需查找此虚拟节点对应的真实节点。

    根据虚拟节点的server成员,在真实节点数组中查找server成员一样的且可用的真实节点。

    如果找不到,那么沿着顺时针方向,继续查找下一个虚拟节点对应的真实节点。

    如果找到一个真实节点,那么就是它了。

    如果找到多个真实节点,使用轮询的方法从中选取一个。

    static ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc, void *data)
    {
        ngx_http_upstream_hash_peer_data_t *hp = data; /* 请求的负载均衡数据 */
        time_t now;
        intptr_t m;
        ngx_str_t *server;
        ngx_int_t total;
        ngx_uint_t i, n, best_i;
        ngx_http_upstream_rr_peer_t *peer, *best;
        ngx_http_upstream_chash_point_t *point;
        ngx_http_upstream_chash_points_t *points;
        ngx_http_upstream_hash_srv_conf_t *hcf;
        ...
        pc->cached = 0;
        pc->connection = NULL:
        now = ngx_time();
        hcf = hp->conf;
        points = hcf->points; /* 虚拟节点数组 */
        point = &points->point[0]; /* 指向第一个虚拟节点 */
    
        for ( ; ; ) {
            /* 在peer.init中,已根据请求的哈希值,找到顺时针方向最近的一个虚拟节点,
             * hash为该虚拟节点在数组中的索引。
             * 一开始hash值肯定小于number,之后每尝试一个虚拟节点后,hash++。取模是为了防止越界访问。
             */
            server = point[hp->hash % points->number].server;
            best = NULL;
            best_i = 0;
            total = 0;
    
            /* 遍历真实节点数组,寻找可用的、该虚拟节点归属的真实节点(server成员相同),
              * 如果有多个真实节点同时符合条件,那么使用轮询来从中选取一个真实节点。
              */
            for (peer = hp->rrp.peers->peer, i = 0; peer; peer = peer->next, i++) {
                /* 检查此真实节点在状态位图中对应的位,为1时表示不可用 */
                n = i / (8 * sizeof(uintptr_t));
                m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
                if (hp->rrp.tried[n] & m)
                    continue;            
    
                /* server指令中携带了down属性,表示后端永久不可用 */
                if (peer->down)
                    continue;
    
                /* 如果真实节点的server成员和虚拟节点的不同,表示虚拟节点不属于此真实节点 */
                if (peer->server.len != server->len || 
                    ngx_strncmp(peer->server.data, server->data, server->len) != 0)
                    continue;
    
               /* 在一段时间内,如果此真实节点的失败次数,超过了允许的最大值,那么不允许使用了 */
               if (peer->max_fails
                    && peer->fails >= peer->max_fails
                    && now - peer->checked <= peer->fail_timeout)
                    continue;
            
                peer->current_weight += peer->effective_weight; /* 对每个真实节点,增加其当前权重 */
                total += peer->effective_weight; /* 累加所有真实节点的有效权重 */
    
                /* 如果之前此真实节点发生了失败,会减小其effective_weight来降低它的权重。          
                 * 此后又通过增加其effective_weight来恢复它的权重。          
                 */        
                if (peer->effective_weight < peer->weight) 
                    peer->effective_weight++;
            
                /* 选取当前权重最大者,作为本次选定的真实节点 */
                if (best == NULL || peer->current_weight > best->current_weight) {
                    best = peer;
                    best_i = i;
                }
            }
    
            /* 如果选定了一个真实节点 */
            if (best) {
                best->current_weight -= total; /* 如果使用了轮询,需要降低选定节点的当前权重 */
                goto found;
            }
    
            hp->hash++; /* 增加虚拟节点的索引,即“沿着顺时针方向” */
            hp->tries++; /* 已经尝试的虚拟节点数 */
    
            /* 如果把所有的虚拟节点都尝试了一遍,还找不到可用的真实节点 */
            if (hp->tries >= points->number)
                return NGX_BUSY;
        }
    
    found: /* 找到了和虚拟节点相对应的、可用的真实节点了 */
        hp->rrp.current = best; /* 选定的真实节点 */
        /* 保存选定的后端服务器的地址,之后会向这个地址发起连接 */
        pc->sockaddr = peer->sockaddr;
        pc->socklen = peer->socklen;
        pc->name = &peer->name;
        best->conns++;
    
        /* 更新checked时间 */
        if (now - best->checked > best->fail_timeout)
            best->checked = now;
    
        n = best_i / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << best_i % (8 * sizeof(uintptr_t));
    
        /* 对于本次请求,如果之后需要再次选取真实节点,不能再选取同一个了 */    
        hp->rrp->tried[n] |= m;
    
        return NGX_OK;
    }

     

     

    展开全文
  • 一致性hash C++实现

    千次阅读 2015-04-26 15:30:39
    一致性hash C++实现 知识标签: Consistent hashing, C++ 这两篇关于Consistent hashing的文章不错: 理想化的 Redis 集群 一致性hash和solr千万级数据分布式搜索引擎中的应用该代码是我偶然在别人github上找到的...

    一致性hash C++实现

    知识标签: Consistent hashing, C++

    这两篇关于Consistent hashing的文章不错:
    理想化的 Redis 集群
    一致性hash和solr千万级数据分布式搜索引擎中的应用

    该代码是我在别人github上找到的源码,自己添加了一些注释

    一致性哈希的功能被封装在模板类consistent_hash_map中

    consistent_hash_map.h

    consistent_hash_map.h如下:

    #include <map>
    #include <string>
    #include <list>
    #include <functional>
    #include <algorithm>
    
    
    
    #ifndef __CONSISTENT_HASH_H__
    #define __CONSISTENT_HASH_H__
    
    
    //consistent hash的节点类型。
    //一元函数对象。接收T类型对象作为参数,返回一个整形作为其hash值,该hash值将被用于内部的排序。Hash需在其内部定义result_type 指明返回整形的类型。
    template <typename T,
             typename Hash,
             typename Alloc = std::allocator<std::pair<const typename Hash::result_type,T > > >
    class consistent_hash_map
    {
        public:
    
            //hash函数返回值的类型
            typedef typename Hash::result_type size_type;
            //使用std::map来管理节点
            typedef std::map<size_type,T,std::less<size_type>,Alloc> map_type;
            //std::pair<const size_type, T>,first为节点的哈希值,second为节点。
            typedef typename map_type::value_type value_type;
            typedef value_type& reference;
            typedef const value_type& const_reference;
            typedef typename map_type::iterator iterator;
            typedef typename map_type::reverse_iterator reverse_iterator;
            typedef Alloc allocator_type;
    
        public:
    
            consistent_hash_map() {}
    
            ~consistent_hash_map() {}
    
        public:
    
            //返回consistent_hash_map内的节点数量
            std::size_t size() const 
            {
                return nodes_.size();
            }
    
            //判断consistent_hash_map是否为空
            bool empty() const
            {
                return nodes_.empty();
            }
    
            //插入一个节点,如果返回值中bool变量为真,iterator则为指向插入节点的迭代器。
            //如果bool为假,表示插入失败,iterator指向已经存在的节点。
            //插入失败因为节点已经存在或者是节点的hash值与其他节点发生冲突
            std::pair<iterator,bool> insert(const T& node)
            {
                size_type hash = hasher_(node);
                return nodes_.insert(value_type(hash,node));
            }
    
            //通过迭代器删除指定节点
            void erase(iterator it) 
            {
                nodes_.erase(it);
            }
    
            //通过节点值删除指定节点
            std::size_t erase(const T& node) 
            {
                size_type hash = hasher_(node);
                return nodes_.erase(hash);
            }
    
            //hash为数据关键字的hash值, find方法能找到该数据映射的节点
            iterator find(size_type hash)
            {//按照一个圆环方向(顺时针或逆时针),寻找hash值>=给定hash的节点
                if(nodes_.empty()) 
                {
                    return nodes_.end();
                }
    
                //找到map中key值>=hash的第一个迭代器
                iterator it = nodes_.lower_bound(hash);
    
                if (it == nodes_.end())
                {
                    it = nodes_.begin();
                }
    
                return it;
            }
    
            iterator begin() { return nodes_.begin(); }
            iterator end() { return nodes_.end(); }
            reverse_iterator rbegin() { return nodes_.rbegin(); }
            reverse_iterator rend() { return nodes_.rend(); }
    
    
        private:
    
            Hash hasher_;
            map_type nodes_;
    };
    
    
    #endif

    test.cpp只是简单实现consistent hashing, 并没实现虚拟节点,关于虚拟节点的例子在下面testVnode.cpp中

    test.cpp

    test.cpp如下:

    #include <iostream>
    #include <string>
    #include <boost/functional/hash.hpp>
    
    #include <stdint.h>     // for uint32_t
    #include <boost/format.hpp>
    #include <boost/crc.hpp>    //for crc_optimal
    
    #include "consistent_hash_map.hpp"
    
    struct crc32_hasher 
    {
        uint32_t operator()(const std::string& node) 
        {
            //定义crc_optimal对象
            boost::crc_32_type ret;
            //处理字符串,生成CRC序列
            ret.process_bytes(node.c_str(),node.size());
            //checksum()返回CRC序列
            return ret.checksum();
        }
    
        typedef uint32_t result_type;
    };
    
    
    int main(int argc, char const *argv[])
    {
        typedef consistent_hash_map<std::string,crc32_hasher> consistent_hash_t;
        consistent_hash_t consistent_hash_;
        //定义格式化字符串的类
        boost::format node_fmt("192.168.1.%1%");
    
        for(std::size_t i=0;i<3;++i) 
        {
            std::string node = boost::str(node_fmt % i);
            consistent_hash_.insert(node);
            std::cout<<boost::format("add node: %1%") % node << std::endl;
        }
    
    
        {
            std::cout<<"========================================================="<<std::endl;
            for(consistent_hash_t::iterator it = consistent_hash_.begin();it != consistent_hash_.end(); ++it) 
            {
                std::cout<<boost::format("node: %1%,%2%") % it->second % it->first << std::endl;
            }
        }
    
        // 输出相关数据关键字hash值映射的节点
        {
            consistent_hash_t::iterator it;
            it = consistent_hash_.find(290235110);  //290235110代表数据关键字的hash值
            std::cout<<boost::format("node:%1%,%2%") % it->second % it->first << std::endl;
        }
    
        {
            consistent_hash_t::iterator it;
            it = consistent_hash_.find(2286285664);
            std::cout<<boost::format("node:%1%,%2%") % it->second % it->first << std::endl;
        }
    
        {
            consistent_hash_t::iterator it;
            it = consistent_hash_.find(4282565578);
            std::cout<<boost::format("node:%1%,%2%") % it->second % it->first << std::endl;
        }  
    
    
        std::cout<<"========================================================="<<std::endl;
        {// 删除192.168.1.1
            std::string node = boost::str(node_fmt % 1);
            consistent_hash_.erase(node);
            for(consistent_hash_t::iterator it = consistent_hash_.begin();it != consistent_hash_.end(); ++it) 
            {
                std::cout<<boost::format("node:%1%,%2%") % it->second % it->first << std::endl;
            }
        }
    
        std::cout<<"========================================================="<<std::endl;
        {
            consistent_hash_t::iterator it;
            it = consistent_hash_.find(4282565578);
            std::cout<<boost::format("node:%1%,%2%") % it->second % it->first << std::endl;
            std::cout<<"-------------------------------------------"<<std::endl;
            consistent_hash_.erase(it);
            for(consistent_hash_t::iterator it = consistent_hash_.begin();it != consistent_hash_.end(); ++it) 
            {
                std::cout<<boost::format("node:%1%,%2%") % it->second % it->first << std::endl;
            }
        }  
    
        std::cout<<"========================================================="<<std::endl;
        {
            std::cout<<"-------------------------------------------"<<std::endl;
            consistent_hash_t::iterator it;
            it = consistent_hash_.find(4282565578);
            std::cout<<boost::format("node:%1%,%2%") % it->second % it->first << std::endl;
            std::cout<<"-------------------------------------------"<<std::endl;
    
            it = consistent_hash_.find(4282565576);
            std::cout<<boost::format("node:%1%,%2%") % it->second % it->first << std::endl;
            std::cout<<"-------------------------------------------"<<std::endl;
    
            consistent_hash_.erase(it);
    
            for(consistent_hash_t::iterator it = consistent_hash_.begin();it != consistent_hash_.end(); ++it) 
            {
                std::cout<<boost::format("node:%1%,%2%") % it->second % it->first << std::endl;
            }
            std::cout<<"-------------------------------------------"<<std::endl;
        }
    
    
        std::cout<<"========================================================="<<std::endl;
        {
            std::cout<<"-------------------------------------------"<<std::endl;
            consistent_hash_t::iterator it;
            it = consistent_hash_.find(4282565578);
            if(it == consistent_hash_.end()) 
            {
                std::cout<<"not found, consistent_hash is empty"<<std::endl;
            }
        }
    
        return 0;
    }

    编译:g++ test.cpp -o test
    运行:./test

    test结果

    结果如下:
    这里写图片描述

    testVnode.cpp

    testVnode.cpp如下:

    #include <stdint.h>
    #include <iostream>
    #include <string>
    #include <boost/functional/hash.hpp>
    #include <boost/format.hpp>
    #include <boost/crc.hpp>
    
    #include "consistent_hash_map.hpp"
    
    
    
    const char* nodes[] =   {
        "192.168.1.100",
        "192.168.1.101",
        "192.168.1.102",
        "192.168.1.103",
        "192.168.1.104"     };
    
    struct vnode_t 
    {
        vnode_t() {}
        vnode_t(std::size_t n,std::size_t v):node_id(n),vnode_id(v) {}
    
        std::string to_str() const 
        {
            return boost::str(boost::format("%1%-%2%") % nodes[node_id] % vnode_id);
        }
    
        std::size_t node_id;
        std::size_t vnode_id;
    
    };
    
    
    struct crc32_hasher 
    {
        uint32_t operator()(const vnode_t& node) 
        {
            boost::crc_32_type ret;
            std::string vnode = node.to_str();
            std::cout<<"vnode:"<<vnode<<std::endl;
            ret.process_bytes(vnode.c_str(),vnode.size());
            return ret.checksum();
        }
        typedef uint32_t result_type;
    };
    
    
    int main(int argc, char const *argv[])
    {
        typedef consistent_hash_map<vnode_t,crc32_hasher> consistent_hash_t;
        consistent_hash_t consistent_hash_;
    
        for(std::size_t i=0;i<5;++i) 
        {//每个节点插入100个虚拟节点
            for(std::size_t j=0;j<100;j++) 
            {
                consistent_hash_.insert(vnode_t(i,j));
            }
        }
    
    
        //遍历consistent_hash中的所有的vnode,统计每个虚拟节点的key的数量和每个主机包含key的数量
        {
            std::cout<<"========================================================="<<std::endl;
            //sums统计每个主机可以包含的key数量
            std::size_t sums[] = {0,0,0,0,0};
    
            //处理圆环的链接点处第一个vnode
            consistent_hash_t::iterator i = consistent_hash_.begin();
            consistent_hash_t::reverse_iterator j = consistent_hash_.rbegin();
            // 计算第一个节点包含的key数量
            // static_cast<uint32_t>(-1)源码为UINT32_MAX, 但无法通过编译,替代之
            std::size_t n = i->first + static_cast<uint32_t>(-1) - j->first;
            std::cout<<boost::format("vnode:%1%,hash:%2%,contains:%3%") 
                % i->second.to_str() % i->first % n << std::endl;
            sums[i->second.node_id] += n;
    
            uint32_t priv = i->first;
            uint32_t cur;
            consistent_hash_t::iterator end = consistent_hash_.end();
    
            // 处理圆环中间的vnode
            while(++i != end)
            {
                cur = i->first;
                n = cur - priv;
                std::cout<<boost::format("vnode:%1%,hash:%2%,contains:%3%") 
                    % i->second.to_str() % cur % n << std::endl;
                sums[i->second.node_id] += n;
                priv = cur;
            }
    
            for(std::size_t i=0;i<5;++i) 
            {
                std::cout<<boost::format("node:%1% contains:%2%") % nodes[i] % sums[i] <<std::endl; 
            }
    
        }
    
    
        //查找某个hash值对应的vnode 和 主机
        {
            consistent_hash_t::iterator it;
            it = consistent_hash_.find(290235110);
            std::cout<<boost::format("node:%1%,vnode:%2%,hash:%3%") 
                % nodes[it->second.node_id] % it->second.vnode_id % it->first << std::endl;
        }
    
    
        return 0;
    }

    testVnode结果自己测

    展开全文
  • 先从一个小测试开始 #include<iostream> using namespace std; class CExample { ... CExample(int x) : m_nTest(x) //带参数构造函数 { cout << "constructor with argumen...

    先从一个小测试开始

    #include<iostream>
    using namespace std;
     
    class CExample
    {
    private:
    	int m_nTest;
     
    public:
    	CExample(int x) : m_nTest(x)      //带参数构造函数
    	{ 
    		cout << "constructor with argument"<<endl;
    	}
     
    	// 拷贝构造函数,参数中的const不是严格必须的,但引用符号是必须的
    	CExample(const CExample & ex)     //拷贝构造函数
    	{
    		m_nTest = ex.m_nTest;
    		cout << "copy constructor"<<endl;
    	}
     
    	CExample& operator = (const CExample &ex)   //赋值函数(赋值运算符重载)
    	{	
    		cout << "assignment operator"<<endl;
    		m_nTest = ex.m_nTest;
    		return *this;
    	}
     
    	void myTestFunc(CExample ex)
    	{
    	}
    };
     
    int main(void)
    {
    	CExample aaa(2);
    	CExample bbb(3);
    	bbb = aaa;
    	CExample ccc = aaa;
    	bbb.myTestFunc(aaa);
     
    	return 0;	
    
    }

    运行结果为:

    
    constructor with argument        // CExample aaa(2);
    constructor with argument        // CExample bbb(3);
    assignment operator              // bbb = aaa;
    copy constructor                 // CExample ccc = aaa;
    copy constructor                 //  bbb.myTestFunc(aaa)
    

    如果你能一眼看出就是这个结果的话, 恭喜你,可以站起来扭扭屁股,不用再往下看了。

    如果你的结果和输出结果有误差, 那拜托你谦虚的看完。

    第一个输出: constructor with argument      // CExample aaa(2);

    如果你不理解的话, 找个人把你拖出去痛打一顿,然后嘴里还喊着“我是二师兄,我是二师兄.......”

    第二个输出:constructor with argument     // CExample bbb(3);

    分析同第一个

    第三个输出: assignment operator                // bbb = aaa;

    第四个输出: copy constructor                      // CExample ccc = aaa;

    这两个得放到一块说。 肯定会有人问为什么两个不一致。原因是, bbb对象已经实例化了,不需要构造,此时只是将aaa赋值给bbb,只会调用赋值函数,就这么简单,还不懂的话,撞墙去! 但是ccc还没有实例化,因此调用的是拷贝构造函数,构造出ccc,而不是赋值函数,还不懂的话,我撞墙去!!

     

    第五个输出: copy constructor                      //  bbb.myTestFunc(aaa);

    实际上是aaa作为参数传递给bbb.myTestFunc(CExample ex), 即CExample ex = aaa;和第四个一致的, 所以还是拷贝构造函数,而不是赋值函数, 如果仍然不懂, 我的头刚才已经流血了,不要再让我撞了,你就自己使劲的再装一次吧。

    通过这个例子, 我们来分析一下为什么拷贝构造函数的参数只能使用引用类型。

    看第四个输出: copy constructor                      // CExample ccc = aaa;

    构造ccc,实质上是ccc.CExample(aaa); 我们假如拷贝构造函数参数不是引用类型的话, 那么将使得 ccc.CExample(aaa)变成aaa传值给ccc.CExample(CExample ex),即CExample ex = aaa,因为 ex 没有被初始化, 所以 CExample ex = aaa 继续调用拷贝构造函数,接下来的是构造ex,也就是 ex.CExample(aaa),必然又会有aaa传给CExample(CExample ex), 即 CExample ex = aaa;那么又会触发拷贝构造函数,就这下永远的递归下去。

    所以绕了那么大的弯子,就是想说明拷贝构造函数的参数使用引用类型不是为了减少一次内存拷贝, 而是避免拷贝构造函数无限制的递归下去。
     

    转载自:https://blog.csdn.net/hackbuteer1/article/details/6545882 

     

    因此:

    一、为何要用引用:

    由上节的第五个输出分析可知,在执行bbb.myTestFunc(aaa);时,其实会调用拷贝构造函数。如果我们的拷贝构造函数的参数不是引用,那么在bbb.myTestFunc(aaa);时,调用CExample ex = aaa;,又因为ex之前没有被创建,所以又需要调用拷贝构造函数,故而又执行CExample ex = aaa;,就这样永远的递归调用下去了。

      所以, 拷贝构造函数是必须要带引用类型的参数的, 而且这也是编译器强制性要求的。

    二、为何要要用const

    如果在函数中不会改变引用类型参数的值,加不加const的效果是一样的。而且不加const,编译器也不会报错。但是为了整个程序的安全,还是加上const,防止对引用类型参数值的意外修改。(提示这是一个输入参数)

    展开全文
  • PCL采样一致性算法

    千次阅读 2017-04-11 13:53:55
    在计算机视觉领域广泛的使用各种不同的采样一致性参数估计算法用于排除错误的样本,样本不同对应的应用不同,例如剔除错误的配准点对,分割出处在模型上的点集,PCL中以随机采样一致性算法(RANSAC)为核心,同时...
  • C++中Const的用法总结

    2019-02-15 18:23:38
    const 修饰的东西都受到强制保护,可以预防意外的变动,能提高程序的健壮。所以很多书都建议尽可能使用const。 目录 一、const修饰变量 二、const的引用 三、指针和const 四、const修饰函数参数...
  • C++ const关键字的总结

    万次阅读 多人点赞 2018-07-31 01:03:30
    const关键字是c++中一个很重要又很有迷惑的知识点,这里对其进行一次总结。 const修饰非成员变量  const全局/局部变量  const全局变量 在文件a.cpp中定义了一个全局变量a int a = 1;  在文件test.cpp中...
  • C++ const用法详解

    2019-08-11 21:53:28
    C++ const用法详解 const可被施加于任何作用域内的对象,函数参数,...文章目录C++ const用法详解`const` 用来修饰变量`const` 用来修饰函数的参数以及返回值`const` 用来修饰**成员函数** const 用来修饰变量 用con...
  • PCL点云随机采样一致性分割算法

    千次阅读 2019-07-04 16:58:54
    最近在学习点云的分割算法,目前了解到有两种分割算法,一种是聚类分割算法,一种是随机采样一致性算法,聚类算法上篇文章已经有所提及。今天分析下随机采样一致性算法,然后代码理解; RANSAC随机采样一致性算法...
  • typedef const

    千次阅读 2013-10-12 14:51:12
    不过,在真实项目中的命名一致性更重要。你应该在两种情况下都能适应,并能自如的转换,公司习惯, 商业利润不论在什么时候都应该优先考虑!不过在开始一个新项目的时候,你可以考虑优先使用const在后面的习惯...
  • C/C++中的const

    2018-07-24 19:17:20
    用途三:const修饰函数参数 前言  在C/C++中,常量是固定值或字面量,且在程序执行期间不会改变。常量可以是任何的基本数据类型,比如整数常量、浮点常量、字符常量,或字符串字面值,也有枚举常量;也...
  • RANSAC 随机一致性采样

    千次阅读 2014-07-14 19:28:21
    随机一致性采样是一种鲁棒的模型拟合算法,
  • C++ const 用法

    2014-03-22 11:16:59
    1.const关键字 常类型是指使用类型修饰符const说明的类型,常类型的变量或对象的值是不能被更新的。不管出现在任何上下文都是为这个目的而服务的。 2.const使用方法 定义const对象 const修饰符...
  • 随机抽样一致性算法

    万次阅读 2013-06-13 11:19:13
    随机抽样一致性算法(RANSAC) 作者:王先荣  本文翻译自维基百科,英文原文地址是:http://en.wikipedia.org/wiki/ransac,如果您英语不错,建议您直接查看原文。  RANSAC是“RANdom SAmple ...
  • const的作用和用法

    2020-02-11 15:12:25
    一、const的作用 ...3.合理使用关键字const可以使编译器很自然的保护那些不希望被修改的参数,防止无意的代码修改,可以减少bug的出现; 二、const的用法 常变量: const 类型说明符 变量名 常引用:...
  • // 阈值等参数 const int ORBmatcher::TH_HIGH = 100;// 相似变换 描述子匹配 阈值 const int ORBmatcher::TH_LOW = 50; // 欧式变换 描述子匹配 阈值 const int ORBmatcher::HISTO_LENGTH = 30;// 匹配点对 ...
  • C++中const用法总结

    千次阅读 2016-04-10 14:35:40
    const在C++中使用十分广泛,不同位置使用的意义也不尽相同,所以想写篇文章对其做一个总结。 首先,明确const是“不变”这个基本意义,但是不变不意味着什么都不变,下面将会看到。 1. const与变量 ...
  • int printf( const char* format, ...);  它除了有一个参数format固定以外,后面跟的参数的个数和类型是可变的(用三个点“…”做参数占位符),实际调用时可以有以下的形式:  printf("%d",i);  printf("%s...
  • const用法分析

    2013-06-17 12:54:46
    const直接可以取代c中的#define 以下几点很重要,学不好后果也也很严重 const 1. 限定符声明变量只能被读  const int i=5;  int j=0;  ...  i=j; //非法,导致编译错误  j=i; //合法 2....
  • const各种用法总结

    千次阅读 2017-06-05 17:11:41
    const各种用法总结  原文地址:http://www.cnblogs.com/jiabei521/p/3335676.html#2787569 1、const关键字 常类型是指使用类型修饰符const说明的类型,常类型的变量或对象的值是不能被更新的。 1.1 const...
  • ConcurrentHashMap弱一致性迭代器Iterator

    千次阅读 2018-09-13 16:38:59
    答案是不会,少见多怪了,util包中的迭代器实现是fast-failed迭代器,说白了就是一旦由修改就抛异常,在current包中迭代器是弱一致性迭代器,原来两种迭代器情况不一样。 测试代码用以ConcurrentHashMap为例...
  • 随机抽样一致性(RANSAC)算法

    千次阅读 2016-08-03 17:09:31
     随机抽样一致性(RANSAC)算法,可以在一组包含“外点”的数据集中,采用不断迭代的方法,寻找最优参数模型,不符合最优模型的点,被定义为“外点”。在图像配准以及拼接上得到广泛的应用,本文将对RANSAC算法在...
  • 对于const定义的常量,不能直接修改它的值,这是这个限定符最直接的表现。但是某种情况下我们突破const限定修改其内容,C++11中可以使用const_cast转换符是用来移除变量的const限定符。关于const_cast的用法网上可以...
  • C 语言编程 — const 关键字

    千次阅读 2020-06-20 00:43:50
    定义常量:下述两种方式效果一致,通常使用后者。 TYPE const ValueName = value; const TYPE ValueName = value; 注:当 conse 定义的常量是一个 “外部连接” 时,可以不进行初始化,仅仅作为声明,编译器认为该...
  • const在C与C++中的区别

    2016-03-26 00:13:17
    1、C语言中的const a. 修饰变量 使用const修饰变量,使该变量的值不能被修改 b. 修饰函数参数
  • · 说明 以下均为 Being_young 前辈所写,现转载过来,再加上自己的理解,重新写了一遍,方便自己日后使用 ...随机采样一致性算法 (RANSAC) 最小中值法 (LMeds) PCL中 Sample_consensus 模块及类的介绍
  • const与stastic用法

    2017-02-12 16:01:22
    菜鸟加贝的爬升 博客园首页新随笔联系订阅管理 ...随笔 - 23 文章 - 0 评论 ...C++中const关键字的使用方法,烦透了一遍一遍的搜,总结一下,加深印象...知识用时方恨少,这一段时间正好各种笔试题,其中关于const
  • 使用一致性哈希的好处在于,增减集群的缓存服务器时,只有少量的缓存会失效,回源量较小。 在nginx+ats / haproxy+squid等CDN架构中,nginx/haproxy所使用的负载均衡算法便是一致性哈希。   我们举个例子来说明...
  • libmemcached的一致性hash实现源码分析

    千次阅读 2013-03-29 21:57:15
    由于工作上对多语言之间数据缓存一致性的需要,个人分析了libmemcached的实现,对底层一致性的实现有了一些了解,这里分享一些分析的一些过程,也给自己做个笔记。我使用是php,从php的扩展开始分析应该来说是最方便...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 86,661
精华内容 34,664
关键字:

const参数一致性