Re: [Condor-devel] Avoiding redundant executables in the SPOOL

[Alan De Smet <adesmet@xxxxxxxxxxx>]

The problem and goal are unchanged, if you read them before, skip
down to "the plan".  This is a complete overhaul.


The problem: 

We have actual users using Condor-C submit to submit hundreds or
thousands of jobs with the same executable.  For Condor-C
copy_to_spool must be true.  Furthermore, for Condor-C, we
can't use clusters to share an executable; each job becomes a new
cluster.  You end up with one copy of the executable per job.
Given a moderately large executable, you can end up with
gigabytes of duplicate executables.  This is a waste of disk
space and bandwidth.


The goal: 

When copy_to_spool=true, avoid multiple copies of the same
executable in the SPOOL.  

(The more general goal would be to avoid multiple copies of any
input file in the SPOOL, but that's a harder problem as the input
files can potentially be modified.)



The plan: 

0a. condor_submit: Do we skip copying to the spool entirely?  If
yes, none of this matters.

	- is copy_to_spool false?
	- does the cmd include macros, eg $(OpSys) or $(Arch)?
		- Such binaries can _eventually_ end up in the spool.
		  They won't get this benefit.

1. condor_submit: Calculate a hash of the executable.
	
	Discussion:
	- We calculate on the submit side because:
		- It allows the schedd to potentially never look at the
		  file, saving network and schedd processor time for
		  remote submits.
		- submit can be aware that it's submitting the same
		  binary 50 times in different clusters, the schedd
		  can't.  This means we can do the hash once on the
		  client instead of 50 times on the server.
	- Arguably there is a risk of calculating it on the client
	  side: the client can lie.  Later steps will reveal that we
	  don't link between jobs of different Owners, so if client
	  lies about the hash, it only hurts themselves.
	- If at all possible, reuse the hash of executable work done
	  by Ian for signed classads.  I'll talk to Ian about this.
	- The hash
	- What is the hash?  
		- The output is a string in "KEY-value-KEY-value..."
		  form.
			- KEYs and values are escaped using the algorithm
			  described below.
			- By using a list of key-value
			  pairs, we can easily add or change the hashing
			  algorithm in the future.  We might add file size,
			  the timestamp, or other hashing algorithms.
			- For V1, it will likely be
			  "MD5-d41d8cd98f00b204e9800998ecf8427e".  It might
			  not be MD5, depending on reuse of Ian's work.

2. condor_submit: Include checksum in classad sent to the schedd.
CmdHash="MD5-d41d8cd98f00b204e9800998ecf8427e".

3. condor_schedd: Does the CmdHash include anything other than
alphanumeric characters and dash?   If yes, tell condor_submit
you hate it and hang up.  Otherwise, continue.

	- This is just protection from ill behaved submits.

4. condor_submit to condor_schedd: "May I send you the
executable?"

5. condor_schedd: Escape $(Owner) per the algorithm below.
The hash path is now "$SPOOL/exe-$EscapedOwner-$CmdHash".
It will look something like
"/home/condor/spool/exe-adesmet-MD5-d41d8cd98f00b204e9800998ecf8427e".  
If you don't have a CmdHash at all (Say, an old
condor_submit), the resulting hash path should be a special value
of "invalid."

	- We're prepending the Owner for security reasons.  The hash
	  we choose may be broken, allowing an attacker to provide a
	  different binary with the same hash.  
		- If we didn't prepend the Owner, we could have a
		  situation like this: The good user might occasionally
		  submit goodjob, which hashes to 0010.  The evil user
		  might create eviljob, which also hashes to 0010.  The
		  evil user now waits for good user to not have any jobs
		  submitted, then submits eviljob on hold.  Now they
		  wait.  Next time the good user submits goodjob, they'll
		  actually find and use eviljob!
	- We're prepending 'exe-' so they sort together, not scattered
	  around before and after other files and directories.
	- Handily, a sysadmin unsure which jobs are using which files
	  can ask: condor_q -constraint
	  'CmdHash=="MD5-d41d8cd98f00b204e9800998ecf8427e"'

6. condor_schedd: Does the hash path find an existing file?

	6a: No: (The path doesn't exist, or it's invalid) Tell
	condor_submit: "Send it along."  Write the incoming file to
	the ickpt.  Is hash path valid, just not currently existing?
		
		6aa: No, the hash path is the special value "invalid":
		Skip to step 7.

		6ab: Yes: Hard link the ickpt to the hash path.

	6a: Yes: Great, we'll reuse that.  Tell condor_submit: "No
	thanks."  Hard link from hash path to the ickpt
	("$SPOOL/cluster7524.ickpt.subproc0").

7. At this point the job is queued and all is well.  We'll
continue when it's time to remove the ickpt file because the job
is leaving the queue for whatever reason:

8. condor_schedd: Time to remove the job from the queue.  Check
the hard link count for the ickpt file.  Is it 2?  We're the last
user, unlink the hash path.

	- If it's 3 or above, there are other users of this file.
	  Leave it be.
	- If it's 1, this is a job that didn't have a hash.

9: condor_schedd: unlink the ickpt file, same as before.



Escaping algorithm:

The goals are:
- We need a character to separate fields in the CmdHash.  This
  character must be escaped.
- All resulting characters, including the field character, must
  be valid as a file name on all operating systems Condor
  supports.

Field seperator: - (, might be better, but I don't know if
Windows and MacOSX like it)

What to escape?  Anything that doesn't match the regex
/[A-Za-z0-9.]/.  We can probably add more characters; again what
is portable across all platforms we care about?

Escaping: for each character to escape, replace it with "_XX_"
where XX is the hexadecimal ASCII code for the character.  If '%'
is safe all all systems we care about, URL escaping ("%XX") might be
better, if only because it's widely recognized system.

This is woefully non-Unicode ready, but neither is the rest of
Condor.


General notes:

This is insecure in the face of CLAIMTOBE, ANONYMOUS, or any
other situation in which multiple users map to the same Owner.
Don't do that.  Even without this behavior, that's very insecure
and users can mess with each other using condor_qedit, condor_rm
and more.

If someone downgrades, everything will still work fine, but lots
of exe-username-MD5-asdfasdfasdf files will be left behind.  The
admin can safely remove all of them without harm!  Of course, no
one would ever downgrade Condor.

-- 
Alan De Smet                              Condor Project Research
adesmet@xxxxxxxxxxx                http://www.cs.wisc.edu/condor/