Memory Management and Eviction

Purpose and Scope

This document describes the memory management and eviction mechanisms implemented in the SwooleStore cache driver. The SwooleStore operates in shared memory using Swoole tables, which have fixed size constraints. To prevent memory exhaustion, the store implements multiple eviction policies (LRU, LFU, TTL, NOEVICTION) that automatically remove entries when memory limits are reached. The system uses a LimitedMaxHeap data structure to efficiently identify and evict records based on the selected policy.

For information about the SwooleStore configuration and usage, see 3.2. For other cache stores that do not require eviction management, see 3.

Eviction Policies

The SwooleStore supports four eviction policies that determine which cache entries are removed when memory limits are reached. The policy is configured via the eviction_policy configuration option.

Policy Constants

src/SwooleStore.php16-22 defines the available eviction policies as class constants:

Policy Constant	Value	Behavior
EVICTION_POLICY_LRU	'lru'	Evicts least recently used entries based on last_used_at timestamp
EVICTION_POLICY_LFU	'lfu'	Evicts least frequently used entries based on used_count
EVICTION_POLICY_TTL	'ttl'	Evicts entries with nearest expiration based on expiration timestamp
EVICTION_POLICY_NOEVICTION	'noeviction'	Disables eviction; writes fail when memory is full

Sources: src/SwooleStore.php16-22

Policy Implementation

The removeRecordsByEvictionPolicy() method src/SwooleStore.php298-317 dispatches to the appropriate eviction handler:

• LRU: removeRecordsByLRU() src/SwooleStore.php319-322 evicts entries with the oldest last_used_at timestamp
• LFU: removeRecordsByLFU() src/SwooleStore.php324-327 evicts entries with the lowest used_count
• TTL: removeRecordsByTTL() src/SwooleStore.php329-332 evicts entries with the nearest expiration timestamp
• NOEVICTION: Returns early without evicting any records src/SwooleStore.php300-302

All three active policies delegate to handleRecordsEviction() src/SwooleStore.php334-354 passing the column name to sort by.

Sources: src/SwooleStore.php298-332

Memory Limit Detection

The SwooleStore monitors memory usage and triggers eviction when limits are approached. Memory detection occurs in the memoryLimitIsReached() method src/SwooleStore.php288-296

Memory Metrics

The system evaluates two metrics from Swoole table statistics:

Conflict Rate: Measures hash collision density in the Swoole table. Calculated as 1 - (available_slice_num / total_slice_num) src/SwooleStore.php291

Memory Usage: Measures record density. Calculated as num / table->getSize() src/SwooleStore.php292

Allowed Memory Usage: Calculated as 1 - memoryLimitBuffer src/SwooleStore.php293 The memoryLimitBuffer is a configuration parameter (typically 0.1 or 10%) that provides headroom before the table is completely full.

The memory limit is considered reached when either the conflict rate or memory usage exceeds the allowed threshold src/SwooleStore.php295

Sources: src/SwooleStore.php288-296

Configuration Parameters

The SwooleStore constructor src/SwooleStore.php34-40 accepts memory management parameters:

Parameter	Type	Purpose
$memoryLimitBuffer	float	Headroom before memory is full (e.g., 0.1 = 10%)
$evictionPolicy	string	One of the policy constants (LRU/LFU/TTL/NOEVICTION)
$evictionProportion	float	Fraction of records to evict per cycle (e.g., 0.05 = 5%)

Sources: src/SwooleStore.php34-40

Eviction Process

The eviction process is triggered after every put() operation src/SwooleStore.php94 via the evictRecords() method src/SwooleStore.php249-256

Sources: src/SwooleStore.php85-97 src/SwooleStore.php249-256

Step 1: Flush Stale Records

The flushStaleRecords() method src/SwooleStore.php356-371 removes all expired entries before checking memory limits. This ensures that naturally expired entries are cleaned up first before applying the eviction policy.

The method iterates through all table records, compares each expiration timestamp against the current time src/SwooleStore.php363 and deletes expired keys src/SwooleStore.php368-370

