/usr/sbin/mysqld was deleted and replaced by another mysqld with different inode
At first glance, this seems extremely suspicious, but based on the information below, there may be a very logical and non-dangerous, although counter-intuitive, explanation.  

Out of curiosity, I looked for important-but-deleted files on some Linux machines and I found such interesting things as...

COMMAND     PID       USER   FD      TYPE     DEVICE   SIZE/OFF       NODE NAME

bash      30851       root  txt       REG      202,1     959120     142485 /bin/bash
bash      31501       root  txt       REG      202,1     955024     131092 /bin/bash (deleted)


Yikes.  Really?

These systems are apt vs yum systems but the principle is the same... it's inconceivable in the world of windows but entirely sensible and not all that unexpected in the world of Linux (or any Unix afaik) to overwrite files that are "open" by another process.  The space allocated to the files is freed as soon as all of the processes that are holding them open... close them.

The log, in my case, confirms that "bash" was involved in one of the packages that has been upgraded since the last reboot but some of the copies of bash that are running are actually still the old bash that was running before the update.

However... your binaries are the same size where mine are different, so this would seem to suggest that it wasn't an outright upgrade.  This led me to speculate that it might have been an upgrade of the package that contained mysqld but that didn't change mysqld itself, causing the file to be overwritten by an identical copy of itself.  But that seems like speculation.

I don't like speculation, so I kept digging.  I use Ubuntu these days, but still have some old Red Hat machines around, so I took a look in the directories in /etc/cron.* and stumbled upon prelink.

I realize you said there are no cronjobs running on the system... but are you sure about that?  Not even the "factory" default cronjobs in /etc/cron?

01 * * * * root run-parts /etc/cron.hourly
02 4 * * * root run-parts /etc/cron.daily
22 4 * * 0 root run-parts /etc/cron.weekly
42 4 1 * * root run-parts /etc/cron.monthly


If there really are no cron jobs running, then of course, the rest of this post is nonsense, but it would seem very unusual to me to literally have no cron jobs on a Red Hat machine.

Take a look at the timestamp of /var/log/prelink/prelink.log.  If it's a match for the time window in question, then we have a suspect.

I've been a Linux sysadmin for even longer than I've been a DBA and yet somehow this is the first time I remember ever running across this, and frankly, on first reading, it made me nervous that an overnight process was actually poking at bits inside executables, but I guess it's not as problematic as it seems like it would be.  

Perhaps it's never caught my attention because I never use the package manager to install MySQL (I see it as too important for anything to touch but me) and the "standard" path for installing official binary distributions is /usr/local/mysql[/bin], which isn't in the paths that prelink touches.

Prelink optimizes program execution and and provides some degree of immunity against exploits based on buffer overruns by making the addresses inside executables and shared libraries somewhat random on a system by system basis.  What you might find, depending on the mix of installed software on each machine, is that each machine's current copy of the mysqld binary is the same size but that they do not actually have the same md5sum or sha1sum checksums as each other even if they're identical versions.  Before today, that would have made no sense at all... but given what I found on prelink... it wouldn't surprise me at this point.

http://people.redhat.com/jakub/prelink/prelink.pdf

I think it seems very likely that this is what's happened.  If your servers are properly firewalled and nothing else seems amiss, it seems unlikely that an intruder would have deliberately and successfully compromised multiple machines in the same way.



If the above turns out to be a likely candidate, you should find, curiously enough, the you can still get to, and make copies of, those files that are deleted, as long as you don't shut down the running mysqld process.  I categorically do not recommend that you put them back but if you are curious, you might find the following informative.

Find the process ID of mysqld from lsof and cd into the /proc/nnnnn directory on your system, where nnnnn is the process id.

Inside this directory you'll find what appears to be a broken symlink called exe.  This is not exactly what it seems, because it actually still references the deleted file in a very real fashion.

I'll illustrate the rest of this with one of my deleted copies of "bash" from above.  The process ID was 31501.

root@host:/# cd /proc/31501
root@host:/proc/31501# ls -l exe
lrwxrwxrwx 1 root root 0 May  1 06:41 exe -&gt; /bin/bash (deleted)


You can actually cp exe /some/new/place and salvage this deleted file, precisely because it is still open.  Again, I wouldn't recommend that you start using this copy, but this is the one that is on the disk that has been deleted, if you want to do any detailed byte by byte analysis.  

For a coarser example, you could do a checksum of it.  Again, the example is from my system, with the deleted "bash" which is process 31501.

root@host:/proc/31501# md5sum exe
748c6ee926dd3cf55bcfb60ce928d367  exe


Not surprisingly, that's not the same checksum as the live copy of "bash" on my system.

root@host:/proc/31501# md5sum /bin/bash
3cac23b8442e3971f1d10660cc779b9f  /bin/bash


However, by lucky coincidence, I have another machine that has not been upgraded as recently as the one above.  You'll notice this copy of bash is exactly the same size as the deleted copy on my machine... and it even has the same checksum.

user@older:~$ ls -l /bin/bash
-rwxr-xr-x 1 root root 955024 Apr  3  2012 /bin/bash
user@older:~$ md5sum /bin/bash
748c6ee926dd3cf55bcfb60ce928d367  /bin/bash


You also could... but you really really really shouldn't... actually run the file represented by "exe" from inside the process directory of mysqld (mine is running on 21691).  Seriously, don't do it.  But here's what it will do, if you're curious.  The executable is using its named on disk to identify itself as ./exe ... but it's MySQL all right:

/proc/21691# ./exe --version
./exe  Ver 5.6.10 for linux-glibc2.5 on x86_64 (MySQL Community Server (GPL))


How about that?