MaxCompute：Ikhtisar Graf

Istilah

• Graf: Struktur data abstrak yang digunakan untuk merepresentasikan hubungan antar objek. Simpul dan sisi digunakan dalam graf. Simpul mewakili objek, dan sisi mewakili hubungan antar objek. Data yang dijelaskan dalam graf disebut data graf.

• Simpul: Mewakili sebuah objek dalam graf.

• Sisi: Sisi tunggal berarah yang mewakili hubungan antar objek dalam graf. Sisi terdiri dari ID simpul sumber, ID simpul tujuan, dan data yang terkait dengan sisi tersebut.

• Graf berarah: Graf di mana sisi memiliki arah. Dua simpul pada sisi mewakili objek yang berbeda. Misalnya, Halaman A terhubung ke Halaman B. Dalam graf berarah, sisi diklasifikasikan menjadi sisi keluar dan sisi masuk.

• Graf tak berarah: Graf di mana sisi tidak memiliki arah, seperti pengguna umum dalam grup pengguna.

• Sisi keluar: Sisi berarah di mana simpul saat ini adalah asal.

• Sisi masuk: Sisi berarah di mana simpul saat ini adalah tujuan.

• Degree: Jumlah sisi yang terhubung ke simpul.

• Outdegree: Jumlah sisi keluar yang terhubung ke simpul.

• Indegree: Jumlah sisi masuk yang terhubung ke simpul.

• Superstep: Iterasi dari sebuah graf.

Struktur data graf

MaxCompute Graph memproses graf berarah. MaxCompute hanya menyediakan struktur penyimpanan tabel dua dimensi. Oleh karena itu, Anda harus menguraikan data graf menjadi tabel dua dimensi dan menyimpannya di MaxCompute. Anda dapat menguraikan data graf sesuai dengan kebutuhan bisnis Anda.

Logika program Graf

Program Graf melakukan operasi berikut: pemuatan graf, komputasi iteratif, dan terminasi iterasi.

1. Pemuatan graf.

   Pemuatan graf terdiri dari langkah-langkah berikut:

   1. Pemuatan graf: MaxCompute Graph memanggil GraphLoader kustom untuk mengurai rekaman dalam tabel input menjadi simpul atau sisi.

   2. Pembagian partisi: MaxCompute Graph memanggil Partitioner kustom untuk membagi partisi simpul dan mendistribusikan partisi ke pekerja terkait. Secara default, MaxCompute Graph membagi partisi simpul berdasarkan nilai hash dari ID simpul modulo jumlah pekerja.

   Pada gambar di atas, jumlah pekerja adalah 2. Simpul 0 dan Simpul 2 didistribusikan ke Pekerja 0 karena hasil dari ID simpul modulo 2 adalah 0. Simpul 1, Simpul 3, dan Simpul 5 didistribusikan ke Pekerja 1 karena hasil dari ID simpul modulo 2 adalah 1.

2. Komputasi iteratif.

   Iterasi disebut superstep. Selama iterasi, program melintasi semua simpul non-dihentikan atau semua simpul yang menerima pesan, dan memanggil metode compute(ComputeContext context, Iterable messages). Untuk simpul non-dihentikan, nilai parameter Dihentikan adalah false. Simpul yang dihentikan secara otomatis diaktifkan setelah mereka menerima pesan.

   Metode compute(ComputeContext context, Iterable messages) dapat digunakan untuk melakukan operasi berikut:

   • Memproses pesan yang dikirim oleh superstep sebelumnya ke simpul saat ini.

   • Mengedit graf sesuai kebutuhan:

     • Mengubah nilai simpul atau sisi.

     • Mengirim pesan ke beberapa simpul.

     • Menambahkan atau menghapus simpul atau sisi.

   • Menggunakan pengumpul untuk mengumpulkan informasi dan memperbarui informasi global. Untuk informasi lebih lanjut, lihat Mekanisme Implementasi Aggregator.

   • Menetapkan simpul saat ini ke status dihentikan atau non-dihentikan.

   • Mengaktifkan MaxCompute Graph untuk mengirim pesan secara asinkron ke pekerja terkait di setiap superstep. Pesan kemudian diproses di superstep berikutnya.

3. Terminasi iterasi.

   Iterasi diakhiri jika salah satu atau lebih dari kondisi berikut terpenuhi:

   • Semua simpul berada dalam keadaan dihentikan (nilai parameter Dihentikan adalah true), dan tidak ada pesan baru yang dihasilkan.

   • Jumlah maksimum iterasi telah tercapai.

   • Metode terminate dari aggregator mengembalikan nilai true.

   Pseudocode dari program Graf:

   // 1. load
   for each record in input_table {
     GraphLoader.load();
   }
   // 2. setup
   WorkerComputer.setup();
   for each aggr in aggregators {
     aggr.createStartupValue();
   }
   for each v in vertices {
     v.setup();
   }
   // 3. superstep
   for (step = 0; step < max; step ++) {
     for each aggr in aggregators {
       aggr.createInitialValue();
     }
     for each v in vertices {
        v.compute();
      }
   }
   // 4. cleanup
   for each v in vertices {
     v.cleanup();
   }
   WorkerComputer.cleanup();