DAG eksplisit bukan Vektor Jam untuk sinkronisasi

13

Saya sudah mulai melihat pendekatan untuk sinkronisasi data di antara seperangkat sejawat. Rekan sebaya harus dapat bekerja dengan cara yang terputus dan kemudian menyinkronkan bersama untuk menggabungkan perubahan lokal mereka.

Rekan seharusnya dapat menggabungkan pembaruan lokal dengan "gabungan tiga arah" . Jadi, pada sinkronisasi, teman sebaya harus tahu fakta mana yang lebih baru, tetapi jika tidak ada aturan ketat, mereka harus bisa menggabungkan fakta berdasarkan akar yang sama.

Ketika rekan independen membuat perubahan, mereka dapat "mencap waktu" mereka dengan "jam". Saya menggunakan istilah "jam" dan "cap waktu" tetapi saya tidak bermaksud jam waktu dinding. Maksud saya semacam urutan parsial peristiwa yang membuat kausalitas jelas. Ini adalah hubungan "terjadi sebelumnya" di antara peristiwa yang membentuk grafik asiklik terarah (DAG).

Sepertinya cara "biasa" untuk melakukan pembuatan pemesanan parsial ini adalah dengan menggunakan jam vektor . Namun, ini bisa menjadi sangat besar. Perkembangan yang lebih baru seperti jam pohon interval menyediakan penyimpanan perangko waktu yang lebih kompak.

Yang saya sama sekali tidak jelas tentang mengapa protokol sinkronisasi tampaknya tidak "hanya" menyimpan DAG secara eksplisit. (Atau apakah mereka?)

Peer dapat secara mandiri membuat cap waktu dengan membuat UUID secara acak (atau dengan cara lain, seperti <peer-name> + <local-monotonically-increasing-counter>). Pemesanan cap waktu ini sepenuhnya jelas untuk rekan itu.

Saat 2 rekan saling menyinkronkan, mereka dapat menyetujui cap waktu baru. Sekali lagi, pemesanan cap waktu ini jelas bagi kedua rekan.

Sekarang ada persyaratan untuk melewati yang terjadi sebelum DAG antara rekan-rekan, tetapi persyaratan penyimpanan dan bandwidth ini kecil. Poin waktu adalah titik grafik. Karena itu mereka memiliki 1 atau 2 tepi masuk (1 untuk acara pada klien dan 2 untuk sinkronisasi antara klien). Ini dibatasi dan tidak tergantung pada jumlah rekan di jaringan.

Untuk menggunakan titik waktu individual, Anda memerlukan grafik titik waktu yang mengarah ke ini. Namun, sejauh yang saya bisa lihat, setiap rekan yang dapat mengetahui titik waktu (telah menghasilkan sendiri, atau menghasilkannya dengan rekan lain, atau telah diberitahu oleh rekan lain saat menyinkronkannya) juga telah memiliki kesempatan untuk mengetahui tentang sejarah yang mengarah ke titik waktu itu. Saya pikir mungkin ada bukti induktif untuk ini.

Mengingat bahwa menyimpan dan menyinkronkan DAG secara eksplisit tampak sederhana: apakah ini digunakan dalam praktik? Jika tidak, mengapa jam vektor lebih disukai?

Catatan

Peer to peer

Saya lebih suka solusi peer to peer daripada solusi server klien.

Topologi akhir yang mungkin akan banyak klien terhubung ke kelompok server yang jauh lebih kecil yang mereplikasi di antara mereka sendiri. Namun, alangkah baiknya memiliki solusi umum yang mendukung topologi khusus ini daripada solusi yang memerlukan topologi spesifik ini.

