DBENGINE v2 (#14125)

* count open cache pages refering to datafile

* eliminate waste flush attempts

* remove eliminated variable

* journal v2 scanning split functions

* avoid locking open cache for a long time while migrating to journal v2

* dont acquire datafile for the loop; disable thread cancelability while a query is running

* work on datafile acquiring

* work on datafile deletion

* work on datafile deletion again

* logs of dbengine should start with DBENGINE

* thread specific key for queries to check if a query finishes without a finalize

* page_uuid is not used anymore

* Cleanup judy traversal when building new v2
Remove not needed calls to metric registry

* metric is 8 bytes smaller; timestamps are protected with a spinlock; timestamps in metric are now always coherent

* disable checks for invalid time-ranges

* Remove type from page details

* report scanning time

* remove infinite loop from datafile acquire for deletion

* remove infinite loop from datafile acquire for deletion again

* trace query handles

* properly allocate array of dimensions in replication

* metrics cleanup

* metrics registry uses arrayalloc

* arrayalloc free should be protected by lock

* use array alloc in page cache

* journal v2 scanning fix

* datafile reference leaking hunding

* do not load metrics of future timestamps

* initialize reasons

* fix datafile reference leak

* do not load pages that are entirely overlapped by others

* expand metric retention atomically

* split replication logic in initialization and execution

* replication prepare ahead queries

* replication prepare ahead queries fixed

* fix replication workers accounting

* add router active queries chart

* restore accounting of pages metadata sources; cleanup replication

* dont count skipped pages as unroutable

* notes on services shutdown

* do not migrate to journal v2 too early, while it has pending dirty pages in the main cache for the specific journal file

* do not add pages we dont need to pdc

* time in range re-work to provide info about past and future matches

* finner control on the pages selected for processing; accounting of page related issues

* fix invalid reference to handle->page

* eliminate data collection handle of pg_lookup_next

* accounting for queries with gaps

* query preprocessing the same way the processing is done; cache now supports all operations on Judy

* dynamic libuv workers based on number of processors; minimum libuv workers 8; replication query init ahead uses libuv workers - reserved ones (3)

* get into pdc all matching pages from main cache and open cache; do not do v2 scan if main cache and open cache can satisfy the query

* finner gaps calculation; accounting of overlapping pages in queries

* fix gaps accounting

* move datafile deletion to worker thread

* tune libuv workers and thread stack size

* stop netdata threads gradually

* run indexing together with cache flush/evict

* more work on clean shutdown

* limit the number of pages to evict per run

* do not lock the clean queue for accesses if it is not possible at that time - the page will be moved to the back of the list during eviction

* economies on flags for smaller page footprint; cleanup and renames

* eviction moves referenced pages to the end of the queue

* use murmur hash for indexing partition

* murmur should be static

* use more indexing partitions

* revert number of partitions to number of cpus

* cancel threads first, then stop services

* revert default thread stack size

* dont execute replication requests of disconnected senders

* wait more time for services that are exiting gradually

* fixed last commit

* finer control on page selection algorithm

* default stacksize of 1MB

* fix formatting

* fix worker utilization going crazy when the number is rotating

* avoid buffer full due to replication preprocessing of requests

* support query priorities

* add count of spins in spinlock when compiled with netdata internal checks

* remove prioritization from dbengine queries; cache now uses mutexes for the queues

* hot pages are now in sections judy arrays, like dirty

* align replication queries to optimal page size

* during flushing add to clean and evict in batches

* Revert "during flushing add to clean and evict in batches"

This reverts commit 8fb2b69d068499eacea6de8291c336e5e9f197c7.

* dont lock clean while evicting pages during flushing

* Revert "dont lock clean while evicting pages during flushing"

This reverts commit d6c82b5f40aeba86fc7aead062fab1b819ba58b3.

* Revert "Revert "during flushing add to clean and evict in batches""

This reverts commit ca7a187537fb8f743992700427e13042561211ec.

* dont cross locks during flushing, for the fastest flushes possible

* low-priority queries load pages synchronously

* Revert "low-priority queries load pages synchronously"

This reverts commit 1ef2662ddcd20fe5842b856c716df134c42d1dc7.

* cache uses spinlock again

* during flushing, dont lock the clean queue at all; each item is added atomically

* do smaller eviction runs

* evict one page at a time to minimize lock contention on the clean queue

* fix eviction statistics

* fix last commit

* plain should be main cache

* event loop cleanup; evictions and flushes can now happen concurrently

* run flush and evictions from tier0 only

* remove not needed variables

* flushing open cache is not needed; flushing protection is irrelevant since flushing is global for all tiers; added protection to datafiles so that only one flusher can run per datafile at any given time

* added worker jobs in timer to find the slow part of it

* support fast eviction of pages when all_of_them is set

* revert default thread stack size

* bypass event loop for dispatching read extent commands to workers - send them directly

* Revert "bypass event loop for dispatching read extent commands to workers - send them directly"

This reverts commit 2c08bc5bab12881ae33bc73ce5dea03dfc4e1fce.

* cache work requests

* minimize memory operations during flushing; caching of extent_io_descriptors and page_descriptors

* publish flushed pages to open cache in the thread pool

* prevent eventloop requests from getting stacked in the event loop

* single threaded dbengine controller; support priorities for all queries; major cleanup and restructuring of rrdengine.c

* more rrdengine.c cleanup

* enable db rotation

* do not log when there is a filter

* do not run multiple migration to journal v2

* load all extents async

* fix wrong paste

* report opcodes waiting, works dispatched, works executing

* cleanup event loop memory every 10 minutes

* dont dispatch more work requests than the number of threads available

* use the dispatched counter instead of the executing counter to check if the worker thread pool is full

* remove UV_RUN_NOWAIT

* replication to fill the queues

* caching of extent buffers; code cleanup

* caching of pdc and pd; rework on journal v2 indexing, datafile creation, database rotation

* single transaction wal

* synchronous flushing

* first cancel the threads, then signal them to exit

* caching of rrdeng query handles; added priority to query target; health is now low prio

* add priority to the missing points; do not allow critical priority in queries

* offload query preparation and routing to libuv thread pool

* updated timing charts for the offloaded query preparation

* caching of WALs

* accounting for struct caches (buffers); do not load extents with invalid sizes

* protection against memory booming during replication due to the optimal alignment of pages; sender thread buffer is now also reset when the circular buffer is reset

* also check if the expanded before is not the chart later updated time

* also check if the expanded before is not after the wall clock time of when the query started

* Remove unused variable

* replication to queue less queries; cleanup of internal fatals

* Mark dimension to be updated async

* caching of extent_page_details_list (epdl) and datafile_extent_offset_list (deol)

* disable pgc stress test, under an ifdef

* disable mrg stress test under an ifdef

* Mark chart and host labels, host info for async check and store in the database

* dictionary items use arrayalloc

* cache section pages structure is allocated with arrayalloc

* Add function to wakeup the aclk query threads and check for exit
Register function to be called during shutdown after signaling the service to exit

* parallel preparation of all dimensions of queries

* be more sensitive to enable streaming after replication

* atomically finish chart replication

* fix last commit

* fix last commit again

* fix last commit again again

* fix last commit again again again

* unify the normalization of retention calculation for collected charts; do not enable streaming if more than 60 points are to be transferred; eliminate an allocation during replication

* do not cancel start streaming; use high priority queries when we have locked chart data collection

* prevent starvation on opcodes execution, by allowing 2% of the requests to be re-ordered

* opcode now uses 2 spinlocks one for the caching of allocations and one for the waiting queue

* Remove check locks and NETDATA_VERIFY_LOCKS as it is not needed anymore

* Fix bad memory allocation / cleanup

* Cleanup ACLK sync initialization (part 1)

* Don't update metric registry during shutdown (part 1)

* Prevent crash when dashboard is refreshed and host goes away

* Mark ctx that is shutting down.
Test not adding flushed pages to open cache as hot if we are shutting down

* make ML work

* Fix compile without NETDATA_INTERNAL_CHECKS

* shutdown each ctx independently

* fix completion of quiesce

* do not update shared ML charts

* Create ML charts on child hosts.

When a parent runs a ML for a child, the relevant-ML charts
should be created on the child host. These charts should use
the parent's hostname to differentiate multiple parents that might
run ML for a child.

The only exception to this rule is the training/prediction resource
usage charts. These are created on the localhost of the parent host,
because they provide information specific to said host.

* check new ml code

* first save the database, then free all memory

* dbengine prep exit before freeing all memory; fixed deadlock in cache hot to dirty; added missing check to query engine about metrics without any data in the db

* Cleanup metadata thread (part 2)

* increase refcount before dispatching prep command

* Do not try to stop anomaly detection threads twice.

A separate function call has been added to stop anomaly detection threads.
This commit removes the left over function calls that were made
internally when a host was being created/destroyed.

* Remove allocations when smoothing samples buffer

The number of dims per sample is always 1, ie. we are training and
predicting only individual dimensions.

* set the orphan flag when loading archived hosts

* track worker dispatch callbacks and threadpool worker init

* make ML threads joinable; mark ctx having flushing in progress as early as possible

* fix allocation counter

* Cleanup metadata thread (part 3)

* Cleanup metadata thread (part 4)

* Skip metadata host scan when running unittest

* unittest support during init

* dont use all the libuv threads for queries

* break an infinite loop when sleep_usec() is interrupted

* ml prediction is a collector for several charts

* sleep_usec() now makes sure it will never loop if it passes the time expected; sleep_usec() now uses nanosleep() because clock_nanosleep() misses signals on netdata exit

* worker_unregister() in netdata threads cleanup

* moved pdc/epdl/deol/extent_buffer related code to pdc.c and pdc.h

* fixed ML issues

* removed engine2 directory

* added dbengine2 files in CMakeLists.txt

* move query plan data to query target, so that they can be exposed by in jsonwrap

* uniform definition of query plan according to the other query target members

* event_loop should be in daemon, not libnetdata

* metric_retention_by_uuid() is now part of the storage engine abstraction

* unify time_t variables to have the suffix _s (meaning: seconds)

* old dbengine statistics become "dbengine io"

* do not enable ML resource usage charts by default

* unify ml chart families, plugins and modules

* cleanup query plans from query target

* cleanup all extent buffers

* added debug info for rrddim slot to time

* rrddim now does proper gap management

* full rewrite of the mem modes

* use library functions for madvise

* use CHECKSUM_SZ for the checksum size

* fix coverity warning about the impossible case of returning a page that is entirely in the past of the query

* fix dbengine shutdown

* keep the old datafile lock until a new datafile has been created, to avoid creating multiple datafiles concurrently

* fine tune cache evictions

* dont initialize health if the health service is not running - prevent crash on shutdown while children get connected

* rename AS threads to ACLK[hostname]

* prevent re-use of uninitialized memory in queries

* use JulyL instead of JudyL for PDC operations - to test it first

* add also JulyL files

* fix July memory accounting

* disable July for PDC (use Judy)

* use the function to remove datafiles from linked list

* fix july and event_loop

* add july to libnetdata subdirs

* rename time_t variables that end in _t to end in _s

* replicate when there is a gap at the beginning of the replication period

* reset postponing of sender connections when a receiver is connected

* Adjust update every properly

* fix replication infinite loop due to last change

* packed enums in rrd.h and cleanup of obsolete rrd structure members

* prevent deadlock in replication: replication_recalculate_buffer_used_ratio_unsafe() deadlocking with replication_sender_delete_pending_requests()

* void unused variable

* void unused variables

* fix indentation

* entries_by_time calculation in VD was wrong; restored internal checks for checking future timestamps

* macros to caclulate page entries by time and size

* prevent statsd cleanup crash on exit

* cleanup health thread related variables

Co-authored-by: Stelios Fragkakis <52996999+stelfrag@users.noreply.github.com>
Co-authored-by: vkalintiris <vasilis@netdata.cloud>

4 files changed, 505 insertions, 0 deletions

diff --git a/libnetdata/july/Makefile.am b/libnetdata/july/Makefile.am
new file mode 100644
index 0000000000..161784b8f6
--- /dev/null
+++ b/libnetdata/july/Makefile.am
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+AUTOMAKE_OPTIONS = subdir-objects
+MAINTAINERCLEANFILES = $(srcdir)/Makefile.in
+
+dist_noinst_DATA = \
+    README.md \
+    $(NULL)
diff --git a/libnetdata/july/README.md b/libnetdata/july/README.md
new file mode 100644
index 0000000000..5cf4fb22f4
--- /dev/null
+++ b/libnetdata/july/README.md
@@ -0,0 +1,10 @@
+<!--
+custom_edit_url: https://github.com/netdata/netdata/edit/master/libnetdata/july/README.md
+-->
+
+
+# July
+
+An interface similar to `Judy` that uses minimal allocations (that can be cached)
+for items that are mainly appended (just a few insertions in the middle)
+
diff --git a/libnetdata/july/july.c b/libnetdata/july/july.c
new file mode 100644
index 0000000000..eda2f7ed34
--- /dev/null
+++ b/libnetdata/july/july.c
@@ -0,0 +1,447 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "july.h"
+
+#define JULYL_MIN_ENTRIES 10
+
+struct JulyL_item {
+    Word_t index;
+    void *value;
+};
+
+struct JulyL {
+    size_t entries;
+    size_t used;
+
+    // statistics
+    size_t bytes;
+    size_t bytes_moved;
+    size_t reallocs;
+
+    struct {
+        struct JulyL *prev;
+        struct JulyL *next;
+    } cache;
+
+    struct JulyL_item array[];
+};
+
+// ----------------------------------------------------------------------------
+// JulyL cache
+
+static struct {
+    struct {
+        SPINLOCK spinlock;
+        struct JulyL *available_items;
+        size_t available;
+    } protected;
+
+    struct {
+        size_t bytes;
+        size_t allocated;
+        size_t bytes_moved;
+        size_t reallocs;
+    } atomics;
+} julyl_globals = {
+        .protected = {
+                .spinlock = NETDATA_SPINLOCK_INITIALIZER,
+                .available_items = NULL,
+                .available = 0,
+        },
+        .atomics = {
+                .bytes = 0,
+                .allocated = 0,
+                .bytes_moved = 0,
+                .reallocs = 0,
+        },
+};
+
+void julyl_cleanup(void) {
+    netdata_spinlock_lock(&julyl_globals.protected.spinlock);
+
+    while(julyl_globals.protected.available_items && julyl_globals.protected.available > 10) {
+        struct JulyL *item = julyl_globals.protected.available_items;
+        DOUBLE_LINKED_LIST_REMOVE_UNSAFE(julyl_globals.protected.available_items, item, cache.prev, cache.next);
+        size_t bytes = item->bytes;
+        freez(item);
+        julyl_globals.protected.available--;
+        __atomic_sub_fetch(&julyl_globals.atomics.bytes, bytes, __ATOMIC_RELAXED);
+        __atomic_sub_fetch(&julyl_globals.atomics.allocated, 1, __ATOMIC_RELAXED);
+    }
+
+    netdata_spinlock_unlock(&julyl_globals.protected.spinlock);
+}
+
+struct JulyL *julyl_get(void) {
+    struct JulyL *j;
+
+    netdata_spinlock_lock(&julyl_globals.protected.spinlock);
+
+    j = julyl_globals.protected.available_items;
+    if(likely(j)) {
+        DOUBLE_LINKED_LIST_REMOVE_UNSAFE(julyl_globals.protected.available_items, j, cache.prev, cache.next);
+        julyl_globals.protected.available--;
+    }
+
+    netdata_spinlock_unlock(&julyl_globals.protected.spinlock);
+
+    if(unlikely(!j)) {
+        size_t bytes = sizeof(struct JulyL) + JULYL_MIN_ENTRIES * sizeof(struct JulyL_item);
+        j = mallocz(bytes);
+        j->bytes = bytes;
+        j->entries = JULYL_MIN_ENTRIES;
+        __atomic_add_fetch(&julyl_globals.atomics.bytes, bytes, __ATOMIC_RELAXED);
+        __atomic_add_fetch(&julyl_globals.atomics.allocated, 1, __ATOMIC_RELAXED);
+    }
+
+    j->used = 0;
+    j->bytes_moved = 0;
+    j->reallocs = 0;
+    j->cache.next = j->cache.prev = NULL;
+    return j;
+}
+
+static void julyl_release(struct JulyL *j) {
+    if(unlikely(!j)) return;
+
+    __atomic_add_fetch(&julyl_globals.atomics.bytes_moved, j->bytes_moved, __ATOMIC_RELAXED);
+    __atomic_add_fetch(&julyl_globals.atomics.reallocs, j->reallocs, __ATOMIC_RELAXED);
+
+    netdata_spinlock_lock(&julyl_globals.protected.spinlock);
+    DOUBLE_LINKED_LIST_APPEND_UNSAFE(julyl_globals.protected.available_items, j, cache.prev, cache.next);
+    julyl_globals.protected.available++;
+    netdata_spinlock_unlock(&julyl_globals.protected.spinlock);
+}
+
+size_t julyl_cache_size(void) {
+    return __atomic_load_n(&julyl_globals.atomics.bytes, __ATOMIC_RELAXED);
+}
+
+size_t julyl_bytes_moved(void) {
+    return __atomic_load_n(&julyl_globals.atomics.bytes_moved, __ATOMIC_RELAXED);
+}
+
+// ----------------------------------------------------------------------------
+// JulyL
+
+size_t JulyLGet_binary_search_position_of_index(const struct JulyL *July, Word_t Index) {
+    // return the position of the first item >= Index
+
+    size_t left = 0;
+    size_t right = July->used;
+    while(left < right) {
+        size_t middle = (left + right) >> 1;
+
+        if(July->array[middle].index > Index)
+            right = middle;
+
+        else
+            left = middle + 1;
+    }
+
+    internal_fatal(left > July->used, "JULY: invalid position returned");
+
+    if(left > 0 && July->array[left - 1].index == Index)
+        return left - 1;
+
+    internal_fatal( (left < July->used && July->array[left].index < Index) ||
+                    (left > 0 && July->array[left - 1].index >= Index)
+                   , "JULY: wrong item returned");
+
+    return left;
+}
+
+PPvoid_t JulyLGet(Pcvoid_t PArray, Word_t Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, Index);
+
+    if(unlikely(pos >= July->used || July->array[pos].index != Index))
+        return NULL;
+
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+PPvoid_t JulyLIns(PPvoid_t PPArray, Word_t Index, PJError_t PJError __maybe_unused) {
+    struct JulyL *July = *PPArray;
+    if(unlikely(!July)) {
+        July = julyl_get();
+        July->used = 0;
+        *PPArray = July;
+    }
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, Index);
+
+    if((pos == July->used || July->array[pos].index != Index)) {
+        // we have to add this entry
+
+        if (unlikely(July->used == July->entries)) {
+            // we have to expand the array
+            size_t bytes = sizeof(struct JulyL) + July->entries * 2 * sizeof(struct JulyL_item);
+            __atomic_add_fetch(&julyl_globals.atomics.bytes, bytes - July->bytes, __ATOMIC_RELAXED);
+            July = reallocz(July, bytes);
+            July->bytes = bytes;
+            July->entries *= 2;
+            July->reallocs++;
+            *PPArray = July;
+        }
+
+        if (unlikely(pos != July->used)) {
+            // we have to shift some members to make room
+            size_t size = (July->used - pos) * sizeof(struct JulyL_item);
+            memmove(&July->array[pos + 1], &July->array[pos], size);
+            July->bytes_moved += size;
+        }
+
+        July->used++;
+        July->array[pos].value = NULL;
+        July->array[pos].index = Index;
+    }
+
+    return &July->array[pos].value;
+}
+
+PPvoid_t JulyLFirst(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, *Index);
+    // pos is >= Index
+
+    if(unlikely(pos == July->used))
+        return NULL;
+
+    *Index = July->array[pos].index;
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+PPvoid_t JulyLNext(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, *Index);
+    // pos is >= Index
+
+    if(unlikely(pos == July->used))
+        return NULL;
+
+    if(July->array[pos].index == *Index) {
+        pos++;
+
+        if(unlikely(pos == July->used))
+            return NULL;
+    }
+
+    *Index = July->array[pos].index;
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+PPvoid_t JulyLLast(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, *Index);
+    // pos is >= Index
+
+    if(pos > 0 && (pos == July->used || July->array[pos].index > *Index))
+        pos--;
+
+    if(unlikely(pos == 0 && July->array[0].index > *Index))
+        return NULL;
+
+    *Index = July->array[pos].index;
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+PPvoid_t JulyLPrev(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, *Index);
+    // pos is >= Index
+
+    if(unlikely(pos == 0 || July->used == 0))
+        return NULL;
+
+    // get the previous one
+    pos--;
+
+    *Index = July->array[pos].index;
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+Word_t JulyLFreeArray(PPvoid_t PPArray, PJError_t PJError __maybe_unused) {
+    struct JulyL *July = *PPArray;
+    if(unlikely(!July))
+        return 0;
+
+    size_t bytes = July->bytes;
+    julyl_release(July);
+    *PPArray = NULL;
+    return bytes;
+}
+
+// ----------------------------------------------------------------------------
+// unittest
+
+#define item_index(i) (((i) * 2) + 100)
+
+int julytest(void) {
+    Word_t entries = 10000;
+    Pvoid_t array = NULL;
+
+    // test additions
+    for(Word_t i = 0; i < entries ;i++) {
+        Pvoid_t *PValue = JulyLIns(&array, item_index(i), PJE0);
+        if(!PValue)
+            fatal("JULY: cannot insert item %lu", item_index(i));
+
+        *PValue = (void *)(item_index(i));
+    }
+
+    // test successful finds
+    for(Word_t i = 0; i < entries ;i++) {
+        Pvoid_t *PValue = JulyLGet(array, item_index(i), PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+    }
+
+    // test finding the first item
+    for(Word_t i = 0; i < entries ;i++) {
+        Word_t index = item_index(i);
+        Pvoid_t *PValue = JulyLFirst(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find first item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i))
+            fatal("JULY: item %lu has index %lu", item_index(i), index);
+    }
+
+    // test finding the next item
+    for(Word_t i = 0; i < entries - 1 ;i++) {
+        Word_t index = item_index(i);
+        Pvoid_t *PValue = JulyLNext(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find next item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i + 1)))
+            fatal("JULY: item %lu next has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i + 1))
+            fatal("JULY: item %lu next has index %lu", item_index(i), index);
+    }
+
+    // test finding the last item
+    for(Word_t i = 0; i < entries ;i++) {
+        Word_t index = item_index(i);
+        Pvoid_t *PValue = JulyLLast(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find last item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i))
+            fatal("JULY: item %lu has index %lu", item_index(i), index);
+    }
+
+    // test finding the prev item
+    for(Word_t i = 1; i < entries ;i++) {
+        Word_t index = item_index(i);
+        Pvoid_t *PValue = JulyLPrev(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find prev item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i - 1)))
+            fatal("JULY: item %lu prev has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i - 1))
+            fatal("JULY: item %lu prev has index %lu", item_index(i), index);
+    }
+
+    // test full traversal forward
+    {
+        Word_t i = 0;
+        Word_t index = 0;
+        bool first = true;
+        Pvoid_t *PValue;
+        while((PValue = JulyLFirstThenNext(array, &index, &first))) {
+            if(*PValue != (void *)(item_index(i)))
+                fatal("JULY: item %lu traversal has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+            if(index != item_index(i))
+                fatal("JULY: item %lu traversal has index %lu", item_index(i), index);
+
+            i++;
+        }
+
+        if(i != entries)
+            fatal("JULY: expected to forward traverse %lu entries, but traversed %lu", entries, i);
+    }
+
+    // test full traversal backward
+    {
+        Word_t i = 0;
+        Word_t index = (Word_t)(-1);
+        bool first = true;
+        Pvoid_t *PValue;
+        while((PValue = JulyLLastThenPrev(array, &index, &first))) {
+            if(*PValue != (void *)(item_index(entries - i - 1)))
+                fatal("JULY: item %lu traversal has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+            if(index != item_index(entries - i - 1))
+                fatal("JULY: item %lu traversal has index %lu", item_index(i), index);
+
+            i++;
+        }
+
+        if(i != entries)
+            fatal("JULY: expected to back traverse %lu entries, but traversed %lu", entries, i);
+    }
+
+    // test finding non-existing first item
+    for(Word_t i = 0; i < entries ;i++) {
+        Word_t index = item_index(i) - 1;
+        Pvoid_t *PValue = JulyLFirst(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find first item %lu", item_index(i) - 1);
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i))
+            fatal("JULY: item %lu has index %lu", item_index(i), index);
+    }
+
+    // test finding non-existing last item
+    for(Word_t i = 0; i < entries ;i++) {
+        Word_t index = item_index(i) + 1;
+        Pvoid_t *PValue = JulyLLast(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find last item %lu", item_index(i) + 1);
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i))
+            fatal("JULY: item %lu has index %lu", item_index(i), index);
+    }
+
+    JulyLFreeArray(&array, PJE0);
+
+    return 0;
+}
+
+
diff --git a/libnetdata/july/july.h b/libnetdata/july/july.h
new file mode 100644
index 0000000000..9a273b7e6b
--- /dev/null
+++ b/libnetdata/july/july.h
@@ -0,0 +1,40 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef NETDATA_JULY_H
+#define NETDATA_JULY_H 1
+
+#include "../libnetdata.h"
+
+// #define PDC_USE_JULYL 1
+
+PPvoid_t JulyLGet(Pcvoid_t PArray, Word_t Index, PJError_t PJError);
+PPvoid_t JulyLIns(PPvoid_t PPArray, Word_t Index, PJError_t PJError);
+PPvoid_t JulyLFirst(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+PPvoid_t JulyLNext(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+PPvoid_t JulyLLast(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+PPvoid_t JulyLPrev(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+Word_t JulyLFreeArray(PPvoid_t PPArray, PJError_t PJError);
+
+static inline PPvoid_t JulyLFirstThenNext(Pcvoid_t PArray, Word_t * PIndex, bool *first) {
+    if(unlikely(*first)) {
+        *first = false;
+        return JulyLFirst(PArray, PIndex, PJE0);
+    }
+
+    return JulyLNext(PArray, PIndex, PJE0);
+}
+
+static inline PPvoid_t JulyLLastThenPrev(Pcvoid_t PArray, Word_t * PIndex, bool *first) {
+    if(unlikely(*first)) {
+        *first = false;
+        return JulyLLast(PArray, PIndex, PJE0);
+    }
+
+    return JulyLPrev(PArray, PIndex, PJE0);
+}
+
+void julyl_cleanup(void);
+size_t julyl_cache_size(void);
+size_t julyl_bytes_moved(void);
+
+#endif // NETDATA_JULY_H