Pembangkitan nomor urut terdistribusi?

Saya biasanya telah menerapkan pembuatan nomor urut menggunakan urutan database di masa lalu.

misalnya Menggunakan Postgres SERIAL ketik http://www.neilconway.org/docs/sequences/

Saya penasaran bagaimana cara menghasilkan nomor urut untuk sistem terdistribusi besar di mana tidak ada database. Apakah ada yang punya pengalaman atau saran tentang praktik terbaik untuk mencapai pembuatan nomor urut dengan cara yang aman untuk banyak klien?

Oke, ini pertanyaan yang sangat lama, yang pertama kali saya lihat sekarang.

Anda harus membedakan antara nomor urut dan ID unik yang (opsional) dapat diurutkan secara longgar berdasarkan kriteria tertentu (biasanya waktu pembuatan). Nomor urut yang benar menyiratkan pengetahuan tentang apa yang telah dilakukan semua pekerja lain, dan karena itu memerlukan status bersama. Tidak ada cara mudah untuk melakukan ini dengan cara yang terdistribusi dan berskala tinggi. Anda dapat melihat hal-hal seperti siaran jaringan, rentang berjendela untuk setiap pekerja, dan tabel hash terdistribusi untuk ID pekerja unik , tetapi ini membutuhkan banyak pekerjaan.

ID unik adalah masalah lain, ada beberapa cara bagus untuk menghasilkan ID unik dengan cara yang terdesentralisasi:

a) Anda dapat menggunakan layanan jaringan ID Snowflake Twitter . Kepingan salju adalah:

• Layanan jaringan, yaitu Anda membuat panggilan jaringan untuk mendapatkan ID unik;
• yang menghasilkan 64 bit ID unik yang diurutkan berdasarkan waktu pembuatan;
• dan layanan sangat skalabel dan (berpotensi) sangat tersedia; setiap instans dapat menghasilkan ribuan ID per detik, dan Anda dapat menjalankan beberapa instans di LAN / WAN;
• ditulis dalam Scala, berjalan di JVM.

b) Anda bisa membuat ID unik pada klien itu sendiri, menggunakan pendekatan yang diturunkan dari bagaimana UUID dan ID Snowflake dibuat. Ada beberapa opsi, tetapi sesuatu di sepanjang baris:

• 40 bit paling signifikan atau lebih: Stempel waktu; waktu pembuatan ID. (Kami menggunakan bit paling signifikan untuk stempel waktu agar ID dapat diurutkan berdasarkan waktu pembuatan.)

• 14 bit berikutnya atau lebih: Penghitung per generator, yang setiap generator bertambah satu untuk setiap ID baru yang dihasilkan. Ini memastikan bahwa ID yang dibuat pada saat yang sama (stempel waktu yang sama) tidak tumpang tindih.

• 10 atau lebih bit terakhir: Nilai unik untuk setiap generator. Dengan menggunakan ini, kita tidak perlu melakukan sinkronisasi apa pun antar generator (yang sangat sulit), karena semua generator menghasilkan ID yang tidak tumpang tindih karena nilai ini.

c) Anda dapat membuat ID pada klien, hanya menggunakan stempel waktu dan nilai acak. Hal ini menghindari kebutuhan untuk mengetahui semua generator, dan memberikan nilai unik pada setiap generator. Di sisi lain, ID semacam itu tidak dijamin unik secara global, mereka sangat mungkin unik. (Untuk bertabrakan, satu atau lebih generator harus membuat nilai acak yang sama pada saat yang sama.) Sesuatu di sepanjang baris:

• 32 bit paling signifikan: Stempel waktu, waktu pembuatan ID.
• 32 bit paling tidak signifikan: 32 bit keacakan, dihasilkan lagi untuk setiap ID.

d) Jalan keluar yang mudah, gunakan UUIDs / GUIDs .

Sekarang ada lebih banyak opsi.

Meskipun pertanyaan ini "lama", saya sampai di sini, jadi menurut saya mungkin berguna untuk meninggalkan opsi yang saya ketahui (sejauh ini):

