UUID 及其实现 3

2021-03-07

这一篇来讲 v3 和 v5 的实现。

这两个实现要求使用方提供：

  • 一个称为 namespace 的 UUID
  • 一个叫 name 的数据块（不限于字符串）

然后利用一个 hash 算法算得结果，作为目标 UUID 的基础数据（还需要额外设置 variant 和 version）。

即，对于 v3/v5 的实现，本质上是

1
2
3
uuid = hash(namespace, name)
set_variant(uuid)
set_version(uuid, ver)

v3 和 v5 区别在于，前者是用 MD5，后者使用 SHA-1。

并且可以发现，对于相同的 namespace 和 name，生成的结果 UUID 是一样的。

这个就是 v3/v5 版本的特性。

借用 RFC 的描述就是：

  • The UUIDs generated at different times from the same name in the same namespace MUST be equal.
  • The UUIDs generated from two different names in the same namespace should be different (with very high probability).
  • The UUIDs generated from the same name in two different namespaces should be different with (very high probability).
  • If two UUIDs that were generated from names are equal, then they were generated from the same name in the same namespace (with very high probability).

所以 v3/v5 的版本又被叫做 name-based implementation

Read More

UUID 及其实现 2

2021-03-06

上篇介绍了 UUID 的格式和 v4 的实现，这篇讲 v1 & v2 的实现。

v2 版本是 v1 上衍生出来的，而 v1 因为涉及到时间戳，又称为 time-based implementation。

实现 UUID v1

v1 除了常规的 variant 和 version 部份外，还涉及三个部分：

  • timestamp，需要 60-bit 通常用 64-bit 容纳；非寻常的 Unix Timestamp
  • clock sequence，需要 14-bit，通常用 16-bit 存储
  • node identifier，48-bit 和设备相关

下面逐一解释这三个部分。

0x0. UUID Timestamp

和常见的 Unix 时间戳不同，UUID 时间戳记录的是，自 1582-10-15 00:00:00 至今的 100-ns 数。

1582年10月15日的零点是格里高力历开始的时间，这个时间也是 UUID Epoch Time。

UUID 时间戳的分辨率（resolution）是 100 纳秒，即每 100ns 为一个 tick。

现代编程语言都可以获取 unix 时间戳，因此可以先获取 unix 时间戳，然后加上两个 epoch time 的差值；这个差值是个定值，等于 122192928000000000。

注意：获取时间戳时需要注意系统或者语言库能提供的分辨率。

0x1. Clock Sequence

因为引入了时间戳，所以存在可能由于时钟回拨、闰秒，甚至因为系统提供的时钟分辨率不够导致使用了重复的时间戳。

另外 node identifier 也有可能被改变。

所以为了尽可能保证 UUID 的唯一性，引入了 clock sequence。

注：RFC 4122 没有规定 UUID v1 必须要使用 steady clock，所以使用能够被回拨的 system clock 也是允许的。另外，即使使用了 steady clock，机器在两次启动之间也可能调整了硬件时间，一样可能会导致回拨。

Clock sequence 一开始会被初始化为一个随机值；之后如果某次获取 UUID 时间戳发现 <= 上一次的时间戳，就会自增 clock sequence。

clock sequence 通常会设置为一个无符号数，以确保溢出 wrap-around 的行为是确定的。

Read More

UUID 及其实现 1

2021-02-25

数据格式

UUID 是 Universally Unique IDentifier 的缩写，本质上是一个 128-bit (16-byte) 长的标识符，可以用32个16进制数表示，并且通常以如下形式展示：

1
2
3
4
// 每组字符长度分别是 8-4-4-4-12
XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX
              ^    ^
              M    N

上面 M 和 N 出的数字分别表示了这个 UUID 使用的 version 和 variant；具体下面展开。

HEX 字符存在大小写，按照 RFC 4122 要求，UUID 输出时 'a'-'f' 应为小写；但是在作为输入时大小写不敏感。

因为 UUID 的生成不需要中心管理节点 (central authority)，是天然分布式；也正因如此，没有一个验证 UUID 是否有效的方法，最多只能验证是否满足数据格式要求。

0x0 Variant

上面 N 处的 HEX 的 3-bit MSB 指明了 UUID 使用的 variant。

