EOSIO 资源分配机制

本文为 MEET.ONE 发布的《EOSIO CPU 资源分配原理分析》 的个人版本,稣是其主要编辑之一。

1. 相关概念

您没看错,以下要介绍的几个概念,都是金融词汇。稣的柚子系列文章,又名《程序员转行做金融》,并兼职卖柚子……

  • 存款准备金率

    Deposit-reserve Ratio。存款准备金是指金融机构为保证客户提取存款和资金清算需要而准备的,是缴存在中央银行的存款,中央银行要求的存款准备金占其存款总额的比例就是存款准备金率。

    经常能听到的“降准不降息,等于装牛逼”里面的“降准”全称就是“降低法定存款准备金率”。

    举个外星的例子:如果存款准备金率为 1‰,就意味着金融机构每吸收 1000 元存款,要向央行缴存 1 元的存款准备金,用于发放贷款的资金为 999 元。

  • 挤兑

    Run on Banks。在银行券流通的条件下,银行券持有者争相到发行银行券的银行要求兑现贵金属货币的现象。当一家银行的信用发生动摇,准备金不足,银行券兑现发生困难,就会发生挤兑。挤兑可能使一家银行倒闭,甚至波及整个银行业。现在一般是指存款户集中地大量地到银行提取现钞。

  • 涨跌停板制度

    这个不解释了……就问一句:连续 5 天跌停和一天暴跌 41%,您喜欢那种?如果您喜欢没有板的,再多问一句:一天暴跌 99.9% 您觉得怎么样?

  • 峰谷电价

    又称“分时电价”,也很好理解。再举个类似的例子:下班高峰期打的,不加价基本打不到,因为别人加价优先接单。

2. 资源分配基本原则

EOS 账户可用资源与其抵押给资源的柚子数量的关系是:可用资源 = 总可用资源 * 本用户抵押数量 / 全体用户抵押数量。从这个关系上看,存在两个风险:

  • 大户挤兑散民;
  • 占着茅坑不拉屎。

第一个问题,用成本来解决,要通过加仓把别人的比例减少,按目前 3-4 亿的抵押量来说,需要付出的代价极高。

第二个问题,则通过引入一个放大因子来解决。之所以能放大是因为,某个时间点不拉屎的确实占大多数。只要把您拉屎的时间,除以一天的时间,就可以算出您一天拉屎的占用率。相信是很小的,笑……虽然您有柚子,就有拉屎的权利,但您自己不拉,让给需要拉的也是合理的,毕竟资源利用起来才是好事。

以 CPU 为例,计算公式为:

可用 CPU 微秒数 = max_block_cpu_usage * (account_cpu_usage_average_window_ms / block_interval_ms) * staked_cpu_count / total_staked_cpu_count

其中 max_block_cpu_usage 是可配置的,当前主网配置为默认值 default_max_block_cpu_usage = 200000

所以 max_block_cpu_usage * (account_cpu_usage_average_window_ms / block_interval_ms) = 34560000000

以主网 2018-10-19 为例,CPU 总质押量为 280053493.80756617 EOS,所以每个 EOS 可用 123.40 us。注意:这个数值是没有放大过的。

3. 堵车问题

EOS 定义了两种资源使用状态:拥堵、空闲,由过去一分钟每个块的平均使用量来界定。还是用 CPU 说事:大于 max_block_cpu_usage * target_block_cpu_usage_pct 则进入拥堵。

两个状态下的可用量本来应该有 1000 倍的差距,但因为有涨跌停板保护,并不会直上直下。每一分钟,只能跌到 99/100,只能涨到 1000/999。所以从拥堵开始到绝对拥堵,有 log(0.001) / log(0.99) = 687 分钟之长;从绝对拥堵完全恢复更慢,是 log(1000) / log(1000/999) = 6904 分钟。目前的 target_block_cpu_usage_pct 已经从 10% 调整到 20%,它提高了总使用量临界值,使拥堵状态更难触碰。