• Anda bisa mencoba Hazelcast . Dalam rilis 1.9 itu termasuk implementasi Terdistribusi java.util.concurrent.AtomicLong
• Anda juga dapat menggunakan Zookeeper . Ini menyediakan metode untuk membuat node urutan (ditambahkan ke nama znode, meskipun saya lebih suka menggunakan nomor versi node). Berhati-hatilah dengan yang ini: jika Anda tidak ingin nomor yang terlewat dalam urutan Anda, itu mungkin bukan yang Anda inginkan.

Bersulang

Anda dapat memiliki setiap node memiliki ID unik (yang mungkin Anda miliki) dan kemudian menambahkannya ke nomor urut.

Misalnya, node 1 menghasilkan urutan 001-00001 001-00002 001-00003 dll. Dan node 5 menghasilkan 005-00001 005-00002

Unik :-)

Bergantian jika Anda menginginkan semacam sistem terpusat, Anda dapat mempertimbangkan agar server urutan Anda memberikan blok. Ini mengurangi biaya overhead secara signifikan. Misalnya, alih-alih meminta ID baru dari server pusat untuk setiap ID yang harus ditetapkan, Anda meminta ID dalam blok 10.000 dari server pusat dan kemudian hanya perlu melakukan permintaan jaringan lain saat kehabisan.

Itu bisa dilakukan dengan Redisson . Ini mengimplementasikan versi terdistribusi dan skalabel AtomicLong. Berikut contohnya:

Config config = new Config();
config.addAddress("some.server.com:8291");

Redisson redisson = Redisson.create(config);
RAtomicLong atomicLong = redisson.getAtomicLong("anyAtomicLong");
atomicLong.incrementAndGet();

Jika itu benar-benar harus berurutan secara global, dan tidak hanya unik, maka saya akan mempertimbangkan untuk membuat satu layanan sederhana untuk mengeluarkan nomor-nomor ini.

Sistem terdistribusi bergantung pada banyak layanan kecil yang berinteraksi, dan untuk jenis tugas sederhana ini, apakah Anda benar-benar membutuhkan atau apakah Anda benar-benar mendapat manfaat dari solusi terdistribusi yang kompleks lainnya?

Ada beberapa strategi; tetapi tidak ada yang saya tahu dapat benar-benar didistribusikan dan memberikan urutan yang sebenarnya.

1. memiliki generator nomor pusat. tidak harus database yang besar. memcachedmemiliki penghitung atom yang cepat, dalam sebagian besar kasus, ini cukup cepat untuk seluruh cluster Anda.
2. pisahkan rentang integer untuk setiap node (seperti jawaban Steven Schlanskter )
3. gunakan nomor acak atau UUID
4. menggunakan beberapa bagian data, bersama dengan ID node, dan hash semuanya (atau hmac itu)

Secara pribadi, saya akan condong ke UUID, atau memcache jika saya ingin memiliki ruang yang sebagian besar bersebelahan.

Mengapa tidak menggunakan generator UUID (thread safe)?

Saya mungkin harus memperluas ini.

UUID dijamin unik secara global (jika Anda menghindari yang didasarkan pada nomor acak, di mana keunikan sangat mungkin terjadi).

Persyaratan "terdistribusi" Anda terpenuhi, terlepas dari berapa banyak generator UUID yang Anda gunakan, oleh keunikan global setiap UUID.

Persyaratan "thread safe" Anda dapat dipenuhi dengan memilih generator UUID "thread safe".

Persyaratan "nomor urut" Anda diasumsikan dipenuhi oleh keunikan global yang dijamin dari setiap UUID.

Perhatikan bahwa banyak implementasi nomor urut database (misalnya Oracle) tidak menjamin peningkatan secara monoton, atau (bahkan) peningkatan nomor urut (pada setiap basis "koneksi"). Ini karena kumpulan nomor urut yang berurutan dialokasikan dalam blok "cache" pada setiap koneksi dasar. Ini menjamin keunikan global dan mempertahankan kecepatan yang memadai. Tetapi nomor urut yang benar-benar dialokasikan (dari waktu ke waktu) dapat campur aduk ketika ada yang dialokasikan oleh banyak koneksi!

