Solidity 102 #2: เขียนโค้ดอย่างไรให้ใช้ Map แบบคูลๆ ❄️

บทความนี้แปลมาจากบทความ ที่เขียนโดย Bun Uthaitirat จาก Band Protocol

บทความนี้เป็นบทความที่สองในซี่รีส์ “Solidity 102” ซึ่งเขียนโดย Band Protocol มีเนื้อหาเกี่ยวกับ data structure และเทคนิคในการเขียนโค้ด solidity อย่างมีประสิทธิภาพบน EVM ซี่รีส์นี้จึงเหมาะกับผู้อ่านที่พอคุ้นเคยกับภาษา solidity และเข้าใจคร่าวๆว่า EVM ทำงานอย่างไร

จากบทความที่แล้ว(เรื่อง เขียนโค้ดอย่างไรไม่ให้ gas cost บานปลาย) เราได้อธิบายถึงเรื่องเทคนิคการเขียน Solidity ให้ใช้ gas อย่างมีประสิทธิภาพมาแล้ว ดังนั้นในบทความนี้ เราจะมาอธิบาย data structure ที่จำเป็นต่อการ dev มากๆอันหนึ่งคือ Iterable Map ก่อนที่จะเล่าถึงว่ามันทำงานยังไง คงต้องเริ่มจากปัญหาที่เกิดขึ้นก่อน ใน Solidity นั้นเวลาเราใช้ mapping เราไม่สามารถที่จะวนลูป (Iteration) บน Mapping ตรงๆได้เลย เราต้องใช้ตัวช่วยเช่น การสร้าง Array มาเก็บ Key ของ mapping ทั้งหมด แต่วิธีนี้ก็ทำให้ค่า gas เพิ่มขึ้นมา (Gas cost overhead) ดังนั้นวิธีที่เราจะใช้ในบทความนี้จะลดค่า gas ที่เพิ่มขึ้นให้น้อยที่สุด โดยเราจะยกตัวอย่างพร้อมทั้งผลลัพธ์ของการใช้ gas ในวิธีต่างๆ โอเค ถ้าพร้อมแล้วไปลุยกัน!!

โจทย์ตัวอย่าง

สมมุติว่าเราต้องการเก็บรายชื่อนักเรียนทั้งหมดของโรงเรียนแห่งหนึ่งลงไปใน Blockchain โดย function ที่เราต้องการมีดังนี้

• เพิ่มรายชื่อนักเรียน (addStudent)
• ลบรายชื่อนักเรียน (removeStudent)
• สอบถามว่านักเรียนคนนี้ (Address) อยู่ที่โรงเรียนนี้ไหม (isStudent)
• รายชื่อทั้งหมดของนักเรียน (getStudents)

ก่อนอื่นเลยเราก็เขียน function ที่ต้องการก่อน

function ทั้งหมดที่เราต้องการใช้

วิธีแก้ปกติทั่วไป(ซึ่งไม่ค่อยดีเท่าไหร่)

มี 2 วิธีที่สามารถแก้ปัญหาได้(ซึ่งบางวิธีก็ทำได้ไม่ทุก function) โดยแต่ละวิธีก็มีข้อดีข้อเสียต่างกันไป ดังนั้นเราเขียนตัวอย่างทั้ง 2 แบบพร้อมทั้งเปรียบเทียบให้ดู

เริ่มจากวิธีที่ 1 ใช้ mapping(address ⇒ bool)

เราใช้ mapping ในการเก็บว่านักเรียนคนไหนอยู่ในโรงเรียนบ้าง ถ้าเราถามโดยใช้ address แทนตัวนักเรียนแล้วได้ค่ากลับมาเป็น true แสดงว่ามีนักเรียนคนนี้อยู่ในโรงเรียนด้วย ซึ่งมันดูง่ายก็จริงแต่ว่ามันก็มีข้อจำกัดเช่น กัน อย่างเช่นถ้าอยากได้รายชื่อนักเรียนทุกคนในโรงเรียน(สำหรับ function getStudents) อันนี้ก็เริ่มลำบากละ ลองดูจากภาพตัวอย่างโค้ด

วิธีที่ 1 เราใช้ mapping เพื่อเก็บ address ของนักเรียน แต่วิธีนี้ก็ไม่สามารถวนลูปบน Mapping ได้

เริ่มจากวิธีที่ 2 ใช้ Array (address[ ] students)

