There are some very confusing behaviors in Lua C API. Here are some explanations for these. (Tested on Lua 5.4)

1. Type of number, integer, string

Operations like lua_isnumber, lua_pushinteger, lua_isstring don’t mean checking the value’s type:

• Values with type number can also get true of lua_isstring. (Number is also string)
• There are no integer types in Lua. Values generated by lua_pushinteger have type number.
• Only values generated by lua_pushinteger can get true of lua_isinteger. (But get false after lua_tostring)
• lua_isnumber gets true if the value is a real number or a string but convertible to number.

lua_tostring will implicitly convert number to string:

• After calling lua_tostring on a value of type number, the value’s type will change to string implicitly, but it is still lua_isnumber.
• After calling lua_tostring on a value generated by lua_pushinteger, it cannot get true of lua_isinteger anymore. (String is always not integer)

Test cases

[1] Applies to all float or integer numbers. e.g. lua_pushnumber(L, 0), lua_pushnumber(L, 123), lua_pushnumber(L, 0.1), etc.

[2] e.g. “123”, “1.23”, “12.”, “.12”, “-1.23”, “+1.23”, “1.2e3”, “-1.2E-3”, etc.

[3] e.g. “1.2.3”, “1+2”, “hello”, “inf”, etc.

Conclusion

1. Integer is not a type. Integer is a special case of number.
2. Number is also string.
3. String is also number if it is convertible to number.
4. String is always not integer.
5. lua_tostring will implicitly convert number to string.

More to say

Not like lua_tostring, luaL_tolstring won’t convert number to string. But it can convert any value to string, while lua_tostring will return NULL if the value is not a string or number.

2. Type of userdata, light userdata

Userdata and light userdata have different type ID, but they have a same type name. lua_islightuserdata is a subset of lua_isuserdata:

• lua_isuserdata returns true for both userdata and light userdata. (Light userdata is userdata)
• lua_islightuserdata only returns true for light userdata.

Test cases

Conclusion

1. Type ID of light userdata is “LUA_TLIGHTUSERDATA” (value 2), type ID of userdata is “LUA_TUSERDATA” (value 7), but they have a same type name “userdata”.
2. Light userdata is a subset of userdata, although they have different type ID.
3. Light userdata is userdata.

3. Metatable of light userdata

Light userdata (unlike heavy userdata) have no per-value metatables. All light userdata share the same metatable, which by default is not set (nil).

nullptr是指针类型吗？

nullptr是C++里预定义的一个变量，它的类型是std::nullptr_t。 判断一个类型是否是指针类型，可以用std::is_pointer来判断。 测试std::nullptr_t是否是指针类型的代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <myostream.h>
myostream::ostream mycout(std::cout.rdbuf());
#define watch(...) MYOSTREAM_WATCH(mycout, " = ", "\n", "\n\n", __VA_ARGS__)

int main() {
    // 确认nullptr就是std::nullptr_t类型
    static_assert(std::is_same_v<decltype(nullptr), std::nullptr_t>, "Never happen");

    watch(std::is_pointer_v<std::nullptr_t>,
          std::is_member_pointer_v<std::nullptr_t>,
          std::is_pointer_v<std::nullptr_t *>
    );
    return 0;
}

输出：

1
2
3

std::is_pointer_v<std::nullptr_t> = 0
std::is_member_pointer_v<std::nullptr_t> = 0
std::is_pointer_v<std::nullptr_t *> = 1

可见std::nullptr_t并不是一个指针类型。 只不过我们平时常用nullptr来赋值给任意指针类型，会给人一种std::nullptr_t是指针类型的错觉。

从上例中还可以看出std::nullptr_t *等类型是指针类型，它们是指向std::nullptr_t的指针类型。

原理

std::nullptr_t不是指针类型，但是却可以转换成任意指针类型，并且以0为值。 它的一种实现方式如下：

 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

#ifdef _LIBCPP_HAS_NO_NULLPTR

_LIBCPP_BEGIN_NAMESPACE_STD

struct _LIBCPP_TEMPLATE_VIS nullptr_t
{
    void* __lx;

    struct __nat {int __for_bool_;};

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR nullptr_t() : __lx(0) {}
    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR nullptr_t(int __nat::*) : __lx(0) {}

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator int __nat::*() const {return 0;}

    template <class _Tp>
        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
        operator _Tp* () const {return 0;}

