Repository: Netflix/metaflow
Pull request: Add a uid for the kubernetes job creation
Fixes #1554 

When running large for-each branches (3000+) Metaflow will sometimes cause job name collisions on kubernetes. This adds a UUID to the prefix which should add sufficient entropy to prevent this from happening.

Problem statement:
Name collisions on kubernetes jobs cause flow to fail
If there is a random UID created for a kubernetes job that is the same as an existing job, the job will fail:

```
2023-09-26 19:59:06.554 [26708/write_refl_store/232688 (pid 332902)] metaflow.plugins.kubernetes.kubernetes_job.KubernetesJobException: Unable to launch Kubernetes job.
2023-09-26 19:59:06.554 [26708/write_refl_store/232688 (pid 332902)] jobs.batch "t-hcwfq" already exists, the server was not able to generate a unique name for the object
```

Hints from issue discussion:

Commit message: Add a uid for the kubernetes job creation

Patch to review:
diff --git a/metaflow/plugins/kubernetes/kubernetes.py b/metaflow/plugins/kubernetes/kubernetes.py
index 410651f1e29..ed034be8cad 100644
--- a/metaflow/plugins/kubernetes/kubernetes.py
+++ b/metaflow/plugins/kubernetes/kubernetes.py
@@ -5,6 +5,7 @@
 import shlex
 import time
 from typing import Dict, List, Optional
+import uuid
 
 from metaflow import current, util
 from metaflow.exception import MetaflowException
@@ -178,7 +179,7 @@ def create_job(
         job = (
             KubernetesClient()
             .job(
-                generate_name="t-",
+                generate_name="t-{uid}".format(uid=str(uuid.uuid4())),
                 namespace=namespace,
                 service_account=service_account,
                 secrets=secrets,


Code review comments:
diff_hunk: @@ -178,7 +179,7 @@ def create_job(
         job = (
             KubernetesClient()
             .job(
-                generate_name="t-",
+                generate_name="t-{uid}".format(uid=str(uuid.uuid4())),
path: metaflow/plugins/kubernetes/kubernetes.py
text: @user1:
another approach here would be to rely on the existing id's for namespacing purposes (added benefit of making the pod name more descriptive). e.g.
```python
generate_name="t-{run_id}-{step_name}-{task_id}-".format(run_id=run_id, step_name=step_name, task_id=task_id),
```
This is similar to what is happening with Argo Workflows pod naming.

there's a max length of 63 characters for the name, and with a suffix of 5 characters there might be truncation in some cases. From what I've understood, the truncation only happens for the generatedName part, so we would still get a random suffix.

@user1:
alternatively we can just chop up the first one or two parts of the uuid, as we're still receiving the suffix from the apiserver on top of it.

@author:
I do like your method better as it embeds more useful information in the id as well as preventing collisions

@user2:
I like adding more info to the name 👍

Potential issue:
1. If the step name is super long, then `truncate("t-{run_id}-{step_name}-{task_id}")` could end up not containing the task id, and thus we would have massive collisions on branching steps. So we would need something like `"t-{truncate(run_id)}-{truncate(step_name)}-{task_id}")` instead.
2. What if you have two or more metadata services running (I would even try to imagine why, but I think we have to assume people will do it), then the run_id, step_name, and task_id might be equal. I know it is probably unlikely, but I still kind of like having the 4 random characters to be on the safe side. 4 should be enough at this point :D

Unimportant side questions: What does the `t-` mean? And why not use f-strings? 

EDIT: Sorry. I misunderstood. The 4 random characters would still be appended at the end, right? Then my concerns are not really valid.

@user3:
to introduce enough entropy - how about simply doing `generate_name="t-{entropy}".format(entropy=secrets.token_hex(2))`. This should be good enough for a vast majority of use cases till kubernetes address the [collision problem](https://github.com/kubernetes/kubernetes/issues/115489) on their end.

@user1:
The `token_hex` seems like a good way forward. Doesn't stretch the id's that much while providing enough entropy.

My earlier note about embedding more info to the pod id is a bit moot; as noted it is subject to truncation, and the relevant bits are recorded in pod annotations in full detail.

@user4:
The context was slightly different but we did face a similar issue here at Netflix and we solved it by doing something like this: 
- take 18 characters of a sha1 hash (or something like it)
- convert it to a smaller 12 characters using base64 encoding
- this gives you 72 bits of entropy and if you look here: https://kevingal.com/apps/collision.html, that is good enough for a billion tasks (well you have a 1e-6 chance of collision which is good enough for me :) ).

I don't fully understand how long lived the job name is but 16 bits of entropy (2 bytes for token_hex) seems low and you are likely to get a collision for 12000 jobs (one of the use cases brought on slack). The "trick" of using base64 encoding gives you higher entropy for fairly low cost (you just have to pick your other two characters carefully in case of naming conventions but that's not impossible). Not saying you need the full 72 bits but 16 feels low.

@user1:
the configurable part here is just a prefix supplied to the Kubernetes apiserver, it will still generate a 5-character suffix which it appends to it so overall it should be sufficient (`(16**4)*(40**5)` items if my midnight math is correct)

@user4:
Ah, I had missed the addition of 5 characters. If those characters have a 6 bit entropy (which covers alphanumerical strings using the full 52 characters and 10 digits) that would be 46 bits of entropy that would definitely be better :) (chances of collision under 1% for 1M jobs).

@user2:
The 5 characters provided by Kubernetes are all lowercase, thus 26 + 10 digits, I believe. So there are 36^5 total possible outcomes? With an additional 16 bits of entropy, I could run 100.000 jobs per day for 7 days and that would give me a 6% chance of collision - is that an acceptable scaling limit? I would vote for adding more bits of entropy.

```python
n_possible_job_names = (36**5) * (2**16) 
n_jobs = 7 * 100000
round(1 - np.prod([(n_possible_job_names - j) / n_possible_job_names for j in range(n_jobs)]), 2)
# = 0.06
```

UPDATED, I had an error in my first calculation

@user5:
Perhaps a unix timestamp would be an option?

@user2:
Timestamps would be good if we could guarantee at most one job per second. But that is not really the case here.

As I see it, either we go with:

**1. Complete randomness**. In which case we should try to be on the safe side regarding entropy, eg.
```python
generate_name="t-{entropy}".format(entropy=secrets.token_hex(4))
```
which will give us around 0.01% chance of collisions with 7M jobs within 7 days TTL. 

**2. Some kind of increment like the task id**. Plus a little entropy to allow for eg. having two metadata services. So could be:
```python
generate_name="t-{task_id}-{entropy}".format(entropy=secrets.token_hex(2), task_id=task_id)
```

@user5:
Wouldn't the the random 5 character suffix (generated via`generateName`) mean you wouldn't need to to be restricted to one job per second? 

I was expecting the job name to be something like `t-1697967000-fjdkt` with this approach.

@user2:
Sorry. You are right @user5. Keep forgetting that. Then a UNIX timestamp should not be a problem.

@author:
Since this is a temporary solution until the Kubernetes folks fix this, @user3's simple solution seem sufficient