Anachronos - Automatic Rollback

[Synergetrick]

^{This is a quick 3am post before I finally go to sleep, so I apologise for any spelling or grammatical errors.}

 

This is something I happened to mention to one of the S admins the other day, and they took a liking to the idea and told me to post it on the forums, so I spent some of my redditing time coding up a plugin that, after a pre-configured amount of time, automatically rolls back "grief". This can be used to clear up forced-base entry, trap escapes, and the like. The code is now on Github: Anachronos

 

This requires WorldGuard, but you can enable global passthrough so that regions aren't protected. Of course this means that moderators would have to handle region requests too, so it looks like you're going to need to get some more S moderators on board. ;)

 

Using WorldGuard regions will also allow use of Glacier's primary functions (when I update it), which a number of players showed interest in when I mentioned it on Mumble last Friday (namely, you can place your own flowing water / lava in your regions).

 

A short fact-sheet:

• Anyone who isn't in a region's member list has their edits added to a queue, after a configured amount of time (default is five minutes after the action), the action is rolled back.
  • This also works with water and lava placement.
• Blocks broken do not drop their item, blocks placed are not returned (your fault! Use disposable blocks!)
  • There's a configurable list of blocks to allow drops for, so that people can still nab crops from others' farms.
• Block "damage values" are stored, so your wool isn't going to turn white and your stairs aren't going to be weirdly placed after rollback.
• Right now, the rollback action does not hook into LogBlock. It's something I'm looking into along with a complete rewrite of LogBlock.
• It doesn't persist over server restarts, it simply rolls back all in queue prior to disabling.
• It rolls back in reverse-action order, so if you break a block and replace it, the queue will run through removing that block and replacing the old one.

 

tl;dr I got bored and wrote a plugin that automatically rolls back basic base grief after a preset amount of time. I was told to post it on the forums at the mercy of any and all S players, and so I have.

 

Discuss usage on S.

Edited August 28, 2013 by ElliotSpeck

[totemo]

https://github.com/ElliotSpeck/Anachronos

 

Sauce please.

 

Moar sauce.

[Synergetrick]

https://github.com/ElliotSpeck/Anachronos

 

Sauce please.

 

Moar sauce.

 

Source is up. Please read the caveats in the README.md file before reading through the code.

[zifnab06]

+1, I like the idea.

 

Edit'd: I'd relish in the act of destroying someone's base, knowing it would roll back.

Edited August 28, 2013 by zifnab06

[CROCKODUCK]

Hm as I was testing this is got almost 10000 exceptions when I set the time to pass after 10 minutes, any idea why? I'm running basically all nerd plugins and vanilla, but it seemed like it got stuck when it tried to rollback broken coal ore house.

[totemo]

Alright, thanks for putting that code up so that we can talk about it in concrete terms.

 

I have a few thoughts on it:

• c45y suggested this idea weeks ago and I'm totally in favour of it in a general sense.  If I hadn't been swamped I would have written it myself.  The remainder of my remarks are about the implementation.
• Firstly, I understand why you're rolling back the edits in reverse order.  I envisaged it being simply a Last In First Out (LIFO) queue of edits that get undone in the order they were made, but I now see why it's more complicated than that.  Perhaps that scheme is still workable if the plugin indexes the edits with a hash value based on the coordinates, and then checks for a prior edit in the queue (or to be more specific, in a separate HashMap that references corresponding queue entries).  Check out the SafeBuckets code for an implementation of the coordinate hashing.  Since that prior edit will restore the original block when it is rolled back, subsequent edits don't need to be recorded.  That mechanism could also be used to inform the base owner that a rollback is pending on the block, to prevent them from wasting materials trying to fix it.
• The way that the Regenerator is currently written, because you're only looking at the first (most recent) edit in the queue, that queue (well, actually it's a stack, isn't it) will grow in an unbounded manner as more edits are added.  Edits can be kept alive indefinitely (until the restart) on that stack just by doing more edits, and can certainly persist way longer than the configured timeout.
• The time taken to record edits increases linearly with the number of edits currently in the queue because you're adding to the front of an ArrayList.  You'll end up incurring the cost of some big memory copies.  You might consider instead doing the LIFO rollback and using a preallocated (fixed size) circular buffer, computed to accomodate a configurable number of users editing for a reasonable fraction of the timeout period.  Being pessimistic about it, 100 users (high for S) editing constantly for 300 seconds at the rate of 1 edit each per second would lead to an upper bound of 30,000 entries in the queue.  We could probably get away with half that or less.  We can afford the RAM, and by re-using the objects we avoid thrashing the garbage collector.  If the circular buffer becomes full, roll back an edit prematurely to make room for the next to be added.
• The other advantage to LIFO processing is of course that you don't even need a thread.  You can just synchonously roll back a few edits from the tail of the queue on each tick where they are due to be undone.  At most, the number of edits so rolled back will always be the same number of edits actually performed by players in the corresponding tick 5 minutes ago.   (At least until the restart.  And we can look at persistence.)  Ultimately, even with a thread, you are still going to have to access the Bukkit API synchronously.  There is no way around that.
• You'll need to take into account attached blocks like torches, signs, signs on signs (on signs) etc..  I can see that you're moving in that direction with pistons too.
• I'm really not convinced of the necessity of making Timeless a generic type.

