Call for contributions: how to store and generate the Node Identifier

[Manuel Finelli]

Narayana is changing towards becoming more cloud native to keep up with modern technologies (te.g. K8s/OpenShift, Azure, AWS, etc.). As Narayana is a transaction manager for distributed systems, most of its functionalities are ready to be hosted in cloud environments. Nevertheless, there are some parts of Narayana that need to be improved to optimise the integration of our code base in cloud environments. One of them is the node identifier (ID). In fact, in scenarios where the runtime controls the ID (e.g. the integration of Narayana in WildFly), there is the need to:

1. generate a globally unique identifier and 
2. store it up somewhere to persist it across several JVM restarts 

(reminder: the node identifier is currently defined through a configuration property (com.arjuna.ats.arjuna.nodeIdentifier) of the core transaction system).

For what concerns the persistence of the ID (point 2 above), we are still discussing what is the best approach to store the ID up. Initially, we thought to store the node identifier into the object store but then the generation of the ID must come before choosing the object store; moreover, if the object store is shared among different Narayana instances, there might also be a problem identifying the owner of a particular ID.

On the other hand, to address point 1, the team has put together a couple of options. Following, some of the available algorithms to generate a globally unique identifier (GUI) are listed:

• Universally unique identifier: in its version 4, this algorithm can be used to produce globally unique identifier based on a purely random source
  
  • Are UUIDs really unique?
  • Random UUID probability of duplicates
• KSUID
• FireBase
• ULID
• SnowFlake
  
  • Flake
  • TimeFlake
  • SonyFlake

In my opinion, KSUID would be the best choice to generate GUI and the reason is well explained in its GitHub page: “[...] A KSUID includes 128 bits of pseudorandom data ("entropy"). This number space is 64 times larger than the 122 bits used by the well-accepted RFC 4122 UUIDv4 standard. The additional timestamp component can be considered "bonus entropy" which further decreases the probability of collisions, to the point of physical infeasibility in any practical implementation. [...]”. Moreover, this algorithm has been “Battle Tested” for several years in a production environment.

This conversation is very important for the future development of Narayana in the cloud environment so your contribution is essential :-) Feel free to propose any solution/suggestion for either point above. Thanks!

[Mark Little]

Would be good to articulate pros and cons for these options.

--
You received this message because you are subscribed to the Google Groups "narayana-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to narayana-user...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/2d821d08-7015-4182-b1f1-2d7ee3b77fdbn%40googlegroups.com.

---
Mark Little
mli...@redhat.com

JBoss, by Red Hat
Registered Address: Red Hat Ltd, 6700 Cork Airport Business Park, Kinsale Road, Co. Cork.
Registered in the Companies Registration Office, Parnell House, 14 Parnell Square, Dublin 1, Ireland, No.304873

[Manuel Finelli]

Of course Mark, that is not a problem at all :-)
Following, (in relation to Narayana) pros and cons of every algorithm are summarised.

UUID v4

This is a widespread algorithm/standard to generate random numbers of 128 bit

• Pros

  • Generation of UUIDs is a decentralised process that can be executed locally without any interaction with other participants

  • It has been widely used in distributed systems since its origin (1980s). It is currently employed as primary key of DBs as well as in systems that are locally confined (e.g.linux filesystem)

  • Even though it is not guaranteed to be collision-free, UUID v4 can rely on a very low probability of producing duplicates, which suggests that UUID can be reliably used in scenarios where UUIDs are generated every once in a while (as it would be used in Narayana to generate the node’s identifier)

  • With 128 bit (i.e. 16 byte) UUIDs can be comfortably used as node’s identifier as they can be squeezed into the transaction identifier (XID) without any problem of space

  • UUID is part of Java already

• Cons

  • Source of randomness plays an important role when UUIDs are generated. In fact, the source of randomness (i.e. entropy) should be reliable (for example, atmospheric noise, laser, white noise). The lack of entropy is particularly evident in embedded systems, where the source of randomness can be limited. On the other hand, the source of randomness in modern OSs is quite reliable as many random events happen while a machine is operating (e.g. exchange of data on network interfaces, interaction with users, interrupts, etc.)