    template <class _Tp, class _Up>
        _LIBCPP_INLINE_VISIBILITY
        operator _Tp _Up::* () const {return 0;}

    friend _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR bool operator==(nullptr_t, nullptr_t) {return true;}
    friend _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR bool operator!=(nullptr_t, nullptr_t) {return false;}
};

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR nullptr_t __get_nullptr_t() {return nullptr_t(0);}

#define nullptr _VSTD::__get_nullptr_t()

_LIBCPP_END_NAMESPACE_STD

#else  // _LIBCPP_HAS_NO_NULLPTR

namespace std
{
    typedef decltype(nullptr) nullptr_t;
}

#endif // _LIBCPP_HAS_NO_NULLPTR

可见std::nullptr_t不是指针类型，可能是类似类的类型。 所以当然可以构造出指向std::nullptr_t的指针类型了，例如std::nullptr_t *，const std::nullptr_t *等。 那么std::nullptr_t是类类型吗？

nullptr是类类型吗？

通过以上源码可以看出std::nullptr_t通过宏开关设置了两种实现方式， 第一种就是一个普通的struct，是类类型，而第二种似乎是编译器内置的，不是类类型。 所以std::nullptr_t的类型是依赖实现的，可能是类类型，也可能不是。

判断一个类型是否是类类型，可用std::is_class。测试代码如下：

1
2
3
4
5
6
7
8

watch(std::is_class_v<std::nullptr_t>,
    std::is_union_v<std::nullptr_t>,
    std::is_null_pointer_v<std::nullptr_t>,
    std::is_scalar_v<std::nullptr_t>,
    std::is_object_v<std::nullptr_t>);

watch(std::is_null_pointer_v<std::nullptr_t>,
    std::is_null_pointer_v<void*>);

Clang和GCC在 -std=c++17 下默认输出是一样的：

1
2
3
4
5
6
7
8

std::is_class_v<std::nullptr_t> = 0
std::is_union_v<std::nullptr_t> = 0
std::is_null_pointer_v<std::nullptr_t> = 1
std::is_scalar_v<std::nullptr_t> = 1
std::is_object_v<std::nullptr_t> = 1

std::is_null_pointer_v<std::nullptr_t> = 1
std::is_null_pointer_v<void*> = 0

可见默认情况下std::nullptr_t也不是类类型，它就是独特的一个类型，可用std::is_null_pointer来判断。

（当然，如果在Clang下编译时手动添加宏定义_LIBCPP_HAS_NO_NULLPTR，那么std::is_class_v<std::nullptr_t>就等于true了，它就是普通的类类型了。）

nullptr能被取地址吗？

nullptr是右值临时变量，无法取地址，但是我们可以使用std::nullptr_t重新定义一个新的"nullptr"左值，然后就可以对其取地址了。代码如下：

1
2
3
4
5

// watch(nullptr, &nullptr); // error: cannot take the address of an rvalue of type 'nullptr_t'

std::nullptr_t null1, null2;
watch(null1, &null1);
watch(null2, &null2);

输出：

1
2
3
4
5

null1 = nullptr
&null1 = 0x16b1d3578

null2 = nullptr
&null2 = 0x16b1d3570

如何用C++的方式把"T*"转换成"void*"

假如T是某种未知的模版类型，如何把T*的变量转换成void*类型呢？ 用C语言的强制类型转换很容易实现：

1
2
3
4

template <typename T>
void* c_cast(T* p) { // 使用C风格的强制类型转换
    return (void*)(p);
}

那么如何用C++的类型转换方式实现呢？

事实上只用reinterpret_cast或static_cast是不行的，因为它们不能将 cv-qualified pointer 转换成 cv-unqualified pointer。 所以必须首先使用const_cast将cv属性去掉，然后再使用reinterpret_cast或static_cast。如下：

1
2
3
4
5
6
7

template <typename T>
void* cpp_cast(T* p) { // 使用C++风格的强制类型转换
    // return reinterpret_cast<void*>(p); // error
    return reinterpret_cast<void*>(const_cast<std::remove_cv_t<T>*>(p)); // OK
    // 或者用static_cast亦可
    // return static_cast<void*>(const_cast<std::remove_cv_t<T>*>(p)); // OK
}

cv-qualified std::nullptr_t及其指针

经过以上讨论，知道std::nullptr_t不是指针类型，那么如下两个问题就可迎刃而解。

cv-qualified std::nullptr_t 类型的变量能直接赋值给 std::nullptr_t 类型的变量吗？