可用量的变化过程是可能随时改变方向的,类似多头和空头拉锯。比如拥堵时,可用量变少,能够使用资源的用户也随之减少,使用量降到阈值以下,可用量又会开始慢慢上升。

4. 阈值的设定

max_block_cpu_usage 和 target_block_cpu_usage_pct 都是可以配置的,为什么不一次性配高点呢?主要考虑的因素是,目前各个 BP 的机器性能参差不齐,如果冒然的把这两个值调高,可能会导致节点 replay 变慢,同时对于配置低的机器来说,同步区块也会很吃力。别忘了,我们的准备金率才 1‰,属于严重超发,提高可用率,虽然会使拥堵来得晚点,但真到拥堵的那刻,爆发的能量可是更大的哦!

总之,还是稳一点好,慢慢涨经验。目前来看昨天的调整,对节点之间的同步、CPU 使用率没有太大影响。

5. 参考

EOSIO 代码

EOS资源模型

人工神经网络训练方法——后向传播

人工神经网络训练方法——随机查找》介绍的随机查找方法,有点盲人摸象,所以继续介绍主流的后向传播(BackPropagation)算法。

填坑

先给随机查找做个优化!上篇中的激活函数统一使用 ReLU,其实这是不好的,输出层可以改为 Sigmoid 或 Tanh:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline double ActivationFunction_ReLU(double x) {
return std::max(0.0, x);
}
inline double ActivationFunction_Sigmoid(double x) {
return 1.0 / (1 + exp(-x));
}
inline double ActivationFunction_Tanh(double x) {
return (tanh(x) + 1.0) / 2;
}

double AnnRun(const double x[2], double* w) {
double f = ActivationFunction_ReLU(x[0] * w[0] + x[1] * w[1] - w[2]);
double g = ActivationFunction_ReLU(x[0] * w[3] + x[1] * w[4] - w[5]);
return ActivationFunction_Sigmoid(f * w[6] + g * w[7] - w[8]);
}

原因很简单,我们已经知道 Xor 的结果不是 0 就是 1,用 ReLU 是可能大于 1 的,而 Sigmoid 和 Tanh 不会大于 1。

后向传播

理论学习:《如何直观地解释 back propagation 算法?》

原理:求导

训练时,x 和 y 都是固定的,要求的是 a 和 b,所以问题是:当 y 偏离了 delta_y,求 a 和 b 应该修正多少?

分别对 a 和 b 求偏导,则:

1
2
dy/da = x
dy/db = 1

所以

1
2
delta_a = delta_y / x
delta_b = delta_y

代码不会骗人,来一个简化的例子:

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
// BackPropagation.cpp
//

#include <iostream>

void Train(double& a,
double& b,
double input,
double expect_output,
double learning_rate)
{

double delta_y = expect_output - (input * a + b);
if (input != 0) {
a += (delta_y / input) * learning_rate;
}
b += delta_y * learning_rate;
}

int main() {
// 要求的函数是:y = 2 * x + 3
const double input[4] = {0, 1, 2, 3};
const double expect_output[4] = {3, 5, 7, 9};

// 初始化状态是:y = 1 * x + 4
double a = 1.0;
double b = 4.0;

std::cout << "Initial: y = " << a << " * x + " << b << "\n";

// 两轮就搞定了
for (int t = 0; t < 2; ++t) {
for (int i = 0; i < 4; ++i) {
Train(a, b, input[i], expect_output[i], 1);
}
}
std::cout << "Trained: y = " << a << " * x + " << b << "\n";

return 0;
}

人工神经网络训练方法——随机查找

人工神经网络究竟是什么鬼?》中没有讲到如何训练神经网络,本篇延续用 XOR 运算为例,介绍一种随机查找的训练方式,主要原理是:随机初始化 w,计算错误率,在循环中,保存错误率小的 w,直到错误率小于等于 0.01 为止。

