Rumah > Artikel > Peranti teknologi > Optimumkan prestasi penyambungan pelan pengangkutan pemindahan Ctrip
Mengenai pengarang
Ringkasnya, pengurus pembangunan bahagian belakang Ctrip, memfokuskan pada seni bina teknikal, pengoptimuman prestasi, perancangan pengangkutan dan bidang lain.
Disebabkan oleh batasan dalam perancangan pengangkutan dan sumber kapasiti pengangkutan, mungkin tiada pengangkutan langsung antara dua tempat yang ditanya oleh pengguna, atau semasa cuti besar, pengangkutan terus Semua habis dijual. Walau bagaimanapun, pengguna masih boleh sampai ke destinasi mereka melalui pemindahan dua hala atau pelbagai hala seperti kereta api, kapal terbang, kereta, kapal, dll. Di samping itu, pengangkutan pemindahan kadangkala lebih menguntungkan dari segi harga dan penggunaan masa. Contohnya, dari Shanghai ke Yuncheng, menyambung melalui kereta api mungkin lebih pantas dan lebih murah daripada kereta api terus.
Rajah 1 Senarai pengangkutan pemindahan kereta api Ctrip
Apabila menyediakan penyelesaian pengangkutan pemindahan, ia adalah sangat penting Satu pautan adalah untuk menggabungkan dua atau lebih perjalanan kereta api, kapal terbang, kereta, kapal, dll. untuk membentuk pelan pemindahan yang boleh dilaksanakan. Kesukaran pertama dalam penyambungan trafik transit ialah ruang penyambungan adalah besar, memandangkan Shanghai sebagai bandar transit, hampir 100 juta kombinasi boleh dijanakan pada keperluan prestasi masa nyata, kerana data barisan pengeluaran berubah pada bila-bila masa dan perlu sentiasa dikemas kini data pertanyaan tentang kereta api, kapal terbang, kereta dan kapal. Penyambungan trafik transit memerlukan banyak sumber pengkomputeran dan overhed IO, jadi pengoptimuman prestasinya amat penting.
Artikel ini akan menggabungkan contoh untuk memperkenalkan prinsip, analisis dan kaedah pengoptimuman yang diikuti dalam proses mengoptimumkan prestasi penyambungan trafik pemindahan, bertujuan untuk menyediakan rujukan dan inspirasi yang berharga kepada pembaca.
Pengoptimuman prestasi memerlukan pengimbangan dan membuat pertukaran antara pelbagai sumber dan kekangan pada premis memenuhi keperluan perniagaan, dan mengikuti beberapa prinsip utama Membantu menghapuskan ketidakpastian dan mendekati penyelesaian optimum kepada masalah tersebut. Secara khususnya, tiga prinsip berikut dipatuhi terutamanya semasa proses pengoptimuman penyambungan trafik pemindahan:
Walaupun artikel ini adalah mengenai pengoptimuman prestasi , tetapi ia masih perlu ditekankan pada permulaan: jangan mengoptimumkan demi pengoptimuman. Terdapat banyak cara untuk memenuhi keperluan perniagaan, dan pengoptimuman prestasi hanyalah salah satu daripadanya. Kadangkala masalahnya sangat kompleks dan terdapat banyak sekatan Tanpa menjejaskan pengalaman pengguna dengan ketara, mengurangkan kesan kepada pengguna dengan melonggarkan sekatan atau menerima pakai proses lain juga merupakan cara yang baik untuk menyelesaikan masalah prestasi. Dalam pembangunan perisian, terdapat banyak contoh pengurangan kos ketara yang dicapai dengan mengorbankan sejumlah kecil prestasi. Sebagai contoh, algoritma HyperLogLog yang digunakan untuk statistik kardinaliti (penyingkiran duplikasi) dalam Redis hanya memerlukan ruang 12K untuk mengira 264 data, dengan ralat standard 0.81%.
Kembali kepada masalah itu sendiri, memandangkan data barisan pengeluaran perlu disoal dengan kerap dan operasi penyambungan besar-besaran dilakukan, jika setiap pengguna dikehendaki memulangkan segera pelan pemindahan terkini apabila membuat pertanyaan, The kos akan menjadi sangat tinggi. Untuk mengurangkan kos, keseimbangan perlu dicapai antara masa tindak balas dan kesegaran data. Selepas pertimbangan yang teliti, kami memilih untuk menerima ketidakkonsistenan data peringkat minit Untuk beberapa laluan dan tarikh yang tidak popular, mungkin tiada rancangan pemindahan yang baik apabila membuat pertanyaan buat kali pertama, hanya membimbing pengguna untuk memuat semula halaman.
Donald Knuth disebut dalam "Pengaturcaraan Berstruktur Dengan Pernyataan Pergi Ke": "Pengaturcara membuang banyak masa Berfikir dan bimbang tentang prestasi laluan bukan kritikal dan cuba mengoptimumkan bahagian prestasi ini akan memberi kesan negatif yang sangat serius terhadap penyahpepijatan dan penyelenggaraan kod keseluruhan, jadi dalam 97% kes, kita harus melupakan titik pengoptimuman kecil." Ringkasnya, sebelum masalah prestasi sebenar ditemui, pengoptimuman yang berlebihan dan menonjol pada tahap kod bukan sahaja tidak akan meningkatkan prestasi, tetapi boleh membawa kepada lebih banyak ralat. Walau bagaimanapun, penulis juga menekankan: "Untuk baki 3% kritikal, kita tidak seharusnya melepaskan peluang untuk mengoptimumkan." Oleh itu, anda perlu sentiasa memberi perhatian kepada isu prestasi, bukan membuat keputusan yang akan menjejaskan prestasi dan membuat pengoptimuman yang betul apabila perlu.
Seperti yang dinyatakan dalam bahagian sebelumnya, sebelum mengoptimumkan, anda mesti terlebih dahulu mengukur prestasi dan mengenal pasti kesesakan, supaya pengoptimuman boleh lebih disasarkan . Analisis kuantitatif prestasi boleh menggunakan pemantauan yang memakan masa, alat analisis prestasi Profiler, alat ujian penanda aras, dsb., memfokuskan pada kawasan yang mengambil masa yang sangat lama atau mempunyai kekerapan pelaksanaan yang sangat tinggi. Seperti yang dinyatakan oleh undang-undang Amdahl: "Tahap peningkatan prestasi sistem yang boleh diperolehi dengan menggunakan kaedah pelaksanaan yang lebih pantas untuk komponen tertentu dalam sistem bergantung pada kekerapan kaedah pelaksanaan ini digunakan, atau perkadaran jumlah masa pelaksanaan. "
Selain itu, adalah penting juga untuk ambil perhatian bahawa pengoptimuman prestasi ialah perjuangan yang berlarutan. Apabila perniagaan terus berkembang, seni bina dan kod sentiasa berubah, jadi lebih penting lagi untuk terus mengukur prestasi, menganalisis kesesakan secara berterusan dan menilai kesan pengoptimuman.
Sebelum analisis prestasi, kita mesti menyusun proses perniagaan terlebih dahulu. Penyambungan pelan pengangkutan pemindahan terutamanya merangkumi empat langkah berikut:
a Muatkan peta laluan, seperti Beijing ke Shanghai melalui pemindahan Nanjing, hanya maklumat laluan itu sendiri dipertimbangkan , tanpa mengira penerbangan khusus; baki maklumat tiket, dsb.;
c. Susun semua pilihan pengangkutan pemindahan yang boleh dilakukan, terutamanya dengan mengambil kira masa pemindahan tidak boleh terlalu singkat untuk mengelakkan tidak dapat menyelesaikan pemindahan pada pada masa yang sama, ia tidak boleh terlalu lama untuk mengelakkan menunggu terlalu lama. Selepas menggabungkan penyelesaian yang boleh dilaksanakan, anda masih perlu menambah baik bidang perniagaan, seperti jumlah harga, jumlah penggunaan masa, maklumat pemindahan, dll.; semua yang disambung Di antara penyelesaian pemindahan yang boleh dilaksanakan, beberapa penyelesaian yang mungkin menarik minat pengguna dipilih.
3.2 Prestasi analisis kuantitatif
(1) Tambah pemantauan yang memakan masa
Masa -memakan Pemantauan ialah cara yang paling intuitif untuk memerhati situasi memakan masa setiap peringkat dari perspektif makro. Ia bukan sahaja boleh melihat nilai memakan masa dan bahagian memakan masa pada setiap peringkat proses perniagaan, tetapi juga melihat arah aliran perubahan yang memakan masa dalam jangka masa yang panjang.Pemantauan yang memakan masa boleh menggunakan sistem pemantauan dan penggera penunjuk dalaman syarikat untuk menambah pengurusan yang memakan masa kepada proses utama menyambungkan penyelesaian pengangkutan transit. Proses ini termasuk memuatkan peta laluan, menanyakan data anjakan dan menyambungnya, menapis dan menyimpan pelan penyambungan, dsb. Situasi memakan masa setiap peringkat ditunjukkan dalam Rajah 2. Dapat dilihat bahawa penyambungan (termasuk data barisan pengeluaran) mengambil bahagian yang paling tinggi memakan masa, jadi ia telah menjadi sasaran pengoptimuman utama pada masa hadapan.
Rajah 2 Pemantauan memakan masa penyambungan trafik transit
(2) Profiler analisis prestasi
Pengurusan yang memakan masa mungkin menceroboh kod perniagaan dan menjejaskan prestasi, jadi ia tidak sepatutnya terlalu banyak dan lebih sesuai untuk memantau proses utama. Alat analisis prestasi Profiler yang sepadan (seperti Async-profiler) boleh menjana pepohon panggilan yang lebih khusus dan nisbah penggunaan CPU bagi setiap fungsi, dengan itu membantu menganalisis dan mencari laluan kritikal dan kesesakan prestasi.
Rajah 3 Pepohon panggilan penyambungan dan nisbah CPU
Seperti yang ditunjukkan dalam Rajah 3, skema penyambungan (combineTransferLines) menyumbang 53.80% dan data baris pengeluaran pertanyaan (querySegmentCacheable, cache digunakan) menyumbang 21.45%. Dalam skim penyambungan, pengiraan skor skim (computeTripScore, menyumbang 48.22%), mencipta entiti skim (buildTripBO, menyumbang 4.61%) dan menyemak kebolehlaksanaan penyambungan (checkCombineMatchCondition, menyumbang 0.91%) ialah tiga pautan terbesar.
Rajah 4 Pepohon panggilan pemarkahan penyelesaian dan nisbah CPU
Apabila kami terus menganalisis skor pelan pengiraan (computeTripScore) dengan perkadaran tertinggi, kami mendapati ia berkaitan terutamanya dengan fungsi pemformatan rentetan tersuai (StringUtils.format), termasuk panggilan langsung (digunakan untuk memaparkan pelan butiran skor), Serta panggilan tidak langsung melalui getTripId (digunakan untuk menjana ID skim). Bahagian tertinggi StringUtils.format tersuai ialah penggantian rentetan asli Java 8 java/lang/String.replace dilaksanakan melalui ungkapan biasa, yang agak tidak cekap (masalah ini telah diperbaiki selepas Java 9).
// 计算方案评分(computeTripScore) 中调用的StringUtils.format代码示例 StringUtils.format("AAAA-{0},BBBB-{1},CCCC-{2},DDDD-{3},EEEE-{4},FFFF-{5},GGGG-{6},HHHH-{7},IIII-{8},JJJJ-{9}", aaaa, bbbb, cccc, dddd, eeee, ffff, gggg, hhhh, iiii, jjjj) // getTripId 中调用StringUtils.format代码示例 StringUtils.format("{0}_{1}_{2}_{3}_{4}_{5}_{6}", aaaa, bbbb, cccc, dddd, eeee, ffff) // 通过Java replace实现的自定义format函数 public static String format(String template, Object... parameters) { for (int i = 0; i < parameters.length; i++) { template = template.replace("{" + i + "}", parameters[i] + ""); } return template; }
(3) Ujian penanda aras penanda aras
Gunakan alat penanda aras untuk mengukur dengan lebih tepat. masa pelaksanaan kod. Dalam Jadual 1, kami menggunakan JMH (Java Microbenchmark Harness) untuk menjalankan ujian yang memakan masa pada tiga kaedah pemformatan rentetan dan satu kaedah penyambungan rentetan. Keputusan ujian menunjukkan bahawa pemformatan rentetan menggunakan kaedah ganti Java8 mempunyai prestasi yang paling teruk, manakala menggunakan fungsi penyambungan rentetan Apache mempunyai prestasi terbaik.
Jadual 1 Perbandingan pemformatan rentetan dan prestasi penyambungan
实现 |
执行1000次平均耗时(us) |
使用Java8的replace实现的StringUtils.format |
1988.982 |
使用Apache replace实现的StringUtils.format |
656.537 |
Java8自带String.format |
1417.474 |
Apache的StringUtils.join |
116.812 |
StringUtils.format dilaksanakan menggunakan penggantian Apache
656.537
Java8 disertakan dengan String.format
1417.474
Apache's StringUtils.join
通过以上的性能分析,我们发现拼接和查询产线数据是性能瓶颈,字符串格式化影响尤其大。因此,我们将致力于优化这些部分,以提高性能表现。
优化代码逻辑是最简单且性价比最高的方法,可以是修正有问题的代码或替换为更好的实现。不同的实现,哪怕减上几纳秒,累加起来也是很可观的。借助一些经典算法或数据结构(如快速排序、红黑树等)可以在时间和空间复杂度方面带来显著优势。回到中转交通方案拼接性能优化本身,优化的代码逻辑主要包括:
(1)优化字符串拼接性能
如前面的JMH的结果所示,自定义的字符串格式化函数性能最差,因此作为重点优化目标。优化前后的对比如下所示:
// 优化前,通过Java replace实现的format函数 public static String format(String template, Object... parameters) { for (int i = 0; i < parameters.length; i++) { template = template.replace("{" + i + "}", parameters[i] + ""); } return template; } // 优化后,通过Apache replace实现的format函数 public static String format(String template, Object... parameters) { for (int i = 0; i < parameters.length; i++) { String temp = new StringBuilder().append('{').append(i).append('}').toString(); template = org.apache.commons.lang3.StringUtils.replace(template, temp, String.valueOf(parameters[i])); } return template; }
根据JMH的测试结果,即使是优化后的格式化函数,其性能也不是最优的。在不显著影响可读性的前提下,应尽量使用性能更优的StringUtils.join函数。
// 优化前 StringUtils.format("{0}_{1}_{2}_{3}_{4}_{5}_{6}", aaaa, bbbb, cccc, dddd, eeee, ffff) // 优化后 StringUtils.join("_", aaaa, bbbb, cccc, dddd, eeee, ffff)
为进一步提升性能,可以在computeTripScore 函数中添加一个开关,仅在调试模式下才展示评分细节,这将确保该字符串格式化函数仅在需要时才被调用。
if (Config.getBoolean("enable.score.detail", false)) { scoreDetail = StringUtils.format("AAAA-{0},BBBB-{1},CCCC-{2},DDDD-{3},EEEE-{4},FFFF-{5},GGGG-{6},HHHH-{7},IIII-{8},JJJJ-{9}", aaaa, bbbb, cccc, dddd, eeee, ffff, gggg, hhhh, iiii, jjjj); }
优化后的CPU占比如图5所示,此时字符串格式化已经不再是性能瓶颈。
图5 优化后的拼接调用树和CPU占比
(2)增加索引降低拼接时间复杂度
图6 增加索引降低拼接时间复杂度
在中转拼接过程中,我们需要将第一程每个班次的到达时间与第二程每个班次的出发时间进行比较,以判断中转时间是否过短或过长。为简化说明,假设换乘时间间隔需要满足大于30分钟且小于6小时。以北京到上海经南京中转的两程火车为例,3月9日北京到南京有66个班次,南京到上海有275个班次,考虑到隔夜车,还需要算上3月10日南京到上海的275个班次,那么最多需要比较36300(66*275*2)次。
为避免频繁比较,参考了MySQL B+树索引的思想,将第二程南京到上海的所有火车班次数据构建成红黑树。其中,树的键为秒级时间戳,例如2023-03-09 11:29出发的G367键为1677247680,值为G367的班次数据。有了索引树,最多只需要10次比较,就可以找到最近的满足最小换乘时间要求的班次。同理,最多需要10次比较,就能找到满足最大换乘时间要求的最晚班次。两者之间的所有班次都满足耗时要求,直接进行拼接即可。改进后最多需要比较1320(66*(10+10))次,约为原来的1/27.5。
(3)使用多路归并求Top-K算法
在筛选方案时,会存在以下场景:有多个中转点,每个中转点都有数百个得分较高的方案(内部已按得分由高到低排序,通过小根堆实现)。最终需要将这些方案合并,并从中筛选出得分最高的K个方案。
最简单的方法是使用快速排序将所有的方案排序,然后选取前K个,时间复杂度约为O(nlog2n)。然而,这并没有利用到每个队列自身有序的特点。通过多路归并算法时间复杂度可降为O(nlog2k),具体步骤为:
a. 从每个队列中拿出第一个元素(得分最高的方案),放入大根堆中;
b. Ambil elemen terbesar dari bahagian atas timbunan akar besar dan masukkan ke dalam set hasil
c di mana elemen terletak, kemudian Tambah elemen seterusnya pada timbunan;
Rajah 7 Algoritma Top-K gabungan pelbagai hala
4.2 Membina cache berbilang peringkat
Caching ialah strategi ruang-untuk-masa biasa yang boleh cache data dan hasil pengiraan Data cache boleh meningkatkan kecekapan capaian dan keputusan caching mengelakkan pengiraan berulang. Walaupun caching membawa peningkatan prestasi, ia juga memperkenalkan masalah baharu:Kapasiti cache adalah terhad, dan strategi pemuatan, pengemaskinian, pembatalan dan penggantian data perlu dipertimbangkan dengan teliti;
Beratus-ratus pertanyaan produk mungkin ditanya dalam satu penyambungan; Untuk data talian, kelewatan milisaat terkumpul Redis juga sangat besar. Oleh itu, adalah diharapkan untuk membina satu lagi lapisan cache memori di atas Redis untuk meningkatkan prestasi. Melalui analisis, didapati terdapat data panas yang sangat jelas dalam proses penyambungan Perkadaran pertanyaan pada tarikh dan laluan popular adalah sangat tinggi dan bilangannya agak terhad. Oleh itu, bahagian data panas ini boleh disimpan dalam cache memori dan digantikan dengan LFU (Kurang Kerap Digunakan Kadar hit memori data barisan pengeluaran akhir mencapai lebih daripada 45%, yang bersamaan dengan mengurangkan hampir separuh daripada overhed IO). .
Dalam proses penyambungan, berpuluh-puluh baris dengan titik pemindahan yang berbeza perlu diproses. Penyambungan setiap baris adalah bebas antara satu sama lain, jadi pelbagai benang boleh digunakan, yang meminimumkan masa pemprosesan. Walau bagaimanapun, disebabkan oleh pengaruh bilangan peralihan baris dan kadar hit cache, masa penyambungan baris yang berbeza sukar untuk konsisten. Sering kali, apabila dua utas diberikan bilangan tugas yang sama, walaupun satu utas selesai dilaksanakan dengan cepat, ia perlu menunggu sehingga utas lain selesai melaksanakan sebelum meneruskan ke langkah seterusnya. Untuk mengelakkan situasi ini, mekanisme mencuri kerja ForkJoinPool digunakan. Mekanisme ini boleh memastikan bahawa selepas setiap utas menyelesaikan tugasnya sendiri, ia juga akan berkongsi kerja benang lain yang belum selesai, meningkatkan kecekapan serentak dan mengurangkan masa terbiar.
Tetapi multi-threading bukanlah ubat penawar apabila menggunakannya, anda perlu memberi perhatian kepada:
Dengan menangguhkan pengiraan kepada saat yang diperlukan, adalah mungkin untuk mengelakkan banyak overhed berlebihan. Sebagai contoh, selepas menyambung pelan pemindahan, anda perlu membina entiti pelan dan menambah baik bidang perniagaan Bahagian ini juga menggunakan sumber. Dan tidak semua penyelesaian yang disambungkan akan disaring, yang bermaksud bahawa penyelesaian yang tidak disaring ini masih perlu menggunakan sumber pengkomputeran. Oleh itu, pembinaan objek entiti penyelesaian lengkap ditangguhkan Berpuluh-puluh ribu penyelesaian dalam proses penyambungan disimpan terlebih dahulu sebagai objek perantaraan ringan, dan entiti penyelesaian lengkap hanya dibina untuk ratusan objek perantaraan selepas penyaringan.
Projek penyambungan trafik transit adalah berdasarkan Java 8 dan menggunakan pemungut sampah G1 (Sampah-Diutamakan), yang digunakan pada mesin 8C8G. G1 mencapai daya pemprosesan yang tinggi sambil memenuhi keperluan masa jeda sebanyak mungkin Parameter lalai yang ditetapkan oleh jabatan seni bina sistem sudah sesuai untuk kebanyakan senario dan biasanya tidak memerlukan pengoptimuman khas.
Walau bagaimanapun, terdapat terlalu banyak penyelesaian pemindahan talian, mengakibatkan paket yang terlalu besar, melebihi separuh daripada saiz Wilayah (8G, saiz Wilayah lalai ialah 2M), mengakibatkan banyak objek besar yang sepatutnya memasuki generasi muda secara langsung Memasuki usia tua, untuk mengelakkan keadaan ini, tukar saiz Wilayah kepada 16M.
Melalui analisis dan pengoptimuman di atas, perubahan dalam penggunaan masa penyambungan ditunjukkan dalam Rajah 9:
Rajah 9 Kesan pengoptimuman prestasi penyambungan skim pengangkutan pemindahan
Walaupun setiap perniagaan dan senario mempunyai ciri tersendiri, pengoptimuman prestasi juga memerlukan analisis khusus. Walau bagaimanapun, prinsipnya adalah sama, dan anda masih boleh merujuk kepada kaedah analisis dan pengoptimuman yang diterangkan dalam artikel ini. Ringkasan semua kaedah analisis dan pengoptimuman dalam artikel ini ditunjukkan dalam Rajah 10.
Rajah 10 Ringkasan pengoptimuman penyambungan skim pengangkutan pemindahan
Atas ialah kandungan terperinci Optimumkan prestasi penyambungan pelan pengangkutan pemindahan Ctrip. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!