可以。

1
2

const volatile std::nullptr_t p{0};
std::nullptr_t np = p; // OK

cv-qualified std::nullptr_t * 类型的变量能直接赋值给 std::nullptr_t * 类型的变量吗？

不可以。需要用const_cast转换后方可赋值。

1
2
3

const volatile std::nullptr_t * p{0};
// std::nullptr_t* np = p; // Error
std::nullptr_t* np = const_cast<std::nullptr_t*>(p); // OK

考虑有限候选多目标融合排序公式，目标个数$T$，候选对象个数$N$。 每一个候选对象都有$T$个目标分，需要按某个融合公式把它们融合成一个最终用于排序的分数。

加法融合公式

加法融合公式是线性的，形式简单，参数少，调参容易。其形式是： $$ Score = \sum_{i=1}^T w_i \cdot (b_i + t_i) $$ 其中，$t_i$ 为第$i$个目标的得分，$b_i$ 为第$i$个目标的Bias，一般固定为0，$w_i$ 为第$i$个目标的权重。

乘法融合公式

乘法融合公式是非线性的，相对加法融合公式来说形式复杂，参数多，调参稍微困难一些，但一般能比加法融合公式取得更好的效果。 其基础形式是： $$ Score = \prod_{i=1}^T (\beta_i + t_i) ^ {\alpha_i} $$ 其中，$t_i$ 为第$i$个目标的得分，$\alpha_i$和$\beta_i$ 为调整第$i$个目标权重的参数。实践中为了便于调参，可以把它改写成Bias形式： $$ Score = \prod_{i=1}^T (b_i + \beta_i \cdot t_i) ^ {\alpha_i} $$ $b_i$ 为第$i$个目标的Bias，一般固定为1，然后一个简单的调参方式是：在$t_i$的平均值的倒数的基础上调节$\beta_i$，在1附近调节$\alpha_i$。

目标分预处理

除了将目标分直接代入融合公式外，还可以先对其做一定的预处理。

归一化(Normalization)

目标分分布不稳定或分布不便于直接用到排序融合公式中时，可以把目标分归一化线性映射到稳定的$[A, B]$的区间，一般$B$取1，$A$可取0.01或更小或0：

$$ \tilde{t} = \frac{ t - \min t } { \max t - \min t} \cdot (B - A) + A $$

其中， $\max t = \max \limits_{1 \le j \le N} t^{(j)}$ 为目标分在$N$个候选对象上的分布的最大值， $\min t = \min \limits_{1 \le j \le N} t^{(j)}$ 为目标分在$N$个候选对象上的分布的最小值， $t^{(j)}$ 表示第$j$个候选对象的目标分。

要注意，实践中要规避除零的风险。

相对目标分

在推荐系统中，不同用户对某一个动作的喜好程度或使用频率不同，则表现为某一个目标分在不同用户上的分布有大小区别， 因此可以用该目标分在当前待排序的有限候选集上的相对得分取代原始得分：

$$ \hat{t} = \frac {t} { w \cdot \overline{t} + c } $$

其中， $\overline{t} = \frac { \sum_{j=1}^N t^{(j)} } {N}$ 为目标分在$N$个候选对象上的分布的平均值， $w$和$c$为待调整的参数。

例如，应用相对目标分的乘法融合公式为： $$ Score = \prod_{i=1}^T (b_i + \frac {t_i} {w_i \cdot \overline{t}_i + c_i} ) ^ {\alpha_i} $$ 此式也被称为个性化$\beta$形式，因为不同用户的目标分平均值$\overline{t}_i$不同，也就相当于Bias形式乘法融合公式中的$\beta_i$是不同的。

其他

此外，还可以将目标分按大小阈值截断，使用Sigmoid函数映射到0~1等。

在融合公式中使用目标排名

除了在融合公式中使用目标得分外，还可以使用目标排名代替目标分。

对全体候选对象按某一个目标分排序，则可得到每一个候选对象在这一个目标上的排名，记为$r_i$，表示在第$i$个目标上的排名，值为$[1, N]$之间的整数。 然后可以直接在融合公式中使用目标排名，或者将其归一化到$[\frac {1} {N}, 1]$之间，也就是将$r_i$除以$N$，之后再代入融合公式。

需要注意的是，由于排序时一般是逆序排序，目标分最大的排名是1，因此使用目标排名代替目标分时改变了融合公式的单调性，需要相应地再调整一下融合公式的单调性。

