پس از موفقیت چشم‌گیر در پروژه‌ی `Dockerious`، تیم فنی پارک علم و فناوری پردیس متوجه نیاز به یک سیستم کش سریع و سبک برای سرویس‌های داخلی شده است. با الهام گرفتن از *Redis*، پروژه‌ی ساخت یک دیتابیس *in-memory* بومی با نام **`Redious`** به شما سپرده شده است. این دیتابیس باید بتواند داده‌ها را به صورت *Key-Value* در حافظه نگه دارد و از دیتاتایپ معمول پشتیبانی کند و یک سیاست حذف از کش *LRU (Least Recently Used)* برای مدیریت حافظه داشته باشد.
شما در این سوال باید استارت پیادهسازی این دیتابیس را بزنید.
### جزئیات پروژه
پروژه اولیه را از [این لینک](/problemset/assignments/4367/download_problem_initial_project/316824/) دانلود کنید. ساختار پروژه به شکل زیر است:
```shell
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` پیادهسازی کنید.
```go 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`
---
<details class="blue"><summary>دستورات `String`</summary>
\**نیازمندی‌ها:**
- **`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)** باشد.
</details>
<details class="blue"><summary>دستورات `List`</summary>
\**نیازمندی‌ها:**
- **`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{}` برگرداند.
- **نکته مهم:** اسلایس بازگشتی باید یک **کپی** از داده‌های داخلی باشد، نه یک ارجاع مستقیم به آن.
</details>
<details class="blue"><summary>دستورات `Sorted Set` (ZSET)</summary>
\**نیازمندی‌ها:**
- **`ZAdd(key string, members ...ZMember) int`**
- یک یا چند عضو دارای امتیاز (`Score`) را به مجموعه‌ی مرتب‌شده اضافه می‌کند.
- اگر کلید وجود نداشته باشد، مجموعه‌ی جدید ایجاد می‌شود.
- اگر کلید نوع دیگری داشته باشد، عملیات انجام نمی‌شود و `0` برمی‌گردد.
- اگر عضوی از قبل وجود داشته باشد، امتیاز آن باید به‌روزرسانی شود.
- مجموعه باید همواره بر اساس امتیاز (و در صورت تساوی، نام عضو به ترتیب الفبایی) مرتب بماند.
- مقدار بازگشتی باید تعداد **اعضای جدیدی** باشد که به مجموعه اضافه شده‌اند.
- اگر یک `Member` چند بار در همان فراخوانی `ZAdd` تکرار شود، تنها **آخرین Score** آن معتبر است.
- **`ZRange(key string, start, stop int) []string`**
- اعضای مجموعه‌ی مرتب‌شده را بر اساس رتبه در بازه‌ی `[start, stop]` بازمی‌گرداند.
- از ایندکس‌های منفی پشتیبانی می‌کند.
- اگر کلید وجود نداشته باشد یا نوع آن *Sorted Set* نباشد، باید `[]string{}` برگرداند.
</details>
---
### نکات
- تمرکز اصلی این سؤال بر روی **مدیریت صحیح ساختار داده‌های داخلی**، **همزمانی (Concurrency)** و **منطق LRU** است.
### چه چیزی را آپلود کنید
پس از پیادهسازی کامل، صرفا تک فایل `datastore/redious.go` را آپلود کنید.