Proper way to delete?

[mbrevoort]

I'm working through a Seaport issue where when a node disconnects, it deletes the service from the crdt set of services (this line: https://github.com/substack/seaport/blob/master/lib/seaport.js#L176 ).

However, through it deletes from the set the row still exists and it exists in the history. When I connect another node that streams and synchronizes state, these seem to be getting replayed and recognized on the new node as existing again.

Is this the proper way to delete? Just hacking around a bit I've been able to fix my issue by doing the following though I don't appreciate what the consequences of this are:

            delete self.doc.rows[row.id];
            delete self.doc.hist[row.id];

Note, self.doc contains the "set" I was referencing above.

[dominictarr]

Yes, this is an issue. Looks like I neglected to implement delete...

you'd basically just need code to handle when this is null https://github.com/dominictarr/crdt/blob/master/doc.js#L135

the user would call Doc#set(id, null) or maybe add Doc#rm(id), https://github.com/dominictarr/crdt/blob/master/doc.js#L107

then youd have to handle when changes is null here https://github.com/dominictarr/crdt/blob/master/row.js#L27

And make sure that the row is removed from any sets, finally the row emits 'preupdate' which is handled by the Doc again, which is then sent into the scuttlebutt machinery.

https://github.com/dominictarr/crdt/blob/master/doc.js#L92