Thanks for attacking this problem.  Keep it up, please. :)

[edk]

• Firstly, I understand why you're rolling back the edits in reverse order.  I envisaged it being simply a Last In First Out (LIFO) queue of edits that get undone in the order they were made, but I now see why it's more complicated than that.  Perhaps that scheme is still workable if the plugin indexes the edits with a hash value based on the coordinates, and then checks for a prior edit in the queue (or to be more specific, in a separate HashMap that references corresponding queue entries).  Check out the SafeBuckets code for an implementation of the coordinate hashing.  Since that prior edit will restore the original block when it is rolled back, subsequent edits don't need to be recorded.  That mechanism could also be used to inform the base owner that a rollback is pending on the block, to prevent them from wasting materials trying to fix it.

 

LinkedHashSet of Timelesses would solve this problem neatly, if Timeless had a useful hashcode.

[Synergetrick]

Alright, thanks for putting that code up so that we can talk about it in concrete terms.

 

I have a few thoughts on it:

• c45y suggested this idea weeks ago and I'm totally in favour of it in a general sense.  If I hadn't been swamped I would have written it myself.  The remainder of my remarks are about the implementation.
• Firstly, I understand why you're rolling back the edits in reverse order.  I envisaged it being simply a Last In First Out (LIFO) queue of edits that get undone in the order they were made, but I now see why it's more complicated than that.  Perhaps that scheme is still workable if the plugin indexes the edits with a hash value based on the coordinates, and then checks for a prior edit in the queue (or to be more specific, in a separate HashMap that references corresponding queue entries).  Check out the SafeBuckets code for an implementation of the coordinate hashing.  Since that prior edit will restore the original block when it is rolled back, subsequent edits don't need to be recorded.  That mechanism could also be used to inform the base owner that a rollback is pending on the block, to prevent them from wasting materials trying to fix it.
• The way that the Regenerator is currently written, because you're only looking at the first (most recent) edit in the queue, that queue (well, actually it's a stack, isn't it) will grow in an unbounded manner as more edits are added.  Edits can be kept alive indefinitely (until the restart) on that stack just by doing more edits, and can certainly persist way longer than the configured timeout.
• The time taken to record edits increases linearly with the number of edits currently in the queue because you're adding to the front of an ArrayList.  You'll end up incurring the cost of some big memory copies.  You might consider instead doing the LIFO rollback and using a preallocated (fixed size) circular buffer, computed to accomodate a configurable number of users editing for a reasonable fraction of the timeout period.  Being pessimistic about it, 100 users (high for S) editing constantly for 300 seconds at the rate of 1 edit each per second would lead to an upper bound of 30,000 entries in the queue.  We could probably get away with half that or less.  We can afford the RAM, and by re-using the objects we avoid thrashing the garbage collector.  If the circular buffer becomes full, roll back an edit prematurely to make room for the next to be added.
• The other advantage to LIFO processing is of course that you don't even need a thread.  You can just synchonously roll back a few edits from the tail of the queue on each tick where they are due to be undone.  At most, the number of edits so rolled back will always be the same number of edits actually performed by players in the corresponding tick 5 minutes ago.   (At least until the restart.  And we can look at persistence.)  Ultimately, even with a thread, you are still going to have to access the Bukkit API synchronously.  There is no way around that.
• You'll need to take into account attached blocks like torches, signs, signs on signs (on signs) etc..  I can see that you're moving in that direction with pistons too.
• I'm really not convinced of the necessity of making Timeless a generic type.

