Хочется структурировать и нормально организовать хранение в оперативной памяти
Ну, собственно, здесь и содержится ответ на вопрос.
Всякие key-value значения нам не подойдут, а вот прямоугольная таблица - очень даже.
Учитывая что реляционные БД позволяют сохдавать таблицы в памяти, проблема решена. Mysql здесь будет чересчур, а sqlite вполне подойдет
$db = new PDO('sqlite::memory:');
$db->setAttribute( PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION );
$db->query("CREATE TABLE temp (mysite_id int,mysite_ext_id int,service_ext_id int,service_id int)");
ну и дальше обычными запросами
$db->query("INSERT into temp (mysite_id) values (1)");
var_dump($db->query("SELECT service_ext_id FROM temp where mysite_id=1")->fetchColumn());