c# دليل بسيط على أن GUID ليس فريدًا




(24)

for(begin; begin<end; begin)
    Console.WriteLine(System.Guid.NewGuid().ToString());

أنت لا تزيد من begin حتى begin < end الحالة begin < end دائمًا صحيحة.

أود أن أثبت أن المعرف الفريد العمومي (GUID) ليس فريدًا في برنامج اختبار بسيط. كنت أتوقع تشغيل التعليمة البرمجية التالية لساعات ، ولكنها لا تعمل. كيف يمكنني جعلها تعمل؟

BigInteger begin = new BigInteger((long)0);
BigInteger end = new BigInteger("340282366920938463463374607431768211456",10);  //2^128
for(begin; begin<end; begin++)
  Console.WriteLine(System.Guid.NewGuid().ToString());

أنا أستخدم C #.


Answer #1

إذا كان وقت تشغيل 83 مليار سنة لا يخيفك ، فكر أنك ستحتاج أيضًا إلى تخزين المعرف الفريد العمومي المولد في مكان ما للتحقق مما إذا كان لديك نسخة مكررة. تخزين 2 ^ 128 يتطلب 16 بايت فقط لتخصيص 4951760157141521099596496896 تيرابايت من ذاكرة RAM مقدمًا ، لذلك تخيل أن لديك جهاز كمبيوتر يمكن أن يلائم كل ذلك وأنك تجد مكانًا ما لشراء وحدات ذاكرة DIMM بمعدل تيرابايت بسعر 10 جرام لكل منهما ، تزن أكثر من 8 كتل من الأرض ، حتى تتمكن من تحويلها عن المدار الحالي ، حتى قبل الضغط على "تشغيل". فكر مرتين!


Answer #2

Not to p**s on the bonfire here, but it does actually happen, and yes, I understand the joking you have been giving this guy, but the GUID is unique only in principle, I bumped into this thread because there is a bug in the WP7 emulator which means every time it boots it gives out the SAME GUID the first time it is called! So, where in theory you cannot have a conflict, if there is a problem generating said GUI, then you can get duplicates

http://forums.create.msdn.com/forums/p/92086/597310.aspx#597310


Answer #3

Here's a solution, too:

int main()
{
  QUuid uuid;
  while ( (uuid = QUuid::createUuid()) != QUuid::createUuid() ) { }
  std::cout << "Aha! I've found one! " << qPrintable( uuid.toString() ) << std::endl;
}

Note: requires Qt, but I guarantee that if you let it run long enough, it might find one.

(ملاحظة ملاحظة: في الواقع ، الآن بعد أن نظرت إليها ، قد يكون هناك شيء حول خوارزمية الجيل الذي يمنع اثنين من uuids التي تم إنشاؤها في وقت لاحق أن تصطدم - لكني أشك في ذلك).


Answer #4

إليك طريقة تمديد بسيطة يمكنك استخدامها إذا كنت تريد التحقق من التفرد في العديد من الأماكن في التعليمات البرمجية.

internal static class GuidExt
{
    public static bool IsUnique(this Guid guid)
    {
        while (guid != Guid.NewGuid())
        { }
        return false;
    }
}

للاتصال به ، ما عليك سوى الاتصال بـ Guid.IsUnique عندما تقوم بإنشاء دليل جديد ...

Guid g = Guid.NewGuid();
if (!g.IsUnique())
{
    throw new GuidIsNotUniqueException();
}

... هيك ، حتى أنني أوصي بالاتصال بها مرتين للتأكد من أنها حصلت على حق في الجولة الأولى.


Answer #5

لا أفهم لماذا لم يشر أحد إلى ترقية بطاقة الرسومات الخاصة بك ... بالتأكيد إذا كنت قد حصلت على NVIDIA Quadro FX 4800 المتطور أو ما شابه (192 مركز CUDA) ، فإن ذلك سيصبح أسرع ...

بالطبع إذا كنت تستطيع تحمل عدد قليل من نفيديا Qadro Plex 2200 S4s (في 960 CUDA النوى لكل منهما) ، فإن هذا الحساب يصيح حقا . ربما تكون NVIDIA على استعداد لإعارة عدد قليل من "مظاهرة التكنولوجيا" كحركة العلاقات العامة؟

من المؤكد أنهم يريدون أن يكونوا جزءًا من هذا الحساب التاريخي ...


Answer #6