Pembuatan ID terdistribusi dapat diarsipkan dengan Redis dan Lua. Implementasinya tersedia di Github . Ini menghasilkan id unik terdistribusi dan k-sortable.

Saya tahu ini adalah pertanyaan lama tetapi kami juga menghadapi kebutuhan yang sama dan tidak dapat menemukan solusi yang memenuhi kebutuhan kami. Persyaratan kami adalah mendapatkan urutan unik (0,1,2,3 ... n) id dan karenanya kepingan salju tidak membantu. Kami membuat sistem kami sendiri untuk menghasilkan id menggunakan Redis. Redis adalah single threaded maka mekanisme daftar / antriannya akan selalu memberi kita 1 pop pada satu waktu.

Yang kami lakukan adalah, Kami membuat buffer dari id, Awalnya, antrian akan memiliki 0 hingga 20 id yang siap dikirim saat diminta. Beberapa klien dapat meminta id dan redis akan memunculkan 1 id sekaligus, Setelah setiap pop dari kiri, kami memasukkan BUFFER + currentId ke kanan, Yang membuat daftar buffer tetap berjalan. Implementasinya di sini

Saya telah menulis layanan sederhana yang dapat menghasilkan nomor panjang 64 bit semi-unik non-sekuensial. Ini dapat diterapkan pada banyak mesin untuk redundansi dan skalabilitas. Ini menggunakan ZeroMQ untuk perpesanan. Untuk informasi lebih lanjut tentang cara kerjanya, lihat halaman github: zUID

Menggunakan database, Anda dapat mencapai 1.000+ kenaikan per detik dengan satu inti. Sangat mudah. Anda dapat menggunakan database-nya sendiri sebagai backend untuk menghasilkan nomor tersebut (sebagaimana seharusnya merupakan agregatnya sendiri, dalam istilah DDD).

Saya memiliki masalah yang tampaknya serupa. Saya memiliki beberapa partisi dan saya ingin mendapatkan counter offset untuk masing-masing partisi. Saya menerapkan sesuatu seperti ini:

CREATE DATABASE example;
USE example;
CREATE TABLE offsets (partition INTEGER, offset LONG, PRIMARY KEY (partition));
INSERT offsets VALUES (1,0);

Kemudian dieksekusi pernyataan berikut:

SELECT @offset := offset from offsets WHERE partition=1 FOR UPDATE;
UPDATE offsets set offset=@offset+1 WHERE partition=1;

Jika aplikasi Anda memungkinkan Anda, Anda dapat mengalokasikan satu blok sekaligus (itu kasus saya).

SELECT @offset := offset from offsets WHERE partition=1 FOR UPDATE;
UPDATE offsets set offset=@offset+100 WHERE partition=1;

Jika Anda membutuhkan throughput lebih lanjut dan tidak dapat mengalokasikan offset terlebih dahulu, Anda dapat mengimplementasikan layanan Anda sendiri menggunakan Flink untuk pemrosesan waktu nyata. Saya bisa mendapatkan sekitar 100 ribu peningkatan per partisi.

Semoga membantu!

Masalahnya mirip dengan: Di dunia iscsi, di mana setiap lun / volume harus dapat diidentifikasi secara unik oleh pemrakarsa yang berjalan di sisi klien. Standar iscsi mengatakan bahwa beberapa bit pertama harus mewakili penyedia Penyimpanan / informasi pabrikan, dan sisanya meningkat secara monoton.

Demikian pula, seseorang dapat menggunakan bit awal dalam sistem node terdistribusi untuk mewakili nodeID dan sisanya dapat meningkat secara monoton.

Salah satu solusi yang layak adalah dengan menggunakan generasi berbasis waktu lama. Ini dapat dilakukan dengan dukungan dari database terdistribusi.