Distributing graph analytics across machines with DxHash

Summary

Several machines can share the graph-building step of an analytics pipeline without writing any entity twice, if every node and edge has exactly one owning machine. That was the finding of Dylan Costello’s final-year project, one of two WitFoo sponsored in 2026 in the Department of Computer Science and Software Engineering at Te Whare Wānanga o Waitaha | University of Canterbury (UC).

His design pairs a published consistent-hashing algorithm, DxHash, with a directory that records which machine owns each node. He tested it on a model network of one to five processing machines that WitFoo provided for the project, against a single-node model of the same processing step.

• Same artifacts. In every equivalence test (10,000 artifacts each), the distributed design stored the same artifacts as the single-node model, with no duplicates and none missing, checked key by key.
• About half the memory. Five machines together used 54% of the single-node model’s memory, with a much smaller standard deviation.
• More work done. Five machines delivered 134% of the single-node model’s throughput once CPU use is accounted for (140% raw).

These are results from a proof of concept on a test network, not measurements of WitFoo’s products. Recovery from a failed machine was designed for but not tested.

The problem: one owner per entity

Graph processing cannot simply be copied onto more machines, because two machines holding the same entity will both write it to storage.

In the processing step Dylan studied, parsed security events arrive as artifacts. Each artifact becomes graph nodes and edges, which are held in memory and written to storage together at intervals, so that the database sees few, large writes:

"Jane Doe, logged into server-1"
  artifact  {User: "Jane Doe", Asset: "server-1"}
  nodes     User "Jane Doe", Asset "server-1"
  edge      "Jane Doe" -> "server-1"

The bulk write is what makes spreading the work hard. If two machines each see artifacts that mention Jane Doe, each builds its own copy of her node in memory, and both copies reach storage at the next flush. Spreading work across machines is the usual way to add capacity, avoid concentrating traffic on one machine, and keep processing running when a machine fails, so the duplicate problem has to be solved first.

WitFoo set four constraints on any distributed design:

1. Comparable throughput and memory. The machines together should be comparable to a single machine, if not better, so that distributing the work does not multiply the hardware it needs.
2. Balanced memory. No machine should sit idle while another is overloaded.
3. Few database writes. Nodes and edges are still collected in memory and flushed in bulk.
4. Fault tolerance. Processing should survive a machine failing at random. This was wanted but not essential for the project.

To keep the project contained, Dylan assumed that every machine is trusted (machines can fail, but never send malicious messages), that every machine is preloaded with shared settings such as the hashing algorithm and its seeds, and that shared data is protected by locks, which puts race conditions out of scope.

Research questions

The goal was a distributed algorithm that gives the same results as single-node processing and suits WitFoo’s analytics processing. Three questions framed the work, each with its own metric.

The failure scenarios in question 3 were not run in the time available (see Limits of the study).

What the literature offered

Consistent hashing fitted the constraints best, and Dylan chose DxHash among its variants because it gives predictable backup locations that every machine can work out in advance. Dylan surveyed three families of distributed-systems research before choosing it.

That last property decided it: when a machine fails, every other machine already knows where its work goes next, with no extra reorganization.

The design

Every node and edge has exactly one owning machine, and DxHash tells any machine where to ask who that owner is.

DxHash lookup. Every machine holds the same table of slots, sized to u, the smallest power of two greater than the number of machines n:

To place a key, DxHash seeds a pseudo-random number generator with the key’s hash and draws slot numbers below u. Slots numbered n and above are empty, and a slot whose machine is down is skipped, so the generator keeps drawing until it lands on a running machine. The sequence depends only on the hash, so every machine reaches the same answer, and the machines later in the sequence are ready-made backup locations.

1. 1Draw 6: an empty slot, so draw again
2. 2Draw 2: machine M2 is down, so draw again
3. 3Draw 3: machine M3 is running, so the key belongs to M3

