microsoft / l4 Goto Github PK

L4 (Lock-Free on Read) Hashtable is a C++ library that implements hash table with arbitray byte stream keys/values.

License: Other

C++ 97.80% C 1.55% CMake 0.65%

store keyvaluestore lockfree cplusplus lock-free hashtable cross-platform

l4's Introduction

L4 HashTable

L4 (Lock-Free on Read) Hashtable is a C++ library that provides a fixed-size hashtable, where keys and values are arbitrary bytes.

L4 HashTable is optimized for lookup operations. It uses Epoch Queue (deterministic garbage collector) to achieve lock-free lookup operations.

L4 HashTable supports caching based on memory size and time. It uses Clock algorithm for an efficient cache eviction.

L4 HashTable is built with interprocess communication in mind and its shared memory implementation (multiple-readers-single-writer model at process level) is coming soon.

Installation

Visual C++ (Windows)

This library is developed and maintained with Visual Studio 2019. Visual Studio 2019 Community is available for free here.

To get started, open the L4.sln file and build the solution. Initially, it will automatically start downloading boost NuGet package before build starts.

GCC

This library is tested with GCC 6.2. You can run the following commands to get started:

cmake -DBOOST_ROOT=<boost root directory> CMakeLists.txt
make
make test

Getting Started

Start with a simple example.

Check out the wiki.

Contributing

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact [email protected] with any additional questions or comments.

License

Code licensed under the MIT License.

l4's People

Contributors

Stargazers

Watchers

l4's Issues

Add vcpkg package

ITNOA

Please add vcpkg and update readme to helping install this library by vcpkg

Question: Big-endian support

In Metadata.h#L68 the most significant byte of the uint32_t metadatum is accessed by interpreting it as an array of uint8_t and indexing it at the fixed index 3.

As the comment in line 75 of the same file points out, this obviously will only work on little endian machines. I am assuming that this means L4 will not work on big endian machines (e.g. IBM's AIX).

Is this the only issue preventing big endian support or are there other parts (e.g. MurmurHash3.cpp) that would also need to be adapted to support big endian?

Missing continuous integration

Would be good to integrate with Travis CI and AppVeyor for example.

Question: Allocation of RecordBuffer in shared memory context

I am trying to use the hash table in a scenario where the hash table and its records are placed in a fixed size, pre-allocated chunk of shared memory accessed by multiple processes. Allocations in this chunk of shared memory would be managed by a custom allocator.

Adding a key-value pair to a hash table via WritableHashTable::Add causes WritableHashTable::CreateRecordBuffer to be called internally, which allocates a buffer of sufficient size. As far as I can see the allocation does not happen in the critical section of the Add method, thus the custom allocator mentioned above would have to take care of executing these allocations serially.

The README mentions a shared memory implementation, but it is unclear to me how far this shared memory implementation has progressed.
Am I missing something here or is making the custom allocator "multiprocess aware" the only option?

This repo is missing important files

There are important files that Microsoft projects should all have that are not present in this repository. A pull request has been opened to add the missing file(s). When the pr is merged this issue will be closed automatically.

Microsoft teams can learn more about this effort and share feedback within the open source guidance available internally.

Merge this pull request