KSUID (only pros :-) I am a bit biased here)

This algorithm can be considered an evolution of the UUID v4 as it overcomes the issue of relying on a real source of randomness introducing more entropy in the equation. In fact, the overall 160 bit are divided in:

• 128 bit to generate a random number (which works out to be a number-space that is 64 times bigger than UUID v4’s)

• 32 bit are used to report a timestamp (extra entropy)

As a consequence, the probability of producing duplicates becomes even lower than UUID v4, “to the point of physical infeasibility in any practical implementation” (if the equation considered here is modified considering 160 bit, the result will be 1.42*10^24...if an immortal human being (with quite some spare time) wants to measure the diameter of the (observable) universe in meters, they would report a number of 8.8*10^26).

Talking about the size of the number generated using KSUID, 160 bit (i.e. 20 byte) is still a reasonable size to be used as a node's identifier and squeezed into the XID. It is still a decentralised algorithm so numbers produced locally are globally unique. Additionally, KSUID:

• Produces k-sortable IDs

• Is currently supported

• Supplies a Java implementation

I do not see any evident cons using this algorithm but if you spot some, please, let me know.

SnowFlake (and, as a consequence, SonyFlake)

This algorithm was introduced by Twitter in this announcement. Since then, new versions of SnowFlake have been developed and the original source code deprecated. This algorithm is currently used by Twitter to generate an identifier for whatever entity needs to be identified (e.g. tweets, users, etc.).

• Pros:

  • 64 bit (8 byte)

  • Identifiers are guaranteed to be collision-free

• Cons:

  • SnowFlake needs to initially coordinate nodes (basically, nodes need a unique identifier to start the algorithm). Tweeter used to employ ZooKeeper. This is the main disadvantage that excludes SnowFlake from the possible solutions of the ID generation problem we are discussing

  • No maintained implementations available

  • No Java implementation

The reason SnowFlake was listed among the solutions is that this algorithm is the originator of other (more evolved) decentralised algorithms that might be a good solution for our problem.

SonyFlake is an implementation of SnowFlake but it does not resolve the problem of assigning a unique ID to each machine. As a consequence, this algorithm will not be discussed.

Boundary’s Flake

Flake is an evolution of SnowFlake that tries to introduce two important improvements to the original algorithm:

• Identifier generation at a node should not require coordination with other nodes

• IDs should be roughly time-ordered when sorted lexicographically. In other words they should be k-ordered

This sounds very exciting but the shortfall of this algorithm is that the SnowFlake’s coordination phase has been replaced with a “unique” value that is locally available: the MAC address. This solution has been already employed in UUID v1 which has very well-known problems of security and privacy.

• Pros:

  • Solve the SnowFlake’s coordination problem

  • Improved entropy

  • IDs can be ordered

  • Improved implementation of UUID v1

• Cons:

  • Privacy problem due to MAC address

  • MAC addresses can be shared in modern technologies (e.g. cloud)

  • It is no longer supported (last commit is 5 years old)

  • There is not an implementation written in Java

TimeFlake

This algorithm is another improvement of SnowFlake but completely based on time. Pros are very well summarised in the algorithm’s GitHub page:

• Pros:

  • Fast. Roughly ordered (K-sortable), incremental timestamp in most significant bits enables faster indexing

  • Unique enough. With 1.2e+24 unique timeflakes per millisecond, even if you're creating 50 million of them per millisecond the chance of a collision is still 1 in a billion. You're likely to see a collision when creating 1.3e+12 (one trillion three hundred billion) timeflakes per millisecond

  • Efficient. 128 bits are used to encode a timestamp in milliseconds (48 bits) and a cryptographically generated random number (80 bits)

  • Flexible. Out of the box encodings in 128-bit unsigned int, hex, URL-safe base62 and raw bytes. Fully compatible with uuid.UUID

  • Implementation in Java available

  • Currently maintained

• Cons:

  • No evident cons

  • Just as a side note, if compared with KSUID, TimeFlake has less entropy (and therefore a higher probability to produce a duplicate; bare in mind that we are still talking about a very low probability - see pros)

