Warum ist die TrueTime-API von Google schwer zu duplizieren?

Question

Ich bin nicht sicher, warum die Presse im Allgemeinen sagt, dass Googles TrueTime API schwer zu replizieren ist (Wired, Slashdot, etc).

Ich kann verstehen, wie es schwierig wäre, die niedrigen Fehlerintervalle zu erreichen, die Google erreicht, aber ich sehe nicht, wie die API selbst sehr schwierig sein würde.

Zum Beispiel habe ich eine gehackte Version aufgepeitscht. Hier ist das Intervall.

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

Hier ist die Funktion jetzt.

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\n", strerror(errno)); 
      return ERROR; 
     } 

     return SUCCESS; 
    } 

Schließlich ist hier die vor und nach Funktionen (die Wrapper um die jetzt Funktion sind und ein wenig DRY Refactoring verwenden könnte).

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; 
    } 

Ich scheine Intervallfehler von ca. 5000us bis 350,000us (mit einem öffentlichen NTPd) zu bekommen. Das ist weit entfernt von den Google-Zahlen, aber Sie müssen irgendwo anfangen.

Gibt es, abgesehen von der glanzlosen Leistung, einen großen Fehler in diesem Design, der verhindern würde, dass etwas wie Spanner an der Spitze gebaut wird?

Answer 1

Die Herausforderung bei der Implementierung einer TrueTime-API liegt in den Garantien, die Sie bereitstellen müssen. Die absolute Zeit muss nämlich niemals außerhalb des TrueTime-Intervalls auf einem beliebigen Server im System sein. Wenn das passieren kann, dann ist die absolute Reihenfolge der Ereignisse verloren, wie auch die meisten Garantien von Spanner.

Die Spanner paper erreicht dies durch eine Kombination von Mitteln (Abschnitt 3):

1. mehr Zeitserver, mit unterschiedlichen Quellen (GPS, Atomuhr), einschließlich der Zeit-Server von anderen Datenzentren.
2. Marzullos Algorithmus zum Erkennen von Lügnern und Multiplexen der verschiedenen vertrauenswürdigen Zeitquellen in eine Aktualisierung der lokalen Maschinentaktung.
3. Eine angenommene Taktdrift von 200us/s bei Spanservers, die zwischen Taktsynchronisierungen angewendet wird.
4. Treten Maschinen aus dem System, die gemessenen lokalen Uhr Drift> Schwelle (Schwelle < < von Notwendigkeit).

Nun Sie können erreichen dies mit einfacheren Mitteln - NTP und einem angenommenen Fehlerintervall von 10 Minuten trivialer Weise tun würde. Aber wie in der Frage erwähnt, gibt es Auswirkungen auf die Leistung. Lese-Schreib-Transaktionen (4.2.1) müssen beim Commit warten, mit einer erwarteten Wartezeit von 2 * errorAverage - 20 Minuten in diesem Beispiel. In ähnlicher Weise müssen Read-Only-Transaktionen (4.2.2) zum Zeitpunkt "jetzt" - statt in der Vergangenheit - warten, bis die Sicherheitszeit weit genug fortgeschritten ist; mindestens 10 Minuten in diesem Beispiel. Um ein Hochleistungssystem zu haben, müssen Sie die Fehlerintervalle so weit wie möglich minimieren, indem Sie Ihre Garantien verlieren, wo die Komplexität entsteht.

Ich bin mir nicht sicher, wie ntp_adjtime in Ihrem System aufgerufen wird - es ist möglich, dass es bereits mit mehreren nicht vertrauenswürdigen und unkorrelierten Zeitquellen eingerichtet wird. In diesem Fall sind Sie bereits auf dem besten Weg dorthin.Wenn Sie auch sicherstellen können, dass der maximale Fehlerwert schneller als die mögliche Taktabweichung Ihres Systems vorrückt, sollten Sie gut gehen. Die meiste Leistung von Spanner, ohne eigene Atomuhr :).