ZooKeeper
  1. ZooKeeper
  2. ZOOKEEPER-104

KeptSet: a distributed data stucture backed by the children of a ZooKeeper node

    Details

    • Type: New Feature New Feature
    • Status: Resolved
    • Priority: Minor Minor
    • Resolution: Not a Problem
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: java client
    • Labels:
      None

      Description

      Here is an implementation of a ZooKeeper backed Java Set. It should be generally useful.

      1. ZOOKEEPER-104.patch
        14 kB
        Mahadev konar
      2. ZOOKEEPER-104.patch
        14 kB
        Mahadev konar
      3. ZOOKEEPER-104.patch
        14 kB
        Patrick Hunt
      4. ZOOKEEPER-104.patch
        10 kB
        Anthony Urso

        Activity

        Anthony Urso made changes -
        Status Open [ 1 ] Resolved [ 5 ]
        Resolution Not A Problem [ 8 ]
        Hide
        Anthony Urso added a comment -

        This functionality is replicated by KeptCollections, now available at https://github.com/anthonyu/KeptCollections.

        Show
        Anthony Urso added a comment - This functionality is replicated by KeptCollections, now available at https://github.com/anthonyu/KeptCollections .
        Hide
        Mahadev konar added a comment -

        once ZOOKEEPER-103 is resolved then we can add the build file to build this contrib module.

        Show
        Mahadev konar added a comment - once ZOOKEEPER-103 is resolved then we can add the build file to build this contrib module.
        Mahadev konar made changes -
        Attachment ZOOKEEPER-104.patch [ 12387359 ]
        Hide
        Mahadev konar added a comment -

        this is the latest patch which throws Runtimeexcpetions with interrupted exceptions and gets rid of the while true loops.

        Show
        Mahadev konar added a comment - this is the latest patch which throws Runtimeexcpetions with interrupted exceptions and gets rid of the while true loops.
        Hide
        Benjamin Reed added a comment -

        I think we should convert to a runtime exception. (It really seems like InterruptedException should be runtime in the first place...) It looks like this is how other APIs that implement persistent sets work.

        There is another possiblity: keep the whole set in memory and use watches as cache invalidations. Then you could have commit() and refresh() operations that would throw the exceptions. Depending on the size of the sets it does seem wise to keep it all cached in the client so that read operations can be executed quickly. Even the commit() allows you to batch up changes and do them faster as well.

        Show
        Benjamin Reed added a comment - I think we should convert to a runtime exception. (It really seems like InterruptedException should be runtime in the first place...) It looks like this is how other APIs that implement persistent sets work. There is another possiblity: keep the whole set in memory and use watches as cache invalidations. Then you could have commit() and refresh() operations that would throw the exceptions. Depending on the size of the sets it does seem wise to keep it all cached in the client so that read operations can be executed quickly. Even the commit() allows you to batch up changes and do them faster as well.
        Hide
        Mahadev konar added a comment -

        the second thing is what i did in my patch...

        so the interruptexception is thrown by zookeeper only when some other thread interrupts zookeeper and tells zookeeper client to go away. the zookeeper client does blocking calls and thus throws the interrupted exception... the Set api is not supposed to do any blocking calls (looks like)... the only alternative left if throw out a runtime exception.... dont know if this use case fits zookeeper....

        Show
        Mahadev konar added a comment - the second thing is what i did in my patch... so the interruptexception is thrown by zookeeper only when some other thread interrupts zookeeper and tells zookeeper client to go away. the zookeeper client does blocking calls and thus throws the interrupted exception... the Set api is not supposed to do any blocking calls (looks like)... the only alternative left if throw out a runtime exception.... dont know if this use case fits zookeeper....
        Hide
        Anthony Urso added a comment -

        The Set interface does not allow InterruptedException to be passed. I am OK with wrapping the InterruptedException in a RuntimeException and rethrowing it, but I think it violates the semantics of the InterruptedException. It's starting to look like this is not a suitable abstraction for ZooKeeper.

        Show
        Anthony Urso added a comment - The Set interface does not allow InterruptedException to be passed. I am OK with wrapping the InterruptedException in a RuntimeException and rethrowing it, but I think it violates the semantics of the InterruptedException. It's starting to look like this is not a suitable abstraction for ZooKeeper.
        Mahadev konar made changes -
        Status Patch Available [ 10002 ] Open [ 1 ]
        Hide
        Mahadev konar added a comment -

        cancelling for now... i have another patch. will upload by the end of the day or tomm ...

        Show
        Mahadev konar added a comment - cancelling for now... i have another patch. will upload by the end of the day or tomm ...
        Hide
        Patrick Hunt added a comment -

        Committers/reviewers - be sure to give a strong indication when dispositioning a jira/patch. This will help both committers & contributors and keep the process flowing smoothly:

        1) indicate your vote (+/-1 or 0) and provide comment on general issues
        2) if there are issues with a patch that need to be addressed before committing be sure to cancel the patch. Comments should indicate to the contributor what's expected to pass review.

        Show
        Patrick Hunt added a comment - Committers/reviewers - be sure to give a strong indication when dispositioning a jira/patch. This will help both committers & contributors and keep the process flowing smoothly: 1) indicate your vote (+/-1 or 0) and provide comment on general issues 2) if there are issues with a patch that need to be addressed before committing be sure to cancel the patch. Comments should indicate to the contributor what's expected to pass review.
        Hide
        Mahadev konar added a comment -

        ben is right.... the interrupted exception is a tricky bit.... we should let it flow out... i think your client library should also let it flow to the keepset api level. does that make sense anthony?

        Show
        Mahadev konar added a comment - ben is right.... the interrupted exception is a tricky bit.... we should let it flow out... i think your client library should also let it flow to the keepset api level. does that make sense anthony?
        Hide
        Benjamin Reed added a comment -

        InterruptedException is something we have to deal with from Java. We can't just catch them and retry. It is generally unsafe to eat this exception since it usually means someone wants the thread to go away. There seem to be a couple of ways to deal with InterruptedException but the safest seems to be to let it go through.

        Show
        Benjamin Reed added a comment - InterruptedException is something we have to deal with from Java. We can't just catch them and retry. It is generally unsafe to eat this exception since it usually means someone wants the thread to go away. There seem to be a couple of ways to deal with InterruptedException but the safest seems to be to let it go through.
        Hide
        Mahadev konar added a comment -

        > in the keepset contructor i changed if (exits) zk.create() to try

        { zk.create() }

        (nodeexistsexcpetion ){}

        >> Since the set can only be added to by a watcher event, these end up being semantically the same. I think checking the set first is a little more efficient, but either way is fine with me.

        the problem is that if you see that the node does not exist then you will have to create it and the create might fail given that someone else might have added the node. in that case the keepset contructor would throw an exception.. thats why i did that.

        the interrupted exception in truly a bizzare exception in the client library. I think we shuld get rid of it sometime.

        Show
        Mahadev konar added a comment - > in the keepset contructor i changed if (exits) zk.create() to try { zk.create() } (nodeexistsexcpetion ){} >> Since the set can only be added to by a watcher event, these end up being semantically the same. I think checking the set first is a little more efficient, but either way is fine with me. the problem is that if you see that the node does not exist then you will have to create it and the create might fail given that someone else might have added the node. in that case the keepset contructor would throw an exception.. thats why i did that. the interrupted exception in truly a bizzare exception in the client library. I think we shuld get rid of it sometime.
        Hide
        Anthony Urso added a comment -

        >> I took the liberty of making some small updates to Anthony's patch file, Anthony please let me know if you see any issues with this.

        Those changes are all good.

        >> in the keepset contructor i changed if (exits) zk.create() to try

        { zk.create() }

        (nodeexistsexcpetion ){}

        Since the set can only be added to by a watcher event, these end up being semantically the same. I think checking the set first is a little more efficient, but either way is fine with me.

        >> also i added braces around for and if with single lines (its less confusion for readign code ).

        OK.

        >> i dont understand the while loops of while(true) in all the zookeeper calls? why do you need that anthony?

        I do that to handle an InterruptedException by retrying the same command. Hopefully that is the right behavior.
        The purpose of the InterruptedException has always been a mystery to me when coding non-interactive programs.

        Show
        Anthony Urso added a comment - >> I took the liberty of making some small updates to Anthony's patch file, Anthony please let me know if you see any issues with this. Those changes are all good. >> in the keepset contructor i changed if (exits) zk.create() to try { zk.create() } (nodeexistsexcpetion ){} Since the set can only be added to by a watcher event, these end up being semantically the same. I think checking the set first is a little more efficient, but either way is fine with me. >> also i added braces around for and if with single lines (its less confusion for readign code ). OK. >> i dont understand the while loops of while(true) in all the zookeeper calls? why do you need that anthony? I do that to handle an InterruptedException by retrying the same command. Hopefully that is the right behavior. The purpose of the InterruptedException has always been a mystery to me when coding non-interactive programs.
        Hide
        Patrick Hunt added a comment -

        See ZOOKEEPER-103. Source structure, incl contrib & recipes, is currently under active discussion.

        Show
        Patrick Hunt added a comment - See ZOOKEEPER-103 . Source structure, incl contrib & recipes, is currently under active discussion.
        Hide
        Mahadev konar added a comment -

        also we would need some build files for building these recipes ... since we have non right now.

        Show
        Mahadev konar added a comment - also we would need some build files for building these recipes ... since we have non right now.
        Mahadev konar made changes -
        Attachment ZOOKEEPER-104.patch [ 12387143 ]
        Hide
        Mahadev konar added a comment -

        i took the liberty of changing pat's patch . .

        1) in the keepset contructor i changed
        if (exits)
        zk.create()

        to
        try

        { zk.create() }

        (nodeexistsexcpetion ){}

        2) also i added braces around for and if with single lines (its less confusion for readign code ).
        3) i dont understand the while loops of while(true) in all the zookeeper calls? why do you need that anthony?

        Show
        Mahadev konar added a comment - i took the liberty of changing pat's patch . . 1) in the keepset contructor i changed if (exits) zk.create() to try { zk.create() } (nodeexistsexcpetion ){} 2) also i added braces around for and if with single lines (its less confusion for readign code ). 3) i dont understand the while loops of while(true) in all the zookeeper calls? why do you need that anthony?
        Patrick Hunt made changes -
        Attachment ZOOKEEPER-104.patch [ 12387139 ]
        Hide
        Patrick Hunt added a comment -

        I took the liberty of making some small updates to Anthony's patch file, Anthony please let me know if you see any issues with this.

        1) fixed the tests so that they will run on my machine (starting a server for client tests is complex due to timing issues - we really need to work on making our tests easier to write)
        1.5) fixed call to KeptSet constructor in test (added flags)
        2) added apache licenses to the source files
        3) small formatting changes
        4) implementation note in the class javadoc
        5) we use spaces, not tabs

        Show
        Patrick Hunt added a comment - I took the liberty of making some small updates to Anthony's patch file, Anthony please let me know if you see any issues with this. 1) fixed the tests so that they will run on my machine (starting a server for client tests is complex due to timing issues - we really need to work on making our tests easier to write) 1.5) fixed call to KeptSet constructor in test (added flags) 2) added apache licenses to the source files 3) small formatting changes 4) implementation note in the class javadoc 5) we use spaces, not tabs
        Anthony Urso made changes -
        Attachment ZOOKEEPER-104.patch [ 12387053 ]
        Hide
        Anthony Urso added a comment -

        Revised patch attached,

        Show
        Anthony Urso added a comment - Revised patch attached,
        Anthony Urso made changes -
        Attachment ZOOKEEPER-104.patch [ 12386934 ]
        Hide
        Anthony Urso added a comment -

        >> You might consider throwing KeeperException on KeptSet.add to avoid problems, for example, with addAll.

        KeptSet.add does throw a wrapped KeeperException whenever one is caught. I have to wrap it in an unchecked exception because of the Set interface.

        >> the idea is to let ZooKeeper store the elements of a set despite failures of the client that created these elements

        For my needs, I would like the set to contain the nodes even if the creating client dies. But I've made it configurable at instantiation in the new patch.

        >> Again on KeptSet.add, it seems to me that you can shrink your synchronized block.

        Good idea. I think catching NodeExistsException eliminates the need for it entirely.

        >> the set is not resync'd with the server after disconnect

        I think that's fixed now, by synchronizing upon getting any event with a connected state.

        >> rather than add returning false, which would happen if the client added a string that was already present

        Good catch, fixed.

        >> Also note that the set is updated via a watch (even for changes made by this client), so you could add a string and an immediate check for existence may fail.

        Documented.

        Show
        Anthony Urso added a comment - >> You might consider throwing KeeperException on KeptSet.add to avoid problems, for example, with addAll. KeptSet.add does throw a wrapped KeeperException whenever one is caught. I have to wrap it in an unchecked exception because of the Set interface. >> the idea is to let ZooKeeper store the elements of a set despite failures of the client that created these elements For my needs, I would like the set to contain the nodes even if the creating client dies. But I've made it configurable at instantiation in the new patch. >> Again on KeptSet.add, it seems to me that you can shrink your synchronized block. Good idea. I think catching NodeExistsException eliminates the need for it entirely. >> the set is not resync'd with the server after disconnect I think that's fixed now, by synchronizing upon getting any event with a connected state. >> rather than add returning false, which would happen if the client added a string that was already present Good catch, fixed. >> Also note that the set is updated via a watch (even for changes made by this client), so you could add a string and an immediate check for existence may fail. Documented.
        Hide
        Patrick Hunt added a comment -

        Great idea, +1

        I agree with flavio, this should go into contrib, unfort we don't have one yet. Makes sense to me that this should be part of the recipes
        src/contrib/recipes/src/java/org/apache/zookeeper/recipes/util/KeptSet.java
        package org.apache.zookeeper.recipes.util.KeptSet
        how's that sound?

        Anthony, I think there's an issue in the watcher - it doesn't handle the case where the client is re-connected (disconnected then reconnected) - ie the set is not resync'd with the server after disconnect.

        (the following doc hasn't been moved to apache yet)
        http://zookeeper.wiki.sourceforge.net/ZooKeeperWatches
        specifically:
        "when a client gets a disconnect event, it must consider that an implicit trigger of all watches. When a client reconnects to a new server, the client should re-set any watches that it is still interested in"

        Also, this is a leaky abstraction (not that that's necessarily bad). Notice that if two clients add the same, new, string to the same set (relative to the znode path on the zk server) one of the clients will succeed and the other will get a runtime exception (wrapping keeperexception) (rather than add returning false, which would happen if the client added a string that was already present). Also note that the set is updated via a watch (even for changes made by this client), so you could add a string and an immediate check for existence may fail. Might be confusing for ppl expecting Set semantics, would be a good idea to document.

        Show
        Patrick Hunt added a comment - Great idea, +1 I agree with flavio, this should go into contrib, unfort we don't have one yet. Makes sense to me that this should be part of the recipes src/contrib/recipes/src/java/org/apache/zookeeper/recipes/util/KeptSet.java package org.apache.zookeeper.recipes.util.KeptSet how's that sound? Anthony, I think there's an issue in the watcher - it doesn't handle the case where the client is re-connected (disconnected then reconnected) - ie the set is not resync'd with the server after disconnect. (the following doc hasn't been moved to apache yet) http://zookeeper.wiki.sourceforge.net/ZooKeeperWatches specifically: "when a client gets a disconnect event, it must consider that an implicit trigger of all watches. When a client reconnects to a new server, the client should re-set any watches that it is still interested in" Also, this is a leaky abstraction (not that that's necessarily bad). Notice that if two clients add the same, new, string to the same set (relative to the znode path on the zk server) one of the clients will succeed and the other will get a runtime exception (wrapping keeperexception) (rather than add returning false, which would happen if the client added a string that was already present). Also note that the set is updated via a watch (even for changes made by this client), so you could add a string and an immediate check for existence may fail. Might be confusing for ppl expecting Set semantics, would be a good idea to document.
        Flavio Junqueira made changes -
        Assignee Anthony Urso [ anthonyu ]
        Hide
        Flavio Junqueira added a comment -

        Again on KeptSet.add, it seems to me that you can shrink your synchronized block. The only access to "this.set" is on the predicate of the if statement, and the call to create doesn't realy need to be synchronized, right?

        Show
        Flavio Junqueira added a comment - Again on KeptSet.add, it seems to me that you can shrink your synchronized block. The only access to "this.set" is on the predicate of the if statement, and the call to create doesn't realy need to be synchronized, right?
        Hide
        Flavio Junqueira added a comment -

        I agree, nice idea. I took a look at the patch, and I have a comment.

        You might consider throwing KeeperException on KeptSet.add to avoid problems, for example, with addAll. On addAll, if you try to add a number of elements, the first succeeds, but some other succeeding element fails, then addAll will end up returning true, although not all elements have been written. You can change the logic so that it returns false, but in general I think it is a good idea to expose to the application that there was a problem with ZooKeeper.

        Just to make sure that I have understood correctly your abstraction, the idea is to let ZooKeeper store the elements of a set despite failures of the client that created these elements, and that's why you create regular nodes and not ephemeral nodes.

        Finally, I don't see a contrib folder in the svn, so I suspect that we don't have one yet. I'm mentioning this because your patch should add KeptSet to contrib. Pat can either agree or correct me on this part.

        Show
        Flavio Junqueira added a comment - I agree, nice idea. I took a look at the patch, and I have a comment. You might consider throwing KeeperException on KeptSet.add to avoid problems, for example, with addAll. On addAll, if you try to add a number of elements, the first succeeds, but some other succeeding element fails, then addAll will end up returning true, although not all elements have been written. You can change the logic so that it returns false, but in general I think it is a good idea to expose to the application that there was a problem with ZooKeeper. Just to make sure that I have understood correctly your abstraction, the idea is to let ZooKeeper store the elements of a set despite failures of the client that created these elements, and that's why you create regular nodes and not ephemeral nodes. Finally, I don't see a contrib folder in the svn, so I suspect that we don't have one yet. I'm mentioning this because your patch should add KeptSet to contrib. Pat can either agree or correct me on this part.
        Hide
        Mahadev konar added a comment -

        nice idea....

        Show
        Mahadev konar added a comment - nice idea....
        Anthony Urso made changes -
        Status Open [ 1 ] Patch Available [ 10002 ]
        Hide
        Anthony Urso added a comment -

        Patch attached.

        Show
        Anthony Urso added a comment - Patch attached.
        Anthony Urso made changes -
        Field Original Value New Value
        Attachment ZOOKEEPER-104.patch [ 12386934 ]
        Anthony Urso created issue -

          People

          • Assignee:
            Anthony Urso
            Reporter:
            Anthony Urso
          • Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development