سؤال مصاحبه

چرا کش کلید-مقدار استخری از بلوک‌های 16 توکنی است؟

Why the KV cache is a pool of 16-token blocks

  • سطح ۲: میانی
  • مفهومی
  • ۸ دقیقه

توضیح دهید vLLM چگونه کش کلید-مقدار (KV cache) را در حافظه‌ی GPU نگه می‌دارد. چرا به هر درخواست یک بافر اختصاصی نمی‌دهد، چطور پرامپتی را که قبلاً دیده تشخیص می‌دهد، و وقتی حافظه تمام می‌شود چه اتفاقی می‌افتد؟

اول خودتان جواب بدهید، بعد پاسخ را باز کنید.

پاسخ کوتاه

کش کلید-مقدار یک استخرِ واحد از بلوک‌های 16 توکنی است و هر درخواست هم‌زمان با رشد خود، بلوک‌ها را یکی‌یکی دریافت می‌کند که با یک جدول بلوک (Block Table) کوچک نگاشت می‌شوند. اختصاص یک بافر به ازای هر درخواست حافظه را در دو جا هدر می‌دهد: یکی برای طولی که درخواست هرگز به آن نمی‌رسد، و دیگری در فاصله‌ی خالی بین درخواست‌هایی با اندازه‌های مختلف. هر بلوک کامل، هشی دریافت می‌کند که با هش بلوکِ قبل از خودش زنجیر می‌شود؛ بنابراین یک هش هویت یک پیشوند کامل است و هر درخواست جدید زنجیره‌ی خود را بررسی می‌کند و با دیدن اولین خطا (miss) متوقف می‌شود. وقتی هیچ بلوک آزادی نباشد، اسکژولر (Scheduler) روی جدیدترین درخواست پیش‌دستی (Preemption) می‌کند و بعداً آن را دوباره محاسبه خواهد کرد.

پاسخ کامل

بلوک‌ها، نه بافرها

سامانه‌ی vLLM هنگام راه‌اندازی، کش را به بلوک‌های 16 توکنی خرد می‌کند و همه‌ی آن‌ها را درون یک استخرِ واحد نگه می‌دارد. لزومی ندارد بلوک‌های یک درخواست کنار هم قرار بگیرند. یک جدول بلوک، موقعیت توکن‌های درخواست را به شماره‌ی بلوک‌ها نگاشت می‌کند. مقاله‌ی اصلی، با الهام از نحوه‌ی صفحه‌بندی (paging) حافظه در سیستم‌عامل‌ها، این سازوکار را پجد اتنشن (PagedAttention) نامید.

این درس نشان می‌دهد ساختار فوق جلوی چه حجم عظیمی از هدررفت حافظه را می‌گیرد. تخصیص‌دهنده‌های سنتی حافظه که طول کامل را برای هر درخواست رزرو می‌کنند، بین 60 تا 80 درصد حافظه را به خاطر تکه‌تکه شدن (fragmentation) هدر می‌دهند. با بلوک‌ها، این هدررفت زیر 4 درصد می‌ماند. برای یک مدل 70B با طول دنباله‌ی 8192 توکن در فرمت BF16، فضای رزروشده برای یک دنباله حدود 1.25 گیگابایت است؛ اگر درخواستی فقط از 1500 توکن استفاده کند، نزدیک به 82 درصد آن را تلف کرده است.

زنجیره‌ی هش

وقتی یک بلوک پر می‌شود، vLLM توکن‌های آن را همراه با هشِ بلوکِ قبلی هش می‌کند. به لطف این زنجیره، یک هش هویتِ کلِ یک پیشوند است، نه فقط 16 توکن. این هش ورودی‌های دیگری را هم که کلیدها و مقدارها را تغییر می‌دهند پوشش می‌دهد: تطبیق‌دهنده‌ی (Adapter) مربوط به LoRA، تصاویر موجود در پرامپت، و یک salt اختیاری به ازای هر درخواست. هر درخواست جدید همین زنجیره را روی پرامپت خود حساب می‌کند و تک‌تک هش‌ها را داخل یک جدول جست‌وجو می‌نماید. هر بلوکی که قبل از اولین خطا قرار دارد اصابت (hit) محسوب می‌شود و به هیچ محاسبه‌ای نیاز ندارد. فقط بلوک‌های کامل کش می‌شوند؛ بنابراین دُم پرامپت که زیر 16 توکن است همیشه محاسبه می‌شود.

از نسخه‌ی 0.11 به بعد، این هش به‌طور پیش‌فرض SHA-256 است. هش سریع‌تری هم وجود دارد، ولی مستندات هشدار می‌دهند که رخداد تصادم (collision) ممکن است بلوک‌های نادرست برگرداند یا داده‌ها را بین مستأجرانِ مختلف نشت دهد.

پاک‌سازی

بلوکی که هیچ درخواستی از آن استفاده نمی‌کند وارد فهرستِ بلوک‌های آزاد می‌شود و هش خود را نگه می‌دارد. اگر بعداً درخواستی با همان پیشوند برسد، همچنان می‌تواند از آن استفاده کند. زمانی که vLLM به یک بلوک جدید نیاز داشته باشد، ابتدای فهرست بلوک‌های آزاد را برمی‌دارد؛ یعنی بلوکی را که بیش از بقیه بلااستفاده مانده است. تنها در این لحظه محتوای قدیمی از بین می‌رود. بنابراین کل کش همان استخر است: هیچ حافظه‌ی جداگانه‌ای برای کش وجود ندارد، و یک سرور شلوغ پیشوندهای قدیمیِ کمتری را نسبت به یک سرور خلوت نگه می‌دارد.

