treee
Update with Windows10 and MacOS executables
เอ็นจิ้นการจัดทำดัชนีอย่างรวดเร็วสำหรับข้อมูลที่ระบุโดย Hashed ID และเก็บไว้ในไฟล์ที่ไม่เปลี่ยนรูป
นี่คือการใช้งาน GO ของเอ็นจิ้นการทำดัชนี Treee ™ มันเป็นทั้งห้องสมุดที่ใช้เป็นโมดูลในโครงการ GO ของคุณและการดำเนินการเพื่อทำงานเป็นบริการขนาดเล็กเหนือ HTTP
ความท้าทายคือการตั้งค่าเครื่องมือค้นหาที่มีประสิทธิภาพและปลอดภัยที่จะใช้เมื่อข้อมูลเป็นรายการที่เชื่อมโยงบางรายการที่สามารถเชื่อมต่อกันในเครือข่ายย่อยจัดทำดัชนีผ่านตัวระบุที่ทำจากค่าแฮชเท่านั้น (เช่นการเป็นตัวแทนสตริง SHA-256)
แอปพลิเคชั่นที่ดีที่สุดของมันคือไฟล์ blockchain ที่รายการคือการทำธุรกรรมฝังสัญญาอัจฉริยะและแต่ละรายการย่อยของรายการการใช้งานที่ตามมาและ/หรือการดัดแปลงของสัญญาอัจฉริยะนี้ ดังนั้นดัชนี Treee ™จึงถูกใช้ใน Rooot ™ blockchain
เรากำหนดอัลกอริทึมที่นี่สำหรับการจัดทำดัชนีระบบตามตัวระบุที่เป็นค่าแฮชซึ่งในเวลาเดียวกันมีประสิทธิภาพมากสำหรับการเขียนและการอ่าน
ดัชนี Treee ™ถูกสร้างขึ้นเป็นกราฟ acyclic (ต้นไม้) แต่ละโหนดมีที่อยู่โหนด (บุตรชาย) หรือชุดของ ใบไม้ ซึ่งเป็น ใบ ที่สอดคล้องกับข้อมูลที่ช่วยดึงรายการที่เชื่อมโยงอย่างน้อยหนึ่งรายการ
จำนวนบุตรของโหนดมีการกำหนดและขึ้นอยู่กับความลึกของต้นไม้ เราแสดงถึงจำนวนบุตรชายของโหนดที่ระดับความลึก 1 จำนวนบุตรของโหนดที่ระดับความลึก 2, ... จำนวนบุตรที่ลึก
เป้าหมายคือการสร้างต้นไม้ที่สมดุลซึ่งมีความกว้างปรับตัวเพื่อลดความลึกและเพิ่มประสิทธิภาพประสิทธิภาพ เรากำลังมองหาหมายเลขดัชนีในกรณีนี้ค่าตัวเลขของตัวระบุที่ไม่ซ้ำกันของรายการ
เรามาอธิบายหลักสูตรของดัชนี
สำหรับต้นไม้ไบนารีเราเขียนหมายเลขในรูปแบบไบนารี (ตัวอย่างเช่น 100 ) ซึ่งระบุตำแหน่งของมันในต้นไม้
ในขั้นตอนเราจะส่งต่อไปยังเด็กถ้าบิตเป็น 0 มิฉะนั้นเราจะส่งต่อไปยังเด็กถ้าบิตคือ 1 เราหยุดเมื่อโหนดเป็น ใบไม้
สำหรับต้นไม้เราสร้างการแสดงหมายเลขนี้ตามลำดับของตัวเลขและเราสำรวจต้นไม้ในลักษณะเดียวกัน ในขั้นตอนของความลึกเราส่งต่อไปยังเด็กหากตัวแทนคือ 0 เราส่งต่อไปยังเด็กถ้าตัวแทนคือ 1 , ... เราส่งต่อไปยังเด็กถ้าตัวแทนคือ เราหยุดเมื่อโหนดเป็น ใบไม้
ในการสร้างการเป็นตัวแทนของตัวเลขเราจะใช้โมดูโลของจำนวนนายกอย่างต่อเนื่อง ตามทฤษฎีบทของซากศพจีนแต่ละหมายเลขมีตัวแทนที่ไม่ซ้ำกันซึ่งสามารถเขียนได้ว่าเป็นความต่อเนื่องของโมดูโลเหล่านี้ แน่นอนตัวเลขสามารถเขียนในรูปแบบต่อไปนี้:
ค่าของตัวระบุของรายการ (หมายเลขของมัน) จะถูกแสดงและจำนวนการปรับ โมดูโลถูกคำนวณในจำนวนเต็มขนาดคงที่ เนื่องจากการคูณนั้นเร็วกว่าการแบ่ง (จำเป็นสำหรับการคำนวณโมดูโล) จึงสามารถใช้การคูณโดยการลอยตัว:
เมื่อพิจารณาถึงลักษณะการสุ่มของตัวเลข (หรือหลอกเทียมเนื่องจากตัวระบุของรายการถูกสร้างขึ้นโดยเทคโนโลยีการแฮชการเข้ารหัส) ต้นไม้จึงมีความสมดุล เพื่อไม่สมดุลต้นไม้ในทางที่เป็นอันตรายจำเป็นต้องสามารถสร้างแฮชที่มีโมดูโลตามวิถีการเคลื่อนที่โดยเฉพาะ อย่างไรก็ตามความยากลำบากของการดำเนินการดังกล่าวจะเพิ่มขึ้นอย่างทวีคูณ (ของคำสั่งของความลึกคือที่ไหน) เพื่อเป็นการเตือนความจำผลิตภัณฑ์ของตัวเลขสำคัญ 16 ครั้งแรกเท่ากับ ดังนั้นทันทีที่ดัชนีมีข้อมูลจำนวนมากพอสมควรการทำให้ต้นไม้ไม่สมดุลในทางที่เป็นอันตรายจะกลายเป็นไปไม่ได้มากขึ้นเรื่อย ๆ หากเป็นไปได้
ใบไม้ มีรายการข้อมูลต่อไปนี้เกี่ยวกับรายการ:
ใบไม้ ที่มีฟิลด์รายการถัดไปว่างเปล่าเป็นรายการสุดท้ายใน subchain
ใบไม้ ที่มีฟิลด์รายการต้นกำเนิดเท่ากับตัวระบุของรายการปัจจุบันจำเป็นต้องเป็นแหล่งกำเนิดของเชนย่อย ด้วยเหตุนี้จึงมีการดำเนินงานเฉพาะตั้งแต่หากมีรายการหนึ่งหรือมากกว่านั้นหลังจากนั้นรายการสุดท้ายของเชน subchain จะถูกระบุที่นี่เป็นรายการก่อนหน้า สามฟิลด์สุดท้ายของ ใบไม้ จึงสอดคล้องกับรายการที่เชื่อมโยงวงกลม
เพื่อเพิ่มองค์ประกอบในดัชนี:
ในการอ่าน/ค้นหารายการในดัชนี:
เมื่อใช้ดัชนีเราสามารถเห็นได้ว่าเราจะทำการอ่านมากที่สุด 3 ครั้งหรือ 3 WRITES WRITES และ INDEX RUNS ของคำสั่งซื้อจำนวนรายการในดัชนีอยู่ที่ไหน
สำหรับรายละเอียดเพิ่มเติมอย่าลังเลที่จะอ่านกระดาษสีขาวเต็มรูปแบบ
$ go get github.com/cyrildever/treee import (
"github.com/cyrildever/treee/core/index"
"github.com/cyrildever/treee/core/index/branch"
"github.com/cyrildever/treee/core/model"
)
// Instantiate default index (could be any prime number up to the 1000th existing prime number,
// but should be much lower to better leverage the solution, and if 0 will use the default INIT_PRIME value)
treee , err := index . New ( index . INIT_PRIME )
if err != nil {
// Handle error
}
// Add to index
leaf := branch. Leaf {
ID : model . Hash ( "1234567890abcdef" ),
Position : 0 ,
Size : 100 ,
}
err = treee . Add ( leaf )
if err != nil {
// Handle error
}
// Search
if found , err := treee . Search ( leaf . ID ); err == nil {
// Do something with found Leaf
} เพื่อประสิทธิภาพที่ดีขึ้นคุณควรใส่คำขอค้นหาของคุณใน goroutines ที่แตกต่างกัน (ดูการใช้งาน GetLeaf() ในไฟล์ API/handlers/leaf.go เป็นต้น)
สำหรับการดีบักหรือวัตถุประสงค์ false การจัดเก็บคุณอาจต้องการใช้วิธี true PrintAll() บนดัชนี Treee เพื่อพิมพ์ใบที่บันทึกไว้ทั้งหมดไปยังนักเขียน
// To print to Stdout
fmt . Println ( treee . PrintAll ( true )) การคงอยู่ของดัชนีทำได้ผ่านการใช้บันทึกอัตโนมัติที่ทำเมื่อมีการแทรกและการใช้ฟังก์ชัน Load() แทนการสร้างอินสแตนซ์ของ Treee ด้วย New() เมื่อเริ่มต้น
treee , err := index . Load ( "path/to/treee.json" ) // If empty, will use "./saved/treee.json"มันอาจถูกปิดใช้งานโดยใช้ตัวแปรสภาพแวดล้อมที่สอดคล้องกันหรือการตั้งค่าสถานะในบรรทัดคำสั่งหรือแม้กระทั่งเป็นโปรแกรม:
treee . UsePersistence ( false ) // If you're positive you don't want itคุณสามารถสร้างการปฏิบัติการและเริ่มต้นอินสแตนซ์ของเอ็นจิ้นการจัดทำดัชนี Treee ™
$ git clone https://github.com/cyrildever/treee.git && cd treee && go build
$ ./treee -t.port 7001 -t.host localhost -t.init 101 Usage of ./treee:
-t.file string
File path to an existing index
-t.host string
Host address (default "0.0.0.0")
-t.init string
Initial prime number to use for the index (default "0")
-t.persist
Activate persistence (default true)
-t.port string
HTTP port number (default "7000")
หากตั้งค่าตัวแปรสภาพแวดล้อมต่อไปนี้จะแทนที่การกำหนดค่าเริ่มต้นที่สอดคล้องกันหรือการตั้งค่าสถานะที่ส่งผ่านด้วยบรรทัดคำสั่ง:
HOST : ที่อยู่โฮสต์;HTTP_PORT : หมายเลขพอร์ต http ที่จะใช้;INDEX_PATH : พา ธ ไปยังไฟล์ดัชนีในรูปแบบ JSON;INIT_PRIME : หมายเลขพรีย์เริ่มต้น (โปรดทราบว่าจะไม่มีผลกระทบใด ๆ หากใช้ไฟล์เพราะหลังจะเหนือกว่า);USE_PERSISTENCE : ตั้งค่า false เพื่อปิดใช้งานการใช้การบันทึกดัชนีลงในไฟล์ จุดสิ้นสุดต่อไปนี้มีอยู่ภายใต้กลุ่ม /api :
DELETE /leafจุดสิ้นสุดนี้จะลบรายการที่ผ่านออกจากดัชนี
คาดว่าอาร์เรย์ของ IDS เป็นอาร์กิวเมนต์การค้นหา ids เช่น
DELETE /api/leaf?ids=1235467890abcdef [ ... ] &ids=fedcba0987654321 [ ... ]
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)
Host: treee.io
Accept-Language: fr-FR
Accept-Encoding: gzip, deflate
Accept: application/json จะส่งคืนรหัสสถานะ 204 หากรายการที่ผ่านทั้งหมดถูกลบหรือรหัสสถานะ 200 พร้อมกับรายการ JSON ของ ID ที่ยังไม่ได้ลบต่อไปนี้หากบางรายการไม่ได้ลบ:
{
"ids" : [ " fedcba0987654321[...] " ]
}GET /leafจุดสิ้นสุดนี้ค้นหารายการตามรหัสที่ผ่าน
คาดว่าอาร์เรย์ของ IDS เป็นอาร์กิวเมนต์ ids Query และบูลีน takeLast ที่เป็นตัวเลือก (ค่าเริ่มต้นเป็น false ) เช่น http://localhost:7000/api/leaf?ids=1234567890abcdef[...]&ids=fedcba0987654321[...]&takeLast=true
มันส่งคืนรหัสสถานะ 200 พร้อมกับวัตถุ JSON ที่เกี่ยวข้องกับรูปแบบต่อไปนี้:
[
{
"id" : " 1234567890abcdef[...] " ,
"position" : 0 ,
"size" : 100 ,
"origin" : " 1234567890abcdef[...] " ,
"previous" : " 1234567890abcdef[...] " ,
"next" : " "
},
[ ... ]
] ในกรณีที่ไม่พบรายการจะส่งคืนรหัสสถานะ 404 พร้อมกับร่างที่ว่างเปล่า
GET /lineจุดปลายนี้ส่งคืน ID ทั้งหมดในสายย่อย/บรรทัดเดียวกัน
คาดว่า ID ใด ๆ ของบรรทัดเป็นอาร์กิวเมนต์ id Query เช่น http://localhost:7000/api/line?id=1234567890abcdef[...]
มันส่งคืนรหัสสถานะ 200 ยาวด้วยอาร์เรย์ที่เรียงลำดับ JSON ต่อไปนี้ของ ID (ดัชนี 0 เป็นแหล่งกำเนิด):
[
" 1234567890abcdef[...] " ,
" fedcba0987654321[...] "
] ในกรณีที่ไม่พบรายการจะส่งคืนรหัสสถานะ 404 พร้อมกับร่างที่ว่างเปล่า
POST /leafจุดสิ้นสุดนี้เพิ่มรายการลงในดัชนี
คาดว่าวัตถุ JSON ต่อไปนี้เป็นร่างกายสามสาขาแรกที่บังคับใช้:
{
"id" : " <The item ID as a hash string representation> " ,
"position" : 0 ,
"size" : 100 ,
"previous" : " <An optional item ID of the previous item in the current subchain if any> "
}มันส่งคืนรหัสสถานะและวัตถุต่อไปนี้เป็น JSON:
{
"code" : 200 | 303 | 400 | 404 | 412 | 500,
"result" : " <The inserted item ID if success> " ,
"error" : " <The error message if failed> "
}รายการรหัสสถานะ (และความหมายของพวกเขา) มีดังนี้:
200 : รายการแทรก;303 : รายการมีอยู่แล้ว (ไม่ได้อัปเดตเนื่องจากไฟล์ควรจะเปลี่ยนไม่ได้);400 : พารามิเตอร์ที่ไม่ถูกต้อง (รายการที่หายไป, สนามบังคับที่หายไป ฯลฯ );404 : ไม่พบรายการก่อนหน้านี้;412 : มีบางอย่างในข้อมูลที่ผ่านมาทำให้เซิร์ฟเวอร์ล้มเหลว (รูปแบบ JSON ที่ไม่ถูกต้อง ... );500 : เกิดข้อผิดพลาดบนเซิร์ฟเวอร์โดยเฉลี่ยแล้วเครื่องพื้นฐานควรจะสามารถนำบันทึกใหม่กว่า 100 ล้านบันทึกใหม่และจัดการการค้นหาประมาณ 5 พันล้านครั้งต่อชั่วโมง
ตัวอย่างเช่นบน Apple MacBook Pro 2.3 GHz Intel Core i9 พร้อม 16 GO DDR4 RAM โอเวอร์คล็อกที่ 2,400 MHz ฉันสังเกตการแสดงต่อไปนี้เมื่อใช้ 101 เป็น Init Prime:
101 เป็น init Prime: โมดูลนี้มีการแจกจ่ายภายใต้ใบอนุญาต MIT
ดูไฟล์ใบอนุญาต
