ทำไมการค้นหาโค้ดจึงเป็นเรื่องยาก
(blog.val.town)- การค้นหาของ Val Town เป็นการค้นหาสตริงย่อยบน Postgres ด้วย ILIKE จึงแทบไม่มีการจัดอันดับ และยังอ่อนกับคิวรีหลายคำ ทำให้มีคำขอให้ปรับปรุงจำนวนมาก
- กฎของการค้นหาภาษาธรรมชาติ เช่น การตัดคำหยุด, การหา stem และการทำ lemmatization อาจทำให้ชื่อวาริเอเบิล ชื่อฟังก์ชัน และขอบเขตโทเคนของโค้ดเสียหายได้
- Full Text Search ของ Postgres ช่วยให้โครงสร้างพื้นฐานยังเรียบง่ายได้ แต่โปรเจกต์ก่อนหน้าเคยเจอปัญหาด้านการขยายตัว และ Val Town เองก็กำลังทดสอบขีดจำกัดของ Postgres โหนดเดียวอยู่
- ระบบค้นหา v2 ที่ซอฟต์ลอนช์ใช้การค้นหาแบบ trigram บน pg_trgrm แต่ต่างจากการค้นหาด้วย regular expression การปรับอันดับของคิวรีรูปแบบอิสระให้ได้ตามต้องการทำได้ยาก
- มีทางเลือกอย่าง Elasticsearch, Meilisearch, Zoekt, ParadeDB แต่โครงสร้างพื้นฐานแยกต่างหาก ภาระด้านปฏิบัติการ และการรองรับของโฮสติ้งยังเป็นข้อจำกัดในการเลือก
จุดที่การค้นหาของ Val Town ติดขัด
- ปัจจุบันการค้นหาของ Val Town ใช้ ILIKE ของ Postgres
- เป็นวิธี ค้นหาสตริงย่อย ที่ถ้าคำค้นอยู่ในโค้ด ผลลัพธ์ก็จะแสดงขึ้นมา
- แทบไม่มีการจัดอันดับ และไม่รองรับคิวรีหลายคำได้ดี
- การค้นหาที่ดีกว่านี้เป็น หนึ่งในฟีเจอร์ที่ถูกขอมากที่สุด บน Val Town
- งานปรับปรุงกำลังดำเนินอยู่ แต่ยังไม่พบวิธีแก้ที่ตรงกับข้อกำหนด
- เงื่อนไขที่ตรวจสอบมาจนถึงตอนนี้มีดังนี้
- โซลูชันค้นหากระแสหลักถูกออกแบบมาให้เหมาะกับ ภาษาธรรมชาติ
- บริษัทขนาดใหญ่ที่ต้องการค้นหาโค้ดลงทุนเวลาและเงินจำนวนมากกับระบบค้นหาของตนเอง
- Val Town มีข้อมูลอยู่มากแล้ว จึงต้องการโซลูชันที่ขยายตัวได้ดี
- หากใช้บริการค้นหาแยกแทนการขยายฐานข้อมูล ต้องพิจารณาการแลกเปลี่ยนด้านโครงสร้างพื้นฐานและความซับซ้อนอย่างสำคัญ
ทำไมกฎการค้นหาภาษาธรรมชาติจึงไม่เหมาะกับโค้ด
- การตั้งค่า full-text search (FTS) ทั่วไปมีอัลกอริทึมสำหรับภาษาธรรมชาติอย่างภาษาอังกฤษให้เป็นค่าเริ่มต้น
- การตัดคำหยุด: ลบคำที่พบบ่อยเกินไปอย่าง “the”, “it” ก่อนทำดัชนี
- การหา stem: แปลง “running” เป็น “run” เพื่อให้ค้นหาด้วย “runs” แล้วเจอได้ด้วย
- การทำ lemmatization: อาจแทนคำพ้องความหมายด้วยคำที่พบบ่อยกว่า เพื่อให้การค้นหา “excellent” พบเอกสารที่มี “great” ด้วย
- เมื่อนำกฎเดียวกันมาใช้กับโค้ด ความหมายจะคลาดเคลื่อน
- ใน TypeScript
theไม่ใช่คำหยุด แต่อาจเป็น ชื่อวาริเอเบิลที่ถูกต้อง ซึ่งต้องการค้นหา - ขอบเขตคำในโค้ดต่างจากภาษาธรรมชาติ
- การนำการหา stem ไปใช้กับชื่อฟังก์ชันก็ยากที่จะคาดหวังผลลัพธ์ที่มีความหมาย
- ใน TypeScript
to_tsvector('english', ...)ของ Postgres เปลี่ยนข้อความต้นฉบับอย่างมากระหว่างทำดัชนีประโยคภาษาธรรมชาติI am writing this example sentenceจะถูกแปลงเป็นประมาณ'exampl':5 'sentenc':6 'write':3
- ในโค้ด ปัญหาการ tokenization จะเด่นชัดยิ่งขึ้น
function stringifyNumber(a: number): string { return a.toString() }ถูกทำดัชนีเป็นประมาณ'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2- คำอย่าง
functionยังคงอยู่ ส่วนa.toString()ไม่ถูกแยกเป็นสองโทเคนเพราะ.ไม่ใช่ขอบเขตคำตามค่าเริ่มต้น
ข้อดีข้อเสียของ Postgres Full Text Search
- Postgres มีส่วนขยาย Full Text Search และ Render ซึ่งเป็นผู้ให้บริการโฮสติ้งของ Val Town ก็รองรับด้วย
- Val Town ใช้ Postgres อย่างจริงจังมาจนถึงตอนนี้ และ Postgres ถูกมองว่าเป็นเทคโนโลยีที่มีเอกสารและการรองรับบนโฮสติ้งดี
- สำหรับทีมเล็ก การทำให้โครงสร้างพื้นฐานเรียบง่ายที่สุดเท่าที่ทำได้เป็นเรื่องสำคัญ หากแก้ด้วย Postgres ได้ ก็มีแรงจูงใจสูงที่จะใช้ Postgres
- อย่างไรก็ตาม โปรเจกต์ก่อนหน้าที่ใช้ FTS เคยเจอปัญหาด้านประสิทธิภาพและการขยายตัว
- Observable สุดท้ายย้ายไป Elasticsearch
- Val Town มี vals จำนวนมาก และกำลังทดสอบขีดจำกัดของคลัสเตอร์ Postgres โหนดเดียว
- เนื่องจากหากรณีที่ใช้ FTS กับการค้นหาโค้ดได้สำเร็จได้ยาก จึงยังเก็บไว้เป็นแผนสำรองมากกว่าจะใช้เป็นตัวเลือกแรก
การทดลองค้นหา v2 บน pg_trgrm
- อัลกอริทึมค้นหา v2 ที่ Val Town ซอฟต์ลอนช์นั้นอิงกับ
pg_trgrmของ Postgrespg_trgrmใช้การ ค้นหาแบบ trigram ใน Postgres
- ในการค้นหาโค้ด trigram มีกรณีสำเร็จอยู่แล้ว
- บทความปี 2012 ของ Russ Cox กล่าวถึงกรณีที่ Google Code Search ใช้ดัชนี trigram และการใช้งาน regular expression แบบพิเศษ
- ระบบค้นหาโค้ดใหม่ ของ GitHub ก็ใช้การค้นหาแบบ trigram
- Sourcegraph มีเครื่องมือค้นหาบน trigram ที่สืบต่อมาจาก Google
- แนวทาง Postgres
pg_trgrmของ Val Town ได้รับอิทธิพลมากจากบทความของ Stephen Gutekanst เกี่ยวกับการทำดัชนี repository ในเครื่องด้วย Postgres - การติดตั้งใช้งานคือใส่ดัชนี GIN พร้อม
gin_trgm_opsให้กับคอลัมน์ที่มีข้อความสำหรับค้นหา pg_trgrmเป็นวิธีแก้ที่ดีสำหรับการค้นหาด้วย regular expression แต่ไม่ค่อยเหมาะกับคิวรีที่อิสระกว่าอย่างการค้นหาส่วนใหญ่ของ Val Town- ตอนนี้ใช้ word_similarity สำหรับการจัดอันดับผลค้นหา
- การปรับอัลกอริทึมให้เข้าใกล้อันดับที่สมเหตุสมผลนั้นทำได้ยากมาก
ตัวเลือก search engine และการแลกเปลี่ยนด้านปฏิบัติการ
- ตัวเลือกที่พิจารณามีทั้งบริการค้นหาแบบ standalone และส่วนขยายของ Postgres ปะปนกัน
- Meilisearch: standalone, Rust, 41k stars
- Typesense: standalone, C++, 17k stars
- Zoekt: standalone, Go, 406 stars
- ParadeDB: ส่วนขยาย Postgres, Rust, 3.2k stars
- Sonic: standalone, Rust, 19.4k stars
- มีเครื่องมือเฉพาะสำหรับโค้ดอยู่ แต่ส่วนใหญ่เป็นระบบปิด
- การค้นหาของ GitHub ยอดเยี่ยม แต่เป็นผลลัพธ์จากทีมเฉพาะทางและงบเวลาจริง
- fork ของ Zoekt ที่ Sourcegraph ดูแลนั้นน่าสนใจ แต่เป็นสิ่งเฉพาะทางมาก และต้องลงทุนโครงสร้างพื้นฐานใหม่ครั้งใหญ่
- Elasticsearch อาจกลายเป็นวิธีแก้ที่หลีกเลี่ยงไม่ได้ในท้ายที่สุด
- แม้ไม่มีการประมวลผลเฉพาะสำหรับโค้ด แต่สามารถปรับแต่งได้แทบไม่จำกัด
- ภาระคือการเรียนรู้การจูนหน่วยความจำ Java, การนำ persistent disk storage ตัวแรกเข้ามาในแอปพลิเคชัน และการจัดการแหล่งความจริงเพิ่มเติมของข้อมูล
- หากใช้ Elasticsearch Cloud อาจช่วยลดภาระการบำรุงรักษาได้
- Meilisearch ดูมีแนวโน้มในฐานะทางเลือกแทน Elasticsearch
- ความที่ใช้ Rust เป็นจุดดึงดูด
- ในบทความเปรียบเทียบของตัวเอง ดูเหมือนจะเน้น latency มากกว่าการขยายตัว และยังไม่ชัดเจนว่าภาระโครงสร้างพื้นฐานจะต่ำกว่าหรือไม่
- ParadeDB น่าสนใจตรงที่ทำงานคล้าย Elasticsearch แต่เป็น “แค่ Postgres”
- อย่างไรก็ตาม Render ยังใช้ส่วนขยายนี้ไม่ได้
ภาระของทีมเล็กในการเลือกโครงสร้างพื้นฐานด้านค้นหา
- การค้นหาโค้ดยากกว่าการค้นหาภาษาอังกฤษ
- ทีมเล็กมีแรงจูงใจที่จะทำให้โครงสร้างพื้นฐานเรียบง่าย ตั้งค่าสภาพแวดล้อมพัฒนาได้ง่าย และเก็บข้อมูลไว้ที่เดียวกัน
- Val Town ไม่ต้องการรีบผูกตัวเองกับตัวเลือกที่ต้องการการดูแลต่อเนื่อง
- บริษัทขนาดกลางถึงใหญ่มีไม่ใช่แค่ “บริการ” ค้นหา แต่มี “ทีม” ค้นหา ด้วยเหตุผลบางอย่าง
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
อยู่ที่ Sourcegraph และแม้การรองรับสเกลใหญ่จะจำเป็นแน่นอน แต่ถ้าจะใส่การค้นหาโค้ดเข้าไปในผลิตภัณฑ์เป็นครั้งแรก ผมแนะนำว่าอย่าเริ่มจาก ดัชนี ตั้งแต่ต้น แต่ให้ใช้การค้นหาแบบทำทันทีไปจนกว่าจะชนข้อจำกัด
ในกรณีที่ต้องหาแค่ผลลัพธ์ N รายการแรก ไม่จำเป็นต้องไล่ดูทั้งหมดจนจบก็เติมบัฟเฟอร์ผลลัพธ์ได้แล้ว จึงอยู่ได้นานกว่าที่คิด ยินดีมากที่จะคุยกับคนที่ทำสิ่งแบบนี้ รวมถึงคนฝั่ง Val Town ด้วย
Sourcegraph เคยรับหน้าที่ดูแล Zoekt มาก่อน และ Livegrep กับ Hound ก็รับมือได้ลำบากในหลายด้านกับสเกลที่เราต้องการทำดัชนี หลังย้ายจากการ deploy OpenGrok ที่เก่าและง่อนแง่นมาเป็น Zoekt ความแตกต่างทั้งด้านประสิทธิภาพการทำดัชนีและประสิทธิภาพ/ความสะดวกในการค้นหานั้นชัดเจนมาก Sourcegraph วางฟีเจอร์ที่ซับซ้อนกว่ามากไว้บนการค้นหาโค้ดที่ Zoekt ให้มา
เช่น GritQL(https://github.com/getgrit/gritql) ผมเคยคิดเสมอว่าสุดท้ายก็คงต้องมีดัชนีเพื่อความเร็ว แต่จนถึงตอนนี้ก็ยังพอไปได้ดีด้วยการค้นหาแบบทำทันทีทั้งหมด
ถ้าไม่มีแคช การดูแลให้ถูกต้องจะง่ายกว่ามาก
สิ่งที่เข้า L2 cache ได้ทำงานได้เร็วมากจริง ๆ
การค้นหาโค้ดยากจริง ๆ และ แพลตฟอร์มค้นหาโค้ด ที่ดีทำให้ชีวิตง่ายขึ้นมาก
ถ้าต้องออกจาก Google สิ่งที่น่าจะคิดถึงที่สุดคือการค้นหาโค้ดภายใน มันผสานกับ workflow ทุกอย่างได้ดีมาก เช่น การหาเป้าหมาย blaze, guice binding ฯลฯ จนจินตนาการไม่ออกว่าจะทำงานโดยไม่มีมันได้อย่างไร ทุกครั้งที่ใช้การค้นหาของ GitHub ก็ยิ่งรู้สึกถึงคุณค่านี้มากขึ้น ไม่ใช่ว่าการค้นหาของ GitHub แย่ แต่เพราะการสร้างแพลตฟอร์มค้นหาโค้ดแบบอเนกประสงค์นั้นยากกว่ามากโดยเนื้อแท้
ตอนนี้ผมไม่ได้ใช้ส่วนตัว แต่เป็นของที่ยอดเยี่ยมและน่าจะตอบโจทย์ส่วนใหญ่ได้ https://github.com/livegrep/livegrep
ถ้าหาผู้ให้บริการหรือจุดที่ใช้งานได้โดยตรงจากช่องค้นหาก็คงดี
ทักษะพื้นฐานในการค้นหาโค้ด มักไม่ได้สอนนักพัฒนาใหม่อย่างชัดเจน แต่ดูเหมือนเป็นความสามารถหลักที่ควรเรียนรู้ตั้งแต่ช่วงแรก
ขั้นตอนที่แนะนำคือเรียนรู้การค้นหาแบบที่ใช้ได้ทุกที่เหมือน Ctrl+F แล้วค่อยขยับไปใช้ ripgrep(https://github.com/BurntSushi/ripgrep) นี่ไม่ใช่แค่ตัวเลือกเสริม แต่เป็นเครื่องมือที่ยอดเยี่ยมและค้นพบได้ง่ายจริง ๆ และการต้องเปิดเทอร์มินัลไว้ก็กลับเป็นเรื่องดีสำหรับมือใหม่ด้วย ถ้าเป็นไปได้ ควรเรียนรู้ command-line editor ที่ทรงพลังสักตัวด้วย สมัยก่อนผมคงแนะนำ Emacs แต่ตอนนี้แนะนำ vim รุ่นพื้นฐานที่ติดตั้งอยู่แทบทุกที่ เพราะ grep และแก้ไขในหน้าต่างเดียวกันได้ จากนั้นค่อยเรียนรู้การทำงานที่ ripgrep ทำให้เป็นค่าเริ่มต้นด้วย grep รุ่นเก่า เช่น
grep -r,grep -ri,grep -rilและสุดท้ายเมื่อชนข้อจำกัดของ ripgrep แล้วค่อยย้ายไปใช้เครื่องมือค้นหาโค้ดเฉพาะทางที่ใช้ดัชนีจริง ๆgit grepแปลกใจที่ไม่มีการกล่าวถึง hound(https://github.com/hound-search/hound)
เคยคิดว่านี่เป็นหนึ่งในโซลูชันโอเพนซอร์สแถวหน้าของสายนี้ ผมใช้ instance ของ Wikimedia(https://codesearch.wmcloud.org/search/) มา และโดยรวมก็พอใจ
https://codesearch.wmcloud.org/search/?q=test&files=&exclude... ในกรณีของผมใช้เวลา 13 วินาทีเพื่อสร้าง response JSON ขนาด 55MB และยังต้องใช้เวลาอีกหลายวินาทีในการ render กลับเข้า DOM ด้วย Zoekt JSON API ที่ใช้ใน neogrok จำเป็นต้องมีการจำกัดขนาด response การค้นหาอย่างถูกต้อง จึงต้องทำให้รับประกันเรื่องนี้ได้: https://github.com/sourcegraph/zoekt/pull/615
นี่คือเหตุผลที่คนทำ IDE และเครื่องมือสำหรับนักพัฒนามองกันมานานแล้วว่า ถ้าจะทำการค้นหาโค้ดให้ได้ดีจริง ๆ ต้องเปิด แพลตฟอร์มคอมไพเลอร์ ออกมา
เพราะงานที่จำเป็นจำนวนมาก สุดท้ายก็คือการสร้าง representation ภายในที่คอมไพเลอร์ใช้อยู่ขึ้นมาใหม่ การค้นหาโค้ดที่ดีเป็นรากฐานของการรองรับการรีแฟกเตอร์ การเติมโค้ดอัตโนมัติ และฟีเจอร์ IDE ทั่วไปอีกหลายอย่างด้วย แน่นอนว่ามันไม่ง่ายอย่างที่พูด ฝั่งที่ทำคอมไพเลอร์มักปล่อยให้เครื่องมือเป็นเรื่องรอง และ JetBrains ก็เคยพลาดแบบนี้ในช่วงแรกของ Kotlin ตอนนี้กำลังแก้บางส่วนใน Kotlin 2.0 เพื่อให้รองรับสิ่งอย่าง incremental compilation ได้ง่ายขึ้น ชุมชน Rust ก็ได้ insight แบบเดียวกันเมื่อไม่กี่ปีก่อน ตอนที่ทุ่มแรงครั้งใหญ่เพื่อทำให้เป็นมิตรกับ IDE มากขึ้น IBM เคยทำเรื่องนี้ได้อย่างถูกต้องใน Eclipse ยุคก่อน และหลังจากนั้นก็แทบไม่มีใครตามทัน IntelliJ ช้ากว่าราว 2–3 หลัก ทำให้ต่างกันระดับวินาทีกับมิลลิวินาที Eclipse มี incremental compiler สำหรับ Java ที่เร็วมาก ซึ่งยังคอมไพล์บางส่วนได้แม้มี syntax error และ representation ของโค้ดใน IDE ก็เชื่อมกับคอมไพเลอร์นั้นอยู่ ถ้าพิมพ์ผิดจนทำให้โค้ดบางส่วนพัง ไฟล์ที่มีปัญหาทั่วทั้ง codebase จะแสดงขีดเส้นใต้สีแดงขึ้นมาทันที และเมื่อแก้คำผิดก็หายไปโดยไม่หน่วง เรื่องนี้เป็นไปได้เพราะต้องมี mapping ระหว่างไฟล์กับ syntax tree และ Eclipse ทำได้เพราะเชื่อมกับ incremental compiler ส่วน IntelliJ ทำไม่ได้ จึงมักหลอกสถานะดี/เสียอย่างกระตือรือร้นจนกว่าจะ rebuild และถ้า state ภายในไม่ตรงกับดิสก์ก็จะแสดง error ปลอมจำนวนมาก พอรันแล้วมีการหน่วงคอมไพล์อยู่หลายวินาที ถึงตอนนั้นบางครั้งจึงค่อยรู้ว่าสถานะที่ IDE แสดงว่ารันได้ก่อนหน้านั้นผิด ใน Eclipse ทุกอย่างนี้เกิดขึ้นทันทีและชัดเจน เพราะแชร์ state ภายในกับคอมไพเลอร์ แม้จะมีข้อบกพร่องและบั๊กน่ารำคาญอยู่มาก แต่ฟีเจอร์นั้นก็ยังน่าคิดถึง
https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
https://ericlippert.com/2012/06/08/red-green-trees/
เคยลองทำเครื่องมือด้วย Roslyn SDK แล้วดีมากจริง ๆ
นี่เป็นเหตุผลหลักที่คนจำนวนมากไม่ย้ายไป IDE ตัวอื่น
เมื่อก่อน GitHub ดูเหมือนเคย “แก้” ด้วยการแยก
a.toString()ออกเป็นสอง token ซึ่งค่อนข้างน่ารำคาญGitHub กำลังเพิ่มความสามารถการค้นหาตำแหน่งใช้งานแบบ IDE อยู่ แต่ยังไม่สมบูรณ์ บางครั้งจึงอยากทำ text search อย่าง
"foo.bar()"เพื่อหาจุดใช้งานที่ตกหล่น แต่พฤติกรรมการทำ stemming แบบนี้ทำให้ค้นเจอทุกตำแหน่งที่มีการกล่าวถึง foo และ bar แยกกันด้วย จนผลลัพธ์บวมขึ้นมาไม่เข้าใจว่าทำไมถึงปัด Zoekt ผ่านไปง่าย ๆ
มันถูกสร้างมาเพื่อจุดประสงค์นี้โดยตรง และก็ไม่ได้เพิ่ม ภาระโครงสร้างพื้นฐานใหม่ มากกว่าทางเลือกอื่น ๆ เซิร์ฟเวอร์ก็เป็น binary เดียว ตัวทำดัชนีก็เป็น binary เดียว จะให้เรียบง่ายกว่านี้คงยาก ไม่เห็นเหตุผลว่าทำไมต้องกลัว Zoekt มากกว่า Elasticsearch
หนึ่งในแนวทางค้นหาโค้ดที่น่าสนใจที่สุดที่ได้เห็นช่วงหลังคือ septum: https://github.com/pyjarrett/septum
มองว่าส่วนที่ยากที่สุดของการทำ code search ให้ดีคือการดึง บริบทแวดล้อม ในปริมาณที่เหมาะสมมาให้ได้ และ septum เป็นเครื่องมือที่พยายามแก้ปัญหานี้ในระดับไฟล์ อีกอย่างที่แปลกใจที่ไม่ถูกกล่าวถึงคือ stack-graphs(https://github.com/github/stack-graphs) ซึ่งพยายามตีความความสัมพันธ์ของสัญลักษณ์ทั่วทั้ง codebase แบบค่อยเป็นค่อยไป มันขับเคลื่อน precise index ข้ามไฟล์ของ GitHub และในเชิงแนวคิดก็สมเหตุสมผล แต่เคยเจอปัญหาในการทำให้เวอร์ชันโอเพนซอร์สทำงานได้
Oracle มี view USER/ALL/DBA_SOURCE และโค้ด PL/SQL(SQL/PSM) ทั้งหมดที่โหลดอยู่ในฐานข้อมูลจะปรากฏในนั้น
ถ้าไม่ได้ตั้งใจทำ obfuscation ไว้ ทุกอย่างจะเห็นเป็นข้อความธรรมดา มีคอลัมน์ owner, object name, LINE[NUMBER], TEXT[VARCHAR2(4000)] และสามารถใช้
LIKEหรือregexp_like()กับซอร์สโค้ดที่เก็บไว้ได้ สงสัยว่า EnterpriseDB ทำสิ่งนี้ไว้ใน Postgres แล้วหรือยัง หรือมีให้เป็น extension ส่วนใหญ่ของ SQL/PSM ก็มาจาก Oracle อยู่แล้ว จึงเป็นฟีเจอร์ที่คาดหวังได้อยู่แล้ว https://en.wikipedia.org/wiki/SQL/PSMบอกว่า “การค้นหาของ GitHub ยอดเยี่ยม” แต่มันเป็นแบบนั้นจริงหรือ?
ส่วนใหญ่แล้วรู้สึกว่าแทบใช้ประโยชน์ไม่ได้ และการ clone มาแล้วใช้ ripgrep มีประสิทธิภาพกว่ามาก ปัญหาอาจอยู่ที่ UX แย่มาก มากกว่าตัวการค้นหาจริง ๆ