代码不会骗人,简单的实现如下:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// TrainXor_RandomSearch.cpp
// UMUTech @ 2018-07-05 23:45:52
// Be aware that I'm only a novice to ANN. My apologies for any wrong info.
//
#include <algorithm>
#include <iostream>
#include <random>

std::default_random_engine random_engine;

void RandomizeW(double* w, size_t size) {
std::uniform_real_distribution<double> r(0, 1);
for (size_t i = 0; i < size; ++i) {
w[i] = r(random_engine);
}
}

void PrintW(double* w, size_t size) {
for (size_t i = 0; i < size; ++i) {
std::cout << i << "\t" << w[i] << "\n";
}
}

double ActivationFunction(double x) {
// ReLU
return std::max(0.0, x);
}

double AnnRun(const double x[2], double* w) {
// bias 乘了 -1,让结果更好地收敛到 [0, 1]
double f = ActivationFunction(x[0] * w[0] + x[1] * w[1] - w[2]);
double g = ActivationFunction(x[0] * w[3] + x[1] * w[4] - w[5]);
return ActivationFunction(f * w[6] + g * w[7] - w[8]);
}

int main() {
const double input[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
const double expect_output[4] = {0, 1, 1, 0};

double last_error = 1000;

double w[3 * 3];
double w_copy[3 * 3];

std::random_device rd;
random_engine.seed(rd());

int train_count = 0;
for (; last_error > 0.01; ++train_count) {
if (train_count % 10000 == 0) {
std::cout << "Randomize\n";
RandomizeW(w, _countof(w));
}

memcpy(w_copy, w, sizeof(w));

// 随机改变 w
std::uniform_real_distribution<double> r(-0.5, 0.5);
for (int i = 0; i < 3 * 3; ++i) {
w[i] += r(random_engine);
}

double error = pow(AnnRun(input[0], w) - expect_output[0], 2.0);
error += pow(AnnRun(input[1], w) - expect_output[1], 2.0);
error += pow(AnnRun(input[2], w) - expect_output[2], 2.0);
error += pow(AnnRun(input[3], w) - expect_output[3], 2.0);

if (error < last_error) {
// 错误率更小,保存
last_error = error;
} else {
// 恢复 w
memcpy(w, w_copy, sizeof(w));
}
}

printf("Finished in %d loops.\n", train_count);

PrintW(w, _countof(w));

/* Run the network and see what it predicts. */
printf("Output for [%1.f, %1.f] is %1.f.\n", input[0][0], input[0][1],
AnnRun(input[0], w));
printf("Output for [%1.f, %1.f] is %1.f.\n", input[1][0], input[1][1],
AnnRun(input[1], w));
printf("Output for [%1.f, %1.f] is %1.f.\n", input[2][0], input[2][1],
AnnRun(input[2], w));
printf("Output for [%1.f, %1.f] is %1.f.\n", input[3][0], input[3][1],
AnnRun(input[3], w));

return 0;
}

效果主要看人品,可能跑个不停,也可能几乎立刻完成。一次运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Randomize
Finished in 344 loops.
0 -1.18943
1 -1.60685
2 -0.848489
3 1.28751
4 1.21697
5 0.532657
6 -2.27322
7 -0.77646
8 -1.57966
Output for [0, 0] is 0.
Output for [0, 1] is 1.
Output for [1, 0] is 1.
Output for [1, 1] is 0.

另一次:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Randomize
Finished in 444 loops.
0 1.6138
1 1.4345
2 1.33925
3 1.50895
4 1.09461
5 -0.283878
6 -2.37528
7 1.08117
8 0.239626
Output for [0, 0] is 0.
Output for [0, 1] is 1.
Output for [1, 0] is 1.
Output for [1, 1] is 0.

显卡名称包含汉字导致 DX11 程序无法正常工作

某游戏在 RemoteFX 远程桌面下无法正常运行。提示:

运行引擎需要DX11特征等级10.0

英文版提示:

DX11 feature level 10.0 is required to run the engine.

稣立刻调用 dxdiag 查看,结果 Feature Level 10.0 是支持的!

然后决定自己写个 DX11 程序测试一下,于是找到这里例子:Tutorial 3: Initializing DirectX 11,稍加修改后运行,得到一个错误提示:

MessageBox(hwnd, L”Could not initialize Direct3D.”, L”Error”, MB_OK);

接下来,仔细检查这个初始化过程,发现居然是因为 wcstombs_s 失败引起的:

1
2
// Convert the name of the video card to a character array and store it.
error = wcstombs_s(&stringLength, m_videoCardDescription, 128, adapterDesc.Description, 128);

原来是因为 RemoteFX 显卡的名字里有汉字……

RemoteFX 3D 视频适配器

设备名称:

Microsoft RemoteFX 图形设备 - WDDM

通过注册表改显卡名字,测试代码的问题解决!但 wcstombs_s 这块代码其实并无与显卡功能相关,去掉这段代码也可以解决问题。

RemoteFX 能否用于物理机的远程桌面服务?

用户故事

大学时期(2002-2006 年)经常在学校机房使用远程桌面(RDP)连自己宿舍的电脑,当时的校园网是 100Mpbs 的,但每次一开视频,还是卡成翔……

后来慢慢发现,远程桌面看视频已经不是事儿了,甚至可以玩游戏!

近几年,云游戏的概念越来越流行,曾经用远程桌面连到开启 RemoteFX 的虚拟机上玩过街霸,发现体验很好。于是有了一个疑问:稣有一台 PC,配了块 GeForce GTX 980 Ti 显卡,能不能开启 RemoteFX,然后在烂机器远程桌面上去愉快地玩耍?

调研结论

截止目前还不能在物理机上开启远程桌面的 RemoteFX 功能。其中原因是微软的商业策略,并不是技术问题。

参考链接

Windows 10 RDP with RemoteFX

学习 MongoDB 选举机制

为了快速了解 MongoDB 选举机制,在网上找了一些文章来学习,后来发现里面提到的一些机制都过时了,尝试看代码了解,发现协议有 PV0 和 PV1 两种。

代码:https://github.com/mongodb/mongo/blob/r3.6.5/src/mongo/db/repl/topology_coordinator.cpp

一篇比较新的参考文章:https://blog.csdn.net/wentyoon/article/details/78986174

如果新选举出的主节点立马挂掉,至少需要 30s 重新选主,这个是由 leaseTime 常量决定的:

const Seconds TopologyCoordinator::VoteLease::leaseTime = Seconds(30);

PV0 时,一个反对会将最终票数减 10000,即在绝大多数情况下,只要有节点反对,请求的节点就不能成为主节点,由 prepareElectResponse 函数实现,里面有不少 vote = -10000;,PV1 版本取消了否决票。

批量导出 QQ 空间说说

创作故事

  2015-03-16 为了导出自己的说说,写了个半自动的程序,手动分析几个参数填到代码理,很快就刷刷地下载了 7 年的说说。第二天,就在知乎回答了两贴。

如何一次性导出QQ空间说说?

如何批量导出特定 QQ 号的所有说说?

  2015-09-07 发现导出程序失效了,参数有点变化,但很快又跟进。

  2015-11-27 又失效了,除了 json 字段有变化,还增加了对 Cookie 的验证,于是又加上了 Cookie 的模拟。

  2015-12-11 又又失效了,这次增加了对 UserAgent 的验证……继续跟进。

  由于知乎的热度,越来越多的人找 UMU 导出,但这个程序是半自动的,会占用宝贵的时间,所以后来干脆让全职带孩子的脑波来,收点人工费。需要的可以联系 QQ:372769132(验证消息:qzone)。

收费规则

1. 8.88 元起,每 1000 条 8.88 元人民币;

2. 未满 1000 条部分,采用进一法,即 10001 条,是收费 8.88 * 2 = 17.76 元;

3. 封顶 88.88 元,所以,如果您的说说很多也不用害怕会很贵。

4. 支持 QQ 红包、微信、支付宝。

FAQ

1. 要交出 QQ 密码吗?

答:不必须。如果您的说说都是公开的,则完全没有必要交出密码。如果您发过只有自己或者少数好友可见的说说,则需要用您的账号密码登陆才能抓全。

2. 我的 QQ 空间被封了,别人都无法访问,可以导出吗?

答:只要您自己能访问就可以,但要提供您的账号和密码。您可以事先改一个临时密码,事后再改掉。

3. 导出的格式是什么样的?

答:主体是一个 json 文件,里面有您全部说说,包括说说本身、别人的回复、图片链接(没有图片本身)。另外生成一份 txt 文件,只有发帖时间和说说本身,其它都没有。

备注

如果有时间会改进,比如说搞成图文并茂的格式,也导出博客。

MongoDB Shard ID hash 算法 std::hash 的跨平台性

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
#include <functional>
#include <iomanip>
#include <iostream>
#include <string>


int main()
{

std::string str = "Meet the new boss...";
std::size_t str_hash = std::hash<std::string>{}(str);
std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << std::endl;

str = "Meet the new boss..;";
str_hash = std::hash<std::string>{}(str);
std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << std::endl;

str = "Meet the new boss../";
str_hash = std::hash<std::string>{}(str);
std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << std::endl;

str = "Meet the new boss..,";
str_hash = std::hash<std::string>{}(str);
std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << std::endl;

return 0;
}

Windows, VS 2017 的结果:

hash(“Meet the new boss…”) = 5935324269489717502

hash(“Meet the new boss..;”) = 5935347359233909933

hash(“Meet the new boss../“) = 5935325369001345713

hash(“Meet the new boss..,”) = 5935322070466461080

Ubuntu 16.04, g++ 5.4.0 20160609 的结果:

hash(“Meet the new boss…”) = 10656026664466977650

hash(“Meet the new boss..;”) = 12509209616339026574

hash(“Meet the new boss../“) = 6552276210272946664

hash(“Meet the new boss..,”) = 15639609178671340058

还好我们不会在生产环境,使用 Windows 部署 MongoDB……

1
2
3
std::size_t ShardId::Hasher::operator()(const ShardId& shardId) const {
return std::hash<std::string>()(shardId._shardId);
}

详见:https://github.com/mongodb/mongo/blob/master/src/mongo/s/shard_id.cpp

这个 std::hash 在 x86 和 x64 下都不一样,所以,让我们看看 MongoDB 如何解决这个问题:

MongoDB 3.4 no longer supports 32-bit x86 platforms.

好样的!

求模版函数地址

最近用 WTL 写 Ribbon 界面,发现一个坑。

先看 WTL9.1 的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void (CharFormat::*Getk_[])(IPropertyStore*) = 
{
&CharFormat::Getk_Family,
&CharFormat::Getk_FontProperties_Size,
&CharFormat::Getk_MaskEffect<CFM_BOLD, CFE_BOLD, UI_PKEY_FontProperties_Bold>,
&CharFormat::Getk_MaskEffect<CFM_ITALIC, CFE_ITALIC, UI_PKEY_FontProperties_Italic>,
&CharFormat::Getk_MaskEffect<CFM_UNDERLINE, CFE_UNDERLINE, UI_PKEY_FontProperties_Underline>,
&CharFormat::Getk_MaskEffect<CFM_STRIKEOUT, CFE_STRIKEOUT, UI_PKEY_FontProperties_Strikethrough>,
&CharFormat::Getk_VerticalPositioning,
&CharFormat::Getk_Color<CFM_COLOR, UI_PKEY_FontProperties_ForegroundColor>,
&CharFormat::Getk_Color<CFM_BACKCOLOR, UI_PKEY_FontProperties_BackgroundColor>,
&CharFormat::Getk_ColorType<CFM_COLOR, CFE_AUTOCOLOR, UI_SWATCHCOLORTYPE_AUTOMATIC, UI_PKEY_FontProperties_ForegroundColorType>,
&CharFormat::Getk_ColorType<CFM_BACKCOLOR, CFE_AUTOBACKCOLOR, UI_SWATCHCOLORTYPE_NOCOLOR, UI_PKEY_FontProperties_BackgroundColorType>,
};

其中 Getk_MaskEffect 是个模版函数,实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <DWORD t_dwMask, DWORD t_dwEffects, REFPROPERTYKEY key>
void Getk_MaskEffect(IPropertyStore* pStore)
{
if (SUCCEEDED(pStore->GetValue(key, &propvar)))
{
UIPropertyToUInt32(key, propvar, &uValue);
if ((UI_FONTPROPERTIES)uValue != UI_FONTPROPERTIES_NOTAVAILABLE)
{
dwMask |= t_dwMask;
dwEffects |= ((UI_FONTPROPERTIES) uValue == UI_FONTPROPERTIES_SET) ? t_dwEffects : 0;
}
}
}

然后,在 VS2017 编译失败了……

1>X:\WTL91_5321_Final\Include\atlribbon.h(422): error C2440: ‘initializing’: cannot convert from ‘overloaded-function’ to ‘void (__thiscall WTL::RibbonUI::CharFormat:: )(IPropertyStore )’

1>X:\WTL91_5321_Final\Include\atlribbon.h(422): note: None of the functions with this name in scope match the target type

然后根据错误提示搜到:Cannot take address of template function,https://gcc.gnu.org/bugzilla/show_bug.cgi?id=39018,翻译一下:模版函数的地址转化,分两步走,第一步先转具化,第二步转目标类型,这样可以;直接转过去不可以!

再来看看 WTL10 怎么解决这个问题的!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void (CharFormat::*Getk_[])(IPropertyStore*) = 
{
&CharFormat::Getk_Family,
&CharFormat::Getk_FontProperties_Size,
&CharFormat::Getk_MaskEffectBold,
&CharFormat::Getk_MaskEffectItalic,
&CharFormat::Getk_MaskEffectUnderline,
&CharFormat::Getk_MaskEffectStrikeout,
&CharFormat::Getk_VerticalPositioning,
&CharFormat::Getk_Color,
&CharFormat::Getk_ColorBack,
&CharFormat::Getk_ColorType,
&CharFormat::Getk_ColorTypeBack,
};

原来的模版函数,已经替换成普通函数了……

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
void Getk_MaskEffectBold(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_BOLD, CFE_BOLD, UI_PKEY_FontProperties_Bold);
}

void Getk_MaskEffectItalic(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_ITALIC, CFE_ITALIC, UI_PKEY_FontProperties_Italic);
}

void Getk_MaskEffectUnderline(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_UNDERLINE, CFE_UNDERLINE, UI_PKEY_FontProperties_Underline);
}

void Getk_MaskEffectStrikeout(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_STRIKEOUT, CFE_STRIKEOUT, UI_PKEY_FontProperties_Strikethrough);
}

void Getk_MaskEffectAll(IPropertyStore* pStore, DWORD _dwMask, DWORD _dwEffects, REFPROPERTYKEY key)
{
if (SUCCEEDED(pStore->GetValue(key, &propvar)))
{
UIPropertyToUInt32(key, propvar, &uValue);
if ((UI_FONTPROPERTIES)uValue != UI_FONTPROPERTIES_NOTAVAILABLE)
{
dwMask |= _dwMask;
dwEffects |= ((UI_FONTPROPERTIES)uValue == UI_FONTPROPERTIES_SET) ? _dwEffects : 0;
}
}
}