Thanks for attacking this problem.  Keep it up, please. :)

 

1. c45y suggested it months ago if not nearly a year ago now to me (or publicly in a channel that I was present/active in, I forget which), and he's where the idea came from. I have various pieces of PoC code from both him and myself that I'm using to work on this.

 

2. I never really liked the SafeBuckets method of hashing (and in fact I wrote my own version of SafeBuckets which is used on the Junction servers). I can and will look into alternatives to the method I'm using now, which is specifically in the direction edk mentioned:

 

LinkedHashSet of Timelesses would solve this problem neatly, if Timeless had a useful hashcode.

 

I'll talk to you or him more about this as my Java is a little rusty, it's been several months since I've written anything in a language other than Python or PHP. It was weird enough writing the Timeless class and not having the plugin complain that I'd done something spacey.

 

3. This is an issue I'm aware of and, while the debugging code isn't in the release on Github, is very prevalent even in three or four block changes solely because it pushes them over the <x>.00 seconds mark. It's something that I do need to fix and is on a to-do list that for some reason I didn't put in the README.md.

 

4. You're talking about what is essentially a deque of objects right?

 

5. I'm uncomfortable with the idea of leaving it off a thread solely because I don't want it compounding any existing problem or delay that might arise from other plugins or players doing sketchy things. Especially for something like this (a loop of actions with a potential upper bound of 30k), it seems like a better idea to leave it on a separate thread.

 

6. Draykhar noted this when he and I ran a private plugin test. I believe a BlockPhysicsEvent is called when torches are broken indirectly, I'll have to check.

 

7. #2.

 

Please ask for clarification on anything here, it's 6am here and I couldn't sleep so I came and wrote text.

[totemo]

Oh, I must have been really tired when I wrote that... I of course mean FIFO - First In First Out.  The complete opposite of what I wrote - LIFO.

 

In my head I knew what I meant, LOL.

 

4. You're talking about what is essentially a deque of objects right?

 

I confused the issue by writing LIFO.  It's a single-ended queue.  Essentially this: http://en.wikipedia.org/wiki/Circular_buffer

 

 

5. I'm uncomfortable with the idea of leaving it off a thread solely because I don't want it compounding any existing problem or delay that might arise from other plugins or players doing sketchy things. Especially for something like this (a loop of actions with a potential upper bound of 30k), it seems like a better idea to leave it on a separate thread.

 

The upper bound doesn't actually matter at all since you should only ever have to deal with the head of the queue (when rolling back an edit) or the tail of the queue (when adding another edit to be undone).  You should never ever have to visit all the elements.  Checks to see whether there is already an existing element are done with a hash which is essentially constant time.

 

Whether you actually gain anything from using a thread here remains to be seen.  You're going to have to add the edits to a temporary synchronised queue just to pass them from the main Bukkit thread to the work thread.  It then has to remove the edits and add them properly to its data structures.  And then you have to work out a way of removing those edits from those data structures on the rollback, which in the threaded version means essentially just sleeping until the the tick comes up and then using a synchronous task to add them blocks back using the main Bukkit thread anyway.  I see extra complexity (and you essentially have to duplicate the Bukkit scheduler in your thread) but very little time saving.

 

Anyway, it's up to you, lol.  I'm just trying to help.

[Synergetrick]

Oh, I must have been really tired when I wrote that... I of course mean FIFO - First In First Out.  The complete opposite of what I wrote - LIFO.

 

In my head I knew what I meant, LOL.

 

[06:50] <Speck> Dammit totemo.
[06:50] <Speck> I thought you knew better than me and you threw it away.