Sources: src/SwooleStore.php356-371

Step 2: Check Memory Limit Loop

After flushing stale records, the eviction loop src/SwooleStore.php253-255 continues while memoryLimitIsReached() returns true. This ensures that if a single eviction cycle doesn't free enough memory, additional cycles run until the memory usage drops below the threshold.

Sources: src/SwooleStore.php253-255

Step 3: Policy-Based Eviction

The handleRecordsEviction() method src/SwooleStore.php334-354 implements the core eviction logic for LRU, LFU, and TTL policies:

1. Calculate Quantity: Determines how many records to evict as table->getSize() * evictionProportion src/SwooleStore.php336 For example, with an eviction proportion of 0.05, it evicts 5% of table capacity per cycle.

2. Create Heap: Instantiates an anonymous class extending LimitedMaxHeap with the calculated quantity src/SwooleStore.php338-343 The comparison function sorts by the specified column (e.g., last_used_at for LRU).

3. Populate Heap: Iterates through all table records, inserting {key, value} pairs into the heap src/SwooleStore.php345-349 The heap automatically maintains only the records with the smallest values for the sort column.

4. Remove Records: Extracts all records from the heap and deletes them src/SwooleStore.php351-353

Sources: src/SwooleStore.php334-354

LimitedMaxHeap Data Structure

The LimitedMaxHeap class src/LimitedMaxHeap.php9-30 is a specialized heap data structure that extends SplMaxHeap to maintain a fixed-size collection of records with the smallest values for eviction.

Design Pattern

Sources: src/LimitedMaxHeap.php9-30 src/SwooleStore.php338-353

Key Features

Fixed Size: The heap is initialized with a $limit parameter src/LimitedMaxHeap.php11 Once the limit is reached, new insertions only succeed if the new value is smaller than the current maximum.

Max Heap Semantics: As a max heap, the top() element has the largest value. When full, the heap maintains the N smallest values from all insertions.

Efficient Eviction: Instead of sorting all records (O(n log n)), the heap approach is O(n log k) where k is the eviction quantity. For evicting 5% of 10,000 records, this means O(10,000 log 500) vs O(10,000 log 10,000).

Custom Comparison: The anonymous class in handleRecordsEviction() src/SwooleStore.php338-343 defines comparison logic that sorts by the target column value src/SwooleStore.php341

Sources: src/LimitedMaxHeap.php9-30 src/SwooleStore.php338-343

Insert Algorithm

The insert() method src/LimitedMaxHeap.php15-29 implements the following logic:

1. Under Limit: If count() < limit, directly insert into the parent heap src/LimitedMaxHeap.php17-20
2. At Limit: If the new value is smaller than the current top (largest), extract the top src/LimitedMaxHeap.php22-24
3. Always Insert: Always insert the new value into the parent heap src/LimitedMaxHeap.php26

This maintains the invariant that after all insertions, the heap contains the N records with the smallest values for the sort column.

Sources: src/LimitedMaxHeap.php15-29

Access Tracking

To support LRU and LFU eviction policies, the SwooleStore tracks access patterns for each cache entry.

Tracking Mechanism

The getRecord() method src/SwooleStore.php261-275 updates tracking metadata on every cache read:

• Last Used Timestamp: Sets last_used_at to the current timestamp src/SwooleStore.php269
• Usage Count: Increments used_count src/SwooleStore.php270

These updates are written back to the Swoole table immediately src/SwooleStore.php272 The get() method uses getRecord() src/SwooleStore.php47 ensuring all read operations update tracking metadata.

Sources: src/SwooleStore.php45-61 src/SwooleStore.php261-275

Configuration Example

A typical configuration for SwooleStore with memory management:

This configuration:

• Triggers eviction when 90% of table capacity is used (90% = 100% - 10% buffer)
• Uses LRU policy to select victims
• Evicts approximately 500 records (5% of 10,000) per eviction cycle
• Continues evicting until memory usage drops below 90%

Sources: src/SwooleStore.php34-40