Port pengembangan kunci / Value store ke C ++ modern

Saya mengembangkan server database yang mirip dengan Cassandra.

Pengembangan dimulai pada C, tetapi berbagai hal menjadi sangat rumit tanpa kelas.

Saat ini saya porting semuanya dalam C ++ 11, tapi saya masih belajar "modern" C ++ dan ragu tentang banyak hal.

Database akan bekerja dengan pasangan Key / Value. Setiap pasangan memiliki beberapa informasi lagi - kapan dibuat juga kapan akan kedaluwarsa (0 jika tidak kedaluwarsa). Setiap pasangan tidak berubah.

Kuncinya adalah string C, Nilai tidak berlaku *, tetapi setidaknya untuk saat ini saya beroperasi dengan nilai sebagai string C juga.

Ada IListkelas abstrak . Itu diwarisi dari tiga kelas

• VectorList - C dynamic array - mirip dengan std :: vector, tetapi menggunakan realloc
• LinkList - dibuat untuk pemeriksaan dan perbandingan kinerja
• SkipList - kelas yang akhirnya akan digunakan.

Di masa depan saya mungkin melakukan Red Blackpohon juga.

Masing IList- masing berisi nol atau lebih pointer untuk dipasangkan, disortir berdasarkan kunci.

Jika IListterlalu lama, dapat disimpan di disk dalam file khusus. File khusus ini semacam read only list.

Jika Anda perlu mencari kunci,

• pertama dalam memori IListdicari ( SkipList, SkipListatau LinkList).
• Kemudian pencarian dikirim ke file yang diurutkan berdasarkan tanggal
  (file terbaru pertama, file terlama - terakhir).
  Semua file ini dalam memori mmap-ed.
• Jika tidak ada yang ditemukan, maka kunci tidak ditemukan.

Saya tidak ragu tentang implementasi IListhal - hal tersebut.

Yang membingungkan saya adalah sebagai berikut:

Pasangan dengan ukuran yang berbeda , mereka dialokasikan oleh new()dan mereka std::shared_ptrmenunjuk ke mereka.

class Pair{
public:
    // several methods...
private:
    struct Blob;

    std::shared_ptr<const Blob> _blob;
};

struct Pair::Blob{
    uint64_t    created;
    uint32_t    expires;
    uint32_t    vallen;
    uint16_t    keylen;
    uint8_t     checksum;
    char        buffer[2];
};

variabel "buffer" adalah variabel dengan ukuran berbeda. Ini menyimpan nilai kunci +.
Misalnya, jika kunci adalah 10 karakter, dan nilainya 10 byte lain, seluruh objek akan menjadi sizeof(Pair::Blob) + 20(buffer memiliki ukuran awal 2, karena dua byte null terminating)

Layout yang sama ini digunakan pada disk juga, jadi saya bisa melakukan sesuatu seperti ini:

// get the blob
Pair::Blob *blob = (Pair::Blob *) & mmaped_array[pos];

// create the pair, true makes std::shared_ptr not to delete the memory,
// since it does not own it.
Pair p = Pair(blob, true);

// however if I want the Pair to own the memory,
// I can copy it, but this is slower operation.
Pair p2 = Pair(blob);

Namun ukuran yang berbeda ini merupakan masalah di banyak tempat dengan kode C ++.

Misalnya saya tidak bisa menggunakan std::make_shared(). Ini penting bagi saya, karena jika saya memiliki 1 juta pasang, saya akan memiliki alokasi 2 juta.

Dari sisi lain, Jika saya melakukan "buffer" ke array dinamis (mis. Char baru [123]), saya akan kehilangan mmap "trik", saya akan melakukan dua dereferensi jika saya ingin memeriksa kunci dan saya akan menambahkan pointer tunggal - 8 byte ke kelas.

Saya juga mencoba untuk "menarik" semua anggota dari Pair::Blobdalam Pair, sehingga Pair::Blobmenjadi hanya buffer, tapi ketika saya diuji, itu cukup lambat, mungkin karena menyalin data objek di sekitar.

Perubahan lain yang saya pikirkan adalah untuk menghapus Pairkelas dan menggantinya dengan std::shared_ptrdan "mendorong" semua metode kembali ke Pair::Blob, tetapi ini tidak akan membantu saya dengan Pair::Blobkelas ukuran variabel .

Saya bertanya-tanya bagaimana saya bisa memperbaiki desain objek agar lebih ramah C ++.

Kode sumber lengkap ada di sini:
https://github.com/nmmmnu/HM3

