Struktur data snapshottable yang baik untuk indeks dalam memori

Saya merancang objek database dalam-memori untuk kasus penggunaan yang sangat spesifik. Ini adalah penulis tunggal, tetapi harus mendukung pembacaan berbarengan yang efisien. Bacaan harus diisolasi. Tidak ada bahasa permintaan, database hanya mendukung:

dapatkan objek / -s dengan atribut / set atribut (mungkin ada dukungan untuk ekspresi, misalnya x.count < 5)
dapatkan atribut objek

Kueri adalah skrip imperatif yang terdiri dari angka arbitrer dari operasi di atas. Ukuran data akan menjadi << memori, jadi semua objek dan indeks pada sebagian besar atribut harus sesuai dengan nyaman tanpa bertukar.

Yang saya butuhkan adalah struktur data untuk indeks atribut objek, yang dapat berupa O (n) pada tulis, tidak mendukung konkurensi tulis, tetapi harus mendukung idealnya O (1) foto (mungkin salin saat menulis) dan akses O (logN). Idealnya itu akan memungkinkan konkurensi tinggi pada bacaan dengan pembagian struktural maksimal antara versi.

Saya sedang melihat CTries , BST bersamaan dan Pohon Rentang bersamaan tapi saya tidak yakin apakah saya benar-benar melihat ke arah yang benar di sini. Struktur di atas memberi banyak perhatian pada kompleksitas sisipan yang tidak saya pedulikan.

Pertanyaannya : apakah ada struktur data yang diketahui yang cocok untuk kasus penggunaan saya di luar kotak?

EDIT : setelah memikirkan beberapa hal lagi, sepertinya pohon BST / Splay yang persisten akan berfungsi. Penulis akan memperbarui salinan 'master' dan pertanyaan akan mendapatkan pohon pada awal eksekusi dan membuangnya setelah selesai. Namun, saya masih tertarik jika ada solusi yang lebih baik.

data-structures concurrency databases dm3
sumber

Apakah Anda memerlukan snapshot dalam memori, atau apakah Anda perlu menyimpannya ke disk / jaringan? Struktur data yang murni fungsional secara otomatis memberi Anda snapshot dalam-memori, jadi jika itu yang Anda butuhkan, itu taruhan terbaik Anda.

Gilles 'SANGAT berhenti menjadi jahat'

Semuanya ada dalam memori. Saya bertanya-tanya mungkin ada versi yang bisa berubah yang efisien dengan snapshot waktu-konstan (seperti CTrie, hanya tanpa menulis bersamaan).

dm3

Masalah Anda mungkin bukan pilihan struktur data, tetapi jenis kontrol konkurensi.

Raphael

Mungkin, bisakah Anda menguraikan sedikit lebih banyak?

DM3

Jawaban:

Gunakan segala jenis struktur data berbasis pohon yang persisten / tidak berubah (yaitu fungsional). Kuncinya adalah mendapatkan penguncian yang benar, seperti @Raphael tunjukkan dalam komentar.

Yang menyenangkan tentang struktur data berbasis pohon fungsional / persisten, adalah Anda mendapatkan "snapshots" secara gratis. Misalkan Anda menggunakan treap (pohon pencarian biner acak) untuk struktur data Anda. Berikut ini contoh dari salah satu yang ditulis dalam Go: https://github.com/steveyen/gtreap . Penulis menggambarkannya sebagai berikut:

Dengan tetap, setiap pembaruan / penghapusan treap akan mengembalikan treap baru yang dapat berbagi node internal dengan treap sebelumnya. Semua node dalam implementasi ini hanya-baca setelah dibuat. Hal ini memungkinkan pembaca secara bersamaan untuk beroperasi secara aman dengan penulis bersamaan karena modifikasi hanya membuat struktur data baru dan tidak pernah memodifikasi struktur data yang ada. Ini adalah pendekatan sederhana untuk mencapai kontrol konkurensi MVCC atau multi-versi.

Pada setiap titik waktu, "saat ini" keadaan pohon diwakili oleh pointer ke akar pohon. Insersi tidak bermutasi. Alih-alih sebuah penyisipan membuat versi pohon sebelumnya tetap utuh, membuat node baru untuk path dari root ke titik penyisipan yang benar, dengan pointer kembali ke node dari versi sebelumnya yang dapat dibagikan. $O(\log n)$

Anda menggunakan kunci untuk melindungi pointer ke root. Karena struktur data tidak dapat diubah, pembacaan dapat dilakukan secara bersamaan, dan Anda dapat menyimpan pointer ke snapshot lama. Bacaan adalah:

lock
tmp = ptr_to_root
unlock
value = search(tmp, <value to search for>)
return value

Meskipun pencarian mungkin memakan waktu cukup lama, Anda hanya memegang kunci saat menyalin pointer, sehingga pencarian dapat terjadi secara bersamaan.

Tulisan adalah:

lock
old_ptr_to_root = ptr_to_root
ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
unlock

Dalam versi ini, menulis perlu memegang kunci selama seluruh proses pembuatan versi baru dari pohon. Anda dapat meningkatkan kinerja baca (dengan biaya kadang-kadang gagal menulis transaksi) dengan mengubah penulisan menjadi seperti ini:

top:
  lock
  old_ptr_to_root = ptr_to_root
  unlock
  new_ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
  lock
  if (ptr_to_root == old_ptr_to_root)   # make sure no other write happened in the interim
    ptr_to_root = new_ptr_to_root
    unlock
  else                                  # transaction fails, try again
    unlock
    goto top

Anda mungkin dapat melakukan sedikit lebih baik (menjadikannya "bebas kunci") jika bahasa pemrograman Anda memiliki variabel atom dengan operasi perbandingan-dan-swap atom. (Misalnya dengan menggunakan C ++ 11's atomic<T*>.)

Logika Pengembaraan
sumber

Terima kasih atas jawaban yang terperinci. Saya agak tahu itu, mungkin saya tidak menempatkannya dengan cukup jelas dalam pertanyaan itu sendiri. Namun, jawabannya tetap bagus!

dm3

Versi "peningkatan" Anda tergantung pada model memori sistem yang digunakan. Mungkin diperlukan verable untuk dinyatakan volatile pada beberapa sistem dan perlu keahlian yang bagus untuk mendapatkan koding yang benar.

Ian Ringrose

Microsoft telah menerbitkan perincian tentang baru mereka di basis data memori, ia memiliki indeks yang tidak memblokir baca saat penulisan sedang dilakukan.

Sebagai contoh:

Justin Levandoski, David Lomet, dan Sudipta Sengupta, The Bw-Tree: A B-tree untuk Hardware Baru, pada 2013 Konferensi Internasional ke-29 IEEE tentang Rekayasa Data (ICDE), Konferensi Internasional tentang Rekayasa Data, 8 April 2013.

Lihat http://research.microsoft.com/en-us/projects/main-memory_dbs/ untuk daftar publikasi mereka.

Ian Ringrose
sumber