وقتی حافظه تمام می‌شود

هر درخواستِ در حال اجرا، هر 16 توکن یک‌بار به یک بلوک جدید نیاز دارد. اگر بلوک آزادی نباشد، اسکژولر روی یک درخواست پیش‌دستی می‌کند. طبق سیاست پیش‌فرضِ «اولویت با ورودِ اول» (first-come)، جدیدترین درخواستِ در حال اجرا را انتخاب می‌کند، همه‌ی بلوک‌هایش را آزاد می‌سازد، و آن را دوباره به ابتدای صف انتظار برمی‌گرداند. وقتی درخواست دوباره اجرا شود، vLLM توکن‌های آن را از نو محاسبه می‌کند. نسخه‌های قدیمی‌تر می‌توانستند بلوک‌ها را به حافظه‌ی CPU کپی و دوباره برگردانند؛ اما موتور کنونی فقط محاسبه‌ی مجدد انجام می‌دهد، چون طبق ارزیابی مستندات، این کار کم‌هزینه‌تر است. این هزینه خود را به‌صورت زمان طولانی‌تر برای درخواستِ تعلیق‌شده و در شمارنده‌ی vllm:num_preemptions نشان می‌دهد.

مدل‌های ترکیبی

مدلی که از لایه‌های پنجره‌ی لغزان (Sliding-window) یا فضای حالت (State-space) استفاده می‌کند، در تمام لایه‌ها یک ورودی به ازای هر توکن نگه نمی‌دارد. هر نوع لایه، گروهِ اختصاصی خود را با اندازه‌ی صفحه‌ی جداگانه و قانون اصابت مخصوص به خود دارد. این گروه‌ها در یک استخرِ واحد سهیم هستند.

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 2: همه‌ی درخواست‌ها با 25 توکن یکسان شروع می‌شوند. چه تعداد از آن‌ها از کش خوانده می‌شوند؟ پاسخ مورد انتظار: 16 تا، یعنی یک بلوک کامل؛ 9 توکن باقی‌مانده روی هر درخواست محاسبه می‌شوند، چون فقط بلوک‌های پر در کش قرار می‌گیرند.
  • سطح 3: دو مستأجر پرامپت سیستمیِ یکسانی می‌فرستند. چه اطلاعاتی را ممکن است یکی از دیگری بفهمد، و کدام فیلد جلوی آن را می‌گیرد؟ پاسخ مورد انتظار: آن‌ها بلوک‌ها را به اشتراک می‌گذارند، بنابراین زمان‌بندی پردازشِ یکی می‌تواند ورودی ارسالیِ دیگری را لو بدهد؛ فیلد cache_salt به ازای هر مستأجر وارد هش می‌شود تا این دو هرگز بلوکی را به اشتراک نگذارند.
  • سطح 4: در سیاست پیش‌فرض، وقتی هیچ بلوکی آزاد نیست، vLLM روی کدام درخواست پیش‌دستی می‌کند و این کار چقدر هزینه دارد؟ پاسخ مورد انتظار: جدیدترین درخواستِ در حال اجرا؛ همه‌ی بلوک‌هایش آزاد می‌شوند، به ابتدای صف انتظار می‌رود و توکن‌هایش از نو محاسبه می‌شوند؛ موضوعی که شمارنده‌ی پیش‌دستی آن را ثبت می‌کند.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «سامانه‌ی vLLM درخواست‌های تعلیق‌شده را به حافظه‌ی CPU منتقل (swap) می‌کند.» نسخه‌های قبلی این قابلیت را داشتند؛ موتور فعلی فقط محاسبه‌ی مجدد انجام می‌دهد، چون طبق مستندات ارزان‌تر تمام می‌شود و هزینه‌ی آن در زمان طولانی‌تر همان درخواست و در شمارنده‌ی پیش‌دستی نمایان است.
  • «کش پیشوندها، سهمیه‌ی حافظه‌ی اختصاصی دارد.» کل کش همان استخر است؛ بلوکِ آزادشده تا وقتی که بلوک جدیدی نیاز نباشد، هش خود را در فهرست بلوک‌های آزاد حفظ می‌کند؛ در نتیجه یک سرور شلوغ پیشوندهای قدیمی کمتری نسبت به یک سرور خلوت نگه می‌دارد.
  • «هش هر بلوک تنها 16 توکنِ خودش را پوشش می‌دهد.» این مقدار با هش بلوک قبلی زنجیر می‌شود، بنابراین یک هش نماینده‌ی کل یک پیشوند است و علاوه بر آن تطبیق‌دهنده، تصاویر و salt را هم پوشش می‌دهد.

کجای دوره آموزش داده می‌شود

بخش نحوه‌ی مدیریت حافظه‌ی KV در استخر بلوک‌ها این استخر را توضیح می‌دهد، بخش سهمیه‌ی توکن به پیش‌دستی می‌پردازد، و درس ساختار داخلی موتور ارائه‌ی سرویس آمارهای تکه‌تکه شدن حافظه را ارائه می‌کند.