Pendekatan yang saya sarankan adalah untuk fokus pada antarmuka toko nilai kunci Anda, sehingga membuatnya sebersih mungkin dan sebatas mungkin, yang berarti bahwa itu harus memungkinkan kebebasan maksimum untuk penelepon, tetapi juga kebebasan maksimum untuk memilih bagaimana cara mengimplementasikannya.

Kemudian, saya akan merekomendasikan agar Anda memberikan implementasi yang sebersih mungkin, dan sebersih mungkin, tanpa masalah kinerja apa pun. Bagi saya sepertinya ini unordered_mapharus menjadi pilihan pertama Anda, atau mungkin mapjika semacam pemesanan kunci harus diekspos oleh antarmuka.

Jadi, pertama-tama membuatnya bekerja dengan bersih dan minimal; kemudian, gunakan untuk aplikasi nyata; dalam melakukannya, Anda akan menemukan masalah apa yang perlu Anda atasi pada antarmuka; kemudian, lanjutkan dan tangani mereka. Sebagian besar kemungkinan adalah sebagai akibat dari mengubah antarmuka, Anda harus menulis ulang sebagian besar implementasi, jadi setiap kali Anda telah berinvestasi pada iterasi pertama implementasi di luar jumlah minimum waktu yang diperlukan untuk mendapatkannya hanya nyaris tidak bekerja adalah waktu yang terbuang.

Kemudian, profil itu, dan lihat apa yang perlu diperbaiki dalam implementasi, tanpa mengubah antarmuka. Atau Anda mungkin memiliki ide sendiri tentang cara meningkatkan implementasi, bahkan sebelum Anda membuat profil. Tidak apa-apa, tetapi masih belum ada alasan untuk mengerjakan ide-ide ini pada titik waktu sebelumnya.

Anda mengatakan berharap untuk melakukan lebih baik daripada map; ada dua hal yang bisa dikatakan tentang itu:

a) Anda mungkin tidak akan;

b) hindari optimasi prematur dengan segala cara.

Sehubungan dengan implementasi, masalah utama Anda tampaknya alokasi memori, karena Anda tampaknya peduli dengan bagaimana menyusun desain Anda untuk mengatasi masalah yang Anda perkirakan akan Anda miliki sehubungan dengan alokasi memori. Cara terbaik untuk mengatasi masalah alokasi memori di C ++ adalah dengan menerapkan manajemen alokasi memori yang sesuai, bukan dengan memutar dan menekuk desain di sekitarnya. Anda harus menganggap diri Anda beruntung karena menggunakan C ++, yang memungkinkan Anda melakukan manajemen alokasi memori Anda sendiri, berbeda dengan bahasa seperti Java dan C #, di mana Anda cukup terjebak dengan apa yang ditawarkan runtime bahasa.

Ada berbagai cara untuk menangani manajemen memori dalam C ++, dan kemampuan untuk membebani newoperator mungkin berguna. Alokasi memori yang sederhana untuk proyek Anda akan mengalokasikan banyak byte dan menggunakannya sebagai heap. ( byte* heap.) Anda akan memiliki firstFreeByteindeks, diinisialisasi ke nol, yang menunjukkan byte bebas pertama di heap. Ketika permintaan untuk Nbyte datang, Anda kembali alamat heap + firstFreeBytedan Anda menambahkan Nuntuk firstFreeByte. Jadi, alokasi memori menjadi sangat cepat dan efisien sehingga tidak ada masalah.

Tentu saja, preallocating semua memori Anda mungkin bukan ide yang baik, jadi Anda mungkin harus membagi tumpukan Anda ke bank-bank yang dialokasikan berdasarkan permintaan, dan tetap melayani permintaan alokasi dari bank pada saat-saat-saat-terbaru.

Karena data Anda tidak dapat diubah, ini adalah solusi yang bagus. Ini memungkinkan Anda untuk meninggalkan ide objek panjang variabel, dan masing-masing Pairberisi pointer ke data sebagaimana mestinya, karena alokasi memori tambahan untuk data hampir tidak ada biaya.

Jika Anda ingin dapat membuang objek dari heap, sehingga dapat memperoleh kembali ingatan mereka, maka hal-hal menjadi lebih rumit: Anda harus menggunakan bukan pointer, tetapi pointer ke pointer, sehingga Anda selalu dapat memindahkan objek sekitar di tumpukan untuk merebut kembali ruang objek yang dihapus. Semuanya menjadi sedikit lebih lambat karena tipuan ekstra, tetapi semuanya masih kilat cepat dibandingkan dengan menggunakan rutin alokasi memori perpustakaan runtime standar.

Tetapi semua ini tentu saja benar-benar tidak berguna untuk diperhatikan jika Anda tidak pertama-tama membangun versi database Anda yang sederhana, minimal, berfungsi, dan menggunakannya untuk aplikasi yang nyata.