DependenTree مكتبة تصور الرسم البياني
DependenTree هي مكتبة تصور تسمح للمستخدمين بتصور الرسوم البيانية التبعية الكبيرة كشجرة مرتبة. إنه مبني على قمة D3.js.
في Block ، لدينا أكثر من 14000 ETLs. كان فهم نسب البيانات لأي ETL مهمة شاقة. تضمن ذلك مجموعة من جمع المعلومات حول ETL الفردي وفحص شفرة المصدر. واجهت المحاولات السابقة لتصور هذه البيانات تحديات على نطاق واسع بسرعة.
تم تطوير DependenTree لحل هذه المشاكل. إنه مصمم لتمثيل أي نوع من بيانات التسلسل الهرمي. وهو يدعم عرض كل من التبعيات في المنبع والمصب، ويتعامل مع الرسوم البيانية الدورية، ولديه واجهة برمجة تطبيقات سهلة الاستخدام تسمح للمطورين بإنشاء الرسوم البيانية بسرعة.
لماذا الشجرة بدلاً من الرسم البياني؟
تمثل الصورة أعلاه الرسم البياني للتبعية للملفات في برنامج التحويل البرمجي CoffeeScript. يتم إجراء هذا التصور باستخدام Dependency Cruiser . هذا رسم تخطيطي مفيد، ولكن من السهل أن تضيع في محاولة اتباع النسب لمسار واحد أو مسارين فقط. ليس من الواضح للوهلة الأولى ما هي العلاقات من ملف الجذر “command.coffee” وجميع الآخرين. يصبح هذا الأمر أكثر تعقيدًا بمجرد زيادة عدد العقد في الرسم البياني. أحب أن أسمي هذه مشكلة “الكثير من المعلومات”.
يتيح تمثيل الرسم البياني بتنسيق شجرة قابل للطي للمستخدم رؤية أكبر قدر ممكن من المعلومات كما يريد. يتيح استخدام الشجرة للمستخدم التركيز على عقدة واحدة، والجذر، وتبعياته المباشرة. تتيح الشجرة القابلة للطي للمستخدمين توسيع الفروع بالشكل الذي يرونه مناسبًا دون إغراقهم بالمعلومات.
في الشجرة أعلاه، يمكننا التركيز على خط الخلافة عند فحص العائلة المالكة البريطانية وتجاهل الباقي. آسف، أفراد العائلة المالكة الآخرين.
التحديات الفنية
تعيين العلاقات
في المراحل الأولى من هذا المشروع، حاولنا بسذاجة إنشاء كل شجرة تبعية في المنبع والمصب في ETL وتخزينها في شكل سلسلة JSON. بدأنا برسم خرائط فقط لجزء صغير من إجمالي علاقات ETL لدينا؛ أدى هذا إلى توليد حمولة JSON تبلغ 100 ميغا بايت. يعد تعيين علاقات كل جدول ETL مع ETLs الأخرى عملية فضاء عاملي O (n!). من المحتمل أن يؤدي الوصول إلى جدولنا الكامل البالغ 14000 جدول إلى توليد حمولة ضخمة للغاية بحيث لا يمكن نقلها من خادم إلى عميل.
كان الحل هو إنشاء تعيينات التبعية من جانب العميل. لقد جمعنا كل مستوى من التبعيات في ETL الأول ممثلة كسلاسل وأنشأنا مخرجات JSON. بمجرد تحليل البيانات في الواجهة الأمامية، استبدلنا كل سلسلة بمؤشر.
تم إنشاء JSON على جانب الخادم
من جانب العميل، يتم تعيين JSON
نقوم أيضًا بإنشاء علاقات التبعية النهائية في نفس الوقت عن طريق عكس العلاقات على خريطة منفصلة. من خلال هذا النهج الجديد، تمكنا من تمثيل مجموعتنا الكاملة من سلالات ETL بحمولة JSON بحجم 5 ميغابايت فقط.
مناولة المقياس والدورات
تتطلب خوارزمية d3.tree () التي تعين إحداثيات عقدة شجرة مرتبة اجتياز شجرة الإدخال بالكامل. على الرغم من أن الحمولة أصبحت الآن بحجم يمكن التحكم فيه، إلا أن اجتياز العقد في الرسم البياني من الجذر كان لا يزال عملية ذات تعقيد زمني من الدرجة الثانية O (v² + e) ، حيث يمثل vعدد العقد ويمثل eالاتصالات. عند محاولة عرض أشجار تبعية أكبر، تتعطل علامة تبويب المتصفح بشكل متكرر. ذات مرة، كنت محظوظًا بما يكفي لرؤية خطأ “نفاد الذاكرة” في وحدة التحكم والذي أعطاني فكرة عما كان يحدث. تسببت الاستدعاءات المتكررة لخوارزمية الاجتياز في تجاوز سعة المكدس.
بالإضافة إلى حجم الرسم البياني الكبير، لم يكن لطريقة d3. tree traversal أيضًا منطق للقبض على دورات التبعية، والتي تمتلكها علاقات جدول ETL الخاصة بنا. أدى هذا إلى حلقات لا نهائية والتي تسببت أيضًا في فيضان المكدس.
كان الحل هنا هو تحديد مدى اجتياز طريقة d3. tree للرسم البياني. لقد كتبت خوارزمية اجتياز أولية للعثور على العقد في الرسم البياني التي تفي بواحد من شرطين: هل عمق هذه العقدة بعيد جدًا عن ملاحظة الجذر؟ هل هذه العقدة لها دورة؟
بمجرد استيفاء أحد هذين الشرطين، نقوم باستنساخ العقدة المزعجة. الاختلاف الوحيد بين الأصل والمستنسخ هو عدم وجود المزيد من التبعيات. ثم نقوم بتحريك المؤشر من العقدة المزعجة إلى الاستنساخ. كلما أردنا إنشاء شجرة جديدة، نقوم بإعادة تعيين الرسم البياني عن طريق حذف النسخ وإعادة المؤشر إلى العقدة الأصلية.
قبل
بعد
ومع ذلك، فإن اختيار عمق العقدة التي تقطع عندها الشجرة يمثل مشكلة صعبة. يمكن قراءة المزيد عن التفاصيل في الوثائق .
استكشاف الرسوم المتحركة باستخدام رسومات HTML Canvas
تم إنشاء مخططات D3 باستخدام رسومات موجهة قابلة للتطوير أو صور SVG. من السهل عرض صور SVG ومعالجتها في المتصفح. ولكن في النهاية، ستواجه SVGs تحديات على نطاق واسع وإسقاط الإطارات. اختبر الرسوم المتحركة أدناه على متصفحك الخاص.
إلحاق SVGs مقابل الرسم على اللوحة القماشية
تتضمن عملية إضافة عقدة شجرة إلى الصفحة باستخدام SVG بعض الخطوات الموضحة أدناه. يوضح اختبار التوقيت السريع على المتصفح أن هذه العملية تستغرق 2،005 ميكروثانية، أو 2 مللي ثانية، لإنشاء كل عقدة.
لمحاولة منع الإطارات من السقوط، استكشفت استخدام رسومات قماشية بتنسيق HTML. لا تحتوي اللوحة القماشية على DOM بالطريقة التي تعمل بها عناصر HTML العادية. بدلاً من ذلك، يتم إنشاء الصور بواسطة “الرسم”. لا ترتبط هذه الرسومات بأي كائنات في الذاكرة، فهي مجرد وحدات بكسل. لهذا السبب، هناك خطوات أقل مطلوبة لإضافة عقدة إلى الصفحة. يُرجع اختبار التوقيت على المستعرض الخاص بي 25 ميكروثانية، أو 0.025 مللي ثانية.
تتم كل عملية من هذه العمليات مرة واحدة لكل عقدة معروضة على الشجرة. أظهرت نتائج هذا الاختبار أنه من الناحية النظرية على الأقل، يكون التحريك باستخدام قماش الرسم أسرع.
SVG مقابل قماش، الأداء في الممارسة
أثناء تطبيق الرسوم المتحركة على القماش واستكشافها في الرسم التخطيطي الخاص بي، علمت أنه لا تزال هناك حدود وبعض المفاضلات. في الصورة أعلاه، نقوم بتوسيع الشجرة بمعدل سريع. كلما زاد عدد العقد في الشجرة، تم إسقاط المزيد من الإطارات. لقد أجريت هذا الاختبار نفسه باستخدام كل من SVG وشجرة قماشية تقيس الإطارات في الثانية أثناء الرسوم المتحركة. انظر الرسوم البيانية للأداء أدناه.
يسقط الرسم المتحرك لـ SVG الإطارات بشكل ملحوظ عندما تتغير الشجرة للأشجار الكبيرة، لكنها تعود إلى وضعها الطبيعي عند اكتمال الرسم المتحرك أو على الأقل عندما يقل عدد العقد المتحركة مرة واحدة.
سيؤدي إجراء نفس الاختبار ولكن باستخدام شجرة مرسومة على قماش رسم إلى إسقاط إطارات أقل بشكل عام، لكن معدل الإطارات ينخفض ويظل منخفضًا عند رسم المزيد من العقد على الصفحة. هذا يرجع إلى طريقة الرسم المتحرك للقماش. لمحاكاة الحركة، تعمل اللوحة بنفس طريقة عمل الفيديو. إنها ببساطة سلسلة من الصور التي تظهر في تتابع سريع. يتم تحقيق ذلك من خلال رسم اللوحة القماشية ومسحها ورسمها مرة أخرى ولكن مع كل عقدة متحركة في وضع مختلف قليلاً. هذا يحدث عدة مرات في الثانية. ومع ذلك، لا يزال هذا المسح وإعادة الرسم يحدث حتى عندما لا تتحرك العقد. لذلك كلما زاد عدد العقد في الشجرة، زادت عمليات الرسم التي يجب أن تحدث إلى الأبد.
تشكل فعالية القماش منحنى الجرس. لا يُحدث تحريك شجرة صغيرة فرقًا ملحوظًا في الأداء؛ ستؤدي الشجرة المتوسطة مع القماش إلى أداء أفضل؛ لكن الشجرة الكبيرة ستصبح أسوأ!
الخلاف مع SVGs
كانت هناك صعوبة أخرى في الرسوم المتحركة باستخدام Canvas وهي الحاجة إلى تقليد دورة الرسوم المتحركة الخاصة بـ d3، وتحديثها، والخروج منها. D3 تنقل عناصر SVG ومواقعها للمطور؛ هذا المنطق تم تجريده بعيدا. أثبتت محاولة إعادة إنشاء هذه الدورة باستخدام رسم بياني يتغير كثيرًا أنها صعبة للغاية. تمكنت فقط من تطوير نموذج أولي تقريبي لأغراض الاختبار الخاصة بي.
مع اكتشاف منحنى الجرس الفعال للقماش والتفكير في المقدار المؤلم من حل المشكلات الذي لا يزال مطلوبًا لتشغيل الرسوم المتحركة بشكل كامل، قررت التخلي عن هذا النهج. لقد طمأنني بتذكر الغرض من هذه المكتبة: عدم إعطاء المستخدم الكثير من المعلومات. من غير المحتمل أن يكون لدى المستخدمين أكثر من بضع عشرات من العقد على الصفحة تتحرك في وقت واحد. سيقوم المستخدم فقط بتوسيع الشجرة عقدة واحدة في كل مرة.
المصدر: developer
شاهد المزيد:
