InterShardSegments for each shard rather than a shared one.
-
@systemparadox said in InterShardSegments for each shard rather than a shared one.:
it is impossible to implement locking when your only shared memory is a single asynchronous block
That's absolutely false. Writes to the single asynchronous block are atomic, so it's 100% possible to do locking albeit with an infinite time horizon. The biggest issue is that a shard might stop running while you're in the middle of a locking operation. The second biggest issue is that there are no guarantees about the length of time between ticks - it's conceivable that one shard might have a glitchy tick that takes 1 minute.
-
@wtfrank Technically you could, you simple just let a shard update every few ticks ex. S1: True then when its done it changes S2: True
-
So to sum up, the current method is slow and unreliable.
Suggestions to fix that are:
- Private memory section for each shard, that is readable by the other shards.
- Msg/log based system
I have to agree with @SystemParadox both are useful, the msg system i.e. for inter shard travel to announce a incoming creep.
The memory segment for static like market information that can be read at will by other shards.
-
@communication I'm not sure what you mean exactly, but it's possible to do, lockless style (eventually correct but you don't know if it's up to date or when it will eventually be correct), mutex style (guaranteed correct or you know that it's not correct), and even some kind of time-sharing to manage concurrency.
They thing that all of the methods have in common is that none of them are very fast.
-
@wtfrank Thats true
-
@wtfrank said in InterShardSegments for each shard rather than a shared one.:
That's absolutely false. Writes to the single asynchronous block are atomic, so it's 100% possible to do locking albeit with an infinite time horizon
There are two points that everyone keeps missing when I discuss this:
- Atomic writes are not the only requirement for safe locking. You also have to make sure that no-one else can read or write the lock in between time. You can do this in a CPU environment, but not in screeps.
- Writes are atomic, but you can only write to the entire block. If shardA tries to change a lock flag and shardB tries to write some data, and shardA wins, the data that shardB wrote is gone. At first glance it seems like locking should prevent this situation from occurring at all, but you have to account for slow or glitchy ticks.
Thus, you cannot implement an independent locking system that is 100% safe, because we do not have the guarantees required for this. As previously stated, locking systems which require cooperation between shards are possible, but will block communication if one shard is down (and any attempt to resolve this makes it unsafe again).
I contend that anyone who thinks they have implemented a 100% safe locking system has made one of the following assumptions:
- That shards all run at the same rate and no shard is ever down (not true)
- That only one shard is executing at a time (not true, shards are executing simultaneously on different servers)
- That you can read and write the segment atomically without any other shard reading or writing in between (not guaranteed, since shards are executing simultaneously)
- That there is a limit to the time between reading the segment and writing it (not true, there are no guarantees here)
- That you can atomically update one part of the segment (e.g. a flag) without changing the rest of the segment (not true, it's all one block)
Now I'm sure many people have locking systems implemented and working fine 99.9% of the time. The point is that it's not 100% safe, which means you have to think about what happens when it goes wrong. I suspect for most people the answer is that they don't care (so long as their locking system recovers without blocking everything). They'll lose some data, but it either wasn't important or will be re-written again soon enough. This is perfectly valid, but working 99.9% of the time and not caring when it goes wrong is not the same as provably 100% safe.
The interesting thing about this is that any one of the assumptions above would allow us to implement 100% safe locking. It's entirely possible that assumption 4 is actually already true, but we would need guarantees from the devs before we could rely on it.
Of course, the new
InterShardMemoryscheme is much simpler and solves all these problems.
-
@SystemParadox I believe you are correct for a system based on locking. You don't have to use locks though. There are 100% safe lockless systems.
With the caveat that I've not actually implemented it, here is my (what I believe to be) 100% safe system:
- Partition the segement into sub-segments. Each shard owns a sub-segment.
- If we want to make a modification, read the entire segment, modify our sub-segment, write to the segment.
- On future ticks we know what our sub-segment should look like. Read the sub-segment and check. If it doens't look right that means we have a condented write which the other guy won. Skip a random number of ticks (or wallclock time) and goto 2. The skip probably isn't neccessary unless you're on >2 shards.
This method works around contention by brute force and can handle a shard just disappearing. High contention will cause delays but the random time length skipping should ensure that all writes go through without too much latency. It depends a bit on how much you're willing to tolerate. It's also possible that a shard will see another shard's subsegment go back in time causing some confusion. That can be sorted by having a timestamp in each subsegment.
If you're putting a lot in the segment then checking our section is correct every tick may bit a bit expensive. If you're only using it for small messages it shouldn't be.
-
Yes that's basically what I've done in the polyfill above, although I haven't done anything with high contention so it's possible that one shard might block the others if it writes every tick.
I've got it checking against a tick number so it doesn't have to compare the data itself.
-
Here is a pure mutex system (no backwards writes). The key I think you missed it it's based on time not ticks.
- Claim the segment by writing your shard number and time + 3*N seconds
- Wait till you've claimed the segment for N seconds.
- If N < time < 2*N seconds then write data (also increment a sequence counter).
- Do not reclaim the segment for M seconds.
During all this every shard keeps its own copy of the shared memory. which it refreshes every tick. If their copy is more up to date overwrite the segment.
- N should to be your slowest tick + clock skew between machines.
- The safest M is # of shards * N. Smaller values allow write starvation of slow shards.
The easiest way to break this system is having a shards write get committed long after the script's tick is over (like > 3N after).
It is also possible for this scheme to break when ticks are > N. But even then a single slow tick doesn't break the system. Consistently slow ticks also don't break the system. You need inconsistent tick times.
- Shard A 2N slow tick while Shard B claims
- Shard B has a 3N slow tick while trying to write.
- Shard A claims and writes during B's slow tick.
- Both Shard A and Shard B think they have the next sequence.
Choosing N and M can be tricky but picking large values like 1 minute and 5 minutes respectively for the MMO server will just work.
The big problem with this scheme is it's SLOW. A shard could wait 100 ticks or more before acquiring the shared segment.
-
@artch I think this discussion shows that you should pull that a bit up on your priority list
But I love those kind of discussions they are clear indicators where something is lacking
-
We've got a draft implementation of this already, will polish and deploy it in the coming weeks. Strongholds and Power Creeps are higher priority though.
-
This feature is now deployed to the PTR: https://screeps.com/forum/topic/2534/ptr-changelog-2019-01-30-intershardmemory