(you'd want some logic to remove the listener for preupdate too)

I don't have time to implement this right now, but will be happy to merge.

[mbrevoort]

Thanks for the quick response. I may be able to tackle this, but at this point I'm 4 nested dependencies deep into what I was trying to do in the first place. I'm going to explore plan B for now but I may be forced to come back to this in a couple of days.

[mbrevoort]

OK, plan B didn't work out. :) What do you think of this? Take a look at how I attempted to reconcile the history. It certainly feels like a hack, not sure what else to do though, and this worked in my Seaport tests as well.

[dominictarr]

Thanks!

This is good, but needs a one or two improvements before I can merge,

You need to check if the row was actually in the set and emit 'remove' like this, https://github.com/dominictarr/crdt/blob/master/set.js#L79

Also, don't use removeAllListeners, instead, emit a doc.emit('remove', row) (so, emitting remove on both the doc and the set) then, you can just add a listener to row.on('remove') in the place where the row is created, and remove the preupdate listener there...

And that should do it!

[mbrevoort]

Great, just pushed the cleaned up version. Was the way I cleaned up the history OK? https://github.com/mbrevoort/crdt/blob/d7dedffc57de7e8e97dab23a4171da7cb9d8ea85/doc.js#L164

Shaving yaks one level of dependency at a time™

Thanks!

[dominictarr]

That will work, but that will end up keeping the key for each property in memory, but just pointing to null really, we just want to keep id: null in memory... (later we can add a feature to expire that after a few days or something)

the history is set out like this:

{
  ID: {
    key1: [{key1: value1, key2:value2}, ts1, source],
    key2: [{key1: value1, key2:value2}, ts1, source],
    key3: [{key3: value3},                      ts2, source]
  }
}

for an update that has two changes, it's stored as two references. this is so that when an update comes in for just key2 it can update the datastructure like this:

{
  ID: {
    key1: [{key1: value1, key2:value2}, ts1, source],
    key2: [{key2:value20}                    , ts3, source],
    key3: [{key3: value3},                      ts2, source]
  }
}

So, this pattern supports atomic updates to multiple keys at a time, or single. It's possible to update a whole row, but also to do concurrent updates to it.

We'd need to adjust this to handle deletes of a whole row:

{
  ID: [null, ts4, source]
}

That would be the best, but you'd have to check Array.isArray(hist[id]) and handle that, hmm, before you do this https://github.com/mbrevoort/crdt/blob/d7dedffc57de7e8e97dab23a4171da7cb9d8ea85/doc.js#L154

And also, remember to emit _remove for each (unique) update that is in the hist[id] object.

I think what you have here will work, but it's not optimal.

[mbrevoort]

OK, I'll try to make time to take another pass tomorrow.

On a related note, I'm trying to find a potable solution to this issue I'm working through in Seaport (https://github.com/substack/seaport/pull/29). The main problem is that when a node (represented by a crdt Doc) disappears, if a Seaport server is unavailable, the crdt rows that belong to that node that are synchronized to all other nodes become orphaned. No other nodes including a newly started Seaport server can distinguish which rows are orphaned. In Seaport, when a node goes offline, it's associated data (service registrations) need to go with it.

The approach I'm working though is when a node disconnects from the Seaport server that it deletes any of the rows that it doesn't own, and then be eventually consistent with the Seaport server. However, if I call Doc.rm it will propagate that delete for nodes that really are still online, even from the node itself! So given this approach I need a way to local delete all of the data not owned by the local node but not propagate the changes polluting the other node.

So this is partially of related, I just wonder what you think the best approach would be given the characteristics of crdt.

[dominictarr]

Is this seaport nodes being turned on and off, but having the same data, or are the vm's being destroyed and recreated? (with completely new fs?)

If the nodes maintain their ID across restarts (use udid), then if a computer is merely turned off and turned back on, it will relaim it's orphans, because it will have the same ID.

(maybe, the seaport code will need to use the udid as the id of the document...)

@substack, does that make sense?

[mbrevoort]

Yes, so a Seaport client node may restart because of a service restart, uncaught exception, server restart, etc.

Today, Seaport uses a uid as the document Id. https://github.com/substack/seaport/blob/master/lib/id.js . I had experimented with maintaining the uid on the filesystem so that the same node would retain it's registrations and not unintentionally orphan data, but I had a difficult time avoiding collisions where two nodes used the same uid. I was generating a hash to name the file based on the concatenation of process.args that contained the uid and put the file in the cwd.

For example, there are some cases where you may have multiple process of the same app running out of the same directory (that's why I tried to use something like process.args to distinguish). Or in my case, my app that wraps the Seaport server connect to itself with the Seaport client and registers an API port. What was happening was the client and the server crdt docs shared the same uid as the Doc.id (based on my logic above). So I decided to punt on it and consider another approach.

The tricky part is that I really want the copies of the client nodes service registrations to be deleted if it disappears because I don't know if it will come back up or not (restarted or deprovisioned). The edge cases happen when the server itself is restarted or stopped and/or clients disconnect themselves.

Hmmm... instead maybe the clients could periodically update a heartbeat timestamp as part of the rows they own, perhaps every minute, and the seaport server could periodically scan rows in it's crdt doc copy looking for rows with stale heartbeat timestamps (> 3 minutes) and delete those rows. I wonder how chatty that would be across hundreds of client nodes.

Sorry to take this off topic, but at least it is a tangible use of crdt that raise a few edge cases :)

[dominictarr]

This is good discussion.

+1 to heartbeats.

This seems like the best way to implement heart-beats: https://code.google.com/p/cassandra-shawn/downloads/detail?name=The%20Phi%20Accrual%20Failure%20Detector.pdf

So, I have some modules you could use reuse id's on the same node, because I've solved the same problem in the browser. If your app is opened in multiple tabs, you couldn't just store the id in localStorage, because the new clients (with the same domain) will access the same id

So, we need a way that they pick a new id, but also a way that they can pick the same id if there are no other tabs/processes open.

I wrote this: http://github.com/dominictarr/count-tabs

It can detect when the user has closed a tab (which is equivalent to killing a process) and when the user reopens a tab, it will reuse the unused id. This stops the vector clock from getting too large.

So, this uses autonode, which also runs on the server, but currently uses localStorage directly, but the idea could be adapted.

note: This is already used in udid when running on the client...

Expiring long-dead keys is another problem, but we should discuss that feature too.

[mbrevoort]

Great reference on heart beats. I need some time to pace through it.

The count-tabs stuff is pretty awesome, especially the abstraction of treating a tab like a process in a distributed system. I actually have a another place I could use that now.

So I pushed another update, now row deletes finally result in this form:

{
  ID: [null, ts4, source]
}

I was going to add a reaper to look for keys that can be expired but I don't time right now. If I get a chance I'll try to add that in another pull request in the future. Before that I'll do some testing to see how much of an issue the memory leak of dead keys is in my usage of crdt/seaport.

Thanks!

[dominictarr]

merged into 3.5.0

[dominictarr]

Hey, is it okay If I add you as a collaborator? This will mean that you receive notifications about issues on crdt - not that many, but you have some skin in the game (being a heavy user of this module in production) so, I'd like to hear from you if someone else makes a pull request.

cheers, Dominic

[mbrevoort]

Sure, that sounds good. Thanks for merging!