treee
Update with Windows10 and MacOS executables
محرك الفهرسة السريعة للبيانات التي حددها معرف HASHED وتخزينها في ملف غير قابل للتغيير
هذا هو تنفيذ GO لمحرك فهرسة Treee ™. إنها مكتبة لاستخدامها كوحدة نمطية في مشاريع GO الخاصة بك وقابلة للتنفيذ لتشغيلها كخدمة صغيرة عبر HTTP.
كان التحدي هو إعداد محرك بحث قوي وآمن لاستخدامه عندما تكون البيانات عبارة عن قائمة مرتبطة بالعناصر التي يمكن أن تكون مرتبطة ببعضها البعض في السلاسل الفرعية ، وفهرستها من خلال معرفاتها المصنوعة فقط من قيم التجزئة (مثل تمثيلات سلسلة SHA-256) ، وكلها مخزنة في ملف غير قابل للتغيير.
أفضل تطبيق لها هو لملف blockchain حيث يكون عنصر ما عبارة عن معاملة تضم عقدًا ذكيًا ، وكل مجموعة فرعية من العناصر الاستخدامات و/أو التعديلات اللاحقة لهذا العقد الذكي. على هذا النحو ، يتم استخدام فهرس Treee ™ حاليًا في ROOOT ™ blockchain.
نحن نحدد هنا خوارزمية لفهرسة النظام بناءً على معرفات هي قيم الهاوية التي تكون في نفس الوقت قوية جدًا للكتابة والقراءة.
يتم إنشاء فهرس Treee ™ كرسوم بيانية (شجرة). تحتوي كل عقدة على عنوان العقدة (أبناءها) أو مجموعة من الأوراق ، وهي ورقة تقابل المعلومات التي تساعد على استرداد عنصر واحد أو أكثر.
عدد أبناء العقدة حتمية ويعتمد على عمق الشجرة. نشير إلى عدد أبناء العقد في العمق 1 ، وعدد أبناء العقد في العمق 2 ، ... ، وعدد الأبناء في العمق.
الهدف من ذلك هو إنشاء شجرة متوازنة يكون عرضها متكيفًا لتقليل العمق وتحسين الأداء. نحن نتطلع إلى فهرسة الأرقام ، في هذه الحالة القيمة العددية للمعرفات الفريدة للعناصر.
دعنا نوضح مجرى الفهرس.
بالنسبة للشجرة الثنائية ، نكتب الرقم في شكل ثنائي (على سبيل المثال ، 100 ) مما يشير إلى موضعها في الشجرة.
في الخطوة ، ننتقل إلى الطفل إذا كان البت 0 ، وإلا فإننا ننتقل إلى الطفل إذا كان البت 1 . نتوقف عندما تكون العقدة ورقة .
بالنسبة للشجرة ، نقوم ببناء تمثيل لهذا الرقم من خلال سلسلة من الأرقام ونعبر الشجرة بنفس الطريقة. في خطوة العمق ، ننتقل إلى الطفل إذا كان الممثل 0 ، ننتقل إلى الطفل إذا كان الممثل 1 ، ... ، ننتقل إلى الطفل إذا كان الممثل. نتوقف عندما تكون العقدة ورقة .
لإنشاء تمثيل رقم ، سنأخذ على التوالي موديل الأعداد الأولية. وفقًا لنظرية البقايا الصينية ، فإن كل رقم له ممثل فريد يمكن كتابته كاستمرار لهذه المعدات. في الواقع ، يمكن كتابة رقم في النموذج التالي:
يتم الإشارة إلى قيمة معرف العنصر (رقمه) ورقم التعديل. يتم حساب Modulos في الأعداد الصحيحة ذات الحجم الثابت. نظرًا لأن الضرب أسرع من التقسيم (ضروري لحساب Modulo) ، يمكن للمرء استخدام الضربات عن طريق العائمة :.
بالنظر إلى الطبيعة العشوائية للأرقام (أو العشوائية الزائفة ، نظرًا لأن معرفات العناصر يتم إنشاؤها بواسطة تقنيات تجزئة التشفير) ، فإن الشجرة متوازنة. لإلغاء توازن الشجرة بطريقة خبيثة ، سيكون من الضروري أن تكون قادرًا على توليد تجزئة يتبع Modulo مسارًا معينًا. ومع ذلك ، فإن صعوبة مثل هذه العملية تزيد بشكل كبير (من ترتيب أين هو العمق). كتذكير ، فإن ناتج أول 16 أعداد الأولية يساوي. لذلك ، بمجرد أن يحتوي الفهرس على كمية كبيرة بشكل معقول من البيانات ، فإن عدم توازن الشجرة بطريقة ضارة سيصبح أكثر فأكثر ، إن أمكن.
تحتوي الورقة على قائمة المعلومات التالية حول عنصر ما:
الورقة التي يكون حقل العنصر التالي فارغًا هي العنصر الأخير في المجموعة الفرعية.
إن حقل عنصر الأصل الذي يساوي معرف العنصر الحالي هو الأصل بالضرورة من المجموعة الفرعية. على هذا النحو ، فإنه يحتوي على تشغيل معين لأنه ، إذا كان هناك عنصر واحد أو أكثر بعد ذلك ، فسيتم تحديد العنصر الأخير من المجموعة الفرعية هنا على أنه العنصر السابق. وبالتالي فإن الحقول الثلاثة الأخيرة من الورقة تتوافق مع قائمة مرتبطة دائرية.
لإضافة عنصر إلى الفهرس:
لقراءة/البحث عن عنصر في الفهرس:
عند استخدام الفهرس ، يمكننا أن نرى أننا سنؤدي على الأكثر 3 قراءة 3 أو 3 عمليات كتابة وفهرسة من الترتيب ، حيث يوجد عدد العناصر في الفهرس.
لمزيد من التفاصيل ، لا تتردد في قراءة الورقة البيضاء الكاملة.
$ 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 على سبيل المثال).
لأغراض تصحيح الأخطاء أو التخزين ، قد ترغب في استخدام طريقة PrintAll() على فهرس Treee لطباعة جميع الأوراق المسجلة إلى كاتب (تمريرها true كوسيطة لتجميل JSON المطبوعة ، أو false في السلسلة الأولية).
// To print to Stdout
fmt . Println ( treee . PrintAll ( true )) يتم تحقيق استمرار الفهرس من خلال استخدام الحفظ التلقائي المصنوع عند الإدراج ، واستخدام وظيفة Load() بدلاً من تثبيت TREE مع 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 التالية من معرفات undelet إذا لم تتم إزالتها:
{
"ids" : [ " fedcba0987654321[...] " ]
}GET /leafتبحث نقطة النهاية هذه عن عناصر بناء على معرفات تم تمريرها.
إنه يتوقع مجموعة من المعرفات كوسيطة استعلام ids و takeLast Boolean اختياري (افتراضي إلى 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 ، على سبيل المثال. http://localhost:7000/api/line?id=1234567890abcdef[...]
يقوم بإرجاع رمز الحالة 200 طويلًا مع مجموعة JSON المرتبة التالية من المعرفات (الفهرس 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 على مدار 2400 ميجاهرتز ، لاحظت العروض التالية عند استخدام 101 كـ init prime:
101 كما init prime: يتم توزيع هذه الوحدة تحت رخصة معهد ماساتشوستس للتكنولوجيا.
انظر ملف الترخيص.
