Memindai satu miliar baris dalam basis data ultra-cepat

9

Latar Belakang

Database lokal berisi hampir 1,3 miliar baris unik. Setiap baris secara tidak langsung dikaitkan dengan garis lintang dan garis bujur tertentu (lokasi). Setiap baris memiliki cap tanggal.

Gunakan Kasing

Masalahnya adalah sebagai berikut:

  1. Pengguna menetapkan tanggal mulai / berakhir, dan rentang nilai (misalnya, 100 hingga 105).
  2. Sistem mengumpulkan semua baris yang cocok dengan tanggal yang diberikan, dikelompokkan berdasarkan lokasi.
  3. Performa sistem menentukan lokasi yang, selama tanggal tersebut, memiliki kemungkinan statistik untuk jatuh ke dalam kisaran nilai yang diberikan.
  4. Sistem menampilkan semua lokasi yang cocok kepada pengguna.

Ini adalah masalah kecepatan dan skala.

Pertanyaan

Apa arsitektur solusi paling murah yang dapat Anda bayangkan yang memungkinkan sistem seperti itu untuk mengambil hasil untuk pengguna dalam waktu kurang dari lima detik?

Sistem saat ini

Lingkungan saat ini:

  • PostgreSQL 8.4 (upgrade dimungkinkan; berpindah basis data bukan pilihan)
  • R dan PL / R
  • XFS
  • WD VelociRaptor
  • RAM 8 GB (Corsair G.Skill; 1,3 GHz)
  • Quad core GenuineIntel 7 (2,8 GHz)
  • Ubuntu 10.10

Pembaruan perangkat keras dapat diterima.

Pembaruan - Struktur Database

Miliaran baris berada dalam tabel yang menyerupai:

id | taken | location_id | category | value1 | value2 | value3
  • id - Kunci utama
  • diambil - Tanggal ditetapkan ke baris
  • location_id - Referensi ke garis lintang / bujur
  • kategori - Deskripsi data
  • value1 .. 3 - Nilai lain yang dapat ditanyakan pengguna

The takenkolom biasanya tanggal berturut-turut per location_id, kadang-kadang setiap lokasi memiliki data yang 1800-2010 (sekitar 77.000 tanggal, banyak dari mereka diduplikasi karena masing-masing lokasi memiliki data dalam rentang tanggal yang sama).

Ada tujuh kategori dan tabel sudah dibagi berdasarkan kategori (menggunakan tabel anak). Setiap kategori berisi ~ 190 juta baris. Dalam waktu dekat, jumlah baris per kategori akan melebihi satu miliar.

Ada sekitar 20.000 lokasi dan 70.000 kota. Lokasi berkorelasi dengan kota dengan garis lintang dan bujur. Menugaskan setiap lokasi ke kota tertentu berarti menemukan batas kota, yang bukan tugas sepele.

Ide ide

Beberapa ide yang saya miliki meliputi:

  • Temukan layanan cloud untuk meng-host basis data.
  • Buat garis raid SSD (video hebat).
  • Buat tabel yang menggabungkan semua lokasi dengan kota (pra-perhitungan).

Terima kasih!

architecture database geospatial Dave Jarvis
sumber
10
"berpindah basis data bukanlah suatu pilihan" yah yang cukup banyak menghilangkan sebagian besar solusi. semoga berhasil!
Steven A. Lowe
1
Sulit untuk mengatakan tanpa informasi lebih lanjut tentang apa yang sebenarnya Anda lakukan dengan catatan-catatan itu. Juga, apakah Anda mencari kasus terburuk 5 detik (yang mungkin berarti setiap catatan diperiksa dan nol lokasi cocok)?
Guy Sirton
2
@ Dave: Berapa banyak waktu yang dibutuhkan sistem saat ini? Apakah sistem saat ini menggunakan PostGIS ? Apakah location_ida geographyatau geometry, atau mengacu pada tabel kedua? Apakah location_idkolom diindeks?
rwong
1
@ Thorbjørn & @Darknight - Di bagian ide saya mencantumkan pra-perhitungan, yang akan mengurangi data menjadi satu nilai per kota per hari (per kategori). Perhitungannya bisa berulang setiap tahun, atau bahkan bulanan, saya kira. Ini adalah rencana saya jika tidak ada kemungkinan lain (perhitungannya mungkin akan memakan waktu berminggu-minggu).
Dave Jarvis
1
@Dave, banyak kemungkinan, tetapi pertanyaannya adalah apa yang relevan bagi Anda. Sudahkah Anda menyelidiki di mana kemacetan saat ini?

Jawaban:

12

Yang paling penting adalah untuk benar-benar yakin di mana bottleneck sekarang untuk sejumlah permintaan representatif karena Anda tidak dapat beralih database.

Jika Anda melakukan pemindaian tabel penuh, Anda perlu indeks yang sesuai.

