پس از موفقیت چشم‌گیر در پروژه‌ی Dockerious، تیم فنی پارک علم و فناوری پردیس متوجه نیاز به یک سیستم کش سریع و سبک برای سرویس‌های داخلی شده است. با الهام گرفتن از Redis، پروژه‌ی ساخت یک دیتابیس in-memory بومی با نام Redious به شما سپرده شده است. این دیتابیس باید بتواند داده‌ها را به صورت Key-Value در حافظه نگه دارد و از دیتاتایپ معمول پشتیبانی کند و یک سیاست حذف از کش LRU (Least Recently Used) برای مدیریت حافظه داشته باشد.

شما در این سوال باید استارت پیاده‌‌سازی این دیتابیس را بزنید.

جزئیات پروژه

پروژه اولیه را از این لینک دانلود کنید. ساختار پروژه به شکل زیر است:

redious/
├── datastore/
│   └── redious.go    # TODO Implement
└── main.go           # Just to see the sample result and run on your local

در این پروژه، شما باید اینترفیس DataStore و توابع مربوطه را در فایل datastore/redious.go پیاده‌سازی کنید.

آن‌چه باید پیاده‌سازی کنید

شما باید struct های cacheEntry و rediousStore را تعریف کرده و تابع سازنده NewDataStore و تمام متدهای اینترفیس DataStore را در فایل datastore/redious.go پیاده‌سازی کنید.

package datastore

// ZMember is used to pass score-member pairs to the ZAdd command.
type ZMember struct {
	Score  float64
	Member string
}

// DataStore is the main interface for our in-memory database.
type DataStore interface {
	Set(key, value string)
	Get(key string) (string, bool)
	LPush(key string, values ...string) int
	RPush(key string, values ...string) int
	LRange(key string, start, stop int) []string
	ZAdd(key string, members ...ZMember) int
	ZRange(key string, start, stop int) []string
	Incr(key string) (int, error) // Atomic operations
}

// cacheEntry holds the key and the value (actual data)
type cacheEntry struct {
	// TODO: Define necessary fields based on the table below.
}

// rediousStore is the internal implementation of our DataStore.
type rediousStore struct {
	// TODO: Define necessary fields based on the table below.
}

// NewDataStore creates a new DataStore with a given capacity.
// The capacity determines the maximum number of keys the store can hold.
// If capacity is 0, the cache has unlimited size.
func NewDataStore(capacity int) DataStore {
	// TODO: Initialize and return an instance of rediousStore
	return nil // Placeholder
}

// --- String Commands ---
func (ds *rediousStore) Set(key, value string) {
	// TODO: Implement
}

func (ds *rediousStore) Get(key string) (string, bool) {
	// TODO: Implement
	return "", false // Placeholder
}

func (ds *rediousStore) Incr(key string) (int, error) {
	// TODO: Implement
	return 0, nil // Placeholder
}

// --- List Commands ---
func (ds *rediousStore) LPush(key string, values ...string) int {
	// TODO: Implement
	return 0 // Placeholder
}

func (ds *rediousStore) RPush(key string, values ...string) int {
	// TODO: Implement
	return 0 // Placeholder
}

func (ds *rediousStore) LRange(key string, start, stop int) []string {
	// TODO: Implement
	return nil // Placeholder
}

// --- Sorted Set Commands ---
func (ds *rediousStore) ZAdd(key string, members ...ZMember) int {
	// TODO: Implement
	return 0 // Placeholder
}

func (ds *rediousStore) ZRange(key string, start, stop int) []string {
	// TODO: Implement
	return nil // Placeholder
}

**نکته مهم:** دیتابیس شما باید Thread-Safe باشد. یعنی چندین گوروتین باید بتوانند به صورت همزمان با آن کار کنند بدون اینکه race condition رخ دهد.

ساختار cacheEntry

این استراکت برای نگه‌داری اطلاعات مربوط به هر آیتم در کش استفاده می‌شود و شامل کلید و مقدار آن آیتم است.
مقدار می‌تواند از هر نوع داده‌ای باشد (رشته، لیست، مجموعه و ...).

فیلد	کاربرد
key	نگه‌داری کلید هر آیتم در کش
value	نگه‌داری مقدار آیتم (قابل پشتیبانی از انواع مختلف داده‌ها)

ساختار rediousStore

این استراکت پیاده‌سازی اصلی اینترفیس DataStore است و وضعیت کلی دیتابیس در حافظه را مدیریت می‌کند.

فیلد	کاربرد
capacity	تعیین حداکثر تعداد آیتم‌های قابل نگه‌داری در کش
items	نگه‌داری کلید و عنصر لیست برای دسترسی سریع
ll	نگه‌داری ترتیب استفاده آیتم‌ها برای پیاده‌سازی الگوریتم LRU

نیازمندی‌ها

• ظرفیت و LRU (Least Recently Used):

  • تابع سازنده NewDataStore(capacity int) یک ظرفیت دریافت می‌کند که حداکثر تعداد کلیدهای قابل ذخیره را مشخص می‌کند.
  • اگر capacity برابر با 0 باشد، دیتابیس ظرفیت نامحدود دارد و هیچ کلیدی حذف نمی‌شود.
  • اگر capacity بزرگ‌تر از 0 باشد:
    • هر عملیات خواندن (Get, LRange, ZRange) یا نوشتن (Set, LPush, RPush, ZAdd, Incr) روی یک کلید، آن را به عنوان بیشترین استفاده‌ی اخیر (MRU) علامت‌گذاری می‌کند.
    • زمانی که یک کلید جدید اضافه می‌شود و تعداد کلیدها به ظرفیت رسیده است، کلید کمترین استفاده‌ی اخیر (LRU) باید حذف شود.
    • به‌روزرسانی مقدار یک کلید موجود نباید منجر به حذف کلید دیگری شود، اما همان کلید باید به‌عنوان MRU به‌روزرسانی شود.