For me.. the time it takes for a single core to generate a UUIDv1 guarantees it will be unique. Even in a multi core situation if the UUID generator only allows one UUID to be generated at a time for your specific resource (keep in mind that multiple resources can totally utilize the same UUIDs however unlikely since the resource inherently part of the address) then you will have more than enough UUIDs to last you until the timestamp burns out. At which point I really doubt you would care.


Answer #7

يمكنك تجزئة المعرفات الفريدة العمومية (GUIDs). بهذه الطريقة ، يجب أن تحصل على نتيجة أسرع.

وبالطبع ، فإن تشغيل سلاسل رسائل متعددة في نفس الوقت هو أيضًا فكرة جيدة ، وبهذه الطريقة ستزيد من فرصة وجود حالة سباق تنشئ نفس المعرف الفريد العمومي (GUID) مرتين على سلاسل مختلفة.


Answer #8

يمكنك إظهار ذلك في زمن (1) O مع متغير من خوارزمية bogosort الكمومية .

Guid g1 = Guid.NewGuid();
Guid g2 = Guid.NewGuid();
if(g1 != g2) Universe.Current.Destroy();

Answer #9

من المفترض أن لديك سبب للاعتقاد بأن الخوارزمية لإنتاج Guids لا تنتج أرقامًا عشوائية فعلية ، ولكنها في الحقيقة تدور مع فترة << 2 ^ 128.

على سبيل المثال ، طريقة RFC4122 المستخدمة لاشتقاق المعرفات الفريدة العمومية (GUIDs) التي تعمل على إصلاح قيم بعض البتات.

سيعتمد إثبات ركوب الدراجات على الحجم الممكن لهذه الفترة.

بالنسبة لفترات صغيرة ، جدول تجزئة التجزئة (GUID) -> GUID مع الاستبدال عند الاصطدام إذا لم تتطابق المعرفات الفريدة العمومية (التي تنتهي إذا تم ذلك) قد يكون أسلوبًا. النظر أيضا فقط القيام باستبدال جزء عشوائي من الوقت.

في النهاية ، إذا كانت الفترة القصوى بين الاصطدامات كبيرة بما فيه الكفاية (ولا تُعرف مسبقًا) ، فإن أي طريقة ستؤدي فقط إلى احتمال أن يتم العثور على التصادم في حالة وجوده.

لاحظ أنه إذا كانت طريقة توليد Guids تستند إلى الساعة (انظر RFC) ، فقد لا يكون من الممكن تحديد ما إذا كانت الاصطدامات موجودة إما (أ) لن تتمكن من الانتظار لمدة كافية بما يكفي لساعة الالتفاف ، أو (ب) لا يمكنك طلب ما يكفي من الأدلة داخل علامة على مدار الساعة لفرض التصادم.

بدلاً من ذلك ، قد تتمكن من إظهار علاقة إحصائية بين البتات في Guid ، أو ارتباط البتات بين Guids. قد تجعل مثل هذه العلاقة من المحتمل بدرجة كبيرة أن الخوارزمية معيبة دون أن تكون بالضرورة قادرة على إيجاد تصادم فعلي.

بالطبع ، إذا كنت تريد فقط إثبات أن Guids يمكن أن تتصادم ، فإن البرهان الرياضي ، وليس البرنامج ، هو الحل.


Answer #10

كاي ، لقد قدمت برنامجًا سيفعل ما تريد باستخدام خيوط. وهو مرخص بموجب الشروط التالية: يجب أن تدفع لي 0.0001 دولار في الساعة لكل وحدة معالجة مركزية تقوم بتشغيلها. الرسوم مستحقة الدفع في نهاية كل شهر تقويمي. الرجاء الاتصال بي للحصول على تفاصيل حساب paypal في أقرب وقت ممكن.

using System;
using System.Collections.Generic;
using System.Linq;