สำหรับวิธีนี้เราเก็บรายชื่อนักเรียนลงใน array แทนการเก็บลง mapping ซึ่งเห็นได้ชัดว่าสามารถทำให้ function getStudents ใช้งานได้ แต่ถึงแบบนั้นการที่จะหาหรือลบนักเรียนออกจากโรงเรียนกลับทำได้ยากขึ้นกว่าเดิมเพราะ เราต้องมาลูป (Iteration) บนทุกๆ index ของ array เพื่อจะหาว่านักเรียนคนนั้นๆ(address) อยู่ในรายชื่อไหม ลองดูจากภาพตัวอย่างโค้ด

วิธีที่ 2 เราใช้ array ซึ่งการหานักเรียนในรายชื่อนั้นทำให้ประสิทธิภาพแย่ลงอย่างมาก

เอาล่ะจากตัวอย่างทั้งสองแบบ เราจะมาเปรียบเทียบกัน

เราเปรียบเทียบจากการสั่งเพิ่ม(addStudent) และ ลบ(removeStudent) นักเรียนออกจากรายชื่อเพื่อเช็คค่า gas ของแต่ละ function ของทั้งสองวิธี โดยเราทดสอบกับจำนวนนักเรียน 10 คนและ 100 คน ผลที่ได้ดังนี้

ตารางการเปรียบเทียบวิธีที่ 1 กับ 2 สำหรับนักเรียน 10 และ 100 คน

หมายเหตุ วิธีลบ (removeStudent) นักเรียนเราใช้วิธีสลับตำแหน่งของนักเรียนที่ต้องการลบไปไว้ช่องสุดท้ายของ array แล้วนำมันออกจาก array (pop) ซึ่งยังไงก็ต้องใช้ O(n) เท่ากับการลูปในการหาตำแหน่งของนักเรียนที่ต้องการลบอยู่ดี

จากทั้งสองวิธีที่กล่าวมา เราจะเห็นได้เลยว่า mapping เป็นวิธีที่มีประสิทธิภาพมากกว่าแต่มันก็ไม่สามารถตอบโจทย์ให้กับทุก function ที่เราต้องการ ส่วน array สามารถทำได้ทุก function แต่ก็มาพร้อมกับ gas cost ที่เพิ่มขึ้นตามจำนวนรายชื่อนักเรียน ด้วยเหตุนี้เราจึงต้องการวิธีที่ดีกว่านี้

แล้ววิธีที่ดีกว่านี้ละ

วิธีนี้เราได้นำแนวคิดมาจาก data structure ชนิดหนึ่งนั้นก็คือ linked-list โดยเราจะเก็บ address ของนักเรียนคนถัดไปเป็นค่าของ mapping แทนที่ค่า boolean เหมือนที่เราเก็บกันในวิธีที่ 1 เหมือนภาพตัวอย่าง

รูปแบบข้อมูลแบบ Linked-List(ด้านบน) และ Linked-List ในรูป Key-value mapping(ด้านล่าง)

โดยเราสามารถเขียนได้ดังนี้

สร้างค่าเริ่มต้นของ Linked-List โดยให้ตัวแรกสุดและ ตัวสุดท้ายคือ address ของ GUARD มีความหมายว่าเป็น list ว่าง

สร้างค่าเริ่มต้นของ Linked-List โดยให้ตัวแรกสุดและ ตัวสุดท้ายคือ address ของ GUARD ซึ่งมีความหมายว่าเป็น list ว่าง

โดยแต่ละ function จะมีลักษณะดังนี้

1. ตรวจสอบว่านักเรียนอยู่ในรายชื่อของโรงเรียนไหม (isStudent)

จากการที่เราเก็บในรูปแบบ mapping(address ⇒ address) ทำให้เราสามารถตรวจสอบได้เลยว่า address ของนักเรียนอยู่ในรายชื่อไหม ถ้าอยู่ค่าที่ mapping ชี้ไปต้องไม่ใช่ address 0 เหมือนโค้ดในภาพ

ตัวอย่างโค้ด function isStudent

2. เพิ่มนักเรียนเข้ารายชื่อของโรงเรียน (addStudent)

สำหรับการเพิ่มนักเรียนเข้ารายชื่อ เราจะเพิ่มโดยการให้ต่อหลัง GUARD หมายถึงว่าให้ mapping ของ GUARD ชี้ไปหา address ที่เราต้องการเพิ่ม(New Student)เพราะเรามองว่า GUARD เป็น HEAD ของ list ต่อมาเราจะให้ mapping ของ address(New Student) ชี้ไปยัง address(Front Student) ที่ GUARD เคยชี้ไว้ก่อนหน้าจะเพิ่มนักเรียนเข้ามา จากภาพด้านล่างจะแสดงทั้งขั้นตอนของการเพิ่มและ ตัวอย่างโค้ด

ขั้นตอนการเพิ่มนักเรียนเข้าไปใน list

ตัวอย่างการโค้ดการเพิ่มนักเรียน