The sequence depends only on the hash, so every machine computes the same one, and the next running machines in it are the backup locations for the key.

DxHash lookup for one key · 5 machines, 8 slots · after the example in Dylan’s showcase slides

The ownership directory. A node can carry more than one key, and different artifacts may name the same node by different keys. Dylan therefore adds a directory that maps each key’s hash to the machine that owns the node, and stores each entry on the machine DxHash picks for that key. Any machine can find a node’s owner by asking the directory machine for each of the node’s keys.

Handling an artifact. Any machine can receive an artifact. For each node in it, the machine looks up every key in the directory; if no owner is registered, it becomes the owner itself. It then registers the owner against every key and sends the node to the owner. Each edge goes to the machine DxHash picks for the edge’s key. At each flush, every machine writes the nodes and edges it owns to storage in one bulk insert.

Handling one artifact · owner lookup, registration and the bulk flush · after Dylan’s Algorithms 3 and 4

Backups. For fault tolerance, the lookup returns machines in the order the generator visits them. A machine checks every directory location in that list for an owner, then registers the owner at the first few, so ownership is not lost if a single machine goes down. The extra requests add waiting time, which batching requests would reduce.

The design answers the research questions in turn:

• Equivalence. All information about a node goes to one machine, so nothing is written twice or overwritten.
• Memory. The lookup needs only the list of machines, and each directory entry lives on one machine (before backups). The generator’s randomness spreads directory entries and edges, and new nodes stay where they are first seen, which balances memory given enough artifacts.
• Throughput and faults. Backup locations come with the lookup itself, so a failed machine needs no reorganization, and adding machines does not change the algorithm.

How it was tested

The design was tested by simulation on a model network WitFoo provided, because there was little comparable published research to measure it against.

Dylan wrote the implementation in Go, with NATS carrying messages between machines and Apache Cassandra as the storage, both standard at WitFoo. The model network had five processing machines, a Conductor machine sending them artifacts and a storage machine. For the single-node model, one processing machine ran alone with the distributed functions, DxHash included, removed.

For equivalence, a comparison function read the final contents of storage after a distributed run and a single-node run over the same input. It compared every artifact key, counting duplicates and anything present in one store but not the other, and reported the share that matched.

Results

Five machines stored the same artifacts as the single-node model, used about half its memory and processed 40% more artifacts (34% more once CPU use is allowed for), though the gains shrank after the third machine.

• 134%CPU-normalized throughput at five machines
• 140%raw throughput at five machines
• 54%total memory at five machines
• single-node model (100%)

Dylan Costello’s report, Table VIII · totals computed from per-machine means · 40 runs per size

Means over 40 runs at each size; ± is the confidence interval given in Dylan’s report.

• Equivalence. Every equivalence test (10,000 artifacts each) returned 100%: comparing every artifact key, the distributed runs stored the same artifacts as the single-node runs, with no duplicates and none missing. This answers question 1.
• Memory. Memory per machine fell from 349.86 MB on the single-node model to 37.91 MB at five machines, so the five together used 54% of the single-node model’s memory (±3%, as Dylan reports it). The standard deviation of memory use was also much smaller, 6.18 MB at five machines against 109.57 MB for the single-node model, which Dylan reads as each machine carrying a similar share of the work. This answers question 2.
• Throughput. Throughput per machine fell as machines were added, from 5,621.92 to 1,574.46 artifacts per second at five, which Dylan attributes to the information an artifact needs being held locally only about one time in n. Total throughput still rose with every machine, reaching 140% of the single-node model at five machines, or 134% (±3%, as Dylan reports it) once each machine’s CPU use is taken into account. Two machines processed 117% of the single-node model’s artifacts but fell below it per unit of CPU (79%); the CPU-adjusted gain appeared from three machines on. Throughput and growth answer part of question 3; failures were not tested.

CPU-normalized throughput divides each machine’s throughput by its average CPU use and sums across machines, then compares that total with the same figure for the single-node model.

