This is less than ideal, but seems to work.
What do you do?
Note; I'm talking about binary packages distributed by your OS : apt upgrades / rpms.. not config files (Hi, puppet/chef), or deprec for capistrano style stuff.
/apps/<appname>/<app version> example: /apps/perl/5.8.12 then I would symlink /apps/perl/5.8.12 to /apps/perl/current
The profiles on the machine would add /apps/*/current/bin to the path. This allowed upgrades and roll backs just by changing the symlink to the one I wanted to be current. This also allowed me to push out versions of software ahead of time, and they just change the link when we were ready to use it.
Each machine would rsync /apps from a master distro nightly and of course I could force it with a for i in `cat hosts.list`...
Making the filesystem the actual package database rather than a snapshot of what should be installed is quite tempting.
At my last job we ran Spacewalk on our Koji box. Koji will let you build packages that you can then put in your repo to yum install.
It turns out, that's exactly the problem. The topic was hotly debated and yes, there are endless possible ways to distribute packages across a large environment.
I think choosing a pattern involves deciding for yourself how secure/auditable you need your environment to be and how tightly you want to couple your deployment process to your current architecture (ie. some package managers only work on some systems, etc.). That will narrow your choices down to a handful, and then you get to dig into the implementation details and decide from there.
Depending on the release and the kind of server we're deploying to, we may do them all in one night or in batches of a few hundred over a week. All our boxes install security updates regularly (because we promptly add security updates to our dists.)
If you want to tightly control the packages that get updated then there isn't much to be done other than manually managing your own repo. Although if it is this big of a concern you should probably be running a distribution that is less volatile than Ubuntu. Say RHEL, CentOS, or Debian.
1. Mirror a yum repository plus updates. For each day create a hardlinked directory of updates named reponame.YYYYMMDD. On the hosts you wish to update sed -i to the new day in your yum repo config file and run yum -y upgrade. When you know it works, do it on the other hosts too.
2. Use a configuration management tool like Puppet.
For your sized infrastructure you probably want the first.