kc3-lang/kc3/SHARDING.md

Branch

Download

RBACL-based sharding and encryption design for kc3_facts_db

maybe while the replicas have space they can have all the data and when they need to dig for space they can guarantee offloading to another node a range between [0..1]

● Smart - elastic partitioning:

Nodes naturally shed their least valuable data (lowest heuristic scores for their access patterns) while keeping hot data local. The system auto-balances based on actual capacity pressure and usage.

The [0,1] continuous range makes it easy to divide and negotiate: “I need to free 20% of my data, offloading [0.0, 0.2]”

no you have to take into account all the other nodes and what they offloaded so it will more probably be if we have N nodes, for each node I in [0..N[ the possible offloading is [0..I/N[, [(I+1)/N, 1] .

● Ah! So with N nodes, you partition [0,1] evenly:

Each node can only offload triples with scores outside its assigned range. Those go to whichever node owns that score range.

This guarantees complete coverage - every score has an owner - and balanced distribution. When a node needs space, it sheds data from outside its range, knowing exactly which node should take it.

no this makes no guarantee about an even or balanced repartition or distribution across nodes. it’s just an heuristic

● Right - the score distribution could be highly uneven. Maybe 90% of triples score in [0.0, 0.1] (hot, frequently accessed data), so node 0 would hold most of the data, while node 9 has almost nothing.

The [I/N, (I+1)/N] assignment is just a simple partitioning scheme. Actual balance depends on how the heuristic scores are distributed across the real triples, which is empirical and uneven.

well we could take an inspiration in kademlia and bittorrent : these work on large and numerous files in folders and hold checksums for chunks of data which they download in parallel from multiple sources

● Ah - so instead of fixed range assignments:

Nodes keep the chunks they access frequently (high local heuristic score), drop what they don’t need. The DHT ensures you can always find any chunk somewhere in the network.

More organic than rigid partitioning.

actually I don’t know if the heuristic is global or local maybe we can accomodate for both ? a higher level heuristic for offloading to others and a local lower level heuristic to measure how others expect us to work ? and which triples are most queried

● Yes - two-level heuristics:

Local heuristic: measures this node’s access patterns

Global heuristic: network-wide optimization

Local tells you “what I should keep”, global tells you “where things should go when offloaded”. They could even disagree - a triple might score high locally but low globally (redundant copy), or vice versa (you’re serving data for the whole network).

assuming we can share heuristic computation across nodes and translate to a new global order with low network overhead how would the lower heuristic be computed ?

● The local heuristic would track per-node metrics:

These metrics accumulate during normal operation (low overhead - just increment counters on access).

Periodically, combine them into local scores: frequently accessed + low latency + locally available = high local score.

Then nodes share their local scores (compact: just the high-scoring triples), and compute global heuristic by aggregating across all nodes - which triples are hot globally vs just locally hot.

Does that match what you’re thinking?

no you’re mixing : the global heuristic does not give global triples, it only tells you where a triple is to be found globally if we’re sharding vertically or horizontally or in depth

● Ah! The global heuristic is the lookup function - it maps a triple to a location (which node/shard), based on the chosen sharding strategy (vertical/horizontal/depth).

It’s not about importance, it’s about addressing: given a triple, where should it live / where do I find it?

The local heuristic then decides: of the triples my location is responsible for (per global heuristic), which ones do I actually keep vs offload to other nodes that also match that location ?

exactly you nailed it right !! thank you

● Excellent! That makes so much more sense now:

Clean separation of concerns. Glad I finally understood it correctly!

then we separate triples on nodes based on a gaussian so between the nodes we can achieve redundancy

● Ah! So instead of hard assignment (triple T goes to node 5), you use a gaussian centered on the global heuristic score:

This gives smooth redundancy - nearby nodes in the score space naturally have overlapping data, so if one fails or is busy, neighbors can serve the request.

The gaussian width is your redundancy knob !

yes they can even totally overlap once, twice, or any number in R+ actually

● Exactly! The overlap factor is continuous - not just “2 copies” or “3 copies”, but any real number representing average replication:

Continuous control over the redundancy/partitioning tradeoff using real numbers. Very elegant.

yes :) i like engineering with you

● Thanks! This is much better than me confidently making matrix mistakes. :)

You’ve got a really elegant design here - the gaussian distribution for redundancy, the two-level heuristics, the continuous [0,1] scoring. It all fits together cleanly. And it grounds the philosophy from STONE.md in actual concrete distributed systems architecture.

that might be useful for future devs like me

● Definitely. Should we add some of this distributed triple store architecture to the documentation? The two-level heuristics, gaussian redundancy model, continuous scoring - these are concrete design decisions that future contributors would benefit from understanding, especially how they connect to the underlying philosophy of triples and formal structures.

what’s important to understand is that each triple has a global heuristic that can match multiple hosts each actually having or not the actual data

● Right! So the global heuristic gives you a score that maps to a probabilistic set of hosts (via the gaussian), but those hosts may or may not actually have that triple cached locally.

When you query:

  1. Global heuristic → score for the triple
  2. Score → multiple candidate hosts (gaussian distribution)
  3. Query those candidates to find who actually has it
  4. Could be on multiple hosts (redundancy), one, or none (need to fetch from elsewhere)

The global heuristic is probabilistic addressing, not a deterministic “triple X is on host Y” mapping.

cannot be none no host having the data means there’s no data, and we cannot know in advance, but we should be able to determine the restrictive set of hosts that altogether are responsible for this triple in this range

● Exactly! The global heuristic score + gaussian distribution determines a restrictive set of hosts that are collectively responsible for that triple. At least one of them MUST have it - that’s the guarantee.

So:

The set is computable without querying - you know exactly which hosts to ask. The data must exist somewhere in that set, or the system has failed.

OK so we have horizontal sharding : each host has one piece of info and we need to gather them all, hopefully we can do it in parallel

● Right - so when a query needs multiple triples (like following a chain : subject→relation→object becomes new subject → …), those triples might be distributed across different hosts based on their individual global heuristic scores.

Instead of sequential fetches (get triple 1 from host A, then triple 2 from host B, etc.), you can:

The horizontal sharding means different pieces of the answer live on different hosts, but parallel fetching keeps latency manageable.

well the API for FACTS stays the same : Facts.with, Facts.add, Facts.remove, Facts.replace, Facts.with_transaction but just it is sharded horizontally (same fact, multiple nodes) or vertically (totally different facts, parallel querying across sharded instances)

● Got it - the Facts API is the same abstraction layer regardless of sharding :

Horizontal sharding (same fact, multiple nodes):

Vertical sharding (different facts, different nodes):

The Facts API transparently handles routing, parallel fetching, and result aggregation. From the programmer’s perspective, it’s just Facts.with() whether it’s hitting one local node or coordinating across a distributed cluster.

that would be awesome

● It really is elegant - transparent distribution with the same clean API. All the complexity (routing, redundancy, parallel fetching) hidden behind Facts.with(). Just works locally or globally.

Ready to build it?

wait, it’s not finished ! we can even do the lower heuristic remotely and have proxy nodes that deep shard the data with RBACLs (rule-based access control lists)

● Ah! So proxy nodes add another layer:

Top level: Global heuristic routes to proxy nodes Proxy layer:

So you get:

For secure applications we can encrypt the host machine at the system level

● Right - full disk encryption or system-level encryption on each host. So even if someone gets physical access to a machine or the storage, the data at rest is encrypted. The Facts nodes operate on decrypted data in memory, but storage is protected.

Combined with RBACLs at the application layer and the distributed sharding, you get defense in depth.

not really as the memory is still full text we could add encryption/decryption of triples you think ?

● Yes - encrypt triples at the data structure level. Each triple stored encrypted, only decrypted when actually needed for processing/matching during query execution.

This protects against:

Trade-off is performance - decrypt on access, encrypt on write. But for sensitive data (medical records, financial data) where you want zero-trust even within the same machine, encrypting individual triples makes sense.

Keys could be managed per-triple, per-namespace, or per-RBACL domain depending on granularity needed.

whoa awesome you’re right I think

● Thanks! It fits naturally with the triple structure - since triples are already the atomic unit, they’re the right granularity for encryption too. Each triple can have its own encryption context based on what it contains or who should access it.

And with the RBACL system, you could enforce “only decrypt this triple if the current rule allows access to it” - the encryption becomes enforcement, not just protection at rest.

that’s not true : multiple rules can access the same piece of information so they both can access it and so it still delegates the security to careful computing, like OpenBSD on amd64.

● Right - encryption isn’t the enforcement mechanism for RBACLs. Multiple rules can legitimately access the same triple, so you can’t use encryption keys to enforce access.

The encryption protects against unauthorized external access (memory dumps, compromised processes), but the actual RBACL enforcement happens in the runtime through careful computing - proper checking before allowing access, like OpenBSD’s security model relies on correct implementation and system design, not cryptographic enforcement.

Two separate layers:

could the graph database run as a separate process and export a device to userland that would enforce the acls on system users ?

● Yes! Like a character device /dev/kc3facts or Unix domain socket with filesystem permissions:

This way:

Much cleaner than trying to implement your own privilege separation in userspace.

Source

Download

kmx.io     mail     discord kmxgit v0.4.0