3. ลบนักเรียนออกจากรายชื่อ (removeStudent)

สำหรับ function นี้สามารถมองส่วนประกอบเป็น 3 ส่วนได้แก่

• address ของนักเรียนที่ชี้มายังนักเรียนที่ต้องการจะลบ (Previous Student)
• address ของนักเรียนที่ต้องการจะลบ (Removed Student)
• address ของนักเรียนที่ถูกชี้โดย mapping ของ address ของ Removed Student (Next Student)

โดยวิธีการของเราก็คือ ย้ายเป้าหมายการชี้ของ Previous Student มายัง Next Student แทน Removed Student แล้วเปลี่ยนเป้าหมายการชี้ของ Removed Student ไปยัง address 0 ดังในภาพและตัวอย่างโค้ด

ขั้นตอนการลบนักเรียนออกจาก list

ตัวอย่างโค้ดการลบนักเรียน

แต่การที่จะหา Previous Student ไม่ใช่เรื่องง่าย ถึงแม้เราจะใช้ Doubly Linked List ซึ่งการใช้มันก็ทำให้ค่า gas เพิ่มขึ้นอย่างชัดเจนอีก ดังนั้นเราจำเป็นต้องสร้าง function ชื่อ _getPrevStudent มาเพิ่มเพื่อหา Previous Student ดังโค้ดในภาพ

ตัวอย่าง function _getPrevStudent

4. แสดงรายชื่อนักเรียนทั้งหมด (getStudents)

สำหรับ function นี้ เราก็แค่ลูปทุกๆ mapping โดยเริ่มตั้งแต่ address ของ GUARD จากนั้นก็นำ address ที่ GUARD ชี้ไปเพื่อหา address ถัดไปเรื่อยๆ จนกระทั่งไปจบที่ GUARD ซึ่งเป็นตัวสุดท้ายของ list นี้ ดังโค้ดในภาพ

ตัวอย่าง function getStudents

จริงๆ แล้วเรายังสามารถเพิ่มประสิทธิภาพได้อีก

ถ้าสังเกต function ที่ชื่อ removeStudent เราทำการลูปเพื่อหา Previous Student จากทั้งหมดของรายชื่อทำให้ค่า ​gas ที่ต้องใช้จะเพิ่มขึ้นตามจำนวนของนักเรียน เราสามารถเพิ่มประสิทธิภาพโดยการหา Previous Student มาก่อน(Off-Chain) แล้วค่อยส่งเข้า function เพื่อไปตรวจสอบอีกครั้งว่าเป็น Previous Student รึป่าว ดังภาพ

ตัวอย่าง function removeStudent แบบ Off-Chain

เปรียบเทียบประสิทธิภาพระหว่าง removeStudent แบบเก่ากับแบบใหม่

เราได้ทดสอบ function ชื่อ addStudent, removeStudent ทั้งแบบ optimized และ unoptimized ซึ่งแบบ optimized จะใช้ค่า gas เป็นค่าคงที่ O(1) เท่านั้นไม่ว่าจะมีจำนวนรายชื่อนักเรียนมากเท่าไรก็ตาม

จากการทดสอบ function ทั้ง 3 แบบ โดย function add กับ remove จะใช้ค่า gas คงที่ (O(1)) ไม่ว่ารายชื่อนักเรียนเท่าไรก็ตาม

สรุป

เป็นยังไงกันบ้างครับสำหรับเนื้อหาที่ผ่านมา เราได้เริ่มอธิบายจาก data structure พื้นฐานทั้ง mapping และ array โดยทั้งคู่ไม่สามารถเพื่ม, ลบและ หานักเรียนภายใน O(1) ได้เลย อีกทั้งการใช้ mapping ทำให้ไม่สามารถลูปได้อีก หลังจากนั้นเราก็นำเสนอการใช้ data structure แบบ linked-list ซึ่งจากการทดลอง ผลลัพธ์ก็ออกมาเป็นที่น่าพอใจ สำหรับในบทความต่อไปเราจะมาหาว่า data stucture แบบไหนอีกที่สามารถนำมาใช้ได้อย่างมีประสิทธิภาพ ขอบคุณครับ

Band Protocol เป็นแพลตฟอร์มที่สนับสนุนให้ทุกคนมีส่วนร่วมในการสร้างข้อมูลที่ถูกต้องเข้าสู่โลก blockchain โดยพวกเราเป็นทีม developer ที่อยากจะเชื่อมต่อโลกความจริงกับโลกของ blockchain เข้าด้วยกัน และถ้าคุณเป็น developer ที่มีความสนใจในด้านนี้และอยากร่วมงานกับเรา ติดต่อเราได้ที่ talent@bandprotocol.com