namespace GuidCollisionDetector
{
    class Program
    {
        static void Main(string[] args)
        {
            //var reserveSomeRam = new byte[1024 * 1024 * 100];     // This indeed has no effect.

            Console.WriteLine("{0:u} - Building a bigHeapOGuids.", DateTime.Now);
            // Fill up memory with guids.
            var bigHeapOGuids = new HashSet<Guid>();
            try
            {
                do
                {
                    bigHeapOGuids.Add(Guid.NewGuid());
                } while (true);
            }
            catch (OutOfMemoryException)
            {
                // Release the ram we allocated up front.
                // Actually, these are pointless too.
                //GC.KeepAlive(reserveSomeRam);
                //GC.Collect();
            }
            Console.WriteLine("{0:u} - Built bigHeapOGuids, contains {1} of them.", DateTime.Now, bigHeapOGuids.LongCount());


            // Spool up some threads to keep checking if there's a match.
            // Keep running until the heat death of the universe.
            for (long k = 0; k < Int64.MaxValue; k++)
            {
                for (long j = 0; j < Int64.MaxValue; j++)
                {
                    Console.WriteLine("{0:u} - Looking for collisions with {1} thread(s)....", DateTime.Now, Environment.ProcessorCount);
                    System.Threading.Tasks.Parallel.For(0, Int32.MaxValue, (i) =>
                    {
                        if (bigHeapOGuids.Contains(Guid.NewGuid()))
                            throw new ApplicationException("Guids collided! Oh my gosh!");
                    }
                    );
                    Console.WriteLine("{0:u} - That was another {1} attempts without a collision.", DateTime.Now, ((long)Int32.MaxValue) * Environment.ProcessorCount);
                }
            }
            Console.WriteLine("Umm... why hasn't the universe ended yet?");
        }
    }
}

PS: كنت أرغب في تجربة مكتبة الإضافات المتوازية. كان ذلك سهلا.

واستخدام OutOfMemoryException كتدفق التحكم فقط يشعر خطأ.

تصحيح

حسنًا ، يبدو أن هذا ما زال يجذب الأصوات. لذا قمت بإصلاح مشكلة GC.KeepAlive (). وتغييرها لتشغيل مع C # 4.

ولتوضيح شروط الدعم الخاصة بي: يتوفر الدعم فقط في 28 / فبراير / 2010. يرجى استخدام جهاز توقيت لتقديم طلبات الدعم في ذلك اليوم فقط.

EDIT 2 كما هو الحال دائمًا ، يقوم GC بعمل أفضل مما أقوم به في إدارة الذاكرة. أي محاولات سابقة لفعل ذلك بنفسي كانت مآلها الفشل.


Answer #11

The program, albeit its errors, shows proof that a GUID is not unique. Those that try to prove the contrary are missing the point. This statement just proves the weak implementation of some of the GUID variations.

A GUID is not necessary unique by definition, it is highly unique by definition. You just refined the meaning of highly. Depending on the version, the implementator (MS or others), use of VM's, etc your definition of highly changes. (see link in earlier post)

You can shorten your 128 bit table to prove your point. The best solution is to use a hash formula to shorten your table with duplicates, and then use the full value once the hash collides and based on that re-generate a GUID. If running from different locations, you would be storing your hash/full key pairs in a central location.

Ps: If the goal is just to generate x number of different values, create a hash table of this width and just check on the hash value.


Answer #12

إذا كنت قلقًا بشأن التفرد ، فيمكنك دائمًا شراء المعرفات الفريدة العمومية (GUIDs) الجديدة حتى تتمكن من التخلص من القديمة. سأضع بعض على موقع ئي باي إذا أردت.


Answer #13

أنا شخصياً أعتقد أن "الانفجار الكبير" قد نجم عن اصطدام اثنين من المخططات GUID.


Answer #14

ولكن هل يتعين عليك التأكد من أن لديك نسخة مكررة ، أو أنك لا تهتم إلا إذا كان هناك تكرار. للتأكد من أن لديك شخصين لهما نفس عيد الميلاد ، فإنك تحتاج إلى 366 شخصًا (دون احتساب سنة كبيسة). ولكي تكون هناك فرصة أكبر من 50٪ لوجود شخصين في نفس عيد الميلاد ، فإنك تحتاج فقط إلى 23 شخصًا. هذه مشكلة عيد الميلاد .

إذا كان لديك 32 بت ، فأنت تحتاج فقط إلى 77،163 قيمة للحصول على فرصة أكبر من 50٪ للنسخة المكررة. حاول:

Random baseRandom = new Random(0);

int DuplicateIntegerTest(int interations)
{
    Random r = new Random(baseRandom.Next());
    int[] ints = new int[interations];
    for (int i = 0; i < ints.Length; i++)
    {
        ints[i] = r.Next();
    }
    Array.Sort(ints);
    for (int i = 1; i < ints.Length; i++)
    {
        if (ints[i] == ints[i - 1])
            return 1;
    }
    return 0;
}

void DoTest()
{
    baseRandom = new Random(0);
    int count = 0;
    int duplicates = 0;
    for (int i = 0; i < 1000; i++)
    {
        count++;
        duplicates += DuplicateIntegerTest(77163);
    }
    Console.WriteLine("{0} iterations had {1} with duplicates", count, duplicates);
}

1000 iterations had 737 with duplicates

الآن 128 بت هو الكثير ، لذلك كنت لا تزال تتحدث عدد كبير من العناصر لا تزال تعطيك فرصة منخفضة من الاصطدام. ستحتاج إلى العدد التالي من السجلات للأعراف المحددة باستخدام تقريب:

  • 0.8 مليار مليار لفرصة 1/1000 حدوث تصادم
  • 21.7 مليار مليار ل 50 ٪ فرصة حدوث تصادم
  • 39.6 مليار مليار ل 90 ٪ فرصة حدوث تصادم

هناك حوالي 1E14 رسالة بريد إلكتروني يتم إرسالها سنوياً ، بحيث يكون حوالي 400،000 سنة عند هذا المستوى قبل أن تحصل على فرصة 90٪ من وجود اثنين بنفس كود GUID ، ولكن هذا يختلف كثيرًا عن القول أنك بحاجة إلى تشغيل جهاز كمبيوتر 83 مليار مرات عصر الكون أو أن الشمس ستمضي البرد قبل العثور على نسخة مكررة.


Answer #15

المعرف الفريد العمومي (GUID) هو نظريًا غير فريد. هنا دليلك:

  • GUID هو رقم 128 بت
  • لا يمكنك إنشاء GUIDs 2 ^ 128 + 1 أو أكثر بدون إعادة استخدام GUIDs القديمة

ومع ذلك ، إذا كان إخراج الطاقة بالكامل للشمس موجهاً لتنفيذ هذه المهمة ، فستبقى باردة قبل أن تنتهي.

يمكن إنشاء GUID باستخدام عدد من التكتيكات المختلفة ، وبعضها يتخذ إجراءات خاصة لضمان عدم إنشاء جهاز معين نفس GUID مرتين. سيظهر البحث عن الاصطدامات في خوارزمية معينة أن أسلوبك الخاص لتوليد GUIDs سيئ ، ولكنه لن يثبت شيئًا عن GUID بشكل عام.


Answer #16

المعرفات الفريدة العمومية (GUID) هي 124 بتة لأن 4 بت تحتفظ برقم الإصدار.


Answer #17

العد إلى 2 ^ 128 - طموح.

دعونا نتخيل أنه يمكننا عد 2 ^ 32 معرفًا في الثانية لكل جهاز - وهذا ليس طموحًا ، حيث إنه لا يصل إلى 4.3 مليار في الثانية. دعونا تكريس آلات 2 ^ 32 لتلك المهمة. علاوة على ذلك ، يتيح الحصول على 2 ^ 32 حضارات لكل تخصيص نفس الموارد لهذه المهمة.

حتى الآن ، يمكننا حساب 2 ^ 96 معرفًا في الثانية ، مما يعني أننا سنحتسب لمدة ثانيتين و 32 ثانية (أكثر بقليل من 136 عامًا).

الآن ، كل ما نحتاجه هو الحصول على 4،294،967،296 حضارة لكل مكرّسة تبلغ 4،294،967،296 آلة ، كل آلة قادرة على عد 4،294،967،296 معرف في الثانية ، فقط لهذه المهمة على مدى 136 سنة أو نحو ذلك - أقترح أن نبدأ هذه المهمة الأساسية الآن. -)


Answer #18

الحل الوحيد لإثبات المعرفات الفريدة العمومية (GUIDs) ليست فريدة من نوعها سيكون عن طريق وجود تجمع GUID العالمي. في كل مرة يتم إنشاء GUID في مكان ما ، يجب أن يتم تسجيله إلى المؤسسة. أو هيك ، قد نضمن تقييماً يحتاج جميع المولدات المعرف الفريد العمومي (GUID) إلى تسجيله تلقائيًا ولأنه يحتاج إلى اتصال إنترنت نشط!


Answer #19

إذا كان رقم UUID الذي يتم إنشاؤه يتبع قانون Moore ، فإن الانطباع بعدم تشغيل المعرّف الفريد العمومي (GUID) أبداً في المستقبل المنظور غير صحيح.

مع UUIDs 2 ^ 128 ، سوف يستغرق فقط 18 شهرا * Log2 (2 ^ 128) ~ = 192 سنة ، قبل نفاد جميع UUIDs.

وأعتقد (مع عدم وجود دليل إحصائي ما هو أكثر من أي وقت مضى) في السنوات القليلة الماضية منذ التبني الشامل للـ UUID ، فإن السرعة التي ننتجها UUID تتزايد بشكل أسرع من إملاء قانون Moore. بعبارة أخرى ، ربما يكون لدينا أقل من 192 عامًا حتى نتعامل مع أزمة الاتحاد المعرفي ، وهذا أقرب بكثير من نهاية الكون.

ولكن بما أننا لن ننفذها بالتأكيد بحلول نهاية عام 2012 ، فسوف نتركها للأنواع الأخرى للقلق بشأن المشكلة.


Answer #20

ألست جميعًا تفتقد نقطة رئيسية؟

اعتقدت أن تم إنشاء GUID باستخدام أمرين مما يجعل فرص كونها فريدة من نوعها على مستوى العالم مرتفعة للغاية. واحد هو أنها مصنفة مع عنوان MAC الخاص بالجهاز الذي تستخدمه واثنان يستخدمان الوقت الذي تم إنشاؤه بالإضافة إلى رقم عشوائي.

لذلك ما لم تقم بتشغيله على الجهاز الفعلي وتشغيل كل التخمينات ضمن أصغر مقدار من الوقت الذي يستخدمه الجهاز لتمثيل وقت في GUID لن تقوم أبداً بإنشاء نفس العدد بغض النظر عن عدد التخمينات التي قمت بها باستخدام استدعاء النظام.

أعتقد إذا كنت تعرف أن الطريقة الفعلية يتم إجراء GUID بالفعل تقصير الوقت لتخمين بشكل كبير.

توني


Answer #21

إذا كانت اصطدامات GUID مصدر قلق ، فإنني أوصي باستخدام ScottGuID بدلاً من ذلك.


Answer #22

[تحديث:] كما تشير التعليقات أدناه ، فإن GUIDs MS الأحدث هي V4 ولا تستخدم عنوان MAC كجزء من جيل GUID (لم أر أي مؤشر على تنفيذ V5 من MS ، حتى إذا كان لدى أي شخص رابط يؤكد لي أن أعرف). ومع ذلك ، فإن الوقت لا يزال يمثل عاملًا ، ومع ذلك تظل احتمالات التعارض مع GUID صغيرة جدًا بحيث لا تكون ذات صلة بأي استخدام عملي. أنت بالتأكيد لن يكون من المرجح أن تقوم بإنشاء GUID مكررة من مجرد اختبار نظام واحد مثل OP كان يحاول القيام به.

تفتقد معظم هذه الإجابات نقطة حيوية واحدة حول تطبيق GUID الخاص بـ Microsoft. يستند الجزء الأول من GUID إلى طابع زمني ويقوم جزء آخر على عنوان MAC الخاص ببطاقة الشبكة (أو رقم عشوائي إذا لم يتم تثبيت NIC).

إذا فهمت ذلك بشكل صحيح ، فهذا يعني أن الطريقة الوحيدة الموثوقة لتكرار المعرِّف الفريد العمومي (GUID) هي تشغيل أجيال GUID المتزامنة على أجهزة متعددة حيث كانت عناوين MAC متماثلة وحيث كانت الساعات على كلا النظامين في نفس الوقت بالضبط عند توليد حدث (الطابع الزمني مبني على ميلي ثانية إذا كنت أفهمها بشكل صحيح) .... حتى إذا كان هناك الكثير من البتات الأخرى في العدد العشوائي ، لذلك لا تزال الاحتمالات صغيرة بشكل فاضح.

لجميع الأغراض العملية ، تكون المعرفات الفريدة العمومية (GUID) فريدة من نوعها عالمياً.

يوجد وصف جيد لـ MS GUID في مدونة "The Old New Thing"


Answer #23

أي GUIDs اثنين من المحتمل جداً فريدة (غير متساوية).

انظر هذا الدخول SO ، ومن Wikipedia

على الرغم من أن كل GUID الذي تم إنشاؤه ليس مضمونًا ليكون فريدًا ، فإن إجمالي عدد المفاتيح الفريدة (2 ^ 128 أو 3.4 × 10 ^ 38) كبير للغاية بحيث يكون احتمال وجود نفس الرقم مرتين هو صغير جدًا. على سبيل المثال ، ضع في اعتبارك الكون المرئي ، الذي يحتوي على حوالي 5 × 10 ^ 22 نجم ؛ يمكن أن يكون لكل نجم ثم 6.8 × 10 ^ 15 GUIDs الفريدة عالمياً.

لذا عليك أن تنتظر الكثير من مليارات السنين ، وتأمل أن تضرب أحدها قبل الكون كما نعرف أنه ينتهي.





guid