例如，在乘法融合公式中使用目标排名时，可以用$-\alpha$作为指数：

$$ Score = \prod_{i=1}^T (b_i + \beta_i \cdot \tilde{r}_i) ^ {- \alpha_i} $$ 其中，$\tilde{r}_i = \frac {r_i} {N}$。

或者，可以用$\tilde{r}_i = \frac {N + 1 - r_i} {N}$的映射方式对排名数值进行归一化， 则不需要再调整融合公式的单调性。

本文重点描述Maglev一致性哈希算法，并提出使Maglev一致性哈希算法支持带权重候选节点的改进方式， 以及描述了一致性哈希下的动态负载均衡策略，并给出开源C++实现代码库。

一致性哈希

一致性哈希是一种将属于无限集的key稳定地映射到属于有限集的候选节点上的算法，它需要满足：

• 稳定：候选节点集合不变时，一个固定的key，会稳定不变地映射到某一个候选节点上；
• 最小扰动：当增加或减少候选节点时，只有少部分key需要重新映射，大部分key的映射结果不变；
• 均衡：不同key应该均匀地分散到各个候选节点上，即一个key映射到每一个候选节点上的概率是相等的。

常见一致性哈希算法

环形哈希，也叫割环法，经典的一致性哈希算法，作者Karger等人于1997年提出一致性哈希算法的概念， 然后提出了这个一致性哈希算法。 更新和查询时间复杂度都是O(log(n))，空间复杂度O(n)， 但是通常均衡性不好，需要加入较多虚拟节点，也就加倍了时间和空间复杂度。

Jump Consistent Hash。极简的一致性哈希算法，不到十行代码。 查询时间复杂度是O(log(n))，不需要更新操作，也不需要额外存储空间。 但是不能随机增删候选节点，只能在有序候选节点队列的尾部增删节点，实用性不强。

Maglev一致性哈希算法。 查询时间复杂度O(1)，更新时间复杂度O(m)，空间复杂度O(m)，m通常为至少比n大10倍以上的一个素数常量。 较为实用，效果较好，下面重点介绍。

Maglev一致性哈希算法描述

1. 选取哈希槽长度，素数M，生成空哈希槽数组；
2. 将候选节点列表排序；
3. 对每一个候选节点哈希得到两个随机数A、B(模M-1再加1保证非0或M的倍数)，然后得到一个从0到M-1的排列：X[k] = (A + k*B)%M, k=0,1,…,M-1；
4. 排列中每一个数字代表一个槽位，轮询每一个候选节点的排列，从左到右选择排列中的第一个空槽位填充进去，直到哈希槽填充完整为止；
5. 对一个输入key，通过 key%M 映射到哈希槽中对应的候选节点。（这里的key通常需要哈希一下得到一个大随机数）

优缺点：

• 优点：分片均匀，均衡性好，查询速度快O(1)
• 缺点：增删节点后更新较慢O(n)，并且没有完全实现最小扰动。

一致性哈希支持带权重候选节点

通用做法：增加虚拟节点

通常一致性哈希算法都是不支持带权重候选节点的，也就是一个key映射到每一个候选节点的概率是相等的。 因此，想要实现带权重的一致性哈希的一个普遍思路是增加虚拟节点。将一个实际的候选节点拆成多个虚拟节点， 拆成的虚拟节点的多少，即代表了这个实际候选节点的权重的大小。

Maglev一致性哈希算法支持带权重候选节点的特殊做法：按权重正比概率阈值填充哈希槽位。

通常，增加虚拟节点的做法相当于增加了候选节点数n，如果时间空间复杂度与n有关，那么会相应增加复杂度。 其次，如果虚拟节点数增加的少，那么实际的权重比例会比较粗糙，即精度不够。

Maglev算法的查询时间复杂度与n无关，是O(1)，所以增加虚拟节点法不会影响Maglev的查询速度， 但是由于Maglev算法需要选取一个比候选节点数大很多的大素数M，且这个M关系到更新的时间复杂度和占用的空间复杂度， 因此采用增加虚拟节点法也会增加一些消耗。