Jika Anda menunggu di I / O Anda perlu lebih banyak memori untuk caching (Jeff Atwood baru-baru ini menyebutkan bahwa sistem 24 Gb dapat dicapai pada sistem desktop).

Jika Anda menunggu di CPU Anda perlu melihat apakah perhitungan Anda dapat dioptimalkan.

Ini membutuhkan topi-DBA runcing dan Sistem Operasi-topi, tetapi layak untuk memastikan Anda menggonggong pohon yang tepat.


sumber
Bagaimana pun Anda mengiris dan memotongnya - bahkan jika setiap baris hanya membutuhkan 100 byte, baris 1,3Billion = 121 GB. Dengan semua indeks Anda dll., Saya yakin ini akan jauh lebih banyak. Pada satu kotak, Anda akan menjadi lambat kecuali jika Anda memiliki beberapa perangkat keras yang serius di sekitar SSD + ton ram. Cara yang lebih murah adalah dengan menskalakan kotak.
Subu Sankara Subramanian
4
@ Subu, Anda ingin didistribusikan? Sekarang Anda memiliki dua masalah ...
Heh - bahwa saya setuju dengan :) Tapi itu lebih murah!
Subu Sankara Subramanian
@ Thorbjørn: Terima kasih atas waktu dan semua bantuan Anda. Saya pikir saya akan mengurangi kumpulan data menjadi 25 juta baris per kategori kemudian menerapkan indeks pada tanggal tersebut. Itu harus mengurangi pemindaian menjadi ~ 70000 baris (per hari, dengan batas dua minggu untuk rentang), yang seharusnya cukup tajam.
Dave Jarvis
@Dave, Anda masih perlu tahu di mana kemacetan Anda. Belajarlah selagi tidak perlu .
4

Bagaimana dengan mempartisi tabel menjadi beberapa bagian yang terletak di host yang berbeda berdasarkan cap tanggal? Ini dapat diskalakan secara horizontal, dan selama Anda memiliki jumlah kotak yang cukup, Anda dapat menulis mesin agregasi kecil di atas pengaturan ini.

Jika Anda melihat bahwa cap tanggal berubah terlalu banyak, maka Anda dapat mempartisi berdasarkan lokasi - sekali lagi terukur secara horizontal. (Semoga mereka tidak menambahkan lebih banyak garis lintang / bujur!)

Subu Sankara Subramanian
sumber
Terima kasih untuk idenya. Ada kemungkinan 77.066 tanggal, dan tanggal baru akan ditambahkan kedepannya. Saya punya satu mesin. Ada 20.000 lokasi, namun pemisahan berdasarkan lokasi tidak akan membantu karena data untuk menganalisis mencakup semua lokasi.
Dave Jarvis
dan bagaimana menggunakan cloud berbeda dari solusi di atas?
Chani
Inilah yang saya pikirkan juga. Semacam partisi horizontal sehingga pencarian dapat terjadi secara paralel di semua partisi.
davidk01
Memisahkan pada hari itu mungkin akan menjadi yang paling bermanfaat, menghasilkan 2562 tabel terpisah (366 hari x 7 kategori).
Dave Jarvis
4

Skenario kasus terburuk adalah rentang tanggal mencakup semua tanggal di basis data Anda.

Anda ingin membaca 1,3 miliar catatan dan melakukan semacam analisis pada setiap catatan vs. nilai yang dimasukkan, pada satu mesin fisik, dalam waktu kurang dari 5 detik. Hasilnya dapat berupa semua lokasi atau tidak sama sekali - Anda tidak tahu apa-apa sebelumnya.

Mengingat parameter ini saya akan mengatakan kemungkinan tidak mungkin.

Lihat saja hard drive Anda: laju Max Sustained kurang dari 150MB / s. Membaca 1,3 miliar rekaman akan memakan waktu lebih dari 5 detik. Dari segi CPU Anda tidak akan dapat melakukan analisis statistik apa pun pada 1,3 miliar catatan dalam 5 detik.

Satu-satunya harapan Anda (tm :-)) adalah menemukan semacam fungsi pencarian berdasarkan pada nilai yang dimasukkan oleh pengguna yang akan mempersempit pencarian (dengan beberapa urutan besarnya). Anda dapat menghitung fungsi pencarian ini secara offline. Tanpa mengetahui lebih lanjut tentang kriteria pencocokan tepat, saya tidak berpikir ada orang yang bisa memberi tahu Anda bagaimana melakukan itu, tetapi sebuah contoh adalah untuk mempartisi kisaran nilai menjadi beberapa interval diskrit dan membuat pencarian yang memberi Anda semua catatan dalam interval itu. Selama interval cukup kecil, Anda dapat melakukan pekerjaan nyata di dalamnya, misalnya memangkas entri yang tidak cocok dengan nilai yang dimasukkan pengguna. Pada dasarnya perdagangan ruang untuk waktu.