synchronization Benjohn
sumber
Saya mungkin salah memahami apa yang Anda katakan, tetapi tidak jelas bagaimana grafik semua peristiwa yang mengarah ke negara bisa lebih kecil daripada vektor penghitung. Kecuali Anda berada dalam sistem yang memiliki jumlah node yang sangat besar dan jumlah perubahan yang sangat kecil.
kdgregory
Terima kasih @kdgregory - poin bagus. Untuk dapat menghitung penggabungan tiga arah di masa mendatang, Anda harus mengetahui masa lalu (dan dapat menentukan DAG dari poin waktu sebelumnya). Jadi, jika Anda menyimpan titik waktu lalu maka secara eksplisit menyimpan DAG lebih murah. Jika Anda tidak menyimpan titik waktu lalu maka Anda tidak dapat menghitung gabungan tiga cara data. - Saya ingin tahu apakah persyaratan tiga arah ini mungkin? Jika Anda tidak ingin 3 arah, mungkin jam vektor lebih baik daripada DAG eksplisit?
Benjohn
Saya rasa ini bisa menjadi titik penting @kdgregory, jadi saya telah menambahkan sedikit tentang itu ke pertanyaan. Saya mengasumsikan dimungkinkan untuk melakukan penggabungan 3 arah, yang juga menyiratkan bahwa semua sejarah diketahui. Jika semua sejarah diketahui maka (saya rasa) DAG eksplisit lebih murah. Jika sejarah dipotong, maka jam vektor mungkin merupakan pendekatan yang lebih murah.
Benjohn
1
Ya, pemahaman saya tentang jam vektor adalah bahwa itu dimaksudkan hanya untuk menerima / menolak keputusan: "simpul C sedang mencoba memperbarui bagian data ini, tetapi tidak mengetahui pembaruan simpul B".
kdgregory

Jawaban:

1

Sejauh yang saya tahu, sistem kontrol versi seperti Git dan Mercurial menggunakan pendekatan DAG daripada jam vektor.

bikeman868
sumber
1
Tanpa penjelasan, jawaban ini dapat menjadi sia-sia jika ada orang yang memposting pendapat yang berbeda. Sebagai contoh, jika seseorang memposting klaim seperti "Sistem kontrol propersi seperti Git dan Mercurial menggunakan jam vektor daripada pendekatan DAG" , bagaimana jawaban ini membantu pembaca untuk memilih dua pendapat yang berlawanan? Pertimbangkan untuk mengeditnya dalam bentuk yang lebih baik, untuk memenuhi standar kualitas Cara Menjawab .
nyamuk
2
Cara saya memahami pertanyaan itu, mereka bertanya apakah ada contoh dunia nyata di mana DAG digunakan daripada jam vektor.
bikeman868
1
Baik Git dan Mecurial adalah contoh dunia nyata dari sinkronisasi perubahan teman ke teman menggunakan DAG, dan saya berharap benjohn akan menemukan jawaban saya bermanfaat walaupun Anda memilihnya.
bikeman868
Hai @ bikeman868 Saya telah memilih Anda untuk jaring 0 (maaf). Jawaban Anda sangat membantu, bahkan jika dibungkus dengan ketidakpastian! Meskipun referensi atau jawaban resmi selalu bagus, pertukaran tumpukan tidak mengharuskan itu! Saran Anda masuk akal dengan poin dalam komentar pada pertanyaan. Sepertinya ketika Anda ingin menyimpan sejarah dan dapat menggabungkan sejarah, maka DAG sesuai. Ketika Anda tidak menyimpan riwayat dan ingin sinkronisasi dan konsensus pada keadaan saat ini, maka jam vektor adalah yang Anda butuhkan.
Benjohn
1

Lihatlah masalah konsensus . Bergantung pada persyaratan tugas Anda (berapa banyak data yang Anda miliki, berapa banyak node yang disinkronkan, seberapa sering, dll.) Solusi yang ada untuk masalah itu (seperti "Rakit") mungkin cocok untuk kasus Anda.

Pendekatan lain (mungkin tangensial) untuk masalah ini adalah merancang CRDT .

battlmonstr
sumber
Braid HTTP sedang mencoba membuat protokol sinkronisasi status berbasis CRDT melalui penambahan HTTP. Mereka memiliki visualisasi yang hebat dari Time DAG dan Space DAG, dan bagaimana kedua konsep ini saling berhubungan untuk sampai pada konsistensi akhirnya.
Duane J