观察Maglev算法哈希槽的填充过程可知，该算法是轮训每一个候选节点，让每一个候选节点占有一个哈希槽后才轮到下一个候选节点。 因此可以试想，只要让轮训到当前候选节点时，不一定完全占有一个候选节点，而是设定一个与该节点的权重成正比的概率阈值， 达到这个阈值后才占有一个哈希槽。这个概率阈值可以是：当前节点的权重除以所有节点的权重的最大值。 可以看出，无权重的情况，也就相当于每一个候选节点的权重都相等，因此对应的概率阈值也都相等，都是1。 另外，为了保证一致性哈希算法的稳定性，这里的概率生成要用稳定的伪随机概率，每一个候选节点用自己的固定信息， 比如节点ID，作为一个伪随机序列的种子，用这个伪随机序列称重的概率与对应的概率阈值相比较，来判断该节点在这一次轮训中要不要占有一个哈希槽位。

一致性哈希下的动态负载均衡

由开头对一致性哈希算法的描述中可以，输入的key是属于无限集的，是无法提前预知的，无法对其做任何分布性的要求。 因此，极有可能，输入的key就是极其不均衡的，而纯粹的一致性哈希又是要求结果必须是稳定的，所以不均衡的输入集， 最终会造成不均衡的映射结果。比如常见的热key问题，纯一致性哈希是无法解决的。

因此，为了在未知的不确定的任意的输入集上都保持良好的均衡性，需要动态的调整映射策略，需要统计感知每一个候选节点当前的负载情况， 如果负载过高，则应该将当前key用某种算法重新映射到另外一个节点上，而这个重新映射的算法最好也是稳定的。

对于Maglev算法来说，笔者提出一个简单的重新映射算法：(key + (key % C + 1) * retry_cnt) % M。 其中C是某一个常数，而retry_cnt是重新映射次数，可见当retry_cnt为0时，即首次映射时，该算法就退化到了Maglev算法描述第5步描述的 key % M的算法。

除了重新映射即重新选取候选节点外，对于动态负载均衡来说，另一个重点是，如何描述节点负载以及如何判断是否负载过高。

对于候选节点无权重的情况来说，任意一个候选节点每接收一个key，就增加这个key对应的负载值，如果所有的key对应的负载值都一样，即可记为1。 对于候选节点有权重的情况来说，不同的候选节点接收同一个key后对自身的负载影响是不同，需要乘以一个以自身权重为分母的负载归一化因子， 比如可以是：所有候选节点的权重的平均值除以当前节点的权重。这样，每一个候选节点接收一个key后，需要增加自身的负载归一化因子乘上这个key对应的负载值后， 这么多的负载增量。

有了每一个key对每一个候选节点的负载增量定量描述后，就可以计算所有候选节点的平均负载值，然后设定一个阈值，负载大于平均负载某一个倍数的节点， 即可认为是过载节点。例如，这个倍数可选1.2 ~ 1.5。

特别的，在RPC场景下，候选节点就相当于是远程服务器，每处理一个key就相当于一次远程服务请求。 因此，请求量、错误量、延时等信息也可用来描述候选节点的负载。错误数较多，延时过高时，即可认为当前节点负载过高。 但是为了避免全局的一致性哈希结果被大量破坏，可以对候选节点的每一项负载情况进行排名，然后限制只有该项负载排名很高的几个节点才能在这一负载项上被判定为过载。

最后，负载是动态变化的，负载的统计记录信息需要实时更新，通常需要一个滑动窗口，每隔固定几秒钟，就生成一个新的统计单元，并滑动滑动窗口， 丢弃窗口中最老的统计单元的数据，加入最新的统计单元的数据。

开源实现

以上所描述的Maglev一致性哈希算法，以及在此一致性哈希基础上的动态负载均衡策略，笔者已有一个完整的C++开源实现。 代码详见GitHub：cpp-maglev

关于我

李双全，男，90后，天蝎座，河北唐山人，程序员，现居北京。

工作经历

北京，字节跳动，评论排序系统架构和策略，推荐系统架构和策略，广告投放架构。

教育经历

南京，东南大学，自动化学院，获工学学士和工学硕士学位。

业余爱好

徒步🧗，登山🏔️，骑行🚴‍♂️，跑步🏃🏻，健身💪，篮球🏀，羽毛球🏸，乒乓球🏓；

读书📖，旅行🌴，写字✍️，诗歌📓，民谣🎧，逛书店，看展🖼，看音乐剧等等。

联系我

邮箱：lishq991 艾特 gmail 点 com

关于本站

Peacalm寓意: peaceful & calm
建站工具：Hugo + GitHubPages
主题：Jane
域名：使用GitHub提供的域名peacalm.github.io或我的个人域名lishuangquan.cn都可以访问本站