الهدف من هذه المقالة هو بناء لوحة رئيسية متواضعة قوية في Go التي يمكن أن: التعامل مع الآلاف من التحديثات في وقت واحد من عدة goroutines. خدمة طلبات Top-N المتكررة بشكل فعال. الحفاظ على الصور المتوقعة من الأرقام على الرغم من الكتابات المشتركة. أن تكون فعالة ومستعدة لإنتاجها، بما في ذلك الإرشادات على التوسع، واستخدام الذاكرة، والتوسع. سوف نلاحظ ليس فقط الكود ولكن أيضًا فهم لماذا كل قرار تصميم يهم في ظل تكاليف العمل المشتركة. يقدم قواعد القيادة الحية العديد من المضاعفات: تكتب مرتفعة عالية: قد يتم تحديث العديد من المستخدمين في وقت واحد. استفسارات Top-N فعالة: لا يمكن تحديد مجموعة البيانات بأكملها في كل كتابة. كفاءة الذاكرة: يمكن أن تحتوي لعبة Leaderboards على مئات الآلاف من المستخدمين. أسرار عشوائية: يتوقع المستخدمون من سؤال Top-N أن يعكس حالة معقدة من لوحة المرور، حتى عندما يتم إصدار التحديثات. يتطلب مزيج من الكتابات المباشرة والرسائل المتكررة استخدامًا ملموسًا من البروتوكولات والهياكل البيولوجية لـ Go. فهم المشكلة عادة ما يدعم لوحة القيادة اثنين من العمليات الرئيسية: AddScore(UserID string، score int): تخزين النقاط الجديدة للمستخدم. لسهولة البناء، سنبقى تحت إشراف النقاط، وليس للمستخدمين، وهذا يعني أن العديد من النقاط العالية من نفس المستخدم تسمح. Top(n int): احصل على أعلى N أعلى النقاط. وبالإضافة إلى ذلك، هناك عوامل فعالة: تحديثات يجب التوسع مع المنافسة. يجب أن تكون الأسئلة Top-N فعالة ، في الحقيقة أسرع من O (مجموع المستخدمين تسجيل المستخدمين الكامل). يجب أن تتمكن القفازات من الحد من التناقضات ، مما يسمح للعديد من المصممين بالتركيز دون الحد من بعضهم البعض. تحديات المنافسة كتب مرتفعة عالية: بدون هيكلات البيانات التي تزداد أو تزداد تعقيداً ، يتم تصنيف كل تحديث من خلال قفل واحد. التحليلات الأكثر فعالية: سيكون نهائياً الوصول إلى تحليل جميع المستخدمين لكل استفسار.للمستخدمين 100،000، هذا يمكن أن يستغرق عشرات الملي ثانية لكل استفسار - غير قابلة للتأكد من أن أنظمة حية التي تتطلب ردود الفعل على مستوى الملي ثانية. كفاءة الذاكرة: الحفاظ على الهياكل المساعدة مثل المجموعات أو المجموعات المتعددة لكل مستخدم يتطلب إدارة الذاكرة بعناية. مشاهدات متناقضة: يتوقع المستخدمون أن تكون قائمة الأرقام معقولة.إذا قمت بإرسال سؤال Top-N القيمة غير متناقضة على مجموعة متنوعة من الأرقام، فإنه قد يعود إلى نتائج متناقضة أو غير صحيحة. التفكير في التصميم قبل البدء في تشفيرها، يجب أن نحدد كيفية تنظيم هيكلات البيانات لتلبية هذه الاحتياجات. خريطة واحدة مع Global Mutex type Leaderboard struct { mu sync.RWMutex scores map[string]int } : بسيطة وسهلة التفكير حول. Pros التكلفة المنخفضة تحت الأقراص الشديدة - جميع التحديثات تلقائياً من خلال موتيكس واحد. Cons كالة الاستخدام: معدلات التعاقد المنخفضة أو مجموعات البيانات الصغيرة. استخدام sync.Map اذهب الى يوفر خريطة متتالية مع قراءة بدون قفل: sync.Map var leaderboard sync.Map leaderboard.Store("user123", 100) score, ok := leaderboard.Load("user123") : Pros تتيح قراءات بدون قفل للعديد من الباروتين قراءة في وقت واحد. الورق هو آلية وآمنة لاستخدامها معًا. : Cons الإيرادات ضعيفة الدقة. الكتابة المتكررة تقلل من الأداء. لا يدعم بالضرورة طلبات Top-N الفعالة، مما يجعلها غير مثالية للمديرين الحاليين. Sharded Map تصميم لزيادة التكلفة مع العديد من المؤلفين، يمكننا أن نقوم بتقسيم القائمة إلى قطعات. كل قطعة لديها خريطة خاصة بها ومواصفات. الكتابة إلى أجزاء مختلفة تنتهي بشكل مستقل. يمكن أن يحدث القراءة في وقت متأخر من خلال الشقوق. Top-N الأسئلة merge per-shard نتائج. هذا التصميم يحقق المساواة العالية في الوقت الذي يحافظ على الكود بسيطًا نسبياً، لذلك سنبقى معها لتنفيذنا. Top-N على Shard في كل حصة ، علينا أن ننتبه إلى أعلى N النتائج بشكل فعال. يمكننا تقسيم كل حصة في كل استفسار ، ولكن هذا سيكون فظيعا. أو يمكننا أن ننتبه إلى أعلى N النتائج في قائمة معينة ، ثم يمكن إدخال النتائج الجديدة (أو إلغاءها) في وقت O(N). . الرئيسية > min-heap ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي ثنائي. هذا الخصائص يجعل من فعالية استخراج الحد الأدنى من العناصر (العين) وإدخال العناصر الجديدة مع الحفاظ على الهيكل. إنها مجموعة من النقد الأدنى من N لأننا نحتفظ فقط بالعديد من النقد الأدنى من N في العدد. عندما يأتي العدد الجديد، إذا كان أقل من الجذور من العدد الأدنى من N، وهذا هو العدد الأدنى من N، ونحن نرفضه. إذا كان أكبر، ونستبدل العدد الأدنى من N مع العدد الجديد (نحن يمكننا القيام بذلك لأن العناصر الأساسية ستكون خارج العدد الأدنى من N) ويدمج مرة أخرى (إعادة هيكلة العدد). هذا يضمن أن لدينا دائمًا النقد الأدنى من N في العدد. هذه الشاشة تشير إلى ما يحدث في إدراج: يحافظ كل حفرة على مجموعة Top-N المحلية ، ويتم حساب Top-N العالمي عن طريق جمع هذه الحفرة ، وهذا النهج يمنع تقسيم مجموعة البيانات بأكملها في كل استفسار Top-N. تطبيق Sharded Leaderboard مع كل النظرية تحت حزامنا، دعونا نصل إلى ذلك! إطلاق IDE المفضلة لديك والبدء مع تحديد هيكل الحصانة والتشكل الرئيسي من القائمة: // leaderboard/leaderboard.go package leaderboard import "sync" // Shard represents a portion of the leaderboard // It maintains a top-N min-heap of high scores type shard struct { mu sync.RWMutex topN *TopNMinHeap } type Leaderboard struct { shards []*shard n int // global top-N size } تطبيقات Heap بعد ذلك ، سنقوم بتنفيذ الهيكل الأكبر N-min-heap وتطبيقات لإدارةها. وهذا يشمل إدراج وتخفيض وإيجاد النتائج الأكبر N. سنقوم باستخدام Go's يمكننا تنفيذ قوةنا الخاصة لزيادة قليلة في الأداء، ولكن فقط بأسعار زيادة المعقدة - ربما في مقال آخر. container/heap // leaderboard/topnminheap.go package leaderboard import ( "container/heap" ) // ScoreEntry represents a score and its associated player. type ScoreEntry struct { PlayerID string Score int } // TopNMinHeap is a min-heap that stores the top-N high scores with player IDs. type TopNMinHeap struct { scores []ScoreEntry maxN int } // Len implements heap.Interface func (h TopNMinHeap) Len() int { return len(h.scores) } // Less implements heap.Interface (min-heap) func (h TopNMinHeap) Less(i, j int) bool { return h.scores[i].Score < h.scores[j].Score } // Swap implements heap.Interface func (h TopNMinHeap) Swap(i, j int) { h.scores[i], h.scores[j] = h.scores[j], h.scores[i] } // Push implements heap.Interface func (h *TopNMinHeap) Push(x any) { h.scores = append(h.scores, x.(ScoreEntry)) } // Pop implements heap.Interface func (h *TopNMinHeap) Pop() any { old := h.scores n := len(old) x := old[n-1] h.scores = old[:n-1] return x } // NewTopNMinHeap creates a TopNMinHeap with a specified maximum size. func NewTopNMinHeap(maxN int) *TopNMinHeap { return &TopNMinHeap{ scores: make([]ScoreEntry, 0, maxN), maxN: maxN, } } // Add inserts a new score into the heap, maintaining the top-N property. func (h *TopNMinHeap) Add(playerID string, score int) { entry := ScoreEntry{PlayerID: playerID, Score: score} if h.Len() < h.maxN { heap.Push(h, entry) } else if score > h.scores[0].Score { h.scores[0] = entry heap.Fix(h, 0) } } أولاً، يجب علينا تنفيذ ما الذي يحدد ، ، ، و و بعد ذلك، نحن نخلق مصنع أولاً، من أجل إثبات أنّه، في النهاية، يتعامل الطريقة مع إدخال الأرقام الجديدة مع الحفاظ على خصائص أعلى-N: إذا لم يكن الغطاء كاملاً، فإننا نضغط بسهولة على الأرقام الجديدة.إذا كان الغطاء كاملاً وارتفاع الأرقام الجديدة أعلى من الحد الأدنى (الحد الأدنى)، فإننا نستبدل الجذور وتجديدها مرة أخرى (أي نسميها ) heap.Interface Len Less Swap Push Pop NewTopNMinHeap Add heap.Fix Shard Operations: Score Updates والرسائل يجب على كل حفرة إظهار أساليب تضاف إلى الأرقام الجديدة بطريقة آمنة وتتلقى صورة منخفضة N الحالية. تضمن أن التحديثات المباشرة إلى الحفرة آمنة. mu // leaderboard/leaderboard.go ... // AddScore adds a new score to the shard's top-N heap. func (s *shard) AddScore(playerID string, score int) { s.mu.Lock() defer s.mu.Unlock() s.topN.Add(playerID, score) } // Top returns a snapshot of the top-N scores for this shard. func (s *shard) Top() []ScoreEntry { s.mu.RLock() defer s.mu.RUnlock() // Return a copy to avoid exposing internal slice top := make([]ScoreEntry, len(s.topN.scores)) copy(top, s.topN.scores) return top } يلتحق بالكتب، ثم يضيف النتيجة إلى الكتلة باستخدام أسلوب التخطيط الذي نفهمه سابقاً. AddScore Add يلجأ إلى القفز للكتابة ، ويعود نسخة من قطعة القفز حتى لا يمكن للمرشحين تغيير القفز الداخلي بطبيعة الحال. Top استخدام يتيح للعديد من الباروتين قراءة أعلى N في وقت واحد في حين يتم تصنيف النصوص. RWMutex بدء التصميم لـ Leaderboard الآن، عندما يفعل كل قطعة شيئًا، يمكننا إعادة تشكيل القائمة مع عدد محدد من قطعات وأصغر حجم N في العالم: // leaderboard/leaderboard.go // NewLeaderboard creates a sharded leaderboard with `numShards` shards and global top-N size `n`. func NewLeaderboard(numShards, n int) *Leaderboard { lb := &Leaderboard{ shards: make([]*shard, numShards), n: n, } for i := 0; i < numShards; i++ { lb.shards[i] = &shard{ topN: NewTopNMinHeap(n), } } return lb } هذه الوظيفة تخلق a مع عدد المجموعات المحددة ، يتم إعادة تأسيس كل منها مع مجموعة من الأرقام الخاصة بها من أعلى N. إعادة إعطاء علامة تضمن أن جميع goroutines تعمل على نفس الحالة المشتركة من قائمة المرشحين ، وهو أمر ضروري للتحديثات المشتركة. Leaderboard إضافة النقاط عندما نضيف النقاط إلى القائمة ، علينا أن نحدد أي القائمة التي يجب تحديثها. نحن نستخدم القائمة FNV-1a من PlayerID لتخصيص لاعب إلى القائمة ، مما يضمن توزيع اللاعبين على القائمة بشكل متساوٍ تقريباً. هذا أمر مهم من أجل تجنب التخلف في توزيع القائمة ، مما قد يؤدي إلى زيادة عدد القائمة في حين أن القائمة الأخرى غير المستخدمة. // leaderboard/leaderboard.go import "hash/fnv" ... // getShard returns the shard for a given playerID. func (lb *Leaderboard) getShard(playerID string) *shard { h := fnv.New32a() h.Write([]byte(playerID)) idx := int(h.Sum32()) % len(lb.shards) return lb.shards[idx] } مع يمكننا الآن بسهولة تطبيق طريقة إضافة الأرقام إلى لوحة المرشحين: getShard AddScore // leaderboard/leaderboard.go // AddScore adds a new score to the appropriate shard. func (lb *Leaderboard) AddScore(playerID string, score int) { s := lb.getShard(playerID) s.AddScore(playerID, score) } الهاتف للعثور على القطع الصحيح ، ثم إضافة النتيجة إلى ذلك من خلال كل قطعة تتعامل مع قفلها الخاصة بك ، لذلك يزداد هذا مع عدد قطعات. AddScore getShard shard.AddScore تحميل برنامج Global Top-N الآن عندما نتمكن من إضافة الأرقام، لا يزال هناك شيء واحد فقط للقيام به: استرداد الأرقام الكبيرة N على جميع الأقراص. يمكننا القيام بذلك عن طريق دمج أقراص الأقراص N الكبيرة من كل الأقراص. لأن أقراص الأقراص N الكبيرة من كل الأقراص قد تم تقسيمها بالفعل (مثل أقراص دقيقة)، ويمكننا الجمع بينها بشكل فعال باستخدام أقراص الأقراص الكبيرة لتتبع أقراص الأقراص N الكبيرة. (لعدد كبير من الأقراص، يمكن تطبيق أقراص K-Way المعقدة، ولكن بالنسبة إلى أقراص الأقراص التقليدية، هذا النهج يكفي.) // leaderboard/leaderboard.go // Top returns the global top-N across all shards. func (lb *Leaderboard) Top() []ScoreEntry { // Temporary heap to compute global top-N globalHeap := NewTopNMinHeap(lb.n) for _, s := range lb.shards { shardTop := s.Top() // thread-safe snapshot for _, entry := range shardTop { globalHeap.Add(entry.PlayerID, entry.Score) } } // Copy to slice top := make([]ScoreEntry, len(globalHeap.scores)) copy(top, globalHeap.scores) // Sort descending (highest score first) for i, j := 0, len(top)-1; i < j; i, j = i+1, j-1 { top[i], top[j] = top[j], top[i] } return top } يعود كل قطعة واحدة من أعلى N ، لذلك لا نحتفظ بالقفز على عدة قطعات في وقت واحد. نحن نضيف جميع الملفات أعلى N من قطعة واحدة إلى قطعة واحدة مؤقتة من حجم n للحفاظ على أعلى N عالميًا بشكل فعال. لأن قطعة واحدة تخزين أعلى N الأصغر في الجذور، ونحن نترك قطعة واحدة لتعود أعلى النتائج أولاً. اختبار ما بناؤه الآن بعد أن كنا قد انتهينا من جدول أعمالنا، دعونا نرى كيف يعمل ذلك. هنا برنامج اختبار بسيط يظهر إضافة النتائج وإيجاد أعلى N في وقت واحد: // main.go package main import ( "fmt" "math/rand" "sync" "time" "./leaderboard" ) func main() { const ( numShards = 8 topN = 10 numPlayers = 50 numUpdates = 200 updateDelay = 10 * time.Millisecond ) lb := leaderboard.NewLeaderboard(numShards, topN) var wg sync.WaitGroup // Spawn concurrent score updates for i := 0; i < numPlayers; i++ { wg.Add(1) playerID := fmt.Sprintf("player%02d", i) go func(pid string) { defer wg.Done() for j := 0; j < numUpdates; j++ { score := rand.Intn(50000) lb.AddScore(pid, score) time.Sleep(updateDelay) } }(playerID) } // Spawn a goroutine to print live top-N periodically done := make(chan struct{}) go func() { ticker := time.NewTicker(100 * time.Millisecond) defer ticker.Stop() for { select { case <-ticker.C: top := lb.Top() fmt.Println("Top Scores:") for i, entry := range top { fmt.Printf("%2d: %s = %d\n", i+1, entry.PlayerID, entry.Score) } fmt.Println("-----") case <-done: return } } }() // Wait for all updates to finish wg.Wait() close(done) // Print final top-N fmt.Println("Final Top Scores:") top := lb.Top() for i, entry := range top { fmt.Printf("%2d: %s = %d\n", i+1, entry.PlayerID, entry.Score) } } يخلق هذا البرنامج لوحة رئيسية مع 8 حصص و10 حجم أعلى. يولد 50 Goroutines، كل يثبت لاعب يحدد نقاطه 200 مرة مع قيمة عشوائية. يمكنك إجراء هذا البرنامج مع وستكون النتائج مثل هذا: go run main.go Top Scores: 1: player05 = 49830 2: player07 = 49873 3: player46 = 49966 4: player24 = 49800 5: player25 = 49961 6: player10 = 49802 7: player30 = 49812 8: player02 = 49726 9: player19 = 49750 10: player46 = 49718 ----- ... ----- Final Top Scores: 1: player10 = 49971 2: player45 = 49977 3: player00 = 49992 4: player40 = 49979 5: player29 = 49990 6: player19 = 49967 7: player46 = 49966 8: player18 = 49974 9: player25 = 49961 10: player39 = 49960 النتيجة في هذه المقالة، قمنا بتطوير لوحة الملفات المباشرة المباشرة ذات الأداء العالي في Go من البداية، بدءاً من المشكلة الأساسية، قمنا بتناول التحديات التي يواجهها الكتابة عالية التكرار، والتحليلات الأكثر فعالية في N، والتوافق الفوري تحت التوافق المباشر. نحن نبحث عن العديد من خيارات التصميم: خريطة واحدة مع موثوقية عالمية: بسيطة ولكن منخفضة التوسع. sync.Map: مناسبة للرسائل المباشرة، ولكن محدودة للرسائل الأكثر أهمية. لوحة الماجستير المتقطعة مع مجموعة من الماجستير: نهجنا المختار، وتوازن التوازن، والفعالية، والسهولة. ونحن نستخدم: البنية التحتية على مستوى Shard مع قفل القراءة. Top-N min-heads لكل حفرة للتدخل السريع والتردد. استفسارات أعلى N العالمية التي تساهم في تسليط الضوء على الكثافة بشكل فعال دون الحظر على التحديثات المباشرة. إشارة الدعارة / اختبار تظهر التحديثات الحية ، والرسائل المباشرة ، والصور المتكررة من قائمة المرشحين. الرئيسية Takeaways: يمكنك تحديث الأرقام في وقت واحد مع الحد الأدنى من الحظر. يتم تخزين الأرقام الأكثر أهمية، مع الحفاظ على العمليات O(Log N). وبالتالي، من خلال الجمع بين مجموعات كل مجموعة، نحن نمنع تخصيص مجموعات البيانات بأكملها ويحافظ على الأسئلة السريعة. أمن المنافسة بسيط مع محركات الفوركس. لا تحتاج إلى محركات محركات الفوركس المعقدة للعديد من الحالات المستخدمة في القائمة الحية. هذا التصميم يزيد من عدد الأقراص يقلل من التناقض ، ويضمن النهج المرتبط ببطارية الذاكرة كفاءة الذاكرة. مع هذا الأساس، يمكنك توسيع لوحة المرشحين لدعم: الديموقراطيين من أعلى N لكل قسيمة أو قسيمة متعددة المستويات. التكامل مع تخزين مستمر أو أنظمة توزيع للأغراض الكبيرة. معدلات إضافية مثل العلامات الزمنية أو المرتبة أو النتائج. هذا النهج العملي والعملي يمنحك فكرة عن كيفية معالجة برامج العمل المشتركة في العالم الحقيقي بشكل فعال. الآن لديك الأدوات لتنفيذ وتقييم وتطوير أنظمة العمل المشتركة مستعدة للإنتاج في Go. يتوفر الكود لهذا المقال على GitHub: gkoos/article-leaderboard. gkoos/القائمة القائمة
