Faits :
A.
Par jugement du 18 décembre 2015, le Tribunal correctionnel genevois a reconnu Y._ coupable de tentative de meurtre. Il l'a condamné à une peine privative de liberté de trois ans, sous déduction de la détention subie, dont 18 mois avec sursis durant trois ans, ainsi qu'au paiement à A._ d'une somme de 10'000 fr. à titre de réparation du tort moral. Une mesure de traitement ambulatoire médical et/ou psychothérapeutique a été prononcée pour traiter son addiction à l'alcool. X._ a été acquitté du même chef d'accusation et de celui, subsidiaire, d'omission de prêter secours, sa libération immédiate ayant été ordonnée. L'Etat de Genève a été condamné à lui verser les sommes de 47'800 fr. et 7'710 fr. à titre d'indemnisation de la détention subie à tort, d'une part, et dans des conditions illicites, d'autre part.
B.
Par ordonnance du 27 avril 2016, la Cour de justice de la République et canton de Genève, Chambre d'appel et de révision, a déclaré irrecevable l'appel principal du Ministère public du 1er février 2016, faute d'annonce d'appel. Elle a déclaré irrecevable l'appel de A._ en tant que ses conclusions portaient sur la peine. Elle a déclaré recevable l'appel joint du Ministère public.
Le 19 juillet 2016, statuant sur appels principaux de X._ et de A._ ainsi que sur appel joint du Ministère public, la cour cantonale a rejeté le premier et partiellement admis les seconds. Elle a relevé la peine prononcée contre Y._ à quatre ans de peine privative de liberté, sous déduction de la détention subie. Elle a reconnu X._ coupable de tentative de meurtre et l'a condamné à une peine privative de liberté de trois ans et neuf mois, sous déduction de la détention subie. Elle a condamné ces derniers à payer, conjointement et solidairement, 10'000 fr., plus intérêts à 5% dès le 19 août 2014 à A._ à titre de réparation du tort moral ainsi qu'au paiement des frais de procédure de première instance.
L'arrêt cantonal se fonde en substance sur les faits suivants.
Le 19 août 2014 vers 2h00, après une soirée alcoolisée dans un restaurant, A._ s'est rendu à son domicile en taxi. Egalement présents à la soirée, Y._, au volant de son véhicule, accompagné de X._ ont poursuivi le taxi. A destination, Y._ est sorti du véhicule, a échangé quelque mots avec A._, puis lui a asséné plusieurs coups de couteau tandis que X._ immobilisait ce dernier en lui tenant les bras en arrière. Selon le constat de lésions traumatiques du 29 août 2014, A._ présentait, à son arrivée aux urgences, notamment six blessures, dont une au niveau de la région thoracique, d'environ 4 cm de profondeur, qui avait perforé le péricarde et une partie de la paroi antérieure du ventricule droit du coeur et nécessité une intervention chirurgicale en urgence. Sa vie avait été concrètement mise en danger.
C.
Y._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt cantonal et conclut, principalement, avec suite de frais et dépens, à son annulation, et notamment à ce que l'appel joint du Ministère public soit déclaré irrecevable. Subsidiairement, il conclut à la confirmation du jugement de première instance, plus subsidiairement, au renvoi de la cause à la cour cantonale. Il sollicite en outre l'octroi de l'assistance judiciaire et de l'effet suspensif.
X._ forme également un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt cantonal. Il conclut, avec suite de frais et dépens, à sa réforme en ce sens qu'il est acquitté, que les montants de respectivement 95'800 fr. et 51'400 fr. lui sont versés à titre d'indemnité en réparation du tort moral pour 479 jours de détention injustifiée (art. 429 al. 1 let. c CPP) et pour 257 jours de détention subie dans des conditions inhumaines et dégradantes (<ref-law>). Subsidiairement, il conclut à une diminution de sa peine sur la base de l'<ref-law>. Plus subsidiairement, il requiert le renvoi de la cause à la cour cantonale pour nouvelle décision. Il sollicite en outre l'octroi de l'assistance judiciaire.
Invités à se déterminer, le Ministère public et la cour cantonale ne se sont pas exprimés dans le délai imparti s'agissant du recours de X._. S'agissant de celui de Y._, les autorités précédentes se sont rapportées à l'arrêt entrepris.