Dimungkinkan untuk menyimpan semua catatan (atau setidaknya bagian penting) dalam memori. Mungkin tidak dalam 8GB. Ini setidaknya akan menghilangkan bagian I / O disk meskipun bandwidth memori mungkin tidak cukup untuk memindai semuanya dalam 5 detik. Bagaimanapun, ini adalah teknik lain untuk mempercepat aplikasi semacam ini (gabungkan dengan saran saya sebelumnya).

Anda menyebutkan menggunakan layanan cloud. Ya jika Anda membayar cukup untuk CPU dan otot IO dan mempartisi basis data Anda di banyak server, Anda dapat memaksa / membagi dan menaklukkannya.

Guy Sirton
sumber
Terima kasih atas jawabannya. Pembaruan perangkat keras merupakan pertimbangan, sesuai dengan ide yang saya daftarkan. Solusi sub- $ 750 USD akan ideal.
Dave Jarvis
2

Saya kedua komentar rwong untuk pertanyaan: PostgreSQL menawarkan jenis indeks yang sesuai dan alat (indeks GIST, indeks GIN, Postgis, tipe Geometrik) sedemikian rupa sehingga geodata dan data terkait-data harus dapat dicari di sepanjang kriteria tersebut tanpa banyak masalah.

Jika pertanyaan Anda tentang kriteria ini memakan waktu beberapa detik, mungkin berarti tidak ada indeks yang digunakan. Bisakah Anda mengonfirmasi bahwa Anda telah menyelidiki ini sebagaimana mestinya?

Denis de Bernardy
sumber
Terima kasih. Tujuh tabel anak dikelompokkan pada lokasi, tanggal, dan kategori menggunakan btree. Saya meneliti indeks GIN tahun lalu dan mereka tidak (atau tidak mau) membantu, seingat saya.
Dave Jarvis
2
Lokasi pengindeksan berdasarkan B-Tree tidak sedikit berguna mengingat jenis pencarian yang Anda cari. Anda memerlukan indeks terbalik yang berfungsi dengan operator yang dibutuhkan, yang dalam kasus Postgis biasanya berarti GIST. Anda mungkin ingin menyoroti beberapa pertanyaan lambat ...
Denis de Bernardy
1

Mengingat Anda menggunakan PostgreSQL dan data lintang / bujur, Anda pasti harus menggunakan PostGIS juga, dengan cara itu Anda dapat menambahkan indeks spasial GiST ke database Anda untuk membantu mempercepatnya.

Saya punya meja seperti itu (dengan 350k baris) dengan konfigurasi yang jauh lebih kecil dari milik Anda (2 core dan hampir 2Gb RAM) namun pencarian membutuhkan waktu kurang dari satu detik.

wildpeaks
sumber
0

Mungkin Anda bisa memecahkan model relasional seperti yang dilakukan Essbase dengan arsitektur OLAP mereka: Essbase Wikipedia

Yang saya maksud adalah membuat satu tabel per kota, sehingga berakhir dengan 1000 tabel. Tidak satu meja seperti yang Anda sarankan, tetapi banyak. Indeks setiap tabel berdasarkan tanggal dan lokasi. Banyak tabel, banyak indeks -> lebih cepat.

mihaela
sumber
Terima kasih atas catatannya. Ada lebih dari 70.000 kota, dan banyak nilai lintang / bujur yang berbeda berada dalam wilayah kota tertentu.
Dave Jarvis
@ Dave: dapatkah Anda membuat diagram voronoi untuk kota dan mengklasifikasikan nilai lat / lon menjadi tessellations? (yaitu jika kedengarannya serampangan, biarkan saja.) Kemudian, selama pencarian, Anda akan mencari semua kota yang tessasinya menyentuh rentang lat / lon kueri. Jika voronoi tessellation terlalu lambat, kotak kotak (mis. 5 deg lat x 5 deg lon) mungkin layak untuk dicoba.
rwong
0

Sejauh ide Anda menemukan layanan cloud untuk meng-host database, apakah Anda sudah menemukan SimpleGeo ? Mereka hanya memotong pita pada layanan Penyimpanan yang tampaknya "secara khusus disetel untuk menyimpan dan meminta data lokasi dengan sangat, sangat cepat" - meskipun biaya untuk menyimpan dan meminta lebih dari satu miliar baris mungkin membuat pendekatan ini tidak mungkin dilakukan.

IanI
sumber
-2

Anda mengharapkan sepeda untuk berjalan di jalan raya. Saat ini Anda sedang mencari solusi untuk mengatasi masalah ini saja, Anda tidak meramalkan masalah bagaimana jika Anda memiliki 2 miliar catatan? skalabilitas harus diatasi. jawabannya sederhana menggunakan database objek. misalnya cache Antar Sistem

dan percayalah, aku bukan dari intersystems ;-)

anerjan
sumber