为什么 Google 的 TrueTime API 难以复制? [英] Why is Google's TrueTime API hard to duplicate?

问题描述

我不知道为什么媒体普遍说 Google 的 TrueTime API 难以复制(Wired、Slashdot 等).

I'm not sure why the press in general says that Google's TrueTime API is hard to replicate (Wired, Slashdot, etc).

我可以理解获得 Google 实现的低错误间隔是多么困难，但我不认为 API 本身会非常困难.

I can understand how it would be a tough thing to get the low error intervals that Google is achieving, but I don't see how the API itself would be very difficult.

例如，我制作了一个 hacked together 版本.这是间隔.

For example, I whipped up a hacked together version. Here's the interval.

    typedef struct TT_interval {
            struct timeval earliest;
            struct timeval latest;
    } TT_interval;

这是 now 函数.

    int TT_now(TT_interval* interval)
    {
        struct ntptimeval tv;
        struct timeval delta;

        struct timeval* earliest_p = &(interval->earliest);
        struct timeval* latest_p = &(interval->latest);
        struct timeval* now_p = &(tv.time);
        struct timeval* delta_p = δ

        timerclear(&delta);
        timerclear(&interval->earliest);
        timerclear(&interval->latest);

        if(ntp_gettime(&tv) == 0) {
            tv.maxerror = tv.maxerror > 0 ? tv.maxerror : -(tv.maxerror);

            delta.tv_sec = delta.tv_sec + (tv.maxerror / 1000);
            delta.tv_usec = delta.tv_usec + ((tv.maxerror % 1000) * 1000);

            if(delta.tv_usec > 1000000) {
                delta.tv_usec -= 1000000;
                delta.tv_sec++;
            }

            timeradd(now_p, delta_p, latest_p);
            timersub(now_p, delta_p, earliest_p);
        } else {
            printf("error on ntp_gettime. %s
", strerror(errno));
            return ERROR;
        }

        return SUCCESS;
    }

最后，这里是 before 和 after 函数(它们是 now 函数的包装器，可以使用一些 DRY 重构).

Finally, here's the before and after functions (which are wrappers around the now function and could use a bit of DRY refactoring).

    int TT_before(TT_interval* interval, bool* success)
    {
        struct timeval* latest_p;
        struct timeval* earliest_p;
        TT_interval now;

        if(TT_now(&now) != SUCCESS) {
            return ERROR;
        }

        latest_p = &(interval->latest);
        earliest_p = &(now.earliest);

        if(timercmp(latest_p, earliest_p, <) != 0) {
            *success = true;
            return SUCCESS;
        } else {
            *success = false;
            return SUCCESS;
        }

        return ERROR;
    }

   int TT_after(TT_interval* interval, bool* success)
    {
        struct timeval* latest_p;
        struct timeval* earliest_p;
        TT_interval now;

        if(TT_now(&now) != SUCCESS) {
            return ERROR;
        }

        earliest_p = &(interval->latest);
        latest_p = &(now.earliest);

        if(timercmp(latest_p, earliest_p, <) != 0) {
            *success = true;
            return SUCCESS;
        } else {
            *success = false;
            return SUCCESS;
        }

        return ERROR;
    }

我似乎收到了大约 5,000us 到 350,000us 的间隔错误(使用公共 NTPd).这与 Google 的数字相去甚远，但您需要从某个地方开始.

I seem to be getting interval errors of around 5,000us to 350,000us (using a public NTPd). This is a far cry from Google's numbers, but you need to start somewhere.

除了性能不佳之外，这种设计是否存在重大缺陷会阻止像 Spanner 这样的东西构建在上面?

Other than lackluster performance, is there a major flaw in this design that would prevent something like Spanner from being built on top?

推荐答案

实现 TrueTime API 的挑战在于您必须提供的保证.即，绝对时间必须永远在系统中任何服务器上的 TrueTime 间隔之外.如果发生这种情况，那么事件的绝对顺序就会丢失，就像 Spanner 的大多数保证一样.

The challenge in implementing a TrueTime API lies in the guarantees you must provide. Namely, the absolute time must never be outside the TrueTime interval on any server in the system. If this can happen, then absolute ordering of events is lost, as are most of the guarantees of Spanner.

Spanner 论文 通过多种手段(第 3 节)实现这一目标:

The Spanner paper achieves this by a combination of means (section 3):

1. 具有不同来源(GPS、原子钟)的多个时间服务器，包括来自其他数据中心的时间服务器.
2. Marzullo 的算法检测说谎者并将各种可信时间源多路复用到本地机器时钟的更新中.
3. 假设跨服务器的时钟漂移为 200us/s，应用于时钟同步之间.
4. 从系统中踢出的机器表现出测量的本地时钟漂移 > 阈值(阈值 <<200us/s，必要时).

现在，您可以用更简单的方法实现这一点——NTP 和假设的 10 分钟错误间隔就可以了.但正如问题中所指出的，这对性能有影响.读写事务 (4.2.1) 必须在提交时等待，预期等待时间为 2*errorAverage - 在本例中为 20 分钟.类似地，现在"时间(而不是过去时间)的只读事务(4.2.2)必须等待安全时间提前到足够远；在这个例子中至少 10 分钟.因此，要拥有一个高性能系统，您需要尽可能减少错误间隔， 不会失去保证，而这正是复杂性产生的地方.

Now, you can achieve this with simpler means - NTP and an assumed error interval of 10 minutes would trivially do. But as noted in the question, there are performance implications to this. Read-write transactions (4.2.1) must wait on commit, with an expected wait time of 2*errorAverage - 20 minutes in this example. Similarly, read-only transactions (4.2.2) at time "now" - rather than a time in the past - must wait for safetime to advance far enough; at least 10 minutes in this example. So to have a high performance system, you need to minimize the error intervals as far as possible, without losing your guarantees, which is where the complexity arises.

我不确定 ntp_adjtime 在您的系统中是如何被调用的 - 它可能已经使用多个不受信任和不相关的时间源进行设置，在这种情况下，您已经完成了大部分工作.如果您还可以确保保证 maxerror 值比系统可能的时钟漂移更快，那么您应该很高兴.Spanner的大部分性能，没有你自己的个人原子钟:)

I'm not sure how ntp_adjtime is being called in your system - it's possible it's already being set using multiple untrusted and uncorrelated time sources, in which case you're most of the way there already. If you can also ensure that the maxerror value is guaranteed to be advancing faster than the possible clock drift of your system, you should be good to go. Most of the performance of Spanner, without your own personal atomic clock :).

这篇关于为什么 Google 的 TrueTime API 难以复制?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！