Variant 决定了当前 UUID 其他的 bits 如何 interpret。这里的 bits 也包含 M 处指示 version 的那部分。

语义上讲，variant 更适合被叫做 type

Read More

写了一个右键菜单清理工具以及一些吐槽

2021-02-09

注：这是一篇没有什么营养的吐槽文

清理工具

自从一年多前删了一批程序发现右键上下文菜单留下了一批钉子户之后就想着哪天有时间写个工具清理一下。

但是因为比较懒就一直拖到了现在；并且在某天脑袋被门撞了之后想着要不顺带做一个 GUI 吧…

因为核心需要操作注册表，免不了一顿 Win32 API 调用，所以自然用 C++ 比较方便，但是用 C++ 写 GUI 吧，稍有经验的人都知道这是一个蛋疼的事情。

还好我还算比较有毅力：

  1. 用了一个晚上基于 KBase 封装的基础工具写完了核心逻辑
  2. 在网上找了一个比较轻量的 nana-gui 糊了一个周末的 UI

最后算是把成品给做了出来，也确实达成了我的目的，清掉了残留的菜单项。

完整工程链接：the-stupid-context-menu-cleaner

GUI? Thanks, but NO

这部分又名 我为什么不喜欢写 UI。

说起来我的编程生涯是从 GUI 程序开始的。

初中的时候各种折腾 VB6，一直想做个好看、高大上的应用；经常为了追求实现一些炫酷的效果大规模使用当时口口相传的秘术：子类化（sub-classing）。

说是秘术无非是 VB6 本身不支持这样做，强行通过 Win32 API 接管被内部封装的 wndproc（窗口的消息处理过程）；记得很容易因为一个不小心连带 IDE 都自动退出。

并且那会儿也没有所谓的 layout management，全靠可视化界面编辑器一个一个拖控件，然后通过手写 on_resize 事件根据窗口大小来调整控件的布局。

即使到了高中开始学 C++ (with classes)，也是想着怎么在 MFC 里用那些蹩脚的基础控件和机制把应用做得漂亮点。

直到升入大学并在 C++ 和 system programming 这条歪路上越走越远，GUI 编程对我的吸引开始日益减少；直至今天我对这部分事情完全提不起兴趣。

导致这个变化的原因粗想了一下大概有下面几个。

Read More

Reverse Range Based For Loops

2020-12-22

实现

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
template<typename T>
class ReverseIterable {
public:
    template<typename U>
    explicit ReverseIterable(U&& u)
        : iterable_(std::forward<U>(u))
    {}

    ~ReverseIterable() = default;

    ReverseIterable(const ReverseIterable&) = delete;

    ReverseIterable& operator=(const ReverseIterable&) = delete;

    auto begin() noexcept
    {
        return std::rbegin(iterable_);
    }

    auto end() noexcept
    {
        return std::rend(iterable_);
    }

private:
    T iterable_;
};

template<typename T>
auto MakeReverseIterable(T&& iterable)
{
    // 1) if `iterable` is lvalue, then T is deduced as T&
    // 2) if `iterable` is rvalue, then T is deduced as T
    return ReverseIterable<T>(std::forward<T>(iterable));
}

Read More

禁用某些构造函数

2020-10-02

有时候我们希望用更明确的自定义类型取代一些 primitives，依靠类型系统来减少一些人为错误：

1
2
3
4
5
6
7
void Run(WithMultithreading mt, WithAdvancedMode advanced);

// Both of them work like bool
auto mt = WithMultithreading(true);
auto mode = WithAdvancedMode(false);

Run(mt, mode);

类型 WithMultithraeding 和 WithAdvancedMode 用起来很像 bool，但是他们是两个不同的类型，混用会出现编译错误。

1
Run(mode, mt);  // compile failure; type mis-match

不管我们使用 typedef 还是 using，都只能定义 bool 的类型别名；在类型系统看来他们还是一回事。

Read More

Redigo 源码学习：Pipeline

2020-09-20

如何使用 pipeline

先来回顾一下如何在 redigo 中使用 pipeline

1
2
3
4
5
6
7
8
c := pool.Get()
defer c.Close()

c.Send("SET", "foo", "bar")
c.Send("GET", "foo")
c.Flush()
c.Receive() // reply from SET
v, err = c.Receive() // reply from GET

核心是 Send — Flush — Receive 三个步骤。

Read More