Limits of the study

Dylan treats the result as a proof of concept, and he names its limits himself.

• A small equivalence sample. Equivalence was shown on ingestions of 10,000 artifacts sent at a flat rate. Real traffic ebbs and flows with the systems that produce it, so a generator that varies its rate and size would test the design harder.
• The CPU limit. Without the 200% cap, the single-node model reached 800% CPU, and the distributed design, which spends much of its time waiting on replies, gained throughput from more threads. The cap was meant to make the comparison fair, but it held both back; uncapped runs would show each design’s real ceiling.
• Untested settings. Run length, drain time and flush interval were the same for every test but chosen with limited justification. Longer runs might slow throughput, and a longer flush interval might erode the memory advantage.
• Proof-of-concept shortcuts. Requests between machines were not batched, local data was fetched through the network, and directory lookups ran even where they could be skipped. Fixing these should lift total throughput, which came in lower than expected.
• Scale and failures. Five machines are too few to show the trends hold for larger networks, and recovery from failed machines was designed for but not tested.

Memory was one of the critical constraints and throughput a secondary one, so Dylan concludes that the design is a sound starting point for distributing WitFoo’s processing, with fault tolerance and larger-scale testing still to do.

What comes next

Dylan proposes three directions, each of which would make consistent hashing more useful for distributed processing.

1. Larger scale. Rerun the tests with more machines, more artifacts and faster hardware, to see whether the results hold.
2. Weighted DxHash [20]. Give each machine a weight between 0 and 1 that sets how likely the lookup is to settle on it, so more capable machines take a larger share of the work.
3. Dynamic membership. Drop the assumption that every machine is preloaded with the full list of machines, so machines can join and leave as incoming traffic changes.

“The results that Dylan has come up with in this paper have been broken into a dozen work tasks that have been put into the Analytics 1.4 roadmap, which is scheduled to come out this time next year. As Dylan comes over and begins full-time work, he’ll continue working on this to get it production-ready so that our customers and partners have access to these features,” said WitFoo Chairman and co-Founder Charles Herring.

About the project

Dylan Costello carried out this research as his final-year software engineering project at UC in 2026, supervised by UC staff. It was one of two final-year projects WitFoo sponsored this year in UC’s Department of Computer Science and Software Engineering. WitFoo set the problem and its constraints, provided the model network and met with Dylan regularly; the design, implementation and analysis are his.

This article summarizes the research sections of his report, Horizontal Scalability using DxHash for an Analytics Processing System, and is published with his permission.

“Partnering with Dylan and the University of Canterbury to do these production-level problems gave WitFoo a great opportunity to understand the capacity and capability of both the education coming out of UC and Dylan’s personal acumen and work ethic. It was a fantastic opportunity to not only further our own research at WitFoo but create a pipeline for new team members in the years to come,” said WitFoo Chairman and co-Founder Charles Herring.

“Having a project that comes from a real industry challenge helps cement a lot of the concepts taught at UC, while meeting with Charles regularly allowed me to better understand the organisational needs and constraints, and what problems I will actually need to solve,” said Costello.

References

Source report: D. Costello, Horizontal Scalability using DxHash for an Analytics Processing System, final-year project report, Department of Computer Science and Software Engineering, University of Canterbury, 2026.

1. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart and D. Terry, “Epidemic algorithms for replicated database maintenance,” Proc. 6th Annual ACM Symposium on Principles of Distributed Computing, 1987, pp. 1–12.
2. A. Das, I. Gupta and A. Motivala, “SWIM: scalable weakly-consistent infection-style process group membership protocol,” Proc. International Conference on Dependable Systems and Networks, 2002, pp. 303–312.
3. N. Padalia, Apache Cassandra Essentials. Packt Publishing, 2015.
4. L. Lamport, “The part-time parliament,” in Concurrency: the Works of Leslie Lamport, D. Malkhi, Ed. ACM Books, 2019, pp. 277–317. doi:10.1145/3335772.3335939
5. L. Lamport, “Paxos made simple,” ACM SIGACT News, vol. 32, no. 4, pp. 51–58, 2001.
6. H. Garcia-Molina, “Elections in a distributed computing system,” IEEE Transactions on Computers, vol. 31, no. 1, pp. 48–59, 1982.
7. S.-H. Lee and H. Choi, “The fast bully algorithm: for electing a coordinator process in distributed systems,” International Conference on Information Networking, Springer, 2002, pp. 609–622.
8. D. Ongaro and J. Ousterhout, “In search of an understandable consensus algorithm,” 2014 USENIX Annual Technical Conference, 2014, pp. 305–319.
9. M. Vojdani and Y. Taj, “DR: divided ring leader election algorithm,” International Conference on Algorithms and Architectures for Parallel Processing, Springer, 2009, pp. 90–99.
10. D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine and D. Lewin, “Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web,” Proc. 29th Annual ACM Symposium on Theory of Computing (STOC ’97), 1997, pp. 654–663. doi:10.1145/258533.258660
11. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek and H. Balakrishnan, “Chord: a scalable peer-to-peer lookup service for internet applications,” Proc. SIGCOMM ’01, 2001, pp. 149–160. doi:10.1145/383059.383071
12. P. Maymounkov and D. Mazières, “Kademlia: a peer-to-peer information system based on the XOR metric,” International Workshop on Peer-to-Peer Systems, Springer, 2002, pp. 53–65.
13. D. G. Thaler and C. V. Ravishankar, “Using name-based mappings to increase hit rates,” IEEE/ACM Transactions on Networking, vol. 6, no. 1, pp. 1–14, 1998.
14. J. Lamping and E. Veach, “A fast, minimal memory, consistent hash algorithm,” arXiv:1406.2294, 2014. arxiv.org/abs/1406.2294
15. O. Ertl, “JumpBackHash: say goodbye to the modulo operation to distribute keys uniformly to buckets,” Software: Practice and Experience, vol. 55, no. 3, pp. 559–570, 2025.
16. M. Coluzzi, A. Brocco, A. Antonucci and T. Leidi, “MementoHash: a stateful, minimal memory, best performing consistent hash algorithm,” IEEE/ACM Transactions on Networking, vol. 32, no. 4, pp. 3528–3543, 2024. arxiv.org/abs/2306.09783
17. M. Coluzzi, A. Brocco, A. Antonucci and T. Leidi, “BinomialHash: a constant time, minimal memory consistent hash algorithm,” 2025 IEEE International Conference on High Performance Computing and Communications (HPCC), 2025, pp. 87–94.
18. D. E. Eisenbud, C. Yi, C. Contavalli, C. Smith, R. Kononov, E. Mann-Hielscher, A. Cilingiroglu, B. Cheyney, W. Shang and J. D. Hosein, “Maglev: a fast and reliable software network load balancer,” Proc. 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’16), 2016, pp. 523–535.
19. G. Mendelson, S. Vargaftik, K. Barabash, D. H. Lorenz, I. Keslassy and A. Orda, “AnchorHash: a scalable consistent hash,” IEEE/ACM Transactions on Networking, vol. 29, no. 2, pp. 517–528, 2021.
20. C. Dong, F. Wang and D. Feng, “DxHash: a scalable consistent hash based on the pseudo-random sequence,” 2023. arxiv.org/abs/2107.07930

How this paper was produced

WitFoo uses artificial intelligence tools to assist with research, fact-checking, and editing in the preparation of this paper. The research it describes is Dylan Costello’s; this account of it is WitFoo’s. WitFoo reviewed every claim, checked every source, and takes full responsibility for the content. Nothing in this paper was generated without human direction and review. The views expressed represent WitFoo’s perspective and constitute WitFoo’s intellectual property. © 2026 WitFoo, Inc. All rights reserved.