The old/current database structure has the issue where data is being lost in the event of multiple nodes modifying the same entity (player/group) at the same time.

The database structure has the same issue, but on top it can also break the entire data in the event of data being partially overwritten. (Some relations from Server A and some from Server B, or even Server A adds a record with a relation and Server B removes the related entry).

I believe that if the database structure is already being redone, it is time to make it as consistent as possible.

The most simple improvement that comes to my mind is moving to single entry updates instead of entire entities. This reduces the area of conflict. Followed execution time reduction by letting sql handle the logic.

So a query would look like this:

INSERT INTO TABLE 
    permisson_nodes (entity, node, value, last_update) 
    VALUES (UNHEX(REPLACE("a425b545-2c0c-4630-86a6-1b6e2ec55eb6",'-','')), "permission.node", true, 1482969625434821) 
    ON DUPLICATE KEY UPDATE
        value = IF(last_update < VALUES(last_update), VALUES(value), value)
        value = IF(last_update < VALUES(last_update), VALUES(last_update), last_update)
;

DELETE FROM permission_nodes 
WHERE entity=UNHEX(REPLACE("a425b545-2c0c-4630-86a6-1b6e2ec55eb6",'-','')) AND node = "permission.node" AND last_update < 1482969625434821
;

This query inserts the data if a record with the same entity and node does not exist. If it does exist, it checks if the data sent is more up to date comparing timestamps, in this case nanoseconds and if so, updates it. This resolves the issue where nodes require a different amount of time to process the update. note: this is never gonna be accurate, if the timestamps are based on system time from multiple servers which makes this subject to opinion.

This leaves one point of failure, what happens if the user does not exists (was deleted/cleared). Either we have a foreign key set and the query fails or we extend it to include the user creation if not exists.

Overall this cuts down data inconsistency and loss by entry and the supplied timestamps or query arrival.

Edit:
So I misunderstood a part of the plugins core structure. Players and Groups (entities) can only be saved as a whole, it is not possible to save entry by entry as they change. Therefor based on the talk with Luck the best approach is probably to use SQL timestamps for merging the entries.

Should have been mostly resolved by 9f2b59f.