eclipse-iceoryx / eclipse-iceoryx/iceoryx

Implement a lock-free FIFO cache

Open
#857 0 comments 0 reactions 1 assignee Claimed by @MatthiasKillat View on GitHub
enhancement
Dominant language
C++
Stars
2.2k
Forks
492
Avg merge
18h 57m
Merged PRs (30d)
1

Description

## Brief feature description

A lock-free FIFO cache can be used to manage the historic data of a publisher.
It will be sufficiently generic for other use cases but optimized for this particular use case.

For this reason, it will only support one concurrent writer at a time (must not be the same writer but the calling code has to ensure there are no concurrent writes to the cache).
It will support multiple concurrent readers which in the main use case correspond to the subscribers reading the last couple of elements (if any).

Data will be managed as a ringbuffer (FIFO), which means if there is no space left the least recent element will be replaced.

It has to support the following operations
1. Write an element - this will evict elements in FIFO order if necessary
2. Random access read any element - this will return an element if it exists
3. Read last k elements - will return the last k elements if it is possible
4. Clear the cache - this is also a write operation and hence we expect no concurrent clear or write

## Detailed information

Implementation can be done with various atomics and an array of FIFO entries, which involves no locking and moderate memory synchronization effort.

To keep things simple and efficient we have to restrict the type to be stored to be trivially copyable, which suffices for our use case. Otherwise dealing with torn reads (where copy constructors would be involved) would become an issue. While this could be solved, it would involve rather large overhead as now it has to be ensured that while reading an element it cannot be modified (it is undefined behavior to invoke the copy ctor for a partially constructed object).

TBD:
- Reading the last k elements - there are multiple reasonable concurrent semantics to do this in case it is not possible (mainly due to concurrent overwriting of data), we need to define the one we want to use
- other considerations ?

## In scope
- Implementation and testing
- Brief design document

## Out of scope
- replacing the history with the new cache data structure
- multi writer - presumably very difficult to do lock-free and efficiently

## Further information

- for more information about the general problem of caching historic data cf.
https://github.com/eclipse-iceoryx/iceoryx/pull/780

## Differences to Queues

- writing is similar to a queue
- reading is non-destructive (as opposed to pop which takes the element from the queue)
- random access reading (as opposed to read from the front position only)

## Extensions

We may implement more complex caching structure in the future, such as a multi writer variant or a variant where we use different caching strategies (e.g. LRU) and arbitrary removals. Those are more complex to implement lock-free.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.