• مدیریت انواع داده (Type Safety):

  • هر کلید تنها می‌تواند یکی از سه نوع داده را در خود نگه دارد: String, List, یا Sorted Set (ZSet).
  • دستور Set می‌تواند نوع داده‌ی یک کلید را تغییر دهد (مثلاً از List به String).
  • سایر دستورات (مثل LPush, RPush, ZAdd, Incr) نباید نوع موجود کلید را تغییر دهند:
    • اگر نوع کلید با دستور ناسازگار باشد، عملیات باید بدون تغییر داده و بدون ایجاد کلید جدید خاتمه یابد.
    • مقدار بازگشتی در این حالت باید نشان‌دهنده‌ی شکست باشد:
      • 0 برای LPush, RPush, ZAdd
      • false یا مقدار تهی ("", nil, []) برای Get, LRange, ZRange
      • خطا (error) برای Incr

---

دستورات String

**نیازمندی‌ها:**

• Set(key, value string)

  • مقدار رشته‌ای value را برای کلید key تنظیم می‌کند.
  • اگر کلید از قبل وجود داشته باشد (از هر نوعی)، مقدار و نوع آن کاملاً جایگزین می‌شود.

• Get(key string) (string, bool)

  • مقدار رشته‌ای ذخیره‌شده برای key را برمی‌گرداند.
  • اگر کلید وجود نداشته باشد یا از نوع رشته‌ای نباشد، باید "" و false برگرداند.

• Incr(key string) (int, error)

  • مقدار رشته‌ای ذخیره‌شده در key را به عدد صحیح تبدیل کرده و یک واحد به آن اضافه می‌کند.
  • اگر کلید وجود نداشته باشد، باید با مقدار "1" ایجاد شود و مقدار 1 و nil برگرداند.
  • اگر کلید وجود داشته باشد ولی از نوع رشته‌ای نباشد، باید خطا با پیام value at key is not a string برگرداند.
  • اگر کلید وجود داشته باشد ولی مقدار رشته‌ای آن قابل تبدیل به عدد صحیح نباشد (مثلاً "abc" یا "")، باید خطا با پیام value at key is not an integer برگرداند.
  • در صورت موفقیت، باید مقدار جدید (به‌روزشده) و nil برگردانده شود.
  • این عملیات باید اتمیک (atomic) باشد.

دستورات List

**نیازمندی‌ها:**

• LPush(key string, values ...string) int

  • یک یا چند مقدار را به ابتدای لیست اضافه می‌کند.
  • ترتیب اضافه شدن باید مطابق رفتار Redis باشد: آخرین آرگومان ورودی (values)، اولین عضو جدید لیست می‌شود. (برای مثال LPush key a b c لیست را به [c, b, a, <old_items>] تبدیل می‌کند).
  • اگر کلید وجود نداشته باشد، لیست جدید ایجاد می‌شود.
  • اگر نوع کلید متفاوت باشد، عملیات انجام نمی‌شود و 0 برمی‌گردد.
  • در صورت موفقیت، طول جدید لیست بازگردانده می‌شود.

• RPush(key string, values ...string) int

  • مشابه LPush است ولی مقادیر را به انتهای لیست اضافه می‌کند.
  • سایر رفتارها مشابه LPush است.

• LRange(key string, start, stop int) []string

  • اعضای لیست را در بازه‌ی [start, stop] بازمی‌گرداند.
  • از ایندکس‌های منفی پشتیبانی می‌کند.
  • اگر کلید وجود نداشته باشد یا نوع آن List نباشد، باید []string{} برگرداند.
  • نکته مهم: اسلایس بازگشتی باید یک کپی از داده‌های داخلی باشد، نه یک ارجاع مستقیم به آن.

دستورات Sorted Set (ZSET)

**نیازمندی‌ها:**

• ZAdd(key string, members ...ZMember) int

  • یک یا چند عضو دارای امتیاز (Score) را به مجموعه‌ی مرتب‌شده اضافه می‌کند.
  • اگر کلید وجود نداشته باشد، مجموعه‌ی جدید ایجاد می‌شود.
  • اگر کلید نوع دیگری داشته باشد، عملیات انجام نمی‌شود و 0 برمی‌گردد.
  • اگر عضوی از قبل وجود داشته باشد، امتیاز آن باید به‌روزرسانی شود.
  • مجموعه باید همواره بر اساس امتیاز (و در صورت تساوی، نام عضو به ترتیب الفبایی) مرتب بماند.
  • مقدار بازگشتی باید تعداد اعضای جدیدی باشد که به مجموعه اضافه شده‌اند.
  • اگر یک Member چند بار در همان فراخوانی ZAdd تکرار شود، تنها آخرین Score آن معتبر است.

• ZRange(key string, start, stop int) []string

  • اعضای مجموعه‌ی مرتب‌شده را بر اساس رتبه در بازه‌ی [start, stop] بازمی‌گرداند.
  • از ایندکس‌های منفی پشتیبانی می‌کند.
  • اگر کلید وجود نداشته باشد یا نوع آن Sorted Set نباشد، باید []string{} برگرداند.

---

نکات

• تمرکز اصلی این سؤال بر روی مدیریت صحیح ساختار داده‌های داخلی، همزمانی (Concurrency) و منطق LRU است.

چه چیزی را آپلود کنید

پس از پیاده‌سازی کامل، صرفا تک فایل datastore/redious.go را آپلود کنید.