What was the earliest Hadith Book / Collection to be recorded?
I heard it was Muwatta Malik?
The point is what do you define as a hadith book or hadith collection?
Records of hadith in the early days of Islam
As hadith was in first place (the same as Quran) memorized and spread through oral transmission. However recording Quran was allowed and even ordered in a kind that our Prophet () had some scribes. These scribes and maybe other literate sahaba were on the other side frowned upon, discouraged or maybe even prohibited from writing any thing else but Quran, one could discuss if this was a general prohibition, a prohibition for the time a revelation needs to be recorded or prohibition for some people, while it was allowed for others.
While our Prophet () was still alive some sahaba have recorded hadith the most prominent example is Abdullah ibn 'Amr ibn al-'Aas, who according his own statement and a statement of abu Hurairah have been allowed (by our Prophet()) or at least has written ahadith during the life time of the Prophet (). Abduallah ibn 'Amr called his hadith collection as-Sadiqah (or as-sahifa as-Sadiqah, also read this article in Arabic about it), it is widely known because his grand son 'Amr ibn Sho'aib used to narrated and read from it. Note that it was also narrated that Anas ibn Malik and other sahaba had similar collections (this -in Arabic- thread seems to show a long list and answer your Question too). Also our Prophet () has sent a dictated paper with some rulings with Amr ibn Hazm to Yemen (See for example in sunan an-Nasa'i, a short and a long version) beside other dictate "ahadith" to people who had a bad memory.
Is al-Muwatta' the earliest hadith collection?
Note that Muwatta' Malik has been compiled (one could say the first release) somewhere between 148 a.H. and 163 a.H. and in worst case even later (See here). We also know that Imam abu Hanifa (died 150 a.H.) had an own hadith collection called "musnad abu hanifa مسند ابي حنيفة" which some hanafi scholars like Mulla 'Ali al-Qari have even commented, so this book must have existed at a time or what we have is falsely attributed to him. Again one could discuss whether this book has really been compiled by abu Hanifa or not. But for sure abu Hanifa had his hadith "data base" from which we find examples in the version of al-Muwtta' of his student Muhammad ibn al-Hassan a-Shaybani who after commenting of ahadith of Imam Malik, added some narrations of abu Hanifa and other scholars!
Maybe this needs a clarification: Imam Malik's Muwatta' was some kind of work in progress: He started his book with some 10.000 hadith narration out of 100.000 he memorized (according to some of his statements) and with the time verified them (based on the Quran and sahih sunna etc.) until there were less than 2000 narrations (on the whole) kept among them less than 600 hadith musnad (with an intact narrator chain, at least 500 of them are in every later -sunni- hadith collection), beside ahadith where some narrators are missing, sayings of sahaba and fatwas based on fatwas of sahaba or tabi'iyn etc.. So al-Muwatta' when referred to in general refers to the version of Yahya ibn Yahya al-Laithi al-Andalussi, who was the last student who presented his records to Imam Malik (Note that Yahya strictly speaking didn't narrate or record the whole Muwatta' from Malik as once back in al-Andalus he asked his former teacher Ziyad Shabtun to dictate some ahadith from the chapter of al-I'tikaf to him or kept the dictation of Shabtun, as he was in doubt about what he has heard). While earlier Muwatta' copies include much more ahadith like the one of Muhamamd ibn al-Hassan, al-Qaanabi (teacher of al-Bukahri, Muslim and abi Dawood) and ibn Wahb which are among the 7-10 still available copies out of 100 or more which are quoted by scholars such as al-Qadi 'Iyad etc..
Note the same way even sahih al-Bukhari has been brought to us, by many narrators, not only by a printed or recorded book!
A Rough overview on hadith collection and compilation
And 'Umar bin 'Abdul 'Aziz wrote to Abu Bakr bin Hazm, "Look for the knowledge of Hadith and get it written, as I am afraid that religious knowledge will vanish and the religious learned men will pass away (die). Do not accept anything save the Hadiths of the Prophet. Circulate knowledge and teach the ignorant, for knowledge does not vanish except when it is kept secretly (to oneself)." (See in sahih al-Bukhari as an intro to "Chapter: How the (religious) knowledge will be taken away")
I've often heard and read that ibn Shihab az-Zuhri the teacher of 'Omar ibn Abdelaziz and later Imam Malik was among those scholars who were asked, we can find some 2200 hadiths of his narration today.
According to scholars like ibn Hajar al-'Asqalani in his introduction to fath al-Baary (I'll just translate a summary):
فأول من جمع ذلك الربيع بن صبيح وسعيد بن أبي عروبة وغيرهما فكانوا يصنفون كل باب على حدة إلى أن قام كبار أهل الطبقة الثالثة في منتصف القرن الثاني فدونوا الأحكام
فصنف الإمام مالك الموطأ وتوخى فيه القوي من حديث أهل الحجاز ومزجه بأقوال الصحابة والتابعين ومن بعدهم وصنف أبو محمد عبد الملك بن عبد العزيز بن جريج بمكة وأبو عمرو عبد الرحمن الأوزاعي بالشام وأبو عبد الله سفيان الثوري بالكوفة وحماد بن سلمة بن دينار بالبصرة وهشيم بواسط ومعمر باليمن وابن المبارك بخراسان وجرير بن عبد الحميد بالري وكان هؤلاء في عصر واحد فلا يدرى أيهم سبق
ثم تلاهم كثير من أهل عصرهم في النسج على منوالهم الى أن رأى بعض الأئمة منهم أن يفرد حديث النبي صلى الله عليه و سلم خاصة وذلك على رأس المئتين فصنفوا المسانيد فصنف عبد الله بن موسى العبسي مسندا ثم صنف نعيم بن حامد الخزاعي نزيل مصر مسندا
ثم اقتفى الأئمة أثرهم في ذلك فقل إمام من الحفاظ إلا وصنف حديثه في المسانيد كالإمام أحمد بن حنبل واسحاق ابن راهويه وعثمان ابن أبو شيبة وغيرهم ومنهم من صنف على الأبواب والمسانيد معا " كأبي شيبة فلما رأى البخاري هذة التصانيف ووجدها بحسب الوضع جامعة بين ما يدخل تحت التصحيح والتحسين والكثير منها يشتمل على الضعيف فحرك همته لجمع الحديث الصحيح
Among the first who compiled books of hadith where ar-Rabi'i ibn Sabyh (died 160 a.H.) and Sa'id ibn Abi 'Aruba (died 156 a.H.) beside others, but they compiled it in form of single chapters.
In the middle of the second century (a.H.) the big scholars began to compile books with rulings and jurisprudence among them Malik in Medina, Abdulmalik ibn Abdulaziz ibn Jorayj (died 150 a.H.) in Mekka, Abdurrahman al-Awzaa'i (died 157 a.H.) in a-Shaam, Sufyan at-Thawri (died 161 a.H.) in al-Kufa, Hammad ibn Salamah (died 167 a.H.) in al-Basra, Hasheem (or Husahym) ibn Bashir (died 184 a.H.) in Waasit, Ma'amar ibn Rashid (died 153 a.H.) in Yemen, Abdullah ibn al-Mubarak (died 181 a.H.) in Khorasan and Jarir ibn Abdelhamid (died 188 a.H.) in Rey. And all of them lived at the same time, so that it is hard to tell whom compiled first.
Many of their coevals afterwards did the same until people start seeking and compiling (musnad) ahadith exclusively at the end of the 2nd century: 'Obayd Allah ibn Musa al-'Absi (died 213 a.H.) was the first who compiled a Musnad, after that came al-Khoza'y (died 229) who lived in Egypt for a while.
Many hufadh of hadith followed them like Ahamad ibn Hanbal, Ishaq ibn Rahwayh, ibn Abi Shaybah and others some of them compiled it even based on both chapters and sanad (narrator chains) like ibn Abi Shaybah.
And when al-Bukhari saw this and found that the most of is could be qualified as sahih, hassan or da'if according the compilation his decision to dedicate the rest of his life in compiling a book that would be composed strictly of authentic.