Firebase and ULID are two algorithms written in JavaScript and they roughly do what TimeFlake and KSUID do but with less entropy/randomness. As both algorithms do not provide a Java port and they are (apparently) not maintained, I will not go into details.

[Mark Little]

Great write up! One thing I didn't notice for some of these approaches is a reference to any projects we might use to generate the corresponding ID. If some exist, what would be the recommendations? Clearly we need something in Java.

Mark.

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/b1c26baa-d60f-479d-b2da-3706de2a7b63n%40googlegroups.com.

[Manuel Finelli]

From the list of algorithms in my previous message, I found three Java implementations:

• UUID v4

• KSUID

• TimeFlake

The other projects are written in other languages; as a consequence, if we pick up one of them, we will need to rewrite it in Java.

[Mark Little]

In general we should look to contribute to/use other upstream efforts where possible. If that is going to happen, you'll need to check their licences and determine whether or not they're compatible.

Mark.

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/000ae250-694f-4911-a166-e596bcd76dc7n%40googlegroups.com.

[Michael Musgrove]

Would this be an additional config variable (ie will the user still be allowed to set the id via the config) or will we be removing the option to set the nodeIdentifier?

Do we know of any use cases where a user relies on being able to supply the id themselves? I'd argue that the nodeIdentifier/nodeName is internal to the transaction manager which would mean it is okay to remove the ability to set the nodeIdentifier (but probably best to do it in a major version of narayana)?

--

You received this message because you are subscribed to the Google Groups "narayana-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to narayana-user...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/2d821d08-7015-4182-b1f1-2d7ee3b77fdbn%40googlegroups.com.

--

Michael Musgrove

mmus...@redhat.com

JBoss, by Red Hat
Registered Address: Red Hat Ltd, 6700 Cork Airport Business Park, Kinsale Road, Co. Cork.
Registered in the Companies Registration Office, Parnell House, 14 Parnell Square, Dublin 1, Ireland, No.304873

Directors:Michael Cunningham (USA), Vicky Wiseman (USA), Michael O'Neill, Keith Phelan, Matt Parson (USA)

[Manuel Finelli]

> If that is going to happen, you'll need to check their licences and determine whether or not they're compatible.

+1 thanks Mark

> Would this be an additional config variable (ie will the user still be allowed to set the id via the config) or will we be removing the option to set the nodeIdentifier?

>
> Do we know of any use cases where a user relies on being able to supply the id themselves? I'd argue that the nodeIdentifier/nodeName is internal to the transaction manager which would mean it is okay to remove  the ability to set the nodeIdentifier (but probably best to do it in a major version of narayana)?

Personally, I would like to have both options available. On the other hand, I agree with you that the node's identifier is used internally and the Narayana administrator should be relieved from the duty of selecting a unique ID for each node. What other users/contributors think about this? (keeping in mind that the node's identifier is a weak point of Narayana when it is used in a cloud environment, e.g. when a Narayana instance is spun up/down, its node identifier has to be persisted somewhere and be attached back when the new instance is ready).

[Mark Little]

Email is cheap: don’t respond to two separate emails in the same email.

On 30 Sep 2021, at 16:35, Manuel Finelli <jfin...@redhat.com> wrote:

> If that is going to happen, you'll need to check their licences and determine whether or not they're compatible.

+1 thanks Mark

---
Mark Little
mli...@redhat.com

[Mark Little]

Just realised I didn't notice a conclusion on this thread. Where do things stand?

Mark.

[Manuel Finelli]

I believe we have not arrived at a definite conclusion, yet.

Wrapping up this discussion, we have some options (in Java and compatible with our licence) to generate node identifiers with enough entropy to guarantee uniqueness. I guess that we (the community) are at the point where we should decide if the next major release of Narayana will:

1. scrap the ability to manually configure node identifiers
   
2. have the ability to generate node identifiers automatically
3. leave everything as is and forget about this thread

I think that points 1) and 2) should be our targets :-)

[Mark Little]

Given Narayana is in full support within various versions of EAP, option 1 would require deprecation at the very least as it's a public API change. I don't believe we should consider that without hearing from "sufficient" EAP customers on their preference. Since that's likely to be a long wait, I don't think 1 is an option at all for this release, even including deprecation. Therefore, option 2 as an additional capability makes more sense, assuming there's insufficient input to make a case for option 3.

