Hi,
consider WebOfTrust as a graph, consisting of:
- The set of Identities, the vertexes of the graph.
- The set of Score values, the edges of the graph. For each pair of
OwnIdentity & Identity, such an edge exists. This mail assumes N to be the
number of those edges.
Currently, a single WOT instance fetches all new trust lists which each of the
known identities publishes. A new trust list is published whenever someone
changes a trust value or adds a new identity, etc. So there are MANY trust
lists published every day.
For each fetched trust list, a score re-computation happens.
The score re-computation is effectively a graph algorithm.
Where N being the number of Score values, it does an amount of O(N) db4o-
queries of the type: getScore(Identity truster, Identity target)
Obviously, such a query is theoretically executable in a time of O(1) by using
a Hashtable<OwnIdentity truster, Hashtable<Identity target, Score score>>.
HOWEVER, db4o does NOT execute it in O(1). It takes an average of O(N), where
N is the number of Score objects!!! [1]
Therefore, the old implementation of the Score computation algorithm has
an average runtime of O(N^2 * ...) which is VERY bad, N^2 grows insanely fast.
Now the good news is:
I have implemented a branch [2] which DOES reduce the average time of those
O(N) queries to O(1). It does this by creating a composite primary key (ID) for
each Score object:
We construct a String ID which is equal to "ID of the truster concatenated
with the ID of the trustee". We create a db4o index upon those composite IDs.
Now the getScore(Identity truster, Identity target) query does not have 2
field-value constraints anymore, there is only 1. Therefore, due to the index,
that query executes in O(1).
We also do this for Trust-queries. This effectively should make WOT usable
again.
The branch is already fully implemented and I'm doing a test run right now.
The topic of the mail says "almost" done because I have not written code to
upgrade old databases yet. This is a simple task however, maybe 30 lines of
code, and I will definitely do it with then next week.
So we can see an optimized WOT build in two weeks I hope.
Greetings, and THANKS FOR YOUR EPIC PATIENCE WITH ME,
xor
[1] I've written a db4o performance test which proves my theory that queries
which constrain upon two indexed fields take an average execution time of O(N).
I will publish the test in my next flog update.
[2] https://github.com/freenet/plugin-WoT-staging/tree/o1-trust-score-queries
Especially check out those commits:
https://github.com/freenet/plugin-WoT-staging/commit/c11b3873d8577daf2d405e9819fab184ecffee65
https://github.com/freenet/plugin-WoT-staging/commit/f872741e777e1c1a020f0ef1422b2d0421fe4ad2