Considérant en droit :
1.
Les deux recours sont dirigés contre la même décision, concernent le même complexe de faits et portent sur certaines questions de droit qui se recoupent. Il y a lieu de joindre les causes et de les traiter dans un seul arrêt (<ref-law> et 71 LTF).
I. Recours de Y._ (recourant 1)
2.
Le recourant 1 estime qu'en admettant l'appel joint du Ministère public s'agissant de la quotité de sa peine, alors même qu'il n'avait pas formé appel, la cour cantonale a violé l'interdiction de la reformatio in pejuset omis le caractère accessoire de l'appel joint.
2.1.
2.1.1. Aux termes de l'<ref-law>, la direction de la procédure transmet sans délai une copie de la déclaration d'appel aux autres parties (al. 2). Dans les 20 jours à compter de la réception de la déclaration d'appel, ces parties peuvent, par écrit, déclarer un appel joint (al. 3 let. b).
L'<ref-law> prévoit que l'art. 399 al. 3 et 4, s'applique par analogie à l'appel joint (al. 1); l'appel joint n'est pas limité à l'appel principal, sauf si celui-ci porte exclusivement sur les conclusions civiles du jugement (al. 2); si l'appel principal est retiré ou fait l'objet d'une décision de non-entrée en matière, l'appel joint est caduc (al. 3).
D'après l'<ref-law>, la juridiction d'appel ne peut modifier une décision au détriment du prévenu ou du condamné si le recours a été interjeté uniquement en leur faveur (1ère phrase). Elle peut toutefois infliger une sanction plus sévère à la lumière de faits nouveaux qui ne pouvaient pas être connus du tribunal de première instance (2ème phrase). L'existence d'une reformatio in pejus doit être examinée à l'aune du dispositif (<ref-ruling> consid. 4.5 p. 136; <ref-ruling> consid. 2.7.3 p. 140).
2.1.2. Dans un arrêt publié aux <ref-ruling>, le Tribunal fédéral a retenu, en substance, que, quand bien même l'appel joint n'est pas lié à l'appel principal, son caractère accessoire impose toutefois de prendre en compte quelles parties sont aux prises et justifie une délimitation par rapport aux parties concernées. Lorsque l'appel principal émane d'une partie plaignante, le cadre dans lequel l'appel joint est possible sur le plan pénal se détermine en considération des infractions par lesquelles la partie plaignante est directement lésée (cf. <ref-law>). Les parties concernées par l'appel principal sont ainsi définies et l'appel joint doit se situer dans ce cadre (consid. 2.3 p. 95 s.).
Le Tribunal fédéral a relevé que, selon un courant de doctrine, si un seul prévenu forme appel, le ministère public ne saurait alors interjeter un appel joint pour s'en prendre aux autres coprévenus qui n'ont eux-mêmes pas entrepris d'appel, sous peine de méconnaître le caractère accessoire de l'appel joint et de contourner l'interdiction de la reformatio in pejus (<ref-ruling> consid. 2.2 p. 95 et les références citées). Il n'a toutefois pas tranché la question. Dans ce même arrêt, le Tribunal fédéral rappelle que le ministère public est responsable de l'action publique (cf. <ref-law>) et qu'il lui incombe à ce titre de former un appel principal s'il n'est pas satisfait du jugement de première instance (<ref-ruling> consid. 2.3 p. 96).
Ces principes sont repris dans l'arrêt publié aux <ref-ruling>, à teneur duquel, lorsque le prévenu conteste dans un appel principal la peine infligée par rapport à des infractions concernant la partie plaignante, celle-ci est habilitée à former un appel joint sur d'autres aspects du jugement attaqué, en particulier les conclusions civiles (consid. 1.2 p. 236 s.).
2.2. En l'occurrence, contrairement à la victime et au coprévenu, le recourant 1 n'a pas formé d'appel contre le jugement de première instance. Le Ministère public a certes adressé une déclaration d'appel auprès de la cour cantonale, concluant notamment à ce que le recourant 1 soit condamné à une peine privative de liberté de cinq ans, il a toutefois omis d'annoncer l'appel, de sorte que son appel principal a été déclaré irrecevable. Les conclusions de la partie plaignante portant sur la peine ont également été déclarées irrecevables.
La portée de l'appel joint doit être délimitée par rapport aux parties concernées, à savoir, en l'espèce, le coprévenu et la victime. Certes l'appel de la victime visait les deux coprévenus (notamment qualification juridique différente et augmentation de l'indemnité pour tort moral), elle n'avait toutefois pas la qualité pour contester la peine (cf. <ref-law>). Dès lors que l'appel joint devait se situer dans ce cadre, le Ministère public ne pouvait pas s'en prendre à la peine du recourant 1 par la voie de l'appel joint alors même qu'il n'a pas formé d'appel principal recevable. L'appel formé par la partie plaignante s'agissant de la participation du coprévenu à l'acte incriminé, ne permet pas au Ministère public d'attraire le recourant 1 à la procédure pour revoir sa peine, ce d'autant qu'il n'a pas conclu à une qualification juridique plus grave (arrêt entrepris, consid. a.c p. 3 et 2.4.3 p. 22). En déclarant recevables les conclusions du Ministère public dirigées contre le recourant 1, au motif que son appel joint concernait les mêmes parties et portait sur les infractions à l'origine de la qualité de lésée de la victime, la cour cantonale a méconnu les principes tirés de la jurisprudence exposée supraet a violé le droit fédéral.
3.
Le recours de Y._ doit être admis. L'arrêt entrepris doit être annulé en ce qui concerne la peine du recourant 1 et la cause renvoyée à la cour cantonale pour qu'elle déclare l'appel joint du Ministère public irrecevable et confirme la peine fixée en première instance. Dans la mesure où le recourant 1 obtient gain de cause, sa demande d'assistance judiciaire est sans objet. Il est statué sans frais (art. 66 al. 1, 2ème phrase et al. 4 LTF). Le recourant 1 obtiendra des dépens de la part du canton de Genève (<ref-law>). La cause étant jugée, la requête d'effet suspensif devient sans objet.
II. Recours de X._ (recourant 2)
4.
Le recourant 2 conteste s'être rendu coupable de tentative de meurtre. Il prétend ne pas avoir participé à la bagarre et n'avoir eu aucune intention meurtrière. Il s'en prend à l'établissement des faits et à l'appréciation des preuves et invoque une violation du principe " in dubio pro reo ".
4.1. Le Tribunal fédéral n'est pas une autorité d'appel, auprès de laquelle les faits pourraient être rediscutés librement. Il est lié par les constatations de fait de la décision entreprise (<ref-law>), à moins qu'elles n'aient été établies en violation du droit ou de manière manifestement inexacte au sens des art. 97 al. 1 et 105 al. 2 LTF, à savoir, pour l'essentiel de façon arbitraire au sens de l'art. 9 Cst. Une décision n'est pas arbitraire du seul fait qu'elle apparaît discutable ou même critiquable; il faut qu'elle soit manifestement insoutenable, et cela non seulement dans sa motivation mais aussi dans son résultat (<ref-ruling> consid. 1.2 pp. 308 s.). En matière d'appréciation des preuves et d'établissement des faits, il n'y a arbitraire que lorsque l'autorité ne prend pas en compte, sans aucune raison sérieuse, un élément de preuve propre à modifier la décision, lorsqu'elle se trompe manifestement sur son sens et sa portée, ou encore lorsque, en se fondant sur les éléments recueillis, elle en tire des constatations insoutenables (<ref-ruling> consid. 2.3 p. 266 et les références citées). Le Tribunal fédéral n'entre ainsi pas en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 2.4 p. 368).
La présomption d'innocence, garantie par les art. 6 par. 2 CEDH, 32 al. 1 Cst. et 10 CPP, ainsi que son corollaire le principe " in dubio pro reo ", concernent tant le fardeau de la preuve que l'appréciation des preuves. Lorsque l'appréciation des preuves et la constatation des faits sont critiquées en référence au principe " in dubio pro reo ", celui-ci n'a pas de portée plus large que l'interdiction de l'arbitraire (<ref-ruling> consid. 7 p. 82).
Lorsque l'autorité cantonale a forgé sa conviction quant aux faits sur la base d'un ensemble d'éléments ou d'indices convergents, il ne suffit pas que l'un ou l'autre de ceux-ci, ou même chacun d'eux pris isolément, soit à lui seul insuffisant. L'appréciation des preuves doit être examinée dans son ensemble. Il n'y a ainsi pas d'arbitraire si l'état de fait retenu pouvait être déduit de manière soutenable du rapprochement de divers éléments ou indices. De même, il n'y a pas d'arbitraire du seul fait qu'un ou plusieurs arguments corroboratifs sont fragiles, si la solution retenue peut être justifiée de façon soutenable par un ou plusieurs arguments de nature à emporter la conviction. (arrêts 6B_145/2016 du 23 novembre 2016 consid. 1.1; 6B_275/2015 du 22 juin 2016 consid. 2.1).
4.2. S'agissant du rôle du recourant 2 dans la bagarre, la cour cantonale a retenu que le récit de la victime, constant, plausible et corroboré par différents éléments du dossier, était hautement crédible, tandis que celui du recourant 2 n'emportait pas conviction.
En substance, la cour cantonale a considéré que la victime était constante et crédible lorsqu'elle évoquait la participation du recourant 2 dans la bagarre, qu'elle a tout au long de la procédure identifié comme étant celui qui lui avait tenu les mains dans le dos, sans raison de le dénoncer à tort. Dans la mesure où la victime n'avait pas de raison de se préoccuper du trajet en taxi ainsi que de la discussion préalable à l'attaque, le flou dans ses souvenirs sur ces aspects ne rendaient pas ses déclarations peu probantes. L'agression elle-même, par surprise, avait en revanche tout lieu de lui rester en mémoire vu le choc, et d'effacer les instants précédant la bagarre. La victime avait déclaré, dès sa première audition, que ses deux agresseurs cherchaient quelque chose au sol juste avant de fuir. La découverte de la lame de couteau sur les lieux corroborait ce récit. Se fondant sur l'avis de l'expert médical, selon lequel un individu attaqué avait le réflexe de se défendre, notamment en plaçant ses mains devant lui, la cour cantonale a considéré que l'absence de lésions de défense pouvait constituer un indice supplémentaire d'une attaque perpétrée par deux individus.
Le recourant 2 prétendait dans un premier temps n'avoir aucun souvenir des événements en raison de son alcoolémie puis avait modifié ses déclarations en indiquant d'abord que, depuis la voiture, il avait vu son comparse frapper la victime, et était reparti alors que la victime, ensanglantée, gisait à terre. Par la suite, à l'audience de jugement il a déclaré que la victime n'était pas tombée à terre.
D'après les témoins, le véhicule conduit par les comparses avait démarré brusquement à la suite du taxi et l'avait véritablement pourchassé. En outre, le recourant 2 avait indiqué à son patron s'être bagarré avec la victime. Ces témoignages démontraient son implication dans l'attaque. Par ailleurs, le témoin B._, appelé par le recourant 2 après l'agression pour qu'il le rejoigne ainsi que son comparse, avait constaté qu'ils rigolaient comme des fous.
S'agissant de l'intention du recourant 2, la cour cantonale a notamment mis en évidence la présence équivoque des comparses dans la cuisine du restaurant dans la soirée, la poursuite du taxi, la recherche d'un objet par terre après les coups portés ainsi que le comportement du recourant 2 après l'agression, pour retenir que ce dernier savait et avait pleinement accepté que son comparse attaque la victime à l'aide d'un couteau. S'il n'avait pas voulu une issue fatale, il en avait accepté l'éventualité en la tenant par les bras.
En définitive, la cour cantonale a reconnu le recourant 2 coupable, comme coauteur, de tentative de meurtre par dol éventuel.
4.3. Pour l'essentiel, le recourant 2 tente d'imposer son appréciation des preuves en rediscutant les divers éléments et déclarations, sans démontrer en quoi la cour cantonale aurait établi les faits de manière insoutenable. Il isole chaque élément et indice examiné par la cour cantonale et y oppose, en grande partie, une appréciation personnelle. Cette démarche est appellatoire, partant irrecevable.
S'agissant en particulier des déclarations de la victime, la cour cantonale a relevé les quelques incohérences relatives à la période qui a précédé l'agression (trajet en taxi; rencontre) et a expliqué en quoi elles n'influençaient pas la crédibilité du récit de l'attaque en tant que telle. Dans la mesure où le recourant 2 ne tente pas de démontrer en quoi il serait insoutenable de retenir la version des faits de la victime sur ce point, son grief doit être écarté. Le fait que la victime aurait déclaré une première fois que le recourant 2 l'avait " ceinturé depuis l'arrière ", puis " tenu les mains dans le dos " ou aurait également " appuyé avec son genou ", n'est pas apte à rendre arbitraire l'appréciation selon laquelle les déclarations étaient constantes et crédibles s'agissant de l'immobilisation des bras.
Le recourant 2 tente en vain de justifier les contradictions relevées dans son propre discours, en décrivant, de manière purement appellatoire, sa situation personnelle et en relevant des similitudes avec certains témoignages, sur des éléments de fait qui ne sont pas discutés ni pertinents. Il livre également une interprétation personnelle de certaines déclarations de parties.
Expliquer l'absence de lésions de défense par l'état d'alcoolisation de la victime au moment des faits relève d'un procédé purement appellatoire, partant irrecevable. Au demeurant, la cour cantonale pouvait, sans arbitraire, considérer, compte tenu de la nature de l'attaque et sur la base de l'avis de l'expert, que la victime se serait protégée à l'aide de ses mains si elle avait pu. L'absence de marques constatées aux poignets ne rend pas cette appréciation insoutenable. Cela n'exclut pas que la victime se soit débattue dans la mesure où il n'est pas établi que le recourant 2 tenait la victime par les poignets. En tout état, le réflexe de protection contre un coup de couteau dans la poitrine se distingue de l'action de se débattre pour échapper à une immobilisation.
Par ailleurs, le recourant 2 tente de justifier son comportement postérieur à la bagarre en procédant à une appréciation personnelle des événements, de manière appellatoire, partant irrecevable. Il isole en outre certains passages de témoignages en retenant ceux en sa faveur.
Enfin, en se contentant d'affirmer que certains éléments retenus (poursuite du taxi; recherche de la lame de couteau; indifférence sur l'état de la victime) et appréciés comme un tout par la cour cantonale, ne suffiraient pas en soi pour fonder son intention, le recourant échoue à démontrer l'arbitraire de l'appréciation cantonale sur ce point (déterminer ce que l'auteur a su, cru ou voulu relève des faits, cf. <ref-ruling> consid. 2.4.3 p. 343).
En définitive, son grief est rejeté dans la mesure où il est recevable.
5.
Le recourant 2 soutient qu'une indemnisation doit lui être allouée du fait de son acquittement, sur la base de l'art. 429 al. 1 let. c CPP, respectivement de l'<ref-law>. Au vu du considérant précédent, ses arguments sont irrecevables.
6.
Dans un dernier grief, le recourant 2 conteste sa peine. Il fait valoir un défaut de motivation quant à la proportion dans laquelle la peine a été diminuée.
6.1. Les règles générales régissant la fixation de la peine (<ref-law>) ont été rappelées dans les arrêts publiés aux <ref-ruling> et 136 IV 55, auxquels on peut se référer.
6.1.1. S'agissant de coauteurs jugés dans une seule procédure, l'appréciation subjective de la culpabilité et de la situation personnelle de chacun peut justifier des peines différentes pour des mêmes actes. Toutefois, la juste proportion des peines des coauteurs doit être prise en compte comme élément dans l'appréciation de la peine (<ref-ruling> consid. 3.2 p. 193 ss).
6.1.2. Aux termes de l'<ref-law>, si le prévenu a, de manière illicite, fait l'objet de mesures de contrainte, l'autorité pénale lui alloue une juste indemnité et réparation du tort moral. Il appartient à l'autorité de jugement d'examiner les possibles conséquences des violations constatées, par exemple par le biais d'une indemnisation fondée sur l'<ref-law> ou, cas échéant, par une réduction de la peine (<ref-ruling> consid. 4.1 et 4. 3 p. 248 s. et les références citées; <ref-ruling> consid. 2.1 p. 352 s.).
S'agissant du mode et de l'étendue de l'indemnisation fondée sur les <ref-law>, il n'est pas exclu de s'inspirer des règles générales des <ref-law>. Ces dispositions accordent au juge un large pouvoir d'appréciation, que le Tribunal fédéral ne revoit qu'avec retenue. En vertu de l'<ref-law>, une réparation en nature n'est pas exclue (<ref-ruling> consid. 4.1 et 4.3 p. 248 s. et les références citées). L'ampleur de la réparation dépend avant tout de l'appréciation concrète des circonstances particulières de l'espèce, en particulier de la gravité des souffrances physiques ou psychiques consécutives à l'atteinte subie (arrêt 6B_137/2016 du 1er décembre 2016 consid. 2.2; cf. sur la réparation financière, <ref-ruling> consid. 2.2.2 p. 309 s.).
6.2. La cour cantonale a examiné les critères de fixation de la peine pour les deux prévenus et a jugé qu'une peine équivalente devait être prononcée, en l'occurrence, une peine privative de liberté de quatre ans. Or, vu l'issue du recours du coprévenu et son impact sur sa peine (cf. supra consid. 3), la motivation relative à la peine du recourant 2 tombe à faux.
Afin de tenir compte des conditions de détention illicites subies par le recourant 2 en détention provisoire (257 jours), la cour cantonale a réduit la peine de trois mois. Ce faisant, elle s'est référée à des affaires cantonales soulevant des questions identiques mais a omis de se prononcer sur la nature et la gravité des souffrances du recourant en l'espèce.
Faute de toute motivation sur la réduction de la peine, le recours doit être admis sur ce point. La cause doit être renvoyée à la cour cantonale afin qu'elle fixe la peine en tenant compte des principes exposés supraet de la peine prononcée contre le coprévenu. Elle motivera également l'étendue de la réduction de peine déduite de l'<ref-law>.
7.
Le recours de X._ doit être partiellement admis, l'arrêt annulé s'agissant de la peine et la cause renvoyée à la cour cantonale pour nouvelle décision dans le sens des considérants. Pour le surplus, le recours doit être rejeté dans la mesure où il est recevable. Dans la mesure où le recourant obtient partiellement gain de cause, sa demande d'assistance judiciaire est sans objet, elle est rejetée pour le surplus, faute de chance de succès du recours (<ref-law>). Une partie des frais sera ainsi supportée par le recourant, dont le montant sera toutefois fixé en tenant compte de sa situation financière (art. 65 al. 2 et art. 66 al. 1 LTF). Le recourant obtiendra des dépens réduits de la part de la République et canton de Genève (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Les causes 6B_1021/2016 et 6B_1057/2016 sont jointes.
2.
Le recours de Y._ (6B_1057/2016) est admis, l'arrêt cantonal annulé s'agissant de la peine et la cause est renvoyée à la cour cantonale pour nouvelle décision.
3.
Il n'est pas perçu de frais judiciaires pour la cause 6B_1057/2016.
4.
Le canton de Genève versera au conseil du recourant Y._ une indemnité de 3'000 fr. à titre de dépens pour la procédure 6B_1057/2016 devant le Tribunal fédéral.
5.
Le recours de X._ (6B_1021/2016) est partiellement admis. L'arrêt cantonal est annulé s'agissant de la peine et la cause est renvoyée à la cour cantonale pour nouvelle décision. Pour le surplus, le recours est rejeté, dans la mesure de sa recevabilité.
6.
La requête d'assistance judiciaire formulée par le recourant X._ est rejetée dans la mesure où elle n'est pas sans objet.
7.
Des frais judiciaires réduits pour la procédure 6B_1021/2016, arrêtés à 600 fr., sont mis à la charge du recourant X._.
8.
Le canton de Genève versera au conseil du recourant X._ une indemnité de 1'000 fr. à titre de dépens réduits pour la procédure 6B_1021/2016 devant le Tribunal fédéral.
9.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale d'appel et de révision.
Lausanne, le 20 septembre 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke