تولیدکننده شناسه برفی - ایجاد شناسه‌های توزیع‌شده یکتا

مولد شناسهٔ اسنوفلیک چیست؟

مولد شناسهٔ اسنوفلیک یک عدد ۶۴ بیتی یکتا را از مهر زمانی، شناسهٔ ماشین و شمارهٔ توالی می‌سازد. توییتر این قالب را در ۲۰۱۰ ایجاد کرد تا هر توییت شناسه‌ای داشته باشد که بسیاری از سرورها بتوانند هم‌زمان آن را تولید کنند، بدون اینکه از یکدیگر بپرسند «آیا این عدد قبلاً استفاده شده است؟» این ابزار با استفاده از مقادیر واردشده یک شناسهٔ اسنوفلیک می‌سازد و نشان می‌دهد این مقادیر چگونه ۶۴ بیت را پر می‌کنند.

مولد شناسهٔ اسنوفلیک چگونه کار می‌کند

مولد چهار ورودی می‌گیرد:

• مهر زمانی: مهر زمانی یونیکس برحسب میلی‌ثانیه. برای استفاده از زمان فعلی، آن را خالی بگذارید.
• شناسهٔ ماشین: عددی صحیح از ۰ تا ۳۱ (۵ بیت). این همان «شناسهٔ کارگر» اولیهٔ توییتر است.
• شناسهٔ مرکز داده: عددی صحیح از ۰ تا ۳۱ (۵ بیت).
• شمارهٔ توالی: عددی صحیح از ۰ تا ۴۰۹۵ (۱۲ بیت) که برای متمایز کردن شناسه‌های ایجادشده در یک میلی‌ثانیهٔ یکسان به کار می‌رود.

ابزار این چهار مقدار را در یک شناسهٔ ۶۴ بیتی ترکیب می‌کند. سپس نتیجه را به‌صورت دودویی نشان می‌دهد و آن را به بخش‌های مهر زمانی، مرکز داده، ماشین و توالی تقسیم می‌کند.

مهر زمانی از یک نقطهٔ شروع ثابت به نام دورهٔ توییتر اندازه‌گیری می‌شود: ۴ نوامبر ۲۰۱۰، ساعت ۱:۴۲:۵۴٫۶۵۷ به وقت UTC، یا ۱٬۲۸۸٬۸۳۴٬۹۷۴٬۶۵۷ میلی‌ثانیه پس از دورهٔ یونیکس. این مولد اجازهٔ تغییر آن نقطهٔ شروع را نمی‌دهد. هر شناسه‌ای که تولید می‌کند از همان تاریخ ثابت اندازه‌گیری می‌شود.

ساختار شناسهٔ اسنوفلیک

شناسهٔ اسنوفلیک یک عدد صحیح ۶۴ بیتی است که از پرارزش‌ترین بیت به سمت پایین به چهار بخش تقسیم می‌شود:

بیت ابتدایی همیشه ۰ است؛ بنابراین شناسهٔ اسنوفلیک همیشه عددی مثبت است. فیلد مهر زمانی ۴۱ بیتی و فیلد توالی ۱۲ بیتی دو بخشی هستند که شناسه‌های اسنوفلیک را برای مرتب‌سازی مناسب می‌کنند: شناسه‌هایی که دیرتر ساخته شده‌اند بخش مهر زمانی بزرگ‌تری دارند و پس از شناسه‌های قبلی قرار می‌گیرند.

فرمول شناسهٔ اسنوفلیک

مولد شناسه را با این فرمول می‌سازد:

$d = t - 1288834974657$

$I = (d << 22) \mathbin{|} (c << 17) \mathbin{|} (m << 12) \mathbin{|} s$

در اینجا d اختلاف، t مهر زمانی واردشده برحسب میلی‌ثانیه، I شناسهٔ نهایی، c شناسهٔ مرکز داده، m شناسهٔ ماشین و s شمارهٔ توالی است.

<< به‌معنای شیفت بیتی به چپ است. شیفت دادن یک عدد به اندازهٔ ۲۲ بیت به چپ، معادل ضرب آن در ۲²²، یا ۴٬۱۹۴٬۳۰۴، است. مقادیر شیفت (۲۲، ۱۷، ۱۲) مستقیماً از عرض فیلدها به دست می‌آیند: فیلد توالی ۱۲ بیت عرض دارد، پس شناسهٔ ماشین ۱۲ بیت بالاتر قرار می‌گیرد؛ فیلد ماشین ۵ بیت عرض دارد، پس شناسهٔ مرکز داده ۱۷ بیت بالاتر قرار می‌گیرد (۱۲ + ۵)؛ و به همین ترتیب.

روش محاسبهٔ شناسهٔ اسنوفلیک: مثال حل‌شده

فرض کنید فردی این مقادیر را وارد کند:

• مهر زمانی: ۱٬۲۸۸٬۸۳۴٬۹۷۵٬۶۵۷ (دقیقاً ۱٬۰۰۰ میلی‌ثانیه پس از دورهٔ توییتر)
• شناسهٔ مرکز داده: ۱
• شناسهٔ ماشین: ۱
• شمارهٔ توالی: ۰

گام ۱ — یافتن اختلاف. دوره را از مهر زمانی کم کنید: ۱٬۲۸۸٬۸۳۴٬۹۷۵٬۶۵۷ − ۱٬۲۸۸٬۸۳۴٬۹۷۴٬۶۵۷ = ۱٬۰۰۰.

گام ۲ — شیفت دادن هر فیلد به جایگاه خود.

• مهر زمانی: ۱٬۰۰۰ << ۲۲ = ۴٬۱۹۴٬۳۰۴٬۰۰۰
• شناسهٔ مرکز داده: ۱ << ۱۷ = ۱۳۱٬۰۷۲
• شناسهٔ ماشین: ۱ << ۱۲ = ۴٬۰۹۶
• توالی: ۰

گام ۳ — ترکیب با عملگر OR بیتی. چون هیچ‌یک از فیلدهای شیفت‌داده‌شده با یکدیگر هم‌پوشانی ندارند، جمع کردن آن‌ها همان نتیجهٔ اعمال OR را می‌دهد:

۴٬۱۹۴٬۳۰۴٬۰۰۰ + ۱۳۱٬۰۷۲ + ۴٬۰۹۶ + ۰ = ۴٬۱۹۴٬۴۳۹٬۱۶۸

این مقدار شناسهٔ اسنوفلیک برای این ورودی است. نمای نتیجهٔ ابزار همان رشتهٔ دودویی ۶۴ بیتی را دوباره به یک بلوک مهر زمانی ۴۱ بیتی، یک بلوک مرکز دادهٔ ۵ بیتی، یک بلوک ماشین ۵ بیتی و یک بلوک توالی ۱۲ بیتی تقسیم می‌کند تا ساختار عدد قابل مشاهده بماند.

شناسه‌های اسنوفلیک کجا استفاده می‌شوند؟

توییتر این قالب را ایجاد کرد تا برای توییت‌ها در هزاران ماشین پایگاه داده، بدون شمارندهٔ مرکزی‌ای که همهٔ سرورها مجبور باشند آن را بررسی کنند، شناسه‌های یکتا و تقریباً مرتب‌شده بر اساس زمان فراهم کند. دیسکورد و اینستاگرام بعدها طراحی‌های مشابه شناسهٔ ۶۴ بیتی را برای پیام‌ها و پست‌ها به کار گرفتند. همین ایده در بخش‌بندی پایگاه داده، شناسه‌های سفارش در سامانه‌های تجارت الکترونیکی و گزارش‌های رویداد در برنامه‌های توزیع‌شده نیز دیده می‌شود. این روش برای هر محیطی مناسب است که در آن ماشین‌های بسیاری به‌طور مستقل شناسه صادر می‌کنند و همچنان به مرتب‌سازی تقریبی بر اساس زمان نیاز دارند.

محدودیت‌های شناسه‌های اسنوفلیک

یک مولد اسنوفلیک عملیاتی معمولاً ساعت داخلی خود را حفظ می‌کند: برای هر شناسه‌ای که در همان میلی‌ثانیه ساخته می‌شود، شمارهٔ توالی را افزایش می‌دهد و وقتی توالی به ۴٬۰۹۵ برسد، تا میلی‌ثانیهٔ بعد صبر می‌کند. این ابزار بین محاسبات حافظه‌ای ندارد. از هر مقادیری که وارد شوند یک شناسه می‌سازد؛ بنابراین برای بررسی قالب مفید است، اما با یک سرویس عملیاتی زنده تفاوت دارد.

این طراحی، صرف‌نظر از اینکه کدام سرویس آن را پیاده‌سازی کند، محدودیت‌های ثابتی دارد:

• دورهٔ ثابت: این مولد فقط مهرهای زمانی در ۴ نوامبر ۲۰۱۰ یا پس از آن (دورهٔ توییتر) را می‌پذیرد. تاریخ‌های پیش از آن قابل کدگذاری نیستند.
• سقف مهر زمانی: فیلد مهر زمانی ۴۱ بیتی حوالی ژوئیهٔ ۲۰۸۰ تمام می‌شود. پس از آن، اختلاف با دوره در ۴۱ بیت جا نمی‌گیرد.
• محدودیت توالی: پیش از تکرار مقادیر، یک ماشین می‌تواند در همان میلی‌ثانیه فقط ۴٬۰۹۶ شناسهٔ متمایز (۰–۴۰۹۵) صادر کند.
• فضای ماشین: با ۵ بیت برای هرکدام از شناسهٔ ماشین و شناسهٔ مرکز داده، یک استقرار می‌تواند ۱٬۰۲۴ هویت متمایز ماشین (۳۲ × ۳۲) را بدون برخورد اختصاص دهد.
• مرتب‌سازی محلی، نه سراسری: شناسه‌ها فقط زمانی در مقایسه با یکدیگر درست مرتب می‌شوند که از ماشین‌هایی با ساعت‌های همگام آمده باشند. اختلاف ساعت میان ماشین‌ها می‌تواند ترتیب دقیق زمانی را برهم بزند.

تاریخچهٔ شناسهٔ اسنوفلیک

توییتر قالب شناسهٔ اسنوفلیک را در ۲۰۱۰ به‌عنوان جایگزینی برای شناسه‌های سادهٔ خودافزای پایگاه داده معرفی کرد؛ این شناسه‌ها در میان سرورهای مستقل متعدد پایگاه داده مقیاس‌پذیر نیستند. این نام از این ایده گرفته شد که مانند دانه‌های واقعی برف، هیچ دو شناسهٔ تولیدشده‌ای یکسان نیستند. این طراحی بعدها متن‌باز شد و پلتفرم‌های بزرگ دیگر نیز، با تغییراتی، آن را کپی کردند؛ زیرا به شناسه‌های یکتا و قابل مرتب‌سازی نیاز داشتند که چندین ماشین بتوانند هم‌زمان تولید کنند.

سؤالات رایج

شناسهٔ اسنوفلیک چیست؟ شناسهٔ اسنوفلیک عددی ۶۴ بیتی است که از مهر زمانی، شناسهٔ ماشین و شمارهٔ توالی تشکیل می‌شود و به‌گونه‌ای طراحی شده است که ماشین‌های متعدد بتوانند بدون هماهنگی با یکدیگر شناسه‌های یکتا تولید کنند.

فرمول شناسهٔ اسنوفلیک چیست؟ id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence، که در آن دوره یک تاریخ شروع ثابت است و << به‌معنای شیفت بیتی به چپ است.

آیا می‌توانم دوره را در این مولد تغییر دهم؟ خیر. این ابزار همیشه مهر زمانی را از دورهٔ ثابت توییتر، ۴ نوامبر ۲۰۱۰، اندازه‌گیری می‌کند. فیلدی برای تعیین تاریخ شروع دیگری وجود ندارد.

آیا این ابزار یک شناسهٔ اسنوفلیک موجود را رمزگشایی می‌کند؟ خیر. این ابزار فقط از مهر زمانی، شناسهٔ ماشین، شناسهٔ مرکز داده و شمارهٔ توالی واردشده یک شناسهٔ جدید می‌سازد و سپس تفکیک بیتی همان شناسهٔ جدید را نشان می‌دهد.

یک ماشین در هر میلی‌ثانیه چند شناسهٔ اسنوفلیک می‌تواند تولید کند؟ حداکثر ۴٬۰۹۶ شناسه، زیرا فیلد توالی ۱۲ بیت عرض دارد (مقادیر ۰ تا ۴٬۰۹۵).

این مولد تا چه سالی می‌تواند مهرهای زمانی معتبر تولید کند؟ تا حوالی ژوئیهٔ ۲۰۸۰. فیلد مهر زمانی ۴۱ بیتی حداکثر حدود ۶۹٫۷ سال را از دورهٔ ثابت ۲۰۱۰ در خود جای می‌دهد؛ پس از آن مقدار از ظرفیت فیلد سرریز می‌کند.

منابع

1. «معرفی اسنوفلیک». وبلاگ مهندسی توییتر، ۲۰۱۰.
2. "Snowflake ID." ویکی‌پدیا، https://en.wikipedia.org/wiki/Snowflake_ID