Mark.

--
You received this message because you are subscribed to the Google Groups "narayana-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to narayana-user...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/09f07022-9a14-4833-8d39-510d6a06e2a1n%40googlegroups.com.

[Manuel Finelli]

> Given Narayana is in full support within various versions of EAP, option 1 would require deprecation at the very least as it's a public API change. I don't believe we should consider that without hearing from "sufficient" EAP customers on their preference. Since that's likely to be a long wait, I don't think 1 is an option at all for this release, even including deprecation [...]

That makes a lot of sense. So point 1) should be " DEPRECATE the ability to manually configure node identifiers". This would give us more time to hear from EAP customers. Along the same line, I could start a new thread in the WildFly community mentioning what we are discussing here. WDYT?

[Mark Little]

No you misunderstand: we can't deprecate unless we hear from customers. If we deprecate now and then hear from EAP customers that they need this, we then can't "un" deprecate, now can we?! ;)

Whilst WildFly community input is interesting, EAP customers will likely not all be there or even respond. This is a question the project lead should raise through to the PM to figure out.

Mark.

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/823282eb-36fa-4ab4-b356-30167bf0f2d3n%40googlegroups.com.

[Manuel Finelli]

No you misunderstand: we can't deprecate unless we hear from customers. If we deprecate now and then hear from EAP customers that they need this, we then can't "un" deprecate, now can we?! ;)

Got it :-) Thanks

[Manuel Finelli]

Lawyers said that everything licensed under MIT is good for Narayana. So we are good to go with both KSUID and TimeFlake

[Mark Little]

OK so which of the two seems to be the more active?

Mark.

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/36c031b6-a471-4c79-8a52-f64bed152d69n%40googlegroups.com.

[Manuel Finelli]

Both projects are relatively active (even though they are small projects) but it seems that KSUID has a bigger community, older history (starting from 2017) and it "...has been used in production at Segment for several years..." [1]. I would propose to go for KSUID

[1]: https://github.com/segmentio/ksuid#battle-tested

[Mark Little]

This one, I presume? https://github.com/ksuid/ksuid

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/1f7c8732-abd5-4686-8269-b6dd48273908n%40googlegroups.com.

[Mark Little]

I suggest you try both the Java ksuid version and https://github.com/making/timeflake4j with newer versions of Java. Assuming they're both roughly the same in terms of performance and memory consumption, I think you should send a new message to the community (new subject) and make a recommendation, summarising your findings.

Mark.

[Manuel Finelli]

Yes :-)
This is the Java port of the original project

[Manuel Finelli]

That sounds like a good plan :-) very pleased we are moving this forward

[Michael Musgrove]

How do these various strategies compare with our own Uid class which wasn't listed in the pros and cons?

[Mark Little]

This is for the NodeID, which is part of the Uid. So we can’t use the Uid to generate the NodeID because to do that we’d need a NodeID in place already, which we do but it’s manual.

Mark.

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/7a02677f-4191-4d68-bab3-5614cd260cbcn%40googlegroups.com.

[Michael Musgrove]

`CoreEnvironmentBean.nodeIdentifier` only gets embedded in the Xid class so we can still use the Uid class to generate a unique value for it.

The Uid class has a configurable component based on implementations of the `com.arjuna.ats.arjuna.util.Process getpid()` interface method so can't we employ one of the algorithms discussed in this thread to provide an alternative implementation of that method? And the nodeIdentifier would still be configurable (allowing users to provide something more human readable/meaningful), but we would generate the default using the Uid class.

[Mark Little]

Definitely worth consideration.

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/67e3e0f8-ce21-4099-bf61-ca6604181b98n%40googlegroups.com.

[Michael Musgrove]

So @jfinelli what do you think, should we create a JBTM issue to add Java ksuid to the list of getpid implementations?

[Manuel Finelli]

