DOCSEARCHbyAlgolia
Submit Docs

Keyvi

repository·master·Indexed 42 days ago

https://github.com/keyvidev/keyvi

An in-memory FST-based key-value index optimized for size and lookup performance. Version 0.7.7 supports static immutable datasets and near-realtime indexing with online writes.

Tokens
70.6K
Snippets
203
Records
298
Agent score
50%

What's inside Keyvi

  1. What is keyvi?

    master

    Keyvi (short for "Key value index") is a key-value store (KVS) optimized for minimal storage size and high lookup speed. It uses a Finite State Machine (FSM) based data structure, making it highly space-efficient and fast.

    Key features include:

    • Efficient Matching: Designed for high-performance approximate matching, such as fuzzy string matching and geo-spatial queries.
    • Immutable FST: The underlying Finite State Transducer (FST) data structure can be used as a standalone component for static datasets.
    • Near Real-time Indexing: For workloads requiring online writes, use the keyvi index component.
    • Deployment Options:
      • Embedded: Use the index as an embedded KVS within your application (e.g., alongside your own network stack).
      • Server-based: Use keyvi-server for a network-enabled store out of the box.

    The core engine is written in C++, with official bindings available for Python and Rust.

  2. Overview of UTF8-CPP

    master
    UTF8-CPP is a small, C++98 compatible generic library designed for handling UTF-8 encoded strings in a portable way. It is designed to feel natural to developers familiar with STL algorithms and iterators, providing a way to work with Unicode when the standard C++ facilities are insufficient.

  3. Overview of RapidJSON

    master

    RapidJSON is a high-performance C++ library used for parsing and generating JSON. It is a header-only library that depends only on the C++ standard library. It is designed for speed and efficiency, inspired by RapidXML, and supports both DOM and SAX-style APIs.

    Key Features:

    • Header-only: Easy to integrate.
    • Minimal Dependencies: Only requires the C++ standard library.
    • Standards Compliant: Fully complies with RFC7159 and ECMA-404.
    • Performance: Optimized for high-throughput scenarios (e.g., parsing millions of JSON objects daily).
    • Unicode Support: Supports UTF-8, UTF-16 (BE/LE), UTF-32 (BE/LE), and ASCII, including surrogate pairs and null characters (\u0000).

  4. Overview of Keyvi Key-Value Store

    master

    Keyvi (Key value index) is a key-value store (KVS) optimized for size and lookup speed. It uses a data structure based on Finite State Machines (FSM), specifically designed for space efficiency and high-speed approximate matching (such as fuzzy string matching or geo-spatial lookups).

    Keyvi offers two primary modes of operation:

    1. Immutable FST Data Structure: Can be used stand-alone for static datasets.
    2. Keyvi Index: A near-realtime index that supports online writes. It can be used as an embedded key-value store within your application or via a network-enabled server using keyvi-server.

  5. RapidJSON Key Features

    master

    RapidJSON is designed for high performance and low memory footprint:

    • Performance: Extremely fast, comparable to strlen(), with support for SSE2/SSE4.2 acceleration.
    • Memory Efficiency: On most 32/64-bit machines, each JSON value occupies only 16 bytes (excluding strings).
    • Independence: Header-only and does not depend on external libraries like BOOST or even the STL.
    • Unicode Support: Supports UTF-8, UTF-16, and UTF-32 (both big and little endian), including detection, validation, and transcoding.
    • JSON Schema: Supports validation of JSON during parsing or generation.
    • JSON Pointer: Allows for easy access and modification of DOM elements using pointer syntax.

  6. Overview of RapidJSON Stream Types

    master

    RapidJSON provides several specialized stream types for different use cases:

    • Memory Streams: Simple streams for data already in memory.
    • File Streams: FileReadStream (Input) and FileWriteStream (Output). These can reduce memory usage when parsing or generating large JSON files directly from the file system.
    • Encoded Streams: EncodedInputStream to handle conversions between byte streams and character streams.
    • Custom Streams: Users can implement their own stream wrappers using the IStreamWrapper or OStreamWrapper interfaces to bridge RapidJSON with existing code (like std::iostream).

  8. Handle parsing errors with ParseResult

    master

    When parsing fails due to invalid syntax, unrepresentable values (e.g., a number too large), or a handler terminating the process, the parser generates an error.

    Error information is stored in a ParseResult object, which contains:

    • An error code (which can be translated into a human-readable message).
    • An offset (the number of characters from the beginning of the JSON where the error occurred).

  9. Use ReadOnlyIndex for multi-process access

    master

    Keyvi supports multi-process access through a specific read-only mode.

    • Single Writer Rule: Only one process can have a read-write Index open at a time. Within a single process, you can use one Index instance across multiple threads (writes are internally queued).
    • ReadOnlyIndex: To access the index from a different process, use keyvi.index.ReadOnlyIndex("directory_name"). This instance only provides read methods like Get.
    • Visibility between processes: A write in the read-write process is not immediately visible in the read-only process. To see changes, you must call Flush() in the read-write index and then a refresh (which happens automatically every 1s) in the read-only index. In the worst case, visibility can take up to 2s.
    • Memory Efficiency: Because Keyvi uses memory mapping, opening an index in multiple processes does not significantly increase memory consumption.
    import keyvi.index

# In Process A (The Writer)
writer_index = keyvi.index.Index("test-index")
writer_index.Set("key", "value")
writer_index.Flush()

# In Process B (The Reader)
reader_index = keyvi.index.ReadOnlyIndex("test-index")
m = reader_index.Get("key")
if m:
    print(m.GetValue())

  10. How Sparse Array building works during FSA construction

    master

    During the construction of a Finite State Automaton (FSA), a state is written to the persistent storage only after all its outgoing transitions are known. This ensures the algorithm has a complete state vector to work with.

    When building the sparse array, the algorithm attempts to pack the state vector by finding available space within the existing sparse array structure to maximize compression.

  11. Configure Unicode encodings and transcoding

    master

    RapidJSON supports UTF-8, UTF-16, and UTF-32 encodings (including little and big endian).

    Key capabilities include:

    • Automatic detection: Detect encoding in input streams.
    • Transcoding: Automatically transcode between encodings (e.g., reading a UTF-8 file and storing strings as UTF-16 in the DOM).
    • Validation: Check if input byte sequences are valid for the specified encoding.
    • Customization: Support for custom character types (defaults to char for UTF8, wchar_t for UTF16, and uint32_t for UTF32) and custom encodings.

  12. Use `MemoryPoolAllocator` for DOM construction

    master

    The MemoryPoolAllocator is the default allocator for the DOM API. It is optimized for building DOM trees because it allocates memory in large blocks and does not release individual pieces of memory until the entire pool is destroyed.

    Allocation Logic:

    1. It first attempts to use a user-provided buffer if available.
    2. If the user buffer is full, it uses the current internal memory block.
    3. If the current internal block is full, it allocates a new large memory block from a base allocator (defaulting to CrtAllocator) and maintains these blocks in a singly linked list.