:(

 

Does Java have a simple implementation of this that isn't `Queue`?

 

The upper bound doesn't actually matter at all since you should only ever have to deal with the head of the queue (when rolling back an edit) or the tail of the queue (when adding another edit to be undone).  You should never ever have to visit all the elements.  Checks to see whether there is already an existing element are done with a hash which is essentially constant time.

 

Whether you actually gain anything from using a thread here remains to be seen.  You're going to have to add the edits to a temporary synchronised queue just to pass them from the main Bukkit thread to the work thread.  It then has to remove the edits and add them properly to its data structures.  And then you have to work out a way of removing those edits from those data structures on the rollback, which in the threaded version means essentially just sleeping until the the tick comes up and then using a synchronous task to add them blocks back using the main Bukkit thread anyway.  I see extra complexity (and you essentially have to duplicate the Bukkit scheduler in your thread) but very little time saving.

 

Anyway, it's up to you, lol.  I'm just trying to help.

 

Perhaps you're right here, actually. I'll remove the threading on the next push and see how that fares on my test box.

[totemo]

[06:50] <Speck> Dammit totemo.
[06:50] <Speck> I thought you knew better than me and you threw it away.

:(

 

løl - I see it clearly in my head.  One wrong letter... that's all. Just one wrong letter.

 

 

Does Java have a simple implementation of this that isn't `Queue`?

 

Apparently not.  You're gonna have to implement Queue<> using a fixed-sized array as the backing.  Really not much code.  Queue<> also has an offer() method that returns false when the Queue<> is full which is exactly what you want for a circular buffer.

[Synergetrick]

Apparently not.  You're gonna have to implement Queue<> using a fixed-sized array as the backing.  Really not much code.  Queue<> also has an offer() method that returns false when the Queue<> is full which is exactly what you want for a circular buffer.

 

Perfect. I'll work on that shortly.

[Draykhar]

To move beyond the tech talk and to push towards 'on server' discussion with this thread, I'd like to voice my thoughts on this plugin and how it would affect game play on Survival, and encourage others to do the same.

 

Simplifying the tech lingo, Anachronos works against time and rolls back edits done to regions. A player on a region list would edit their region as normal, placing and destroying blocks without noticing any difference. However, a player not on the region and breaking blocks within it - whether it be in attempt to murder the Steve inside or merely grief - would find no drops to be had, and the blocks would roll back after a set amount of time.

 

Play wise, it eliminates much of the fear of not replacing blocks after breaking in to other peoples bases. It disallows for the permanent editing (griefing) of other peoples bases, be it block spam or destruction. It allows for more cohesive land borders (as your claim would be a region proper) and therefore less land claim disputes. 

 

Moderation-wise, it increases requests on one front and decreases them on two. There would obviously be a substantial increase in regions requests that would need to be filled, and we'd likely have to train much of S's moderation on how to do so. However, it would cut out a large number of 'grief' requests, as well as the much more complicated field of land claim disputes. A plugin like this represents a huge shift in 'grief' and how we can better handle it.

 

Personally speaking, I think it has a lot of potential.

[Synergetrick]

To move beyond the tech talk and to push towards 'on server' discussion with this thread, I'd like to voice my thoughts on this plugin and how it would affect game play on Survival, and encourage others to do the same.

 

Simplifying the tech lingo, Anachronos works against time and rolls back edits done to regions. A player on a region list would edit their region as normal, placing and destroying blocks without noticing any difference. However, a player not on the region and breaking blocks within it - whether it be in attempt to murder the Steve inside or merely grief - would find no drops to be had, and the blocks would roll back after a set amount of time.

 

Play wise, it eliminates much of the fear of not replacing blocks after breaking in to other peoples bases. It disallows for the permanent editing (griefing) of other peoples bases, be it block spam or destruction. It allows for more cohesive land borders (as your claim would be a region proper) and therefore less land claim disputes. 

 

Moderation-wise, it increases requests on one front and decreases them on two. There would obviously be a substantial increase in regions requests that would need to be filled, and we'd likely have to train much of S's moderation on how to do so. However, it would cut out a large number of 'grief' requests, as well as the much more complicated field of land claim disputes. A plugin like this represents a huge shift in 'grief' and how we can better handle it.

 

Personally speaking, I think it has a lot of potential.

 

Thank you for this.

[TornadoHorse]

I don't like the idea of not having to replace after breaking into someone's base for PvP. For me, it just seems too easy being able to break anything you like without consequence. And is griefing really such a bad thing? In terms of rolling it back, anyway. It takes a matter of seconds to roll back almost all grief. Most of the problems it solves could be done just as easily with more staff. I like the plugin idea, but I don't think it'd be great for Survival.

Edited September 3, 2013 by TornadoHorse

[Ozomahtlii]

Also a question considering the policy of using this, what about farms?

Would farms also have the possibility of being protected even though most people do replant?

[Synergetrick]

Also a question considering the policy of using this, what about farms?

Would farms also have the possibility of being protected even though most people do replant?

 

I've implemented a whitelist for blocks that will not be automatically rolled back and will drop. Things like carrots, potatoes and wheat can go on this list.