I do not think that our UID class can be employed to generate the node identifier. In fact, our UID class uses the address of the host (i.e. IPv4 or IPv6), which is a major downside (in virtual environments (e.g. OpenShift/K8s), IPs and MACs can be reused for different nodes). In other words, using our UID class would mean facing similar problems that occur also when using UUIDv1 (for example, a higher duplication probability and security issues)

On the other side, the field `process` in our UID class is an int (32 bit). KSUID generates unique identifiers that are 160 bit long (hence its reliability). If we squeeze 160 bit in an int, we will loose all the pros that KSUID introduces.

[Michael Musgrove]

So are you suggesting that our Uid class, which uses (2 * 64) + (3 * 32) bits, is unsafe?

And are you suggesting that we deprecate Uid altogether in favour of something else?

[Mark Little]

Inline ...

On 25 Nov 2021, at 09:37, Michael Musgrove <michael....@gmail.com> wrote:

So are you suggesting that our Uid class, which uses (2 * 64) + (3 * 32) bits, is unsafe?

Yes, I’d like to see the data on this compared to one of the other options.

And are you suggesting that we deprecate Uid altogether in favour of something else?

I’d be -1 to this for a number of reasons, not least of which is the invasiveness of the change and impact on so many other products, like Fuse, Integration and PAM.

Mark.

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/e0ee8c1e-7667-43d8-a447-7de184f3972cn%40googlegroups.com.

[Michael Musgrove]

Me too. So we can either:

1. introduce a new data type for storing the nodeIdentifier, or

2. we re-purpose the hostname + pid fields and stuff one of these 160-bit KSUIDs into them, or

3. we get some hard data on the safety of our current implementation of Uid and then make a decision

[Michael Musgrove]

---------- Forwarded message ---------
From: Mark Little <mli...@redhat.com>
Date: Thu, Nov 25, 2021 at 10:07 AM
Subject: Re: Call for contributions: how to store and generate the Node Identifier
To: Michael Musgrove <michael....@gmail.com>

Agreed. Though I think we should start with your first question: is Uid unsafe for NodeID?

Mark.

On 25 Nov 2021, at 10:05, Michael Musgrove <michael....@gmail.com> wrote:

On Thu, Nov 25, 2021 at 9:57 AM Mark Little <mli...@redhat.com> wrote:

Inline ...

On 25 Nov 2021, at 09:37, Michael Musgrove <michael....@gmail.com> wrote:

So are you suggesting that our Uid class, which uses (2 * 64) + (3 * 32) bits, is unsafe?

Yes, I’d like to see the data on this compared to one of the other options.

And are you suggesting that we deprecate Uid altogether in favour of something else?

I’d be -1 to this for a number of reasons, not least of which is the invasiveness of the change and impact on so many other products, like Fuse, Integration and PAM.

Me too. So we can either:

1. introduce a new data type for storing the nodeIdentifier, or

2. we re-purpose the hostname + pid fields and stuff one of these 160-bit KSUIDs into them, or

3. we get some hard data on the safety of our current implementation of Uid and then make a decision

[Michael Musgrove]

So someone needs to get a handle on the probability of getting duplicates when using our own Uid class for nodeIdentifier. Then we can decide on Uid versus KSUID.

So the alternative products to use listed earlier in this thread needs to include the pros and cons of Uid and it also needs to give some idea of the probability of getting duplicates.

[Manuel Finelli]

inline

On Thursday, November 25, 2021 at 9:37:23 AM UTC Michael Musgrove wrote:

So are you suggesting that our Uid class, which uses (2 * 64) + (3 * 32) bits, is unsafe?

Problem is that 2*64 bits are fixed so the entropy of our Uid class is generated with 3*32 bits. I do not have any data to say that it is unsafe but I will try to work out the probability that our Uid class generates a duplicate.

 

And are you suggesting that we deprecate Uid altogether in favour of something else?

I am not suggesting to deprecate our `Uid` class. Even though, it would be good to double check the efficiency of our Uid class in a virtual environment.

[Mark Little]

All sounds good. Thanks Manuel!

Mark.

To view this discussion on the web, visit https://groups.google.com/d/msgid/narayana-users/c7f4e227-91e8-473b-b98d-6d22